Rafbill_pc

#AHC059, seed=0, moves=988 (Initialize with chokudai's solution, postprocess with my solution (which is similar to @wata_orz 's approach)).

I see that @terry_u16 's solution used randomized dfs, maybe this state representation is a way to turn randomized dfs into something suitable for simulated annealing?

The state representation is quite weird: the tree is determined by dfs with a priority stack (when popping an element, choose the one with the highest priority. In case of a tie, choose the one that was added last). The SA transition is to change the priorities of a few cells.

#AHC054 3rd place on the provisional leaderboard. If you do simulated annealing using simulations to estimate the expected score and let it run for several minutes, you can get a good score. But simulating is very slow (O(N^4) and you need multiple simulations per SA step).

The range ((L-2e12)/8, (U+2e12)/8) is used instead of (L/8,U/8), because otherwise elements close to L or U become too hard to create. The elements close to L or U remain harder to create, so it is better to consider them first (when we have 500 values available in A).

We can estimate how close we can get by looking at: log_2(Choose(500,8)) ~= 56 log_2(Choose(108,8)) ~= 38 log_2(4e12) ~= 42

#AHC053 I got the second place! My solution (atcoder.jp/contests/ahc05…) is based on generalized birthday attacks (iacr.org/archive/crypto…). Generalized birthday attacks can be used to find solution to high-density subset sum problems.

I'm typing this on my phone while on a train, apologies if this is hard to understand.

A better strategy is to consider the whole list of vertices, view it as a list of 2d points (pairs of probabilities), and optimize the area of the region bounded by these points.

#AHC051 Here is a short description of my approach, I'll write a more detailed description soon.