Match Editorial

Match summary

1275 coders have registered for the last SRM before the summer. Petr won the challenge and held a new rating record - 3700 rating points, incredible! bmerry surpassed ACRush during the challenge phase and took the second place. ACRush remained with the third.

In Division 2 the battle for top spots was centered on solving the hard problem. Among the 15 top coders 12 didn't solve the medium. Even Zephyrzzz who finished third had only two solved problems. McRazy from Bulgaria took the first place and sejert took the second. Both solved all three problems. The two other coders who solved all three problems are lagivan, who finished fourth line, and foxwmj, in 17th.

The Problems

Value	250
Submission Rate	603 / 662 (91.09%)
Success Rate	401 / 603 (66.50%)
High Score	emotionalBlind for 249.46 points (1 mins 19 secs)
Average Score	206.60 (for 401 correct submissions)

The most tricky part of the problem is converting given integer room number into an array of digits. This part could be done automatically, using language-specific function that converts integer into a string. Another way to do this is to code such an algorithm manually. The idea of the algorithm is to divide the given integer by 10 until it equals zero.

Having the room number in the form of char array we can calculate how many times each character appears in the array.

The final part of the solution is to take care of the '6' and '9' digits. The easiest way to do this is to replace all '9' digits with the '6' digits and consider that each set contains two '6' digits.

You can see LittlePig's solution as a reference:

    numberOfSets(int roomNumber)  
    {  
        int P[10]; 
        for (int I = 0; I < 10; I++) 
            P[I] = 0; 
        for (; roomNumber > 0; roomNumber /= 10) 
            P[roomNumber % 10]++; 
        P[6] += P[9]; 
        if (P[6] % 2) 
            P[6] = P[6] / 2 + 1; 
        else 
            P[6] = P[6] / 2; 
        int Max = 0; 
        for (int I = 0; I < 9; I++) 
            Max >?= P[I]; 
        return Max; 
    } 

Value	500
Submission Rate	289 / 662 (43.66%)
Success Rate	52 / 289 (17.99%)
High Score	srele for 454.73 points (9 mins 9 secs)
Average Score	311.10 (for 52 correct submissions)

Value	250
Submission Rate	467 / 536 (87.13%)
Success Rate	192 / 467 (41.11%)
High Score	Burunduk3 for 244.13 points (4 mins 25 secs)
Average Score	178.44 (for 192 correct submissions)

The main idea of this problem is very easy: we need to do exchanges in the proper order. But understanding the order and the realization itself plunged coders into trouble. It is not very hard to show that the proper exchange order could be generated by the following strategy:

1. If we have not enough gold coins we should get them from superfluous silver. If we lack silver to do this, we should get silver from superfluous bronze first.
2. If we have not enough silver coins we should get them from superfluous gold. If there is no extra gold we should get silver from bronze.
3. If we have not enough bronze coins we should get them from the superfluous silver. If we lack for silver to do this, we should get silver from superfluous gold first.

  int countExchanges(int G1, int S1, int B1, int G2, int S2, int B2) { 
    int ret=0; 
    while(G1<G2) { 
      if(S1>=11) S1-=11,G1+=1,++ret; 
      else if(B1>=11) B1-=11,S1+=1,++ret; 
      else return -1; 
    } 
    while(S1<S2) { 
      if(G1>G2) G1-=1,S1+=9,++ret; 
      else if(B1>=11) B1-=11,S1+=1,++ret; 
      else return -1; 
    } 
    while(B1<B2) { 
      if(S1>S2) S1-=1,B1+=9,++ret; 
      else if(G1>G2) G1-=1,S1+=9,++ret; 
      else return -1; 
    } 
    return ret; 
  }  

Value	1000
Submission Rate	52 / 662 (7.85%)
Success Rate	20 / 52 (38.46%)
High Score	I-I for 963.24 points (5 mins 35 secs)
Average Score	641.66 (for 20 correct submissions)

First, let's reinterpret the problem. During the move operation described in the problem statement we will erase the taken number but will not put it back into the array. We will continue such operations until the remaining array is sorted. It is quite evident that these two problems are equivalent.

