Saturday, December 8, 2007
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.
Used as: Division Two - Level One:
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.TheDiceGame
Used as: Division Two - Level Two:
Used as: Division One - Level One:
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.TheNumbersLord
Used as: Division Two - Level Three:
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.TheHomework
Used as: Division One - Level Two:
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.TheSquares
Used as: Division One - Level Three:
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.