wata's blog

Kyocera Programming Contest (AtCoder Heuristic Contest 006) Announcement
By wata, history, 2 years ago, In English

We will hold Kyocera Programming Contest (AtCoder Heuristic Contest 006).

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.

We are looking forward to your participation!

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

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I participated in AHC for the first time and it was a really fun contest. Starting with a really dumb first solution to test the waters and then doing incremental improvements turned out to be much more interesting than expected!

Unsurprisingly, there's no official editorial. But it would be interesting if people with more than 2M+ score could explain their approach. Or are we expected to just read the source code of the top score submissions?

A short description of my solution (1,459,751 score and rank 189 out of 522 participants):

  • sorted the routes, based on their proximity to the map center (square of the distance to the restaurant plus square of the distance to the delivery location).
  • discarded the routes that are too far from the map center (the number of discarded routes was a tunable parameter, which varied between 950 and ~500).
  • considering the remaining routes and the current location, always went either to the nearest restaurant (until 50 of them had been visited) or to the nearest valid delivery location: https://i.imgur.com/4orUHXA.gif

Considering two or more steps ahead rather than just one when minimizing the travel distance was the next thing that I wanted to try, but the contest ended before I could implement it. Well, that's probably the reason why long AHC contests exist too.

→ Reply