maroonrk's blog

By maroonrk, 20 months ago, In English

First of all, I have to say sorry for the vacancy of AGCs.

I'm confident in the style of AtCoder problems, but I have to admit that I was too strict; when I found a problem that was interesting but had a tiny flaw, I didn't try to use it in AGCs. In fact, I received several messages that some ARC problems are good enough for AGCs. If people who are stronger than me say that, what is my severe threshold for? Therefore, I'll be looser in selecting problems. It isn't such a big change that ARC becomes AGC. However, with the new policy, I could have made a few more AGCs in the first half of this year.

Now let's get down to the main subject: Call for Tasks. There were a few non-Japanese AGC writers, but the procedure of contest proposals was obscured. I want to make it public here. Please follow the following steps:

  • Come up with tasks for AGCs. It is desirable that you have ideas for a whole AGC set, but it's OK to have only hard problems.
  • DM me, and show me that you can possibly write AGCs. For example, I'll be convinced if
    • You are (ex-)LGM.
    • Your past problems are nice to me. (Tell me your masterpiece!)
    • Or you have some achievements like GCJWF, IOI/IMO gold, etc.
  • I'll grant you access to the problem submission interface of AtCoder. Please submit tasks there!


Q. What kind of problems are welcome/unwanted.
A. I'd love to have ad-hoc problems. I don't like implementation-heavy or knowledge-oriented problems. Data structures are OK as long as implementation<<<thinking.

Q. How much rejection rate should I expect?
A. It highly depends on how your "taste" is similar to mine. For some, I don't often reject proposals, while for others I keep complaining. Please check past AGC problems to see where you stand on.

Q. Why not allow ARC submissions?
A. Currently I check ARC/AGC proposals alone, so I'll be too busy to check additional ARC submissions.

Q. What happens when a problem gets rejected?
A. You are free to use it elsewhere. You may also write an ARC if you want.

Q. What's the fee?
A. 400000 JPY (subtracted by the tax) for one AGC. We can also pay for testers.

Hope to see your submissions and more AGCs!

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

| Write comment?
19 months ago, # |
  Vote: I like it +79 Vote: I do not like it

What kind of tiny flaws did you notice in recent ARC problems that made them "not good for AGC"?

  • »
    19 months ago, # ^ |
      Vote: I like it +82 Vote: I do not like it

    Just to name a few:

    • ARC136E: I had a vague feeling that I could possibly have seen the same technique. It seemed like I was worrying too much.

    • ARC141F: It was hard to implement. I considered lowering the constraint but threw away the idea because it would allow suboptimal solutions like $$$O(L\sqrt{L})$$$ where $$$L=\sum S_i$$$, which we didn't want to pass. However, it seems the problem is still hard and interesting enough even when $$$O(L^2)$$$ is allowed.

    • ARC142E: I was too scared of heuristic solutions. In fact, some heuristic solutions once passed during preparation. However, after some hard work, the final tests were strong enough.

    • »
      19 months ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      From someone who spent a lot of the contest trying to get AC on ARC142E with a heuristic but couldn't, you did a good job with tests!

    • »
      19 months ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      That sounded like an interesting challenge, so I spent some time (definitely more than I'd spend on a normal solution) and got AC on ARC142E with some heuristic solution.

      In case somebody is interested, it works as follows. We try to guess some permutation $$$rank$$$ such that for an edge $$$(i, j)$$$ if $$$rank[i] < rank[j]$$$ our solution will have $$$strength[i] > strength[j]$$$. If we know $$$rank$$$, it is easy to compute best possible $$$strength$$$.

      To find the best $$$rank$$$ we start just from random permutation and then do local optimizations. Every time we choose a random element, and find the best possible rank for it. There are some optimizations to find the best rank for one element in $$$O(n)$$$. When no change increases the answer, we start again from a random permutation and do this until TL.

      This solution passes almost all tests (maybe except one depending on rand seed). The last optimization was to start not from a completely random permutation, but from something depending on initial $$$a$$$ and $$$b$$$.

19 months ago, # |
  Vote: I like it +134 Vote: I do not like it

I enjoyed all recent ARCs, and I didn't find them easy at all. I don't care how they are called, and whether they are rated. If AGCs are rare but extra special, all the more exciting.

19 months ago, # |
  Vote: I like it +128 Vote: I do not like it

What's the reason for ARC to be unrated for 2800+ then? It seems like problem quality and lack of flaws is the distinction between ARCs and AGCs as opposed to problem difficulty (some problem is considered too "hard to implement" for AGC?), but the reason to have a rating boundary would be because of difficulty, as CF does it.

For me personally, I found it hard to give up sleep for a contest that's unrated and doesn't count for Race Ranking (if that even exists). I do agree with Endagorion's comment in theory; however it's not so much the fact that it affects ratings, but ARCs just generally see less participation from high rated users, and saying that a contest is unrated for some users is like telling them not to participate.

  • »
    19 months ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    Both the quality and hardness of the problem are the distinguishing factors between ARCs and AGCs.

    Making a contest rated brings some pressure on participants to compete in the contest. Therefore, when I strongly hope 2800+ people solve problems, I'll declare the contest as rated.

    Of course, I don't think ARC problems are bad. They are good enough for -2800 people, but they can be too easy or typical for very strong participants. I know some recent ARC problems are not easy or typical even for legends like you. And that's the issue I'm going to address.