Algorithm Round 1C Thursday, April 12, 2007 Match summaryTCO07 online Round 1 concluded with section C, which was probably the easiest of the three sections. No targets participated in this section, but that didn't mean things would be easy. With only 300 coders advancing to round 2, people did their utmost best to be one of them. The round started off with an easy problem that didn't cause much trouble for most coders. The medium one was harder and caused about half of the submissions to fail. The tough hard problem was only solved by ten coders.In the end, only seven coders, all of them red, managed to correctly solve all three problems. Leading the pack were gozman, Revenger and JongMan. The other coders to solve all three problems were sql_lall, Jan_Kuipers, xhl_kogitsune and malcin. The ProblemsSquareCypherUsed as: Division One  Level One: This problem didn't cause a lot of trouble. The easiest way to solve it was to first figure out how many characters were moved to the beginning. This turns out to be 1+sqrt(cryptogram.size()1). After that, just put those characters on the squarenumbered places and the others on the remaining places. Code to do this follows: string decrypt(string cryptogram) { int numSquares = (int)floor(sqrt(cryptogram.size()  1.0)) + 1; int i=0, j=numSquares; string sol; for (int k=0; k<cryptogram.size(); k++) if (isSquare(k)) sol+=cryptogram[i++]; else sol+=cryptogram[j++]; return sol; }RaceTrack Used as: Division One  Level Two: A quote from misof the editorial for TC07 Round 1A: "... there is one natural question you should ask: given a fixed value X, can I find an efficient way to verify whether the condition holds for my X?" Well, for this problem you can actually determine easily whether a distance X is achievable. Just put one judge in the first seat, put the next judge in the first seat that has distance greater than or equal to X from that seat, and so on. If you place all the judges this way, it is possible  but if you run out of seats, it isn't. Moreover, the placement is also the one obeying the tiebreaker rule of putting all judges as close to the start as possible. After noticing this, just do a binary search on the answer and you're done: string judgePositions(int length, int judges, vector<int> pos) { int lo=0, hi=length; string sol; while (lo!=hi) { int X=(lo+hi+1)/2; int placed=0; int prev=INFTY; string used(pos.size(), '0'); for (int i=0; i<pos.size(); i++) if (pos[i]>=prev+X && placed<judges) placed++, prev=pos[i], used[i]='1'; if (placed==judges) lo=X, sol=used; else hi=X1; } return sol; }MedievalCity Used as: Division One  Level Three: This problem gave a lot of coders a hard time. First notice that the bounds allow the city to cover an area bigger than 10,000 times 10,000, so that drawing it in an array is impossible. To solve the problem we start with parsing the input string, resulting in the coordinates of the wall. We'd like this boundary to be oriented clockwise (or counterclockwise, whatever you prefer). To do this we calculate the area, and reverse the coordinate list if it turns out to be negative: string s; for (int i=0; i<boundary.size(); i++) s+=boundary[i]; int x=0,y=0,i=0,area=0; vector<int> bx,by; bx.push_back(x); by.push_back(y); while (i<s.size()) { char c=s[i++]; int n = (i<s.size() && isdigit(s[i])) ? 0 : 1; while (i<s.size() && isdigit(s[i])) n=10*n+s[i++]'0'; if (c=='L') x=n; if (c=='R') x+=n; if (c=='U') y+=n; if (c=='D') y=n; bx.PB(x); by.PB(y); area += bx[bx.size()1]*by[by.size()2]  bx[bx.size()2]*by[by.size()1]; } if (area<0) { reverse(bx.begin(),bx.end()); reverse(by.begin(),by.end()); }Now that we have the coordinates of the boundary in a clockwise fashion, we want to figure out which squares are directly adjacent to it on the inside, and which are directly adjacent to the outside. To do so, I'll assign the coordinate (x,y) to the square to the bottomright of lattice point (x,y). A boundary piece from (x,y) going to the right then results in a square (x,y) on the inner boundary and a square (x,y+1) on the outer boundary. Boundary pieces in other directions also result in one square on the inner boundary and one on the outer one. Some squares may enter the lists multiple times. To prevent this, most languages have outofthebox datastructures, like C++'s set: set<pair<int,int> > inner,outer; for (int i=1; i<bx.size(); i++) { int dx=0,dy=0; if (bx[i]>bx[i1]) dx=+1; if (bx[i]<bx[i1]) dx=1; if (by[i]>by[i1]) dy=+1; if (by[i]<by[i1]) dy=1; int x=bx[i1], y=by[i1]; while (x!=bx[i]  y!=by[i]) { if (dx==+1) { inner.insert(make_pair(x,y)); outer.insert(make_pair(x,y+1)); } if (dx==1) { inner.insert(make_pair(x1,y+1)); outer.insert(make_pair(x1,y)); } if (dy==+1) { inner.insert(make_pair(x,y+1)); outer.insert(make_pair(x1,y+1)); } if (dy==1) { inner.insert(make_pair(x1,y)); outer.insert(make_pair(x,y)); } x+=dx; y+=dy; } }Now that we have the inner and outer boundaries, we know how many squares are 0dangerous and we'll proceed with the 1dangerous squares. Those are all squares that are adjacent to 0dangerous squares, but that are not 0dangerous themselves and are not on the outer boundary. We can use this insight iteratively to find all ndangerous cells too: int DX[4] = { 1,1,0,0 }; int DY[4] = { 0,0,1,1 }; int sol=0; for (int danger=0; danger<=dangerBound; danger++) { sol += inner.size(); set<pair<int,int> > newinner; for (set<pair<int,int> >::iterator it=inner.begin(); it!=inner.end(); it++) { int x=it>first, y=it>second; for (int d=0; d<4; d++) { int nx=x+DX[d], ny=y+DY[d]; if (!inner.count(make_pair(nx,ny)) && !outer.count(make_pair(nx,ny))) newinner.insert(make_pair(nx,ny)); } } outer=inner; inner=newinner; } return sol; 
