January 23, 2018 On Marathon Match 96: How It Feels Not To Finish

The Topcoder Marathon Match 96 submission phase ended on December 27. It was one of those tense contests. The 100 provisional tests used during the match, could not determine the winner; sdya and Milanin were tied at the 1st position. My guess is, they both either used the same idea, or the constraints on the data were weak enough for participants to come up with near-perfect or even perfect solutions.
I have mixed feelings about this challenge. I ended up with nothing on my plate – by which I mean I couldn’t submit a solution – despite putting in quite some effort. I developed a solution alright, but it did not work.

The Results

The top-3 solutions this time were created by sdya, NobuMiu, and Milanin, in that order. My congratulations to them and to all those who managed to submit something more advanced than the hardcoded demo solution. Good job to all, as the task seemed to not have a clean, neat, and short solution that could get some considerable amount of points.
Given how complicated the problem was, people tried different approaches to score big. Unfortunately, not all of those approaches worked.

The After Match Forums Discussions

If you did not know it, there are after-match discussions going on right here. Everyone is welcome to post their findings and ask questions of any kind after the match. The usual topics are solution sharing — the “Post your approach” thread — and the “Statistics”. The ‘statistics’ thread is rather interesting. It is made out of public Topcoder API feed calls that are deprecated now, but looks very different in a human-readable format.

Challenge Approach Discussion

I will allow myself to quote some ideas shared on the forums.
NobuMiu, the runner up, uses/used the Divide and Conquer method:
“I split the field into 3×3 – 5×5 sub-rectangles. The number of sub-rectangles should be even, either vertically or horizontally in order to create a hamilton cycle easily.”
Last year TCO algorithm finalist nika estimated the maxima theoretical score for this task:
“You can notice that in any valid solution, number of tiles of type 0 equals to number of tiles of type 2. Same for 1 and 3. So if c[i] is the number of tiles of type i then there is obvious upper bound on optimal length: 2*min(c[0], c[2]) + 2*min(c[1], c[3]) + c[4] + c[5] – (c[4]+c[5]) % 2”
Where did I go wrong? I was trying to implement Beam search top-down in row-major order. The transition function was too difficult for me to grasp, so I ended up with an unfinished solution.
dimkadimon attempted a Simulated Annealing approach with swapping tiles as a transition. He calculated the score after each step and saved best results. I suppose it was not enough to arrive to the optima, because I didn’t see any submissions from him either.

What’s Next

The next ‘fun marathon’, as they are called now, is scheduled to start on January 24. So, Get ready for another gruelling but rewarding session of brainstorming!
There are sponsored marathons running as well. If you feel confident in Neural Networks, Machine Learning algorithms, Data Analysis, or just want to learn those — I suggest you to give it a try. There are some plans to cover them in more details, but some other time.