Match Editorial

Match summary

This SRM gave coders still in the running for the TCCC one more chance to practice for the second online round. In Division 1, most coders finished the easy and the medium problems quite quickly, and many submitted the hard as well. All three problems had many opportunities for errors, though, which led to many succesful challenges. As the end of the challenge phase approached, the match was so tight that the difference between sixth place and first place was less than a challenge! The system test took a number of solutions down, however, leaving only three coders who solved all the problems. andrewzta took the top spot with Petr following closely behind and ploh in third.

In Division 2, the easy problem proved to be quite difficult. Along with the abundant opportunities for mistakes in the other two problems, this led to fairly low scores overall. In the end, there were also only three Division 2 coders who solved all their problems. Newcomer lipstick took the top spot with lidaobing in second position and CandyShop in third.

The Problems

Value	250
Submission Rate	255 / 414 (61.59%)
Success Rate	220 / 255 (86.27%)
High Score	agysejt for 247.68 points (2 mins 45 secs)
Average Score	172.19 (for 220 correct submissions)

First we concatenate all the elements of str. Then we can iterate over all possible even-length substrings. For each substring we have to determine the number of positions in which the first part differs from the second part. If this number is not greater than k, we have to increment our return value. So we get the following algorithm:

int howMuch(vector <string> str, int k) {
        string s; 
        for(int i=0;i<str.size();++i) s+=str[i]; 
        int n=s.size();
        int ret=0;
        for(int a=0;a<n;++a) for(int b=a;b<n;++b) {
                int len=b-a+1;
                if(len%2!=0) continue;
                int half=len/2;
                int cnt=0;
                for(int i=0;i<half;++i) if(s[a+i]!=s[a+half+i]) ++cnt;
                if(cnt<=k) ++ret;
        }
        return ret;
}

Value	500
Submission Rate	246 / 414 (59.42%)
Success Rate	36 / 246 (14.63%)
High Score	lidaobing for 467.27 points (7 mins 37 secs)
Average Score	350.03 (for 36 correct submissions)

Value	250
Submission Rate	406 / 417 (97.36%)
Success Rate	185 / 406 (45.57%)
High Score	Michael_Levin for 246.92 points (3 mins 10 secs)
Average Score	199.72 (for 185 correct submissions)

We first note that if we have a possible final rectangle we can easily determine the number of splits necessary to create the rectangle. If it is the same rectangle as the orignal one it requires zero splits; if only one of the lengths of the final rectangle is equal to one of the lengths of the original rectangle it requires one split; and otherwise, it requires two splits. We can iterate over the side of the smallest side of the final rectangle and we will call its length a. The length of the other side of the final rectangle must be of size b=nTiles/a, and it must be an integer. Since a<=b, we get at most sqrt(nTiles) possible final rectangles. For each possible final rectangle we have to check if it fits in the original rectangle -- if it does, we have to calculate the number of split operations necessary and update our best result so far. In the end, we return the best result found, or -1 if we have found no valid rectangle. The solution follows:

int minSplitNumber(int width, int height, int nTiles) {
        int ret=3;
        for(int a=1;a*a<=nTiles;++a) if(nTiles%a==0) {
                int b=nTiles/a;
                if(a<=width&&b<=height||a<=height&&b<=width) {
                        if(a==width&&b==height||a==height&&b==width)
                            ret=min(ret,0);
                        else if(a==width||a==height||b==width||b==height)
                            ret=min(ret,1);
                        else ret=min(ret,2);
                }
        }
        return ret==3?-1:ret;
}

int minSplitNumber(int width, int height, int nTiles) {
        if((long long)width*height<nTiles) return -1;
        if((long long)width*height==nTiles) return 0;
        if(nTiles%width==0||nTiles%height==0) return 1;
        for(int a=1;a*a<=nTiles;++a) if(nTiles%a==0) {
                int b=nTiles/a;
                if(a<=width&&b<=height||a<=height&&b<=width)
        return 2;
        }
        return -1;
}

Value	1000
Submission Rate	91 / 414 (21.98%)
Success Rate	6 / 91 (6.59%)
High Score	Akinshin for 775.13 points (16 mins 19 secs)
Average Score	572.79 (for 6 correct submissions)

First we have to print all a's, then all b's, etc. To print all the a's, the optimal way is clearly just to move until the last a, printing all a's along the way. To print all the b's, there are two possible ways that can be optimal:

• First go to the leftmost b, than to the rightmost b, printing all b's along the way.
• First go to the rightmost b, than to the leftmost b, printing all b's along the way.

bool have[256];
int first[256];
int last[256];
int cnt[256];

int minMoves(string s) {
        int n=s.size();
        for(int i=0;i<n;++i) {
                if(!have[s[i]]) first[s[i]]=i;
                have[s[i]]=true;
                last[s[i]]=i;
                ++cnt[s[i]];
        }
       
        int leftpos=0,leftval=0,rightpos=0,rightval=0;
        for(char c='a';c<='z';++c) if(have[c]) {
                int nleftval=min(leftval+abs(last[c]-leftpos),rightval+abs(last[c]-rightpos))+abs(first[c]-last[c])+cnt[c];
                int nrightval=min(leftval+abs(first[c]-leftpos),rightval+abs(first[c]-rightpos))+abs(last[c]-first[c])+cnt[c];
                leftpos=first[c], leftval=nleftval, rightpos=last[c], rightval=nrightval;
        }
        return min(leftval,rightval);
}

Value	500
Submission Rate	358 / 417 (85.85%)
Success Rate	120 / 358 (33.52%)
High Score	felix_halim for 482.08 points (5 mins 31 secs)
Average Score	336.66 (for 120 correct submissions)

We first note that if we sort the data and reverse it, we get a valid ordering. To find the lexicographically smallest one, we start with zero elements and, every time, append the smallest element left in data such that it is still possible to create a valid ordering. We can create a valid ordering in each of the following cases:

• If all the remaining elements are the same as the current element. In this case, we can simply append them.
• If the difference between the largest remaining element and the current element is at least two. In this case, we can reverse the remaining elements and append them.
• If there remain elements containing a smaller element than the current element. In this case, we can split the remaing elements into two parts: the ones smaller or equal to the current element and the ones greater than the current element. We can then reverse the first part and append them, then reverse the second part and append them.

vector <int> sortArray(vector <int> data) {
        sort(data.begin(),data.end());
        vector<int> ret;
        while(data.size()>0) {
                for(int i=0;i<data.size();++i) {
                        if(ret.size()>0&&ret.back()+1==data[i]) continue;
                        if(data[i]==data[0]&&data[0]+1==data.back())
                continue;
                        ret.push_back(data[i]);
                        data.erase(data.begin()+i);
                        break;
                }
        }
        return ret;
}

Value	1000
Submission Rate	51 / 417 (12.23%)
Success Rate	7 / 51 (13.73%)
High Score	Petr for 619.76 points (25 mins 52 secs)
Average Score	509.16 (for 7 correct submissions)

First note that we can safely ignore duplicate edges, that the order of the merge operations does not matter and that the number of operations to convert the graph into a cycle is simply n-"the number of vertices in the final cycle." If there is a vertex that has multiple outgoing edges, then the vertices to which these edges point must be merged. Similarly, if there is a vertex that has multiple incoming edges, then the vertices these edges come from must be merged. We can keep merging vertices until every vertex has at most one incoming and at most one outgoing edge. Now, for each connected component, there are two possibilities -- it is path or it is a cycle:

• If there are cycles, the length of each cycle must be a multiple of the cycle of the final solution. In other words, the length of the final cycle must be a divisor of the greatest common divisor of the lengths of all cycles. However, it is clear that we can merge all the cycles and the paths in a final cycle of this length, so the final answer is n-"the greatest common divisor of the lengths of all cycles."
• If there are no cycles, all connected components are paths. We can connect these paths end-to-end to create a final cycle of length equal to the sum of the total number of edges of all paths. But it is clear that this is also the maximum cycle length we can create. So the final answer is n-"the sum of the number of edges in all paths."

• Do exactly what the above algorithm says. This was the approach taken by andrewzta, ploh, Vitaliy and sheiech.
• Try for each possible final cycle length, if we can create it. If there are cycles, we can create a given final cycle length if all cycles have a length that is a multiple of the final cycle length. If there are no cycles, we can create a given final cycle length if the sum of the maximum path length in each component is greater or equal to the final cycle length. This approach was taken by Petr and gawry.
• The approach I found most elegant was to calculate the greatest common divisor of all cycles (if there are any) and the maximum path length in each component and return n-"this common divisor" if there are any cycles and n-"the sum of the maximum path lengths in each component" otherwise. This approach was only taken by ahyangyi.