CS 2018 New Year's competition
Introduction
Already in October 2018, we happily remembered the Advent calendar with the tasks of 2017 (conditions here ) and began to think what can be done this year. Of the several worthy ideas, we chose the option in which we would select diverse “catchy” tasks, combined with a beautiful New Year's story.
All that remained was nothing: in fact, pick up tasks, write a story, make a website with a leaderboard, beautiful and tightly knit with Yandex.Contest, and start in early December :-)
Result
As you know, appetite comes with eating, and we plunged into the process of working out the content of the tasks and their technical implementation. Each successful find inspired for further improvements. As a result, a separate server was raised for one of the tasks, another was optimized (we don’t have the exact answer), we recorded the music ourselves, restored the distributions — we didn’t get bored at all!
The result was:
- 11 tasks (+1 bonus) of varying difficulty, all with verification in the Contest;
- external site for members ;
- 11 days (from December 7 to December 17 inclusive) to solve problems.
Interesting facts and stories
780 participants registered, 333 people started to solve, 203 people successfully passed at least two tasks.
Initially, we estimated the net time to solve all problems at seven days for an unprepared participant and at two days for a very experienced (aka fresh graduate of the CS center). The first Santa Claus assistant, who correctly solved all eleven tasks, did it in about a day, two more coped with the second!
A letter from one of the participants: “Good afternoon! Because of your contest, I stopped the office (40 people) specifically the second task about Santa Claus coffee, give another hint, please. We are all very tormented. "
Analysis of tasks
Conditions here .
Problem D “Musical Message” (Mikhail Plotkin)
It is very easy to solve the problem, having a minimal music education.
An attempt to find a solution in the rhythmic pattern did not lead to success. The next idea was to sit at the piano and pick up the melody you listened to. It turned out la, do, mi, si, la, re, salt, mi. In the treble clef like this:
After the first three notes there was a small pause, as if dividing the musical phrase into two words. It only remained to write the notes in the traditional letter notation (A = la, B = si, C = do, D = pe, E = mi, F = fa, G = salt) and two words opened: ACE BADGE.
Without any knowledge of musical literacy to solve the problem more difficult. For example, one could use any sound processing program and find out either the notes themselves or the frequencies of sounds in hertz, and then find which frequencies correspond to which notes.
The task required to write the letters together without separators, so the answer is: ACEBADGE.
An attempt to find a solution in the rhythmic pattern did not lead to success. The next idea was to sit at the piano and pick up the melody you listened to. It turned out la, do, mi, si, la, re, salt, mi. In the treble clef like this:
After the first three notes there was a small pause, as if dividing the musical phrase into two words. It only remained to write the notes in the traditional letter notation (A = la, B = si, C = do, D = pe, E = mi, F = fa, G = salt) and two words opened: ACE BADGE.
Without any knowledge of musical literacy to solve the problem more difficult. For example, one could use any sound processing program and find out either the notes themselves or the frequencies of sounds in hertz, and then find which frequencies correspond to which notes.
The task required to write the letters together without separators, so the answer is: ACEBADGE.
Problem F "Bag of snowflakes" (Mikhail Plotkin)
The area of the original triangle is 1. Next, at the nth step, t_n of triangles are added, each of which has area s_n. The total area of the resulting figure is expressed as the sum of an infinite series:
S = 1 + Σ (t_n * s_n), the sum of n from 0 to ∞ (1)
At the zero step t_0 = 3, s_0 = 1/9, since the triangle has 3 sides, each of which has a triangle with a side 3 times smaller than the original, and therefore an area 9 times smaller than the area of the original triangle.
At each next step, each side turns into 4 sides, three times smaller, i.e.
t_n = t_ {n-1} * 4 = t_0 * 4n = 3 * 4n,
s_n = s_ {n-1} * (1/9) = s_0 * (1/9) ^ n = 1/9 * (1/9) ^ n.
Therefore, the required area:
S = 1 + Σ (t_n * s_n) = 1 + 1/3 * Σ ((4/9) ^ n), the sum of n from 0 to ∞ (2)
The second term is the sum of an infinitely decreasing geometric progression. To calculate it, we use the school formula.
Σ ((4/9) ^ n) = 1 / (1 - 4/9) = 9/5.
Substituting into formula (2), we get the answer:
S = 1 + 1/3 * 9/5 = 8/5 = 1.6
S = 1 + Σ (t_n * s_n), the sum of n from 0 to ∞ (1)
At the zero step t_0 = 3, s_0 = 1/9, since the triangle has 3 sides, each of which has a triangle with a side 3 times smaller than the original, and therefore an area 9 times smaller than the area of the original triangle.
At each next step, each side turns into 4 sides, three times smaller, i.e.
t_n = t_ {n-1} * 4 = t_0 * 4n = 3 * 4n,
s_n = s_ {n-1} * (1/9) = s_0 * (1/9) ^ n = 1/9 * (1/9) ^ n.
Therefore, the required area:
S = 1 + Σ (t_n * s_n) = 1 + 1/3 * Σ ((4/9) ^ n), the sum of n from 0 to ∞ (2)
The second term is the sum of an infinitely decreasing geometric progression. To calculate it, we use the school formula.
Σ ((4/9) ^ n) = 1 / (1 - 4/9) = 9/5.
Substituting into formula (2), we get the answer:
S = 1 + 1/3 * 9/5 = 8/5 = 1.6
Problem G and L “The route is built” (Artem Romanov)
Thanks to Artem mehrunesartem for the solution! By the way, the graph that was used in task G is built on the London Underground scheme :)
To solve this problem, we use a modified version of the search in width. Let's create an imaginary vertex (source), from which we will draw ribs of zero weight at each vertex of the graph. Each state is uniquely determined by the path from the source. Additionally, we will store the elapsed time and the resulting joy.
Make a priority queue with a fixed size in which we place the states. As an estimate of the states in the queue, we will use the ratio of the resulting happiness to the elapsed time. This estimate is not correct, but showed good results in this task.
At each step, we will get the state with the best estimate from the queue and place the states formed from it into the queue. With this approach, it will take a long time to get the final result.
To speed up the decision we will look for an answer in stages. At each step to find the next vertex in the path, we will clear the queue and place the current state in it. Then we will do a fixed number of steps, simultaneously updating the state that gives the greatest amount of joy. As the next vertex of the path, we take the vertex following the last vertex of the current state in the path of the received state giving the greatest amount of joy. We repeat the done actions as long as we can improve the current state.
Possible improvements
These changes did not provide significant improvements, most likely due to the fact that there was only one closed test, and not a group of different generated tests.
To solve this problem, we use a modified version of the search in width. Let's create an imaginary vertex (source), from which we will draw ribs of zero weight at each vertex of the graph. Each state is uniquely determined by the path from the source. Additionally, we will store the elapsed time and the resulting joy.
Make a priority queue with a fixed size in which we place the states. As an estimate of the states in the queue, we will use the ratio of the resulting happiness to the elapsed time. This estimate is not correct, but showed good results in this task.
At each step, we will get the state with the best estimate from the queue and place the states formed from it into the queue. With this approach, it will take a long time to get the final result.
To speed up the decision we will look for an answer in stages. At each step to find the next vertex in the path, we will clear the queue and place the current state in it. Then we will do a fixed number of steps, simultaneously updating the state that gives the greatest amount of joy. As the next vertex of the path, we take the vertex following the last vertex of the current state in the path of the received state giving the greatest amount of joy. We repeat the done actions as long as we can improve the current state.
Possible improvements
- Use the best heuristics.
- With such an implementation of the algorithm, superfluous states will appear, since at each step we will add all the states that could be obtained from the current one. To prevent this, you can use the Dijkstra algorithm for each vertex of the graph to construct the shortest path tree to all other vertices and make transitions not in one step, but along the constructed tree until we reach the vertices in which we have never been.
These changes did not provide significant improvements, most likely due to the fact that there was only one closed test, and not a group of different generated tests.
Problem I "Bears-digitizers" (Alexander Samofalov)
Let's look at the source code of the service .
A list of all available user IDs can be obtained at
If there is an id, then the data can be obtained using a request to the address
To access the data, the service requires a token for authentication. We have an available token , but it has expired, and the service no longer accepts it.
Let's see in the code how these tokens are generated . The token is obtained by encrypting JSON like
Let's make a query: e = 30593, n = 66043. Because n small enough, then we can easily calculate the private key.
To do this, decompose n into simple factors: 211 * 313.
Calculate the Euler function of n: φ (n) = (211 - 1) (313 - 1) = 65520.
We obtain d = e-1 (mod φ (n)) = 257.
The inverse element of the module can be calculated using the advanced Euclidean algorithm .
Having calculated the private key, we will decipher the token available to us.
We get the following JSON:
Note that the service is enough for the user with the given userId to exist and expireDate to be less than the current time on the server.
That is, knowing userId, we can generate a new valid token.
To do this, take expireDate large enough to pass the test — for example,
We encrypt our new token with a public key.
Making a request to
Let's go through them all.
Among them is a wonderful phrase: the New Year is knocking on the door, open to him soon! .
A list of all available user IDs can be obtained at
/data .If there is an id, then the data can be obtained using a request to the address
/data/id .To access the data, the service requires a token for authentication. We have an available token , but it has expired, and the service no longer accepts it.
Let's see in the code how these tokens are generated . The token is obtained by encrypting JSON like
{ “userId” : “id”, expireDate: “date”} and then encoding it to base64. The service uses RSA for encryption, and the public key can be obtained by requesting the address /key .Let's make a query: e = 30593, n = 66043. Because n small enough, then we can easily calculate the private key.
To do this, decompose n into simple factors: 211 * 313.
Calculate the Euler function of n: φ (n) = (211 - 1) (313 - 1) = 65520.
We obtain d = e-1 (mod φ (n)) = 257.
The inverse element of the module can be calculated using the advanced Euclidean algorithm .
Having calculated the private key, we will decipher the token available to us.
We get the following JSON:
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2018-12-06T14:38:00.898026+00:00"}Note that the service is enough for the user with the given userId to exist and expireDate to be less than the current time on the server.
That is, knowing userId, we can generate a new valid token.
To do this, take expireDate large enough to pass the test — for example,
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2100-01-01T12:00:00.000000+00:00"} .We encrypt our new token with a public key.
Making a request to
/data , we find out that the user has created messages with identifiers from 1 to 4.Let's go through them all.
Among them is a wonderful phrase: the New Year is knocking on the door, open to him soon! .
Tips for solving some other problems (by Artem Romanov)
Task A "Safe with letters"
You may notice that every twenty steps you get the same figure.
Task B "The Secret of the Professor"
Sort the words in descending popularity. You may notice that each subsequent word occurs at approximately 2, 3, 4, etc. times less than the most popular word. Now you can recover the answer.
Task C "Computer Disaster"
Think of the programming language Whitespace.
Task J "Bengal"
Possible accommodation:
Task K "Frosty pattern"
To solve this problem, you can choose any convenient triangle, for example, the right one, and calculate the answer for it.
Thanks
The whole process from the idea to the implementation of the drive and coordinated by Katya Lebedeva. The tasks helped her to compile Katya Artamonova, Alina Mozhina, Sasha Komissarov and me. Lesha Tolstikov wrote three complex checkers, Sasha Komissarov together with Sergey Zherevchuk made a server, Svyaty and Seyozha selflessly in a short time made a beautiful website with tight integration with tasks: each participant could see his progress and leaderboards.
Source: https://habr.com/ru/post/438570/