Tuesday, February 20, 2007 Match summary
Due to some technical problems with the room assignments, the match started four minutes later than planned, but once things settled down all 1135 contestants were able to start on this SRM. In Division 1 all three problems were reasonable tricky. After the coding phase there were only a few contestants who had submitted all three problems, with marek.cygan in first place and liympanda two challenges behind. Because of the tricky problems, there were many possible points to be gained in the challenge phase, and liympanda used this to take the first position. During the system tests many solutions failed, but liympanda's solutions didn't, which made him the winner of this SRM. Because noone else solved all three problems correctly, marek.cygan kept his second place despite his solution to the easy problem failing. Rounding out the top three was ACRush, who had a very fast time on the medium and a good challenge phase.
The ProblemsCssPropertyConverterUsed as: Division Two  Level One:
This is just a 'do what it says'problem. It can help if you are familiar with the string functions of your library, but it is not necessary, as the solution below shows. string getCamelized(string cssPropertyName) { string ret; int i=0; while(i<(int)cssPropertyName.size()) { if(cssPropertyName[i]=='') { ret+=toupper(cssPropertyName[i+1]); i+=2; } else { ret+=cssPropertyName[i+1]; ++i; } } return ret;ProblemsToSolve Used as: Division Two  Level Two: Used as: Division One  Level One:
The easiest way to tackle this problem is to look at the stop condition first. It states: "You may stop once the difference between the maximum and minimum pleasantness of the problems you've solved is greater than or equal to the int variety." Because the constraints are low enough, we can just fix the two problems for which the pleasantness between the two problems is large enough by iterating over all possible pairs of problems. If the constraints allow you to fix some important variables, it is usually a good thing to do, since it usually reduces the problem to a much simpler one. In this case, the problem becomes: "find the minimum number of problems needed to solve problems i and j, starting at problem 0 and skipping at most one problem at a time."
int calc(int x) { return (x+1)/2; } int minNumber(vector <int> pleasantness, int variety) { int ret=pleasantness.size(); for(int i=0;i<(int)pleasantness.size();++i) { for(int j=i+1;j<(int)pleasantness.size();++j) { if(abs(pleasantness[i]pleasantness[j])>=variety) { ret=min(ret,1+calc(i0)+calc(ji)); } } } return ret; }The given algorithm is not the fasted possible (it's O(n^2)), but that is not necessary for a competition like topcoder. What matters is that it works, it is fast to code, and it's easy to see that it works. Just in case you are interested, the problem can be solved in O(n) as follows: iterate through all problems and keep track of the minimum and the maximum encountered so far as well as the minimum and maximum encountered on even positions so far. As soon as the difference between the minimum and maximum of even positions becomes large enough, we can return i/2+1  and as soon as the difference between the minimum and maximum of all positions becomes large enough, we can return i/2+2. To see why this works, I advise you to draw some cases on paper yourself. Of course there are many other algorithms possible. If you are interested, you can find them using the match results on this site. Two noteworthy alternatives are:
Used as: Division Two  Level Three: Used as: Division One  Level Two:
After reading the problem statement, you should immediately think of dynamic programming. If you're unfamiliar with this technique, you should first read the tutorial on dynamic programming, which can be found under the educational content. To see why this is problem is suitable for dynamic programming, consider the following properties: If we know the current theoretical and practical skill and which month it is, we can determine the optimal solution from this point on, without needing to know anything of the past. In other words: the triple of current theoretical skill, practical skill and month is a state. Furthermore, in an optimal solution, the month will be at most equal to the number of courses, because it isn't useful to take a course multiple times. Therefore, there are only a few (51^3 = 132651) possible states.
For the memoization approach, we need two functions. One is a recursive function that, given the current state, returns the cost from that state to reach our wanted skill level. The other is a function that returns the best path. Here is an example of such two such functions. int dp(int curtheoretical,int curpractical,int curmonth) { if(curtheoretical>=skillBound&&curpractical>=skillBound) return 0; if(curmonth>=(int)theoreticalValue.size()) return INF; if(done[curtheoretical][curpractical][curmonth]) return cache[curtheoretical][curpractical][curmonth]; else done[curtheoretical][curpractical][curmonth]=true; int ret=INF; for(int i=0;i<(int)theoreticalValue.size();++i) if(curtheoretical>=theoreticalValue[i]1&&curpractical>=practicalValue[i]1&&curmonth<expire[i]) { int cur=dp(max(curtheoretical,theoreticalValue[i]),max(curpractical,practicalValue[i]),curmonth+1)+1; if(cur<ret) { ret=cur; bestcourse[curtheoretical][curpractical][curmonth]=i; } } return cache[curtheoretical][curpractical][curmonth]=ret; } vector<int> construct() { vector<int> ret; int curtheoretical=0,curpractical=0,curmonth=0; while(curtheoretical<skillBoundcurpractical<skillBound) { int course=bestcourse[curtheoretical][curpractical][curmonth]; ret.push_back(course); curtheoretical=max(curtheoretical,theoreticalValue[course]); curpractical=max(curpractical,practicalValue[course]); ++curmonth; } return ret; }VegetableGarden Used as: Division One  Level Three:
The key to solving this problem is to remember how we test in geometry problems if a certain point lies inside a polygon. One way to do this is to draw a line from the point in an arbitrary direction, and test if the number of lines of the polygon it intersects is even (outside the polygon) or odd (inside the polygon).
vector <int> getMinDistances(vector <string> garden) { int h=(int)garden.size(),w=(int)garden[0].size(); int nrcare=0,nrwant=0,cant=0; for(int i=0;i<h;++i) for(int j=0;j<w;++j) if(garden[i][j]=='I') { garden[i][j]='0'+nrcare; ++nrwant; ++nrcare; } for(int i=0;i<h;++i) for(int j=0;j<w;++j) if(garden[i][j]=='X') { garden[i][j]='0'+nrcare; cant=1<<nrcare; ++nrcare; } for(int j=0;j<w;++j) { under[h][j]=0; for(int i=h1;i>=0;i) under[i][j]=under[i+1][j](isdigit(garden[i][j])?1<<(garden[i][j]'0'):0); } int DX[]={1,0,1,0,0}; int DY[]={0,1,0,1,0}; for(int i=0;i<=h;++i) for(int j=0;j<=w;++j) for(int k=0;k<(1<<nrcare);++k) best[i][j][k]=INF; queue<State> q; best[0][0][0]=0; q.push(State(0,0,0)); while(!q.empty()) { int x=q.front().x,y=q.front().y,z=q.front().z; q.pop(); for(int k=0;k<4;++k) { int nx=x+DX[k],ny=y+DY[k]; if(nx<0nx>hny<0ny>w) continue; int nz=z; if(DY[k]==+1) nz^=under[x][y]; else if(DY[k]==1) nz^=under[nx][ny]; if(best[x][y][z]+1<best[nx][ny][nz]) { best[nx][ny][nz]=best[x][y][z]+1; q.push(State(nx,ny,nz)); } } } vector<int> ret(nrwant,INF); for(int i=1;i<(1<<nrcare);++i) if((i&cant)==0) ret[bitcount[i]1]<?=best[0][0][i]; return ret; } 
