Another year, another year in which I don't get to round 3 of the TopCoder open. But like last year, this brings an opportunity, I can try wearing my problem setter suit this time.
550 points: Block3Checkers
Remember when I talked about problem setting SRM 579 and how we had issues just a day before the match?
Block3Checkers was the problem that was initially intended to be in SRM 579.
First version
You have a NxN board. There are three checkers in the board that belong to Alice, their positions touch the border of the board. 0 to 61 checkers occupy other slots and are neutral (can't be moved). What is the minimum number of squares in the board on which you have to add new checkers so that it is impossible for Alice to move any pair of her checkers to two adjacent cells (She is only allowed to move a checker horizontally or vertically to an empty spot).
I thought of this while walking/running. SRM 579 was nearby and there was no div1 medium. This was my chance to shine. My chance to make 125 bucks. But I didn't have a medium. So my mind started wandering.
The first version of the problem had this intended solution: Let us name Alice's checkers X,Y and Z. We need at most 3 checkers to block the path between X and Y (because we can always surround any of them with only 3 checkers, thanks to them being in the border of the board). We need at most 3 checkers to block the path Z and X or Y. The intersection. Of these two solutions would be THE solution. We just need two brute forces for three cells, and then somehow merge them. Similar to a meet-in-the-middle.
It seemed interested, proposed it. rng_58 liked it, although not because of my approach, but because he thought of another approach, a faster one that I didn't understand at all. But all was right. Kept developing this problem and the others as SRM 579's date approached.
Until the night before SRM 579. In which ivan_metelsky helped us figure out that this clever idea of a solution was wrong. This is a case it gets wrong:
..#A#...
A#.#N...
#.......
...N.N..
.......A
N.......
NN......
.NNN.N..
The Ns are neutral checkers, the As are Alice's checkers and the # are the positions in which to place 5 of Bob's checkers. The clever approach with intersections returns 6.
Pre SRM 579 crisis
So we only had few hours before the match. We didn't have a replacement problem and we knew two things: a) My solution, the intended one, was very wrong. b) rng_58's was probably not wrong but is certainly not easy to find. So we were undecided for a couple of hours whether to use the problem, but allowing brute force (it would become a very simple problem, you bruteforce for up to 5 cells on which to place the checkers, if you don't find a solution, you can return 6 directly). Or find a replacement. As you know, we eventually found a replacement.
TCO revival
This problem still existed, and I knew that, using the solution that rng_58 found, it had potential to either be a div1 hard or be used in the TCO rounds. I made the problem available for the TCO. And it was approved.
It took me a good while to understand the new solution. It requires you to take advantage of the checkers touching the border of the board. They effectively divide the perimeter of the board in three parts. Imagine if there was a 8-connected path of N or B checkers between one segment of the perimeter and another. This would effectively make a cut. Between all checkers inside and all checkers outside the space delimited by the path. So there are four six of connected components of N/B checkers:
1) Does not touch the border.
2) Touches only one of the segments of the border
3) Touches TWO of the segments of the border.
4) Touches all THREE segmens.
In case 1) or 2), this connected component does not block any path between Alice's checkers. If one component like 4) exists, the problem is already solved. Else we need two different components of the kind 3) (Each Connecting a different pair of segments)
So, the problem is, for every possible way to accomplish this, find the minimum number of Bob's checkers to add. What's the minimum number of checkers to make two different pairs of segments connected? What is the minimum number of checkers to make a center checker (N or B) connected to all three segments?.
Constraints discussion
This approach can be implemented fast , in fact it works for 50x50. But it needs work for such an optimization. I initially wanted the constraints to state as 8x8, it would make it not needed to make more test cases. And people would get tricked into making the wrong solution. But it didn't click with the admins. Too much risk to have a situation in which an optimized brute force of up to 5 cells passes.
Then it seemed like up to 12x12 was a fine idea, those bruteforces would be inviable. But rng_58 thought of an exponential approach that relies on dp. You can imagine that all empty cells connected to each of Alice's checkers have a specific color. So all empty cells connected with X are red. All empty cells connected with Y are green and all those connected with Z are blue. The remaining cells, are black. Clearly, two cells of different colors (except black) can't be adjacent, so that they weren't connected. this allows an optimized dp that would pass for n=12. So we needed to increase the constraints, again.
Too bad I learned of that during the morning. I had to give up some hours in the IPSC because of this. I kept my first IPSC hour making new challenges.
0 comments:
Post a Comment