CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
47:48:50
Register now »
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
It would be nice if we could logging with Open Id and also mark "remember me for a month". I was logging in with Open Id today, and it kept forgetting me. I had to eventually try hard to remember my password... Good thing I did.
I noticed during today's round that many of the bits that would normally open a pseudo-popup window with javascript are not working in my Firefox 11 (I know 12 is out, but can't update for now).
For example the "Ask a question" link. Or the links with the submission number in practice that show you your code and the case with the mistake.
I tested in chromium and they work all right.
Anyone else experiencing this?
With the advent of contests that are 24 hours long, they can get a little too long if you start a virtual contest for them and are done with the problems after a couple of hours and do not really plan to do anything more, yet you have to wait the whole 24 hours for it to finish. You currently can just log out and go to standings though, so this is only a slight issue.
And a question, would deleting the virtual contest do this, or will it also remove the participation stats from the round's unofficial standings?
This is as minimal of an issue as possible, but how about a small minimize button that makes the problem tags part of problems in practice room hidden by default?
The thing is although tags are useful to find problems or to know the classification of a problem once you give up, when you try to solve a problem for real they sort of give away the classification while you are reading the problem statement.
Edit: Since minuses indicate that this is not welcome anymore. I will no longer post links to my blog or mention it in this site when I write explanations about a Codeforces round.
More shameless plugs.
http://vexorian.blogspot.com/2012/01/codeforces-round-102-div2.html
Some explanations. Edit: Ok, D and E are ready. Albeit the explanations are vague...
http://vexorian.blogspot.com/2011/12/codeforces-round-96-division-2.html
It may be pointless to do this. Nickolas wrote the problemset and she likely has an editorial ready.
Hopefully I'll get out of division 2 with this.
It wasn't a great day, but at least there are explanations for problems B to E.
http://vexorian.blogspot.com/2011/11/codeforces-beta-round-95.html
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.
