wata's blog

AtCoder Heuristic Contest 004 Announcement
By wata, history, 3 years ago, In English

We will hold AtCoder Heuristic Contest 004.

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
  • +15
  • Vote: I do not like it

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

Any suggestions for improving in this kind of contests? Since the solutions of other people are not available for watching it is very hard to practice.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I guess just watch screencasts of people who did it?

    The ideas just come by thinking "How can I improve this?" or "What's going wrong with this solution?". The latter is mostly how my thought process went for this problem, which I'll share here.

    First, make a naive approach. Start with a grid of periods. Sort the words by non-decreasing length. Then just put the words in each row horizontally. So if the words were AA, BB, and CC, you might have AABBCC as the first row. This gets about $$$1.5 \times 10^9$$$ points.

    But some words might already be in the grid by the time we get to them, so adding them again is useless. Checking for this gets about $$$1.8 \times 10^9$$$ points.

    But there might be some places where you can add just one character, which is better than adding the entire word. Checking all possible spots gets $$$1.9 \times 10^9$$$ points.

    However, this seems like it should give a whole lot more. Looking at the output, we can see many open spaces. This is likely because everything was crammed into the top spots, and unable to fit into the bottom spots. So we can randomize the order we try and put the word into. This gets about $$$3.1 \times 10^9$$$ points.

    But now, we might be using the small words and taking up all the space from the bigger words. So if we start with the longer words first (reverse after sorting), then we get about $$$4.1 \times 10^9$$$ points.

    We can try and visit positions that were previously used more. This got $$$0.04 \times 10^9$$$ more points.

    But now remember that we're using randomness. And my solution ran in 35ms, so we can rerun it many times to try and get a better solution. This gets $$$4.7 \times 10^9$$$ points.

    And one last observation: Some words are contained inside others. Note that it's much more common with small $$$L$$$ (look at the input generation section). If we order the words first by the number of other words contained inside it, then by its length, we get $$$5.3 \times 10^9$$$ points. This would put me at 107th from the official standings, although I wasn't able to take the contest.

    My programs are currently in Rust, I'll convert them to C++ soon so that they're easier to understand for the majority of people.

    I'd like to learn about the approaches that other people (who got more points than me) used.

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

      Thanks! Can you also share the link of the videos of the people who made screen casts?

      → Reply