JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Marathon Matches Marathon Match 96: GarlandOfLights Re: Post your approach Revision History (6 edits)
Re: Post your approach (response to post by nika)
Happy New Year!

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
Re: Post your approach (response to post by nika)
Happy New Year!

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 2 length 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.

I hope someone will prove it. :)

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
Re: Post your approach (response to post by nika)
Happy New Year!

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 simlulated annealing. These two are 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.

Once I reached 976232.19, which seemed an 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 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 2 length 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.

I hope someone will prove it. :)

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
Re: Post your approach (response to post by nika)
Happy New Year!

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 simlulated annealing. These two are 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.

Once I reached 976232.19, which seemed an 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 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 2 length shorter than the above length in some cases. The cases are as follows,
- 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.

I hope someone will prove it. :)

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
Re: Post your approach (response to post by nika)
Happy New Year!

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 simlulated annealing. These two are 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.

Once I reached 976232.19, which seemed an optimal score as Milanin and sdya got. However, in my local test, I failed to reach the optimal, 4 out of 300 . So, I re-submitted my solution and my rank went down to 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 2 length shorter than the above length in some cases. The cases are as follows,
- 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.

I hope someone will prove it. :)

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
Re: Post your approach (response to post by nika)
Happy New Year!

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 simlulated annealing. These two are 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 which connecting between two chains on the border.

Once I reached 976232.19, which seemed an optimal score as Milanin and sdya got. However, in my local test, I failed to reach the optimal, 4 out of 300 . So, I re-submitted my solution and my rank went down to 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 2 length shorter than the above length in some cases. The cases are as follows,
- 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.

I hope someone will prove it. :)

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
Re: Post your approach (response to post by nika)
Happy New Year!

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 simlulated annealing. These two are 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 which connecting between two chains on the border.

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

> 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 2 length shorter than the above length in some cases. The cases are as follows,
- 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.

I hope someone will prove it. :)

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