Match Editorial

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

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.

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)

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.

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.
    }

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.

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 10¹⁸, 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.