JOIN
 Match Editorial
SRM 321
Monday, October 2, 2006

## 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

KDoubleSubstrings
Used as: Division Two - Level One:
 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;
}
```

Chocolate
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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;
}
```
Another approach a lot of coders took during the challenge is handling case by case. If we take this approach, we get the following solution:
```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;
}
```

LexStringWriter
Used as: Division Two - Level Three:
 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.
To print all the c's, we can start from either the leftmost b or the rightmost b, depending on the order in which we printed the b's. From both of these starting points we again have the same possible choices: first left, then right, or first right, then left. Continuing in this way, we will end at either the leftmost or the rightmost z. So we get the following solution:
```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);
}
```

WeirdSort
Used as: Division One - Level Two:
 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.
The only case left is when the current element is the smallest element and the largest remaining element is exactly one greater. It is easy to see that, in this case, it is indeed impossible to create a valid ordering. Because we can only append elements of the same size to it, and after some time we have to append the element which is one greater, this will make the ordering invalid. We then get the following algorithm:
```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;
}
```
There are many other interesting approaches to this problem. You can find some of them by viewing the submitted solutions in the match results section of the site.

MergingGraph
Used as: Division One - Level Three:
 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."
In the contest, three different approaches of implementing this algorithm were successful:
• 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.

By krijgertje
TopCoder Member