Accordingly, with the new problem interpretation we should find the non-decreasing subsequence with the maximal sum of its element. After that erase all elements that are not in the subsequence using the modified move operation. And this will be the optimal sort.

We can find the non decreasing subsequence with the maximal sum of its element using dynamic programming. Let A[n] be a maximal sum of elements of non decreasing subsequence in the case if n is a last taken element. A[n] could be calculated with the following formula:

    A[n] = Max(A[i], (i < n) and (theArray[i]<=theArray[n])) + theArray[n];

    public int calcMinimalCost(int[] theArray) 
    { 
        int[] f = new int[theArray.Length]; 
        int res = 0; 
        for (int i = 0; i < theArray.Length; i++) 
        { 
            f[i] = theArray[i]; 
            for (int j = 0; j < i; j++) 
            { 
                if (theArray[j] <= theArray[i]) f[i] = Math.Max(f[i], f[j] + theArray[i]); 
            } 
            res = Math.Max(res, f[i]); 
        } 
        res = -res; 
        for (int i = 0; i < theArray.Length; i++) res += theArray[i]; 
        return res; 
    }

Value	500
Submission Rate	126 / 536 (23.51%)
Success Rate	90 / 126 (71.43%)
High Score	konqueror for 464.36 points (7 mins 59 secs)
Average Score	319.10 (for 90 correct submissions)

This problem can be solved with dynamic programming. Let's D[N_A][N_B] [N_C][Q][K] will be a maximal number of never moved boxed in the final configuration, if the first N_A+ N_B+ N_C boxes contain N_A 'A' boxes, N_B 'B' boxes and N_C 'C' boxes, the box with the index N_A+ N_B+ N_C-1 has Q color and there are K-1 boxes of the same color being exactly before it.

If we have value for D[N_A][N_B][N_C][Q][K] there are three variants for the box with the index N_A+ N_B+ N_C. They can be either 'A', or 'B' or 'C'. By adding up each of these boxes we will get value for the longer prefix of the boxes. Iterating this process we will find the answer for the problem.

On the challenge konqueror thought out pretty similar approach for this problem. You can use his solution as reference.

Value	1000
Submission Rate	73 / 536 (13.62%)
Success Rate	37 / 73 (50.68%)
High Score	Petr for 814.49 points (14 mins 14 secs)
Average Score	584.90 (for 37 correct submissions)

This problem has at least three principally different solutions. We will examine two of them.

Let's forget for a while that all numbers in one row should be in increasing order. We will only follow the condition that all numbers in a row before a pre-filled cell A be less than A and all numbers in the row after the A be greater than A. Let's find among all such solutions the one that is lexicographically first. It's not difficult to see that this solution is the solution for our problem as well.

Now, for each cell, let's list all values that it could theoretically take. For the cells in the row without a pre-filled cell it will be [1..25] set. For the cells that come before the pre-filled cell A in the row, it will be [1..A-1] set. And for the cell that come after the pre-filled cell A in the row, it will be [A+1..25] set. Next, let's build a bipartite graph where the first part is cells and the second is numbers 1..25. Build the edges from each cell A to all the theoretically allowable values (we've calculated these sets above). At the last step we need to find a lexicographically smallest maximum matching in this graph. This maximum matching will be the answer for the whole problem. You can see andrewzta's code as an example of this solution.

The key for one more solution is a greedy approach. First, we have to find any filled square that meets the problem statement. Second, we should improve the algorithm to get the lexicographically smallest answer. Let's find a pre-filled cell A that contains maximal value and has non-filled cells on the right. Let's get a maximal number B that hasn't been placed yet. We can safely put B to the very right of the row with cell A. We also can do the same with the smallest filled cell that has non-filled cells on the left and smallest non-placed number. Repeating these two operations we will fill the entire square. But this solution is not lexicographically first. To get a lexicographically smallest solution we should iterate over all cells in the order and check all remaining numbers for them in the increasing order. If the solution exists after we place some number we can leave this number. Otherwise we should try the next. You can use krijgertje's code as an example of that solution. He uses a little different approach but the main idea is same.