wata's blog

ALGO ARTIS Programming Contest 2022（AtCoder Heuristic Contest 010）Announcement
By wata, history, 3 years ago, In English

We will hold ALGO ARTIS Programming Contest 2022（AtCoder Heuristic Contest 010）.

AtCoder Heuristic Contest (AHC) is a new series of programming contests that will be held regularly on AtCoder. Unlike algorithm contests such as ABC/ARC/AGC, the goal is to create a better solution to a problem for which it is difficult to find the optimal solution. We are planning to hold a long-term contest with a duration of more than a week and a short-term contest with a duration of less than a day, alternately about once a month.

AHC uses a new rating system that is different from the existing ABC/ARC/AGC rating system. Unlike the ABC/ARC/AGC ratings, AHC rating does not decrease even if contest performance is poor. Please feel free to participate. You can check the current ranking here: https://atcoder.jp/ranking?contestType=heuristic

We are looking forward to your participation!

  • Vote: I like it
  • +43
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Thanks for the very nice problem.

I reached the second place. Congratulations to the winner takumi152!

The main observation for this problem is instead of maximizing the product of the lengths of the two largest loops, we can maximize the total length of all loops. Indeed, half of the tiles on the grid are tiles with two curved train tracks. When both tracks belong to some loop, rotating such a tile will either merge two loops, or split a large loop into two. Thus it is typically possible to merge all small loops in a solution into a single big loop. Once we have a single big loop, it is usually possible to split it into two loops of roughly equal sizes by rotating a single tile.

See the following images for an example of this process.

Images

I encoded the problem as an instance of maxsat. I used the maxsat solver aspino (link). The 30x30 grid is too large, so I repeatedly run the solver on 10x10 subgrids. Optimally solving a subgrid can be done about 50 times in the 2sec time limit.

The 2sec time limit very limiting, I get much higher scores with a 40sec time limits (from an average of 195k to an average of 210k on the first 100 seeds). After the contest, I noticed that 10x10 subgrid (or rather 10x30 and 30x10 subgrids) can probably be solved much faster using profile DP. This could probably be used to reach an average of 210k or higher within the 2sec time limit.

By the way, are SAT/MaxSat/... solvers allowed in Atcoder heuristic contests? Should they be allowed? For reference they are not allowed in Topcoder marathon matches.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Thank you for posting your interesting approach :)

    Yes, you can use solvers as long as the license allows you to redistribute the source code and run the program on AtCoder.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I now started loving RNG. By using 100% RNG-dependent technique, I got over 3,100. (If you print all 0s, you get 2864)

→ Reply