
Match Editorial 
SRM 358Tuesday, July 17, 2007
Match summary
Egor, with fast time on all three problems, won the match thanks to a last minute challenge that left AdrianKuegel, with 7 successful challenges and a resubmit on the 500, behind. They were followed by kia, konqueror and yuhch123 who also had all three problems solved and each had at least one successful challenge. Contestants faced a simple but tricky (and challengeable) 250, a moderate 500 that trapped many coders, and a 1000 that wasn't a big problem for red and top yellow with even some blue coders solving it.
Division 2 was won by WilliamLP with 300 points on challenges followed by deena and AlexBoyko.
The Problems
CyclicWords
Used as: Division Two  Level One:
Value

250

Submission Rate

452 / 565 (80.00%)

Success Rate

356 / 452 (78.76%)

High Score

srele for 246.78 points (3 mins 15 secs)

Average Score

187.39 (for 356 correct submissions)

For every word in the input check if it's the same as at least the one that appeared before it in the input. If there is no such word, add 1 to the solution. The only thing that's left is to make a function that checks if the two words are the same. We can easily generate all the representations of one word. Two words are equal if and only if there exists at least one representation of the first word that is equal to the second word.
Also, we can normalize each word so the two words are equal if and only if their normalizations are equal. Normalization of a word is its unique representation, which can be defined as the lexicographically lowest of all its representations. So, normalization of a word "ball" is lexicographically lowest of { "ball", "allb", "llba", "lbal" }, which is "allb".
For implementation using normalization refer to kjan's solution.
BrokenButtons
Used as: Division Two  Level Two:
Value

500

Submission Rate

260 / 565 (46.02%)

Success Rate

22 / 260 (8.46%)

High Score

tangyouze for 431.30 points (11 mins 43 secs)

Average Score

300.65 (for 22 correct submissions)

Used as: Division One  Level One:
Value

250

Submission Rate

454 / 476 (95.38%)

Success Rate

217 / 454 (47.80%)

High Score

kia for 245.88 points (3 mins 41 secs)

Average Score

192.76 (for 217 correct submissions)

This one was a gold mine for people who found tricky cases like optimal solution navigating to
pages over 500,000. Also, many people's solution thought it can go to page 0 even if the button '0'
is broken. You had to be very careful in reading the statement as in the actual programming to solve it.
The Optimal entered page will never be larger than 1,000,000, so simple brute force will run in
time. Many people wrongly understood the problem statement thinking you can't enter pages
larger than 500,000. For every possible entered page (page for which the digit buttons are not
broken) we navigate first to that page and then enter the '+' or '' buttons. The number of
presses required is the number of digits of the entered page (let's say page 100 has 0 digits) +
the absolute difference between the entered and desired page (number of '+' or '' button presses).
For a nice clean implementation see sluga's solution.
SameDigits
Used as: Division Two  Level Three:
Value

1000

Submission Rate

12 / 565 (2.12%)

Success Rate

0 / 12 (0.00%)

High Score

null for null points (NONE)

Average Score

No correct submissions

Classic example of dynamic programming unfortunately proved to be too hard for division 2 coders.
Let's first solve the problem of finding out how many ndigit numbers have the required
property. Start building the number from left to right. The only things that we must know in
a certain moment is how many digits we must add, how many last digits are the same, and whether we
reach the required maximum subsequence before. Let that number be f( n, last_same, did_reach ).
It is fairly easy to get the recurrence relation from this formula, as we know that
exactly one number will increase the last_same by 1, and the other 9 numbers will downgrade
it back to 1.
To get how many numbers with exactly n digits are there we call 9*f( n1, 1, false ).
For every number i from k to n we sum up number of solutions with exactly i digits and return the sum.
Java code follows:
public class SameDigits {
final static long MOD = 44444444;
long[][][] memo;
int K;
long f( int n, int last_same, int did_reach ){
if( memo[n][last_same][did_reach] != 1 ) return memo[n][last_same][did_reach];
if( n == 0 ){
if( did_reach == 1  last_same == K ) {
return memo[n][last_same][did_reach] = 1;
} else {
return memo[n][last_same][did_reach] = 0;
}
}
if( k == K ) return memo[n][last_same][did_reach] = ( 9*f( n1, 1, 1 ) )%MOD;
return memo[n][last_same][did_reach] =
( f( n1, last_same+1, did_reach ) + 9*f( n1, 1, did_reach ) )%MOD;
}
public int howMany( int n, int k ) {
K = k;
memo = new long[ n+1 ][ k+1 ][2];
for( int i = 0; i < memo.length; ++i )
for( int j = 0; j < memo[i].length; ++j ) Arrays.fill( memo[i][j], 1 );
long sol = 0;
for( int i = k; i <= n; ++i ){
sol = (sol + 9*f( i1, 1, 0 )) % MOD;
}
return (int)sol;
}
}
BalanceScale
Used as: Division One  Level Two:
Value

500

Submission Rate

184 / 476 (38.66%)

Success Rate

81 / 184 (44.02%)

High Score

Egor for 461.31 points (8 mins 22 secs)

Average Score

303.39 (for 81 correct submissions)

First, let's divide all elements from weight with greatest common divisor of weight. Now, gcd of weight is 1.
I will proove that subset of weight that can measure every element from weight is equivalent to
subset of weight for which gcd is 1. If gcd of a subset is 1, with generalization of
Bézout's identity we can easily see that
we can measure all positive integers and therefore we can measure every element from the set. If gcd of a subset
is k which is greater than 1, we can only measure integers divisible by k. GCD of weight is 1, so there
exists at least one element not divisible by k and therefore not measurable.
Now we see that the problem is equivalent to finding minimum subset of weight so that gcd of that
subset equals gcd of weight (or 1 after we divide all the elements with gcd of a set).
Factorize all the elements, so that for every element you have an array of different prime factors of that
element (we ignore multiple prime factors). The maximal number of different prime factors for number less than
or equal to 10,000,000 is 8. For every element first assume that it's in the final answer. Then notice that
for each of these different prime factors there must be at least one element in the final answer that doesn't
contain the prime factor. Do a dynamic programming for every element trying to nullify all of his prime factors.
C++ code of the solve function follows:
(PF[i] is vector containing prime factors of ith weight)
int solve( int k, int n, int mask ){
if( n >= w.size() ) {
if( mask == ( ( 1 << PF[k].size() )  1 ) ) return 0;
else return INF;
}
if( memo[k][n][mask] != 1 ) return memo[k][n][mask];
int new_mask = mask;
for( int i = 0; i < PF[k].size(); ++i ){
if( w[n] % PF[k][i] != 0 ) new_mask = (1<<i);
}
return memo[k][n][mask] =
min( solve( k, n+1, mask ), solve( k, n+1, new_mask )+1 );
}
However, most of the coders used the fact there is not much gcd values of all subsets of a set with 50 elements where
all elements are not greater than 10,000,000. They had state DP[x] = minimal size of a subset with gcd x. The solution
is then DP[1]. See
Abednego's
solution. For optimized recursion that works too, see
andrewzta's
solution.
SharksDinner
Used as: Division One  Level Three:
Value

1000

Submission Rate

138 / 476 (28.99%)

Success Rate

51 / 138 (36.96%)

High Score

kedaizd for 886.11 points (10 mins 27 secs)

Average Score

648.15 (for 51 correct submissions)

We have to maximize the number of eaten sharks. We will first consider a little easier variation of this problem,
in which every shark can eat at most one other shark. Let's describe our problem through a bipartite graph.
Every shark will be represented with two nodes, Ai and Bi. If shark x can eat shark y, let's draw a arc from Ax to By.
Now all we need is to do a maximum cardinality matching, and report number_of_sharks  maximum_matching_cardinality as
the answer.
Similary, if every shark can eat at most 2 other sharks, we will represent every shark as 3 nodes, namely A1i, A2i and Bi.
And if shark x can eat shark y then draw an arc to both A1x>By and A2x>By. Again, just do the maximum cardinality matching
and report the answer.
There was a tricky part of ensuring that two sharks don't eat each other. This is only possible when these sharks have
exactly the same properties. We will call such sharks equivalent. Such cases can be handled by not letting a shark eat
another equivalent shark which has a lower index than him.
For implementation, refer to DStepanenko's solution.
By
icanadi
TopCoder Member