vexorian's blog

Just lost rating for this lame bug.
By vexorian, 15 years ago, In English
So sad, I would have solved C in round 8 since I noticed how to make my memo solution work in time (by making it forcefully consume the first element that is still in the bitmask) but... So what I did was that when I encode the used pairs, I use (x,N) for a "pair" that is just a single element, that's what generated the mistake:

            int x = mem2[mask]/100;
            int y = mem2[mask]%100;
            if(y!=N) {
                cout<< "0 "<<(x+1)<<" "<<(y+1)<<" ";
            } else {
                cout<< "0 "<<(x+1)<<" ";
            }
            mask = mask - (1<<x) - (1<<y);           

Well, I would have solved this easily if I didn't use subtraction for bitmasks or if I actually paid attention .... I am pretty sure I would have reached yellow if it wasn't for this bug, but I dropped to 1500~ instead :(


Edit: wow , so the blog entry gets spammed to everybody in the home page, better change it to something useful.

Problem A:
This one was sort of simple but I don't think it was possible to solve it without knowing KMP, just divide the problem into parts. Eventually, I just used KMP on both the input string and the reversed string to get the minimum area to the left of the string that can hold the first substring and the minimum area to the right of the string that can hold the second one. If the sum of these lengths is <= the length of the string, then the thing is possible. (run KMP four times per case, this is  linear, cool)

Problem B:
This was a nice problem, my first idea was to mark white cells on a 201x201 board that is full of walls (and start simulating the movements from 100,100), if you ever reach a cell that is adjacent to a previously visited cell or if a cyclic is formed then it is not the shortest path.

I am sure that approach works, but before risking it , I noticed the constraints, so I just did the same thing and filled white cells on a 201x201 array of walls starting at (100,100) (and simulating the moves). Then I ran a BFS from (100,100) to the final location. If the distance of the BFS is not the same as the length of the string, it is fine.

Problem C:
O(n * 2^n) runs in time, and O(2^n) memory is short enough.

My first idea was a [2^n] memoization, but I used a n*n loop inside of it, so I hit the time limit. Then I went for lunch where I figured out that you can turn this from O(n*n*2^n) to O(n*2^n) by noticing that every point has to be forcefully visited. So I changed then n* n loop into 2 loops, the first one finds the first element that is in the bitmask and the second loop tries to find pairs that contain this element.

  • Vote: I like it
  • +2
  • Vote: I do not like it

15 years ago, # |
  Vote: I like it +2 Vote: I do not like it
KMP was not needed for problem A. I used this code for the two checks (S, A, B are the three lines of input):

bool check()
{
    char *p = strstr(S, A);
    if (p) return strstr(p + strlen(A), B) != 0;
    return false;
}
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Makes me feel sort of lame, but I do appreciate I had to re-practice on KMP helped me notice I need to familiarize myself better with this great algorithm.
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes,I used the function strstr.
    → Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I made some silly mistakes in problem E too, one of them is I wrote "return -1" instead of "cout << -1" ( although I didn't practice much on TopCoder recently ).
→ Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Problem B doesn't need BFS. I solved it in linear time using followin approach:
set all f[201][201] = 0;
set f[100][100] = 1; // start location
simulate moving and for each new location f[x][y], check the sum of four adjacent cells. If the sum > 1 then answer is BUG.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Yes, problem C turned out to be easier, than my first solution for it. Actually I thought that the girl can visit the object points as many times as she wants, that means the order of points (when you grab two objects) may be important. But it was not true - so coding the bitmasks turned out much simpler in the end.
→ Reply