Rank Handle Country Score PRank PScore Bests Uniques Perfects Zeros TLEs

1 sdya Ukraine 973391.25 1 976232.19 1999 0 0 0 0

2 NobuMiu Japan 973387.81 3 976222.02 1992 0 0 0 0

3 Milanin Russian Federation 973365.56 1 976232.19 1995 0 0 0 0

4 atsT5515 Japan 973312.33 4 976198.43 1949 1(Test Case 1165) 0 0 0

5 hoshi524 Japan 973282.53 5 976196.21 1867 0 0 0 0

6 kurenai3110 Japan 972634.14 6 975658.20 1391 0 0 0 0

7 wleite Brazil 971291.39 7 975431.52 1133 0 0 2 0

8 PItS Japan 967547.39 8 972572.78 759 0 0 3 3

9 yowa Japan 966386.63 9 971217.68 206 0 0 0 0

10 suikkee Japan 966060.48 10 968534.87 477 0 0 0 0

11 neetsdkasu Japan 963709.61 12 966890.38 324 0 0 0 0

12 iehn Japan 963699.73 11 966918.67 267 0 0 0 0

13 iwashi31 Japan 958629.28 13 962928.03 145 0 0 0 0

14 ebicochineal Japan 956366.16 14 961483.99 75 0 0 4 0

15 EvbCFfp1XB Japan 938321.33 16 942728.84 7 0 0 0 0

16 okazaki Japan 935469.62 15 943976.77 6 0 0 24 0

17 olphe Japan 914139.79 17 940273.08 12 0 0 42 0

18 darnley Russian Federation 901541.80 18 906798.95 0 0 0 0 0

19 LLI_E_P_JI_O_K Russian Federation 900818.89 19 906007.94 5 0 0 0 0

20 ferin Japan 892925.46 20 905643.30 0 0 0 30 0

21 fetetriste Russian Federation 844276.36 21 855012.66 0 0 0 0 0

22 Pag2 Netherlands 831481.01 22 848020.44 0 0 0 0 0

23 Krymskij_Stas Russian Federation 785076.40 23 789406.68 0 0 0 0 0

24 m_dz Poland 720540.00 24 752569.54 0 0 0 71 0

25 ty70 Japan 635150.69 25 589807.65 0 0 0 397 0

26 zettix United States 488378.15 26 482388.88 0 0 0 0 0

27 omu Japan 93383.55 27 92281.94 0 0 0 0 0

28 daisyo Japan 85323.73 28 85130.28 0 0 0 137 0

29 r2d1 United States 26906.03 29 26175.64 0 0 0 0 0

30 Zodist South Korea 2923.96 30 3080.76 0 0 0 698 658

31 KulikAlex Russian Federation 947.11 31 769.05 0 0 0 1321 0

32 kosakkun Japan 537.77 32 442.49 0 0 0 1308 0

32 kphmd China 537.77 32 442.49 0 0 0 1308 0

32 rezaie United States 537.77 32 442.49 0 0 0 1308 0

35 ga311301 India 0.00 35 0.00 0 0 0 2000 0

35 masakt Japan 0.00 35 0.00 0 0 0 2000 0

35 varinderbansal India 0.00 35 0.00 0 0 0 2000 0

]]>

My solution looks almost the same as nika's.

I split the field into 3x3 - 5x5 sub-rectangles. The number of sub-rectangles should be even, either vertically or horizontally in order to create a hamilton cycle easily.

https://twitter.com/nico_shindannin/status/946492445335830528

I calculated all the chain patterns for each sub-rectangle size beforehand. Then I used simulated annealing. These two were neighbors ,

(1) Randomly picked up a sub-rectangle and chose a different chain.

(2) Randomly picked up a border of sub-rectangles, moved a position where two chains are connected on the border.

Regarding color, if the number of colors was three or four, the color was trivial. You can use any algorithm to assign them. In the case of two colors, they were assigned to the black or white cell of the checkerboard and they must be the same number. I took it into account during simulated annealing.

Once I reached 976232.19, which seemed the optimal score as Milanin and sdya got. However, in my local test, I failed to reach the optimal, 4 out of 300 cases . So, I re-submitted my solution and my rank went down to the 3rd.

> 2*min(c[0], c[2]) + 2*min(c[1], c[3]) + c[4] + c[5] - (c[4]+c[5]) % 2

At first, I thought it was optimal length. However, I guess it would be length 2 shorter than the above length on the following cases ,

- min(c[0], c[2]) = even, min(c[1], c[3]) = even. c[4] = even. c[5] = odd.

- min(c[0], c[2]) = even, min(c[1], c[3]) = even. c[4] = odd. c[5] = even.

- min(c[0], c[2]) = odd, min(c[1], c[3]) = odd. c[4] = even. c[5] = even.

- min(c[0], c[2]) = odd, min(c[1], c[3]) = odd. c[4] = odd. c[5] = odd.

For example, c[0]=1, c[1]=1, c[2]=1, c[3]=1, c[4]=1, c[5]=1,

2*min(c[0], c[2]) + 2*min(c[1], c[3]) + c[4] + c[5] - (c[4]+c[5]) % 2 = 6

However, I can only create a cycle of length 4 at most. I don't know why, so I hope someone will prove it instead. :)

P.S.

I have just posted my solution for TCO 2017 Announcement Fun Round. I am sorry to late.

https://apps.topcoder.com/forums/?module=Thread&threadID=901996&start=0]]>

2*min(c[0], c[2]) + 2*min(c[1], c[3]) + c[4] + c[5] - (c[4]+c[5]) % 2

I was impressed how quickly wleite produced a solution that was very close to this limit and thought the only way to be competitive in this match was to have "perfect" solution.

Maybe there is some nice mathematical construction but I was looking for solutions that would generate a chain of desired length and then try to modify parts of it until we end up using allowed number of tiles for each color/type. We can have scoring function based on how many extra tiles our current solution needs.

Probably the best idea I had there was to split the grid into subrectangles of size 5x5 (or similar) and connect them with a chain. After that you can modify how to traverse each individual subrectangle to improve scoring function. It didn't quite work and I haven't spent enough time to figure out why.]]>

The idea was to start with topmost row, fill a bunch of patterns into it that "look promising". Then, start building the next layers as usual (much like we did in MM94).

The biggest issue was to match current row (the one appended) to the previous one. Some sort of connecting between the tiles in the currently adding row and already placed tiles was needed. It was clear that a garland can have at most 2 open ends that appear in the current (last added) row. Actually all the other garlands are not interesting, because they are either already closed, or cannot be closed.

So the most interesting part was to join some garlands from the previous rows using some tiles from the current row.

Combined with some semi-greediness for the topmost 30-60% of the board, this approach could beat SA, but as usual I do not have a proof :).]]>

I didn't compete, because I couldn't find an effective method for creating loops. Although I did find a decent method for creating long paths. I used simulated annealing with local-level scoring. You get a point if there are two adjacent tiles whose paths match and colours differ. The task is to maximise the total number of points.

Anyway I am very interested in knowing people's approaches. It looks like a few people got almost perfect results, so I suspect that bipartite matching is involved somehow.

P.S. Happy New Year everyone!]]>