atcoder_official's blog

AtCoder Regular Contest 186 Announcement
By atcoder_official, history, 3 weeks ago, In English

We will hold AtCoder Regular Contest 186.

The point values will be 800-900-900-900-1000 900-900-900-900-1000.

Note: This ARC also serves as a qualification round to select the 18 contestants for the Japanese national finals, making it significantly more difficult than a regular ARC. (For reference, the difficulty is close to that of ARC184.)

Due to circumstances, we replaced the tasks and changed the point values. Since there are no easy tasks, the difficulty level of solving one or more tasks has increased. Please be careful. Since the difficulty level is flat, we recommend reading all the tasks and not necessarily solving them in order.

We are looking forward to your participation!

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

»
2 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

to select the 18 contestants for the Japanese national finals,

Just wondering, is this JOI or something else?

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

    You can switch to the Japanese version; it's a contest held by AtCoder.

    This contest is a programming contest organized by AtCoder Inc. The contest consists of two rounds: the qual and the final. The qual round will be held online and is open to anyone with an AtCoder account. The final round will be held at the Shibuya Solasta Conference venue, with participation limited to 18 individuals selected through the designated process. Those wishing to participate in the final are requested to enter their personal information during registration for the qual round. (Translated by ChatGPT)

    → Reply
»
2 weeks ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

the difficulty is close to that of ARC184

I think that contest already had a difficulty of an AGC...

Ok now it's even harder :(

→ Reply
»
2 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

The only difference between ARC184 and this is that I can solve ARC184A, but I can't solve the first problem of this one...

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Upd: I actually solved A! A really nice constructive problem!

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

      A is really great. It's possible to instantly find out how to reformulate it in terms of graphs but the dp on top of that idea is even better.

      → Reply
»
2 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Auto comment: topic has been updated by atcoder_official (previous revision, new revision, compare).

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it +183 Vote: I do not like it

circumstances

→ Reply
»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I found a hack for problem B:

4
0 0 2 1

Shouldn't output 1?

But I got 3 as result.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    My Code
    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As the first point:

    $$$P_4 > P_2, P_4 > P_3$$$

    As the second point:

    $$$P_1 > P_4, P_2 > P_3$$$

    So:

    $$$P_1 > P_4 > P_2 > P_3$$$

    Shouldn't be 1?

    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    It isn't a valid sample. The answer should be 0 in your sample.

    • For $$$i = 2$$$, $$$P_1 > P_2$$$ holds.
    • But for $$$i = 4$$$, we need $$$P_1 < P_4 < P_2$$$.
    → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I found that:zhoukangyang have got the right answer,but std did not.

    → Reply
»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Is there any story behind problem D?

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

The editorial of A says that:

From the definition of similar graphs, the in-degree and out-degree of each vertex in the remaining graph are equal. Conversely, for any graph, if we reverse all edges in a cycle, we get a graph that is similar to the original.

Conversely, strong connectedness is always achievable if both sides have two or more vertices.

However, I failed to construct such components with 2 rows and 3 columns. If we have something like this then the in-degree and out-degree of R1 and R2 will be different and reversing the edges won't give us a similar graph. What did I miss here?

Link to image (not sure why the upload doesn't work)

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I guess you missed R1 -> C3 -> R2 -> C2 -> R1.

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

      Thanks a lot! I missed that the component may contain multiple cycles and we only need to reverse one of them to get a similar graph.

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

      what's this picture

      → Reply