Match Editorial

Match summary

In Div1 coders faced quite straightforward easy problem. Medium problem appeared to be not that simple and brought lots of challenges. 9 coders successfully solved the hard, what helped them to get top 9 places. The division was won by Petr who had not very high scores for all three problems, but got +125 on challenges. ardiankp became the second and lordmonsoon took the third place.

In Div2 the hard appeared to be quite simple for some of the coders and many fast submissions passed system tests. The first place was taken by Rasifiel, he was followed by ika. tonac119 became third in his first SRM.

The Problems

Value	250
Submission Rate	403 / 507 (79.49%)
Success Rate	307 / 403 (76.18%)
High Score	dogbox for 248.62 points (2 mins 7 secs)
Average Score	198.89 (for 307 correct submissions)

The first and the main thing the competitor had to think about was "What do I have to do with the postmarks which I already have ?". And the answer was quite clear. As sell and buy prices for each postmark are equal you can initialy sell all the postmarks you have and maybe buy some of them later. After realizing that the problem becomes really simple. All you have is to sell all postmarks you initially have and then buy them in the increasing order of prices while you have enough money.

Value	500
Submission Rate	167 / 507 (32.94%)
Success Rate	113 / 167 (67.66%)
High Score	zx19890827 for 454.91 points (9 mins 7 secs)
Average Score	292.95 (for 113 correct submissions)

Let's remove all small cubes and then try to put as many of them as possible to their initial places. If for some cube with coordinates (x,y,z) it turns that A[x][y]='Y' and B[x][z]='Y' and C[y][z]='Y' than it's clear that we can put this cube on its place. If any of the conditions is false we can't leave the cube on its place, so we will have to remove it. Placing cubes in such a way we will leave as many cubes as possible. But don't forget about the case, when all three photos can't be valid. So we have to make some additional checks. If after such a placement it exists such x and y that A[x][y]='Y' but for any z cube with coordinates (x,y,z) has to be removed than there is no way to make the photos valid so -1 has to be returned. The same checks have to be done for B and C. You can find a clear implementation of this idea in this solution by qizichao.

Value	1000
Submission Rate	124 / 507 (24.46%)
Success Rate	70 / 124 (56.45%)
High Score	dogbox for 901.23 points (9 mins 37 secs)
Average Score	632.60 (for 70 correct submissions)

This problem appeared to be quite easy for some division 2 competitors. The main question that appeared was "How big can the answer be ?". Let's look on the deck shuffle as on the permutation of length N. The period of a permutation is the minimum number of repeated invokations required to get back to start. It's clear that the answer can't be equal or greater than the period of this permutation. So the question transforms into "How big can the period of permutation of length N be ?". Looking at any permutation you can notice that it can be broken into some cycles. The least common multiple of the lengths of these cycles is the period of the permutation. For example let's look on the permutation {1,4,0,3,2,5}. It has two cycles: 0->1->4->2->0 and 3->5->3. Their lengthes are 4 and 2, so the period of permutation will be lcm(4,2) = 4. After some additional calculations you can see that the permutation of length 50 can't have it's period greater than 180180. Knowing this fact the solution becomes really short: apply the shuffle to the deck until you get the required order of cards or you make more than 180180 shuffles.

Value	250
Submission Rate	373 / 384 (97.14%)
Success Rate	294 / 373 (78.82%)
High Score	msg555 for 246.64 points (3 mins 19 secs)
Average Score	187.42 (for 294 correct submissions)

Let's assume we can use each crane only once. Then it will be possible to load all boxes to the ship if the crane with the greatest weight limit is able to move the heaviest box, the crane with the second greatest weight limit is able to move the second heaviest box and so on. Now if we can spend X minutes to load the ship, then we can use each crane X times. It is the same as we have each crane cloned X times and after that we can use each crane once. So the solution is to find the minimum X such that it will be possible to load the ship when each crane is cloned X times and each of them can be used once. -1 is possible only if there exists such a box which can't be moved by any of the cranes. You can find a clear implementation of this idea in this solution by neal_wu.

Value	500
Submission Rate	210 / 384 (54.69%)
Success Rate	56 / 210 (26.67%)
High Score	Burunduk1 for 440.04 points (10 mins 47 secs)
Average Score	277.91 (for 56 correct submissions)

The first quiestion which appeared was "What do I have to do with the postmarks which I already have ?". And the answer was quite clear. As sell and buy prices for each postmark are equal you can initialy sell all the postmarks you have and maybe buy some of them later. So now we can assume that we have no postmarks and need to find the set of postmarks with total value not less than K and total price as small as possible. Let's divide all the postmarks into two groups of equal sizes (if the number of postmarks is odd one of the groups will have 1 more element than the other). Each group will have not more than 16 postmarks and the number of subsets of postmarks of each group will be not greater than 2¹⁶. So we can list all subsets of postmarks of first and second group and call the lists A and B respectively. It is also clear than if for some two subsets of first group numbered i and j it appears that A[i].cost >= A[j].cost and A[i].value <= A[j].value then subset A[i] is useless (it will be always better to use subset A[j] than subset A[i]). The same is correct for list B. Now let's assume that both list are ordered in such way that for any i: A[i].value < A[i+1].value, A[i].cost < A[i+1].cost, B[i].value < B[i+1].value and B[i].cost < B[i+1].cost. Now for each i we can find such j that A[i].value+B[j].value >= K and B[j].cost is as small as possible. The pair with the smallest total cost will be the answer. Using the order of elements in A and B all this pairs can be checked in linear time. You can see a clear implementation of this idea in this very fast solution by Burunduk1

Value	1000
Submission Rate	24 / 384 (6.25%)
Success Rate	9 / 24 (37.50%)
High Score	jbernadas for 721.55 points (19 mins 17 secs)
Average Score	562.28 (for 9 correct submissions)

First of all you have to generate the set of all invalid substrings. All of them have equal length, let's call it L. All strings of length L can be ordered lexicographically and numbered from 0 to 2^L-1. Using dynamic programming you can simply generate values r[i][j] for each i and j, where r[i][j] is equal to the number of valid alien words of length i starting with substring of length L numbered j. Having these values the generation of valid alien word of length N numbered x is quite simple. Example java code follows:

int mask;
for (mask = 0; mask < (1 << L); mask ++) {
    if (r[N][mask] > x)
        break;
    x -= r[N][mask];
}

if (mask == (1 << L)) {
    result = "NO PAGE";
    continue;
}

for (int j = L - 1; j >= 0; j --)
    if ((mask & (1 << j)) != 0)
        result+="B";
    else
        result+="A";

for (int step = 1; step + L <= N; step ++) {
    int move1 = (mask % (1 << (L - 1))) * 2;
    int move2 = move1 + 1;

    if (r[N - step][move1] > x) {
        result += "A";
        mask = move1;
    } else {
        result += "B";
        mask = move2;
        x -= r[N - step][move1];
    }
}