
Match Editorial 
SRM 351Tuesday, May 29, 2007
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
RoomNumber
Used as: Division Two  Level One:
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 languagespecific 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;
}
CoinsExchange
Used as: Division Two  Level Two:
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)

Used as: Division One  Level One:
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:

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.
 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.
 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.
krijgertje has a very good implementation of this strategy. Here is his code:
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;
}
InsertSort
Used as: Division Two  Level Three:
Value

1000

Submission Rate

52 / 662 (7.85%)

Success Rate

20 / 52 (38.46%)

High Score

II 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
nondecreasing 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];
The answer for the initial problem will be the sum of all elements in theArray minus the maximum element in the array A.
Here is
II's solution that illustrates this idea:
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;
}
BoxesArrangement
Used as: Division One  Level Two:
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 K1 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.
NewMagicSquare
Used as: Division One  Level Three:
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 prefilled 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 prefilled cell it will be [1..25] set. For the cells that come before the prefilled cell A in the row, it will be [1..A1] set. And for the cell that come after the prefilled 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 prefilled cell A that contains maximal value and has nonfilled 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 nonfilled cells on the left and smallest nonplaced 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.
By
Andrew_Lazarev
TopCoder Member