Feeling of frustration

I joined yesterday a CodeJam practice session. It seems Googlers were fine tuning the contest site for the onsite finals to be held soon.

Problems were (or they look) easy but a combination of stubbornness and not thinking before coding let me in an embarrassing position (the best thing I can say I was not the worst player). However I failed to see the very easy relationship on the number of black balls (odd/even) and the final output of the Old Magician problem (too late I found out that even black balls lead to a WHITE result, BLACK otherwise and UNKNOWN was just a distraction).

The square fields problem looked very much like a k-clustering problem, but here the clusters are all same size and square shape. You have to answer what is the minimum size of the squares to get a partitioning on exactly k-clusters.

I can tell you how other people solve it, but you can read this by yourself. Instead I'll tell you what won't work:

My first idea was to use java awt library and Rectangle class in particular. I started with the largest side possible for the square and then I tried to obtain the full coverage of all the points by creating new rectangles to cover the points not yet included in the covered area. Once all covered I decremented the size and repeated the process. When full coverage was impossible with a given size I output the size+1 value as the result.

This approach work for some of the examples but failed on certain cases, so it was not good.

Second idea (and attempt) was to consider obtain the Minimum Spanning Tree of the points of the problem, then I would remove the k-1 longest links so I would end up with k disconnected sets. Later I will find out what is the largest dimension on any axis of every group, that will be the answer.

Again the idea worked nicely with most of the cases but not with all (Case #5 of the small set was one of the ones that didn't work with). The problem is that in this case the first point (1) is connected to 3,4,5,7 as nodes 2 and 6 remain isolated because of my algorithm. However the solution is that node 1 is connected to node 6 and then the max square side is limited by the vertical distance between nodes 5 and 3 (it's 1000 in case you wonder).

So my second approach did not work in all the cases either. So I will be happy getting a suggestion that works.

Because I've been busy failing on the second question I haven't yet been able to attempt the third exercise (Cycles) that wants us to count the number of Hamiltonian cycles on a undirected total connected graph where some links are forbidden and where shifts of the same node sequence count as 1 case only.

I guess that the result will have to do with dividing the total permutations by the different number of combinations that can be done with the forbidden links. I'm going to have a look at it as soon as I solve the second exercise with a solution that works ok everytime.