Match summary

TCO07 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 Problems

SquareCypher

Used as: Division One - Level One:

Value 250

Submission Rate 397 / 406 (97.78%)

Success Rate 362 / 397 (91.18%)

High Score Eryx for 248.69 points (2 mins 4 secs)

Average Score 205.97 (for 362 correct submissions)

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 square-numbered 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:

Value 500

Submission Rate 252 / 406 (62.07%)

Success Rate 129 / 252 (51.19%)

High Score gozman for 485.78 points (4 mins 53 secs)

Average Score 329.37 (for 129 correct submissions)

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 tie-breaker 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=X-1;
  }

  return sol;
}

MedievalCity

Used as: Division One - Level Three:

Value 1000

Submission Rate 19 / 406 (4.68%)

Success Rate 10 / 19 (52.63%)

High Score malcin for 597.89 points (27 mins 33 secs)

Average Score 482.34 (for 10 correct submissions)

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 bottom-right 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 out-of-the-box 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[i-1]) dx=+1;
  if (bx[i]<bx[i-1]) dx=-1;
  if (by[i]>by[i-1]) dy=+1;
  if (by[i]<by[i-1]) dy=-1;
 
  int x=bx[i-1], y=by[i-1];
  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(x-1,y+1));
      outer.insert(make_pair(x-1,y));
    }
    if (dy==+1) {
      inner.insert(make_pair(x,y+1));
      outer.insert(make_pair(x-1,y+1));
    }
    if (dy==-1) {
      inner.insert(make_pair(x-1,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 0-dangerous and we'll proceed with the 1-dangerous squares. Those are all squares that are adjacent to 0-dangerous squares, but that are not 0-dangerous themselves and are not on the outer boundary. We can use this insight iteratively to find all n-dangerous 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;

By Jan_Kuipers
TopCoder Member