Hello, I'm the writer of SRM 655 Div1 Easy and Hard.

Div1 — Easy

The key is to thinking from last operation: it will make the final board have a k by k monochrome rectangle.

for example, if we have:

BBBW
BWWW
BWWW
WWWW

Then we know in the last step we may paint the right-down 3 by 3 rectangle. And that means, before this step, these 3*3 cells can be any color. So the board will looks like:

BBBW
B???
B???
W???

And we can see the previous step could be upper-left 3 by 3 rectangle (because we can change '?' to 'B' and that is monochrome), so we get:

???W
????
????
W???

And we are done, because if we change '?' to 'W' that is all-white board.

So the algorithm is: keep finding k by k monochrome rectangles and paint it into '?', until can't do it. And check if the board is all-white. You can proof no matter the order of rectangle we choose to paint, we will get the same result.

Code: http://ideone.com/xM13nh

Fun fact: I come up with this idea when I was playing a mobile game: Strata. Usually puzzle games are NP-Hard, but I find this one is not. :P

Div1- Hard

First let's think about how can I solve it if we change blue points to a circle:

(If you can't see the picture, please use this url: http://postimg.org/image/ssvbih7sd/)

For a point P, we say it covers the direction [OA, OB] of that circle.

We can prove: "circle totally in the CH of points" if and only if the union of directions of each point covers is all 360 degree.

The polygon version is same. We can change the vertex to an infinite small arc of circle. Then P will cover the direction [EF, CD]. The condition will remain same.

So the problem becomes: we have lots of interval of directions, each one have a certain probability of occur, you are ask the probability that the union will be [-Pi, Pi]. That could be solved by DP (my solution is N^3).

Code: http://ideone.com/Yq4ReK

Fun fact: there is a simplified version (2 blue points instead of up to 100, but require n^2 solution) used in TCO 2012 round 3B Hard wrote by ivan.metelsky, but today he was solving this harder version during the contest!

And congratulations to tourist! He solved all 3 tasks with highest score with 7 successful challenge!