JOIN
 Match Editorial
SRM 391
Tuesday, February 26, 2008

## Match summary

This SRM attracted 1064 competitors. Div1 competitors confronted problems of relatively math flavor, while Div2 competitors confronted easy level 1 and level 2 problems but a very tough level 3, which leaded to no correct submission for it during the contest.

In Div1 more than 20 competitors solved all three problems successfully. Smylic got his first SRM win by a small gap of less than 4 points, followed by Michael_Levin and SnapDragon. They all got their places mostly thanks to their fast 1000 points solutions.

In Div2 nobody solved all three problems just like the previous SRM due to the tough level 3 problem. Alex_KPR won with a very high score for level 1 and 2 problems and a plus of 100 points in challenge phase. piloop got the second place with a 200 points plus in challenge phase and Rhawk187 got the third place with 100 points plus in challenge phase.

# The Problems

SnowyWinter
Used as: Division Two - Level One:
 Value 250 Submission Rate 501 / 617 (81.20%) Success Rate 423 / 501 (84.43%) High Score nitdgp for 249.27 points (1 mins 32 secs) Average Score 199.69 (for 423 correct submissions)

Based on the constraint that the points only range from 0 to 10000, we can get a very simple solution. Considering that there are at most 10000 unit segments, we use an array of size 10000 to record whether each unit segment has been covered while processing all the reports one by one. After that, we just need count the number of covered unit segments. See Alex_KPR's solution for example.

Another method is more complex. Sort all reports by beginPoints increasingly, process them one by one and meanwhile record and update the last covered rightmost point. See edunov's solution for example.

IsomorphicWords
Used as: Division Two - Level Two:
 Value 500 Submission Rate 397 / 617 (64.34%) Success Rate 334 / 397 (84.13%) High Score Alex_KPR for 486.63 points (4 mins 44 secs) Average Score 346.27 (for 334 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 435 / 440 (98.86%) Success Rate 428 / 435 (98.39%) High Score blueblimp for 247.83 points (2 mins 39 secs) Average Score 218.27 (for 428 correct submissions)

The key step is to check whether two words are isomorphic. Firstly two words of different lengths are definitely not isomorphic. Given two words of the same length, we can construct the required letter-to-letter mapping or report failure, which means the two words are not isomorphic, by scanning both words one by one letter from left to right. All we need are two arrays map[] and remap[] of size 26, the former records which letter the corresponding letter of the first word has been mapped to or not assigned and the latter records which letter has been mapped to the corresponding letter of the second word or not assigned. While scanning two words, we check the inconsistency in map[] and remap[] and update them by adding new single letter-to-letter mapping. See SnapDragon's solution for a neat implementation.

MarbleCollectionGame
Used as: Division Two - Level Three:
 Value 1050 Submission Rate 35 / 617 (5.67%) Success Rate 0 / 35 (0.00%) High Score No correct submissions Average Score No correct submissions

To solve this problem, graph theory knowledge about Strongly Connected Components is of great help, but lack in it will also be OK to understand the solution.

If there are no cells marked with 'L' and 'U', we can easily solve it by dynamic programming from left to right and from top to bottom. But life is not easy. The evil 'L's and 'U's destroy it at all. They make it possible that the robot reenters a cell, which make us headache. Let us see how we can crack the nut.

A key observation is that some cells are just like a friendly group, where the robot starts from any cell of it can successfully move by successive steps to any another cell of it. For example, in the board {"1234","U5L6","UL78"} cells in {"123","U5L","UL"} are just such a group. If such a group is maximal, namely we can't add another cell to it to make a larger group, we call it maximal group. Once the robot enters one of the cells of a maximal group, it can freely move between cells of the group and surely collect all marbles in all the cells. So we can consider a maximal group as a super cell, whose marbles are the sum of all marbles in the original cells and the robot can enter or go out of the super cell from any original cell of the group.

According to the observation we can construct a new "board" made up of super cells. The robot can move in one step from one super cell to another if and only if it can move in one step from one of the original cells of the former group to one of the original cells of the latter group. You can easily show that the robot can never reenter a super cell in the new "board", which is a good condition for dynamic programming. To construct the super cells and new "board", we firstly use BFS from every cell to find the connectivity between any pair of cells. Then, we pick one arbitrary unprocessed cell and find all cells such that there is bi-directional connectivity between the picked cell and them, they all as well as the picked cell consists of a super cell and we mark them all processed.

After constructing the super cells, a simple recursive DP is enough for remaining work. Below is the pseudo code for DP part.

```    int DP(currentSuperCell)
{
if currentSuperCell has been calculated, return the value in the cache.
mark currentSuperCell as calculated
int res = the number of marbles in currentSuperCell
for each super cell reachable from currentSuperCell
res+=DP(another super cell)
cache res
return res.
}
```
See the writer's solution in the practice room for a complete implementation.

KeysInBoxes
Used as: Division One - Level Two:
 Value 500 Submission Rate 259 / 440 (58.86%) Success Rate 185 / 259 (71.43%) High Score Petr for 483.05 points (5 mins 21 secs) Average Score 288.27 (for 185 correct submissions)

Let's see how much one bomb can help for opening boxes. You use a bomb to open a starting box, and then possibly use the key in it to open another box and so on. You will finally go back to the starting box. So one bomb can help you open a group of boxes. Moreover, starting from any one of the boxes in the group, you can always open them all. On the other hand, such a group always need one bomb to crack. Consequently, the number of such groups is just the number of bomb we need to open all the boxes.

A further observation indicates that a cycle in the permutation of the keys just corresponds to such a group of boxes. Now the problem is just to count how many permutations have not more than M cycles. It seems easier to count the number of permutations with exactly K cycles. In fact, it's just Stirling number of first kind, which has a nice recurrence relation. Based on that, we can get a simple solution. See Smylic's solution for a clear implementation.

Transformation
Used as: Division One - Level Three:
 Value 1000 Submission Rate 79 / 440 (17.95%) Success Rate 26 / 79 (32.91%) High Score Smylic for 794.44 points (15 mins 18 secs) Average Score 540.12 (for 26 correct submissions)

Here comes the toughest one! Surprisingly it has a short solution as below(Java code):

```    public String[] transform(String[] origin)
{
final int n=origin.length;
long vector[]=new long[n];
for(int i=0;i < n;i++)
vector[i]=Long.parseLong(origin[i]);
for(int i=n-1;i>=0;i--)
{
for(int j=0;j < n;j++)
{
if(j==i)continue;
long g=gcd(vector[i],vector[j]);
long t=vector[j]/g;
while((gcd(t,vector[i])) > 1)
vector[i]/=gcd(t,vector[i]);
}
for(int j=i+1;j < n;j++)
vector[i]/=gcd(vector[i],vector[j]);
}
String[] re=new String[n];
for(int i=0;i < n;i++)re[i]=(new Long(vector[i])).toString();
return re;
}
```

Let's see why it works step by step.

Firstly, assume we can express each number in A[] as a product of primes and get an integer matrix M[][] such that M[i][j] is the maximum of the set { x | P[j]x divides evenly A[i] }, where P[] is a group of prime numbers which contains all prime factors of numbers in A. Let PM[j]=Maximum{M[i][j] | for all i }. Then the LCM of As is just the product of P[j]PM[j] for all j.

We can transform the matrix M[][] instead of A[] to finish the transformation, because we can reconstruct A[] from M[][]. If we only decrease the value of M[][], the condition 1 in the problem statement will be always satisfied. To keep the LCM invariant, each PM[j] must keep invariant after the transformation. So there must be a M[i][j](among all i) equal to the original PM[j] for all j after transformation.
There are two parts we need do:
(1)We only need one such M[i][j]=original PM[j] for all j due to optimality, so we can safely set all other M[i][j]=0.
(2)If there are multiple M[i][j]=PM[j] for some specified j, we need only keep the one with maximum i due to optimality.

After the transformation of M[][], we can reconstruct the optimal answer. The problem is solved perfectly. But life is not easy as I said before! The numbers in A[] can be as large as 1018, so it's hard to factor them into products of primes. How to crack the nut? A creative idea is to use gcd() procedure to generate the same effect as above. It's not hard to show that the Java code above just finishes the two parts work exactly.

It's interesting to note that Petr's solution seems based on the prime factoring method. But I can't understand how exactly he do it.

By the way, this transformation does have a good application. It can be used to solve the generalized version of Chinese Remainder Theorem, where module numbers are not necessarily relatively prime. These ideas come from the writer's term paper for Concrete Math.

By stone
TopCoder Member