Match Editorial

Match summary

Saturday, the 8th of December, such a beautiful evening here in Ukraine. SRM 381 made it even better. 1500 coders (it seems that there was at least one more who wished to take part in) from all over the world were ready to do their best during amazing 95 minutes of coding and challenging.

Unfortunately, nobody was able to solve all three problems correctly in division 1, but division 2 guys showed that they are quite good and as a result some of them solved all problems in 75 minutes.

Gassa, kalinov and Egor took first three places in division 1. KirillB, impetus and _oyster_ did the same in division 2.

The Problems

Value	250
Submission Rate	659 / 806 (81.76%)
Success Rate	452 / 659 (68.59%)
High Score	bugzpodder for 244.83 points (4 mins 8 secs)
Average Score	178.44 (for 452 correct submissions)

This problem was really not very difficult. All you have to do is just to simulate process of sorting described in problem statement. Generally, there were two basic approaches. First one is to count all Johns and sort other names separately. Another opportunity is to take into account special name John while sorting.

While comparing two names you have to evaluate their weights and in case of a tie compare them lexicographically.

Value	500
Submission Rate	99 / 806 (12.28%)
Success Rate	71 / 99 (71.72%)
High Score	Hamster1800 for 487.56 points (4 mins 33 secs)
Average Score	325.60 (for 71 correct submissions)

Value	250
Submission Rate	366 / 577 (63.43%)
Success Rate	324 / 366 (88.52%)
High Score	Ted for 249.64 points (1 mins 5 secs)
Average Score	190.61 (for 324 correct submissions)

This one requires some basic knowledge from a field of probability theory.

Let’s denote Res[n] as expected number of throws needed for John to get at least n candies.

Obviously, Res[n] = 0 for each n less than or equal to zero. Than, if you just think a little you’ll get very good looking and useful for this problem formula:

Res[n] = 1 + Res[n-1]/6 + Res[n-2]/6 + Res[n-3]/6 + Res[n-4]/6 + Res[n-5]/6 + Res[n-6]/6

Then you should take a look at constrains and decide to implement some simple DP. Sounds easy! And only after the match if you have free time you can spend it working on formal proof of the formula mentioned above. Really, after each John’s throw there are equal possibilities of decreasing required number of candies by 1, 2, 3, 4, 5 and 6. Thus, if you know answers for smaller required numbers you can easily calculate result for n.

Another approach is based on the fact that in average John gets 3.5 points per throw. Thus, for big enough n’s we can assume that Res[n] is very close to Res[n-7] + 2. Thinking like this is not strict and formal but can help you to get high score on problems like this.

Value	1000
Submission Rate	179 / 806 (22.21%)
Success Rate	29 / 179 (16.20%)
High Score	Nikelandjelo for 899.03 points (9 mins 44 secs)
Average Score	617.47 (for 29 correct submissions)

This problem is very practical one. Even if you don’t know how to solve it after reading problem statement you can try to construct some big numbers by yourself. Just take a piece of paper, write down some numbers and guess what is the biggest possible one to achieve. And maybe it helps you, but maybe not. In second case you have no choice and should prepare some tricky test cases for future challenges. Who knows, perhaps it will get you more points than correct solution.

Obviously, we can treat numbers as strings and solve the same problem but with strings. By the way, result wouldn’t change at all. Next observation is that we need to use each string once and if we have some extra slots we should pick up the longest string several times. In case if we have many longest strings, lexicographically last will be chosen. Formal proof of this is rather simple and goes as home task for you.

Now suppose we have n strings (we will make some copies of the longest string if needed). Our task is to arrange them in the best way to form the biggest number. This sound like sorting! Such an amazing idea comes to your mind. Moreover, this idea is really very good.

Suppose, we have two strings s and t. If t comes immediately after s in some arrangement and s+t < t+s we can easily swap them and receive bigger number. So, we can sort all strings according to this rule. It reminds bubble sort. Proof of this is a home task too and you should make it until next SRM.

Value	500
Submission Rate	366 / 577 (63.43%)
Success Rate	111 / 366 (30.33%)
High Score	kalinov for 454.52 points (9 mins 10 secs)
Average Score	304.85 (for 111 correct submissions)

In this problem John has to solve not so hard task. And it wouldn’t be good for him to fail it. So he needs just to concentrate on facts he has and figure out some nice solution.

First of all John can make his task more understandable. Let’s denote n as number of elements in first, m as number of elements in second and k as number of their common elements. I think that calculation of k wouldn’t be a hard task for such a good programmers as you are! Thus n and k will describe a state in John’s homework. So after each operation John will move from one state to another. His task is to reach state (m, m) with minimal possible number of moves.

While adding elements it is very logical for John first of all to add elements that are present in second, but missing in first. Similarly, while deleting/changing elements first of all John will remove/replace elements that are not present in second. Clearly, if after some operation we have at least n+m elements in the list, the number of common elements will be definitely equal to m, so it doesn't make sense to add new elements. This observation allows us to limit the search.

Thus, we can implement simple BFS with initial state (m, m) and find out minimal possible number of operations needed to reach each state. Constrains allow to do this in any way you like.

Value	1000
Submission Rate	80 / 577 (13.86%)
Success Rate	3 / 80 (3.75%)
High Score	Egor for 539.86 points (32 mins 51 secs)
Average Score	444.23 (for 3 correct submissions)

There were distinct names of squares in the first edition of this problem. It was quite interesting. But when names may coincide, it becomes more interesting. And, as far as we like interesting problems very much, it was decided to let squares have equal names.

It is not hard to find maximal possible length of described sequence for each square as initial one. If there are no squares with such maximal length not less than k, then we have no answer at all. Otherwise we will look for lexicographically first square with maximal length not less than k and it’s name will be first element of the answer. But be careful, there may be several appropriate squares with that name and we don’t know which one is better to start from. So we need to hold set of squares with the best possible name and maximal length more than or equal to k. On the next step we will look for a set of squares such that each one lies inside at least one square from previous set and has maximal length of sequence not less than k-1. And so on and so on.

Some accuracy needed when dealing with equal squares. If we have some equal squares (with equal x, y, lengths and names), we will use them in a sequence in order they follow in array. For example we can’t use 4-th square inside of 7-th if they are equal.

Looks not so difficult! But wait, is it division 1 hard? It should be difficult! So what’s the problem? Complexity of algorithm described above is O(N^3) and it is too slow. Thus, we need some additional optimizations to pass system tests.

One way is to to speed up our solution by using some bitsets. Another is to use the following observation. If we have some two squares with equal names and first one lies inside second one, then it is illogical to use them together in a set of squares of some level. If first square generates some sequence, then second one can generate it, too, and, maybe, can generate even better sequence. This observation leads to O(N^2) algorithm, because each square can be present only in one set of squares.