We will hold TOYOTA MOTOR CORPORATION Programming Contest 2022 (AtCoder Heuristic Contest 015).
- Contest URL: https://atcoder.jp/contests/ahc015
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20221030T1500&p1=248
- Duration: 4 hours
- Writer: chokudai
- Rated range: All (Heuristic Rating)
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!
In my opinion, these are the most enjoyable contests and it's great that AtCoder hosts them. Starts in 6 hours, looking forward to everyone's participation :-)
I bet someone took the time to discover the score of all $$$_4 \text{P} _3$$$ ordered combinations of $$$\text{FBLR}$$$ (basically each combination should get you an expected score of ~46 mil)
The most simplistic implementation (which can correctly simulate the whole process and accurately calculate the score) can try all 4 possible tilt directions at each step and make a greedy choice between them even ignoring the type of the next candy. This already scores 69M points: https://atcoder.jp/contests/ahc015/submissions/36091818
Additionally trying all possible placements of the next candy after each tilt (basically look one step ahead) can further improve the score to 117M: https://atcoder.jp/contests/ahc015/submissions/36099248 (in practice mode).
Not sure why, but instead of just submitting the solution that would score me 117M points, I made it worse by additionally trying random placements of the remaining candies in the box before calculating the score. And this resulted in only 108M points (rank 268 out of 778) as my best in-contest submission: https://atcoder.jp/contests/ahc015/submissions/36098082
The time limit most likely allows looking two steps ahead. I wonder if the winning solutions did just that or tried something smarter?
Funnily enough, $$$\text{LLLLLLLL...LLLLLL}$$$ (100 $$$\text{L}$$$'s) scores more than 20m score, and a lot of people seem to have done that.
Always tilting the box to the left is a valid solution too and it would indeed win the "most simplistic implementation" award. Thanks for correcting me.