Monday, October 2, 2006 Match summaryThis 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 ProblemsKDoubleSubstringsUsed as: Division Two  Level One:
First we concatenate all the elements of str. Then we can iterate over all possible evenlength 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=ba+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: Used as: Division One  Level One:
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<=heighta<=height&&b<=width) { if(a==width&&b==heighta==height&&b==width) ret=min(ret,0); else if(a==widtha==heightb==widthb==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==0nTiles%height==0) return 1; for(int a=1;a*a<=nTiles;++a) if(nTiles%a==0) { int b=nTiles/a; if(a<=width&&b<=heighta<=height&&b<=width) return 2; } return 1; }LexStringWriter Used as: Division Two  Level Three:
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:
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:
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:
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:
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:

