atcoder_official's blog

We will hold UNIQUE VISION Programming Contest 2023 Autumn(AtCoder Beginner Contest 323)
By atcoder_official, history, 14 months ago, In English

We will hold UNIQUE VISION Programming Contest 2023 Autumn(AtCoder Beginner Contest 323).

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

Comments Comments (18)
| Write comment?
»
14 months ago, # |
← Rev. 2   Vote: I like it -45 Vote: I do not like it

Hope to solve problem A, B, C, D.

update in 2023-10-07 20:28 CST: I use just 27 minutes to solve them! What easy problems!

update in 2023-10-07 21:40 CST: Sadly, I almost solved problem F but I didn't, I almost!

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved A-F in 70 minutes but started late ,so no positive delta for me.

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

Standard E + some case pondering in F.

An average participant during ABC323

Also there is no link to the discussion (this blog) on the AtCoder contest page, you might wanna look into that

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G — Inversion of Tree?

→ Reply
»
14 months ago, # |
  Vote: I like it -42 Vote: I do not like it

trash D. I TLE for 4 times.

trash F. I got WA on only one testcase!!!!

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    D isn't trash , don't call a problem trash just because you bricked in it

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      Don't use #define int long long, or you'll get wrong answer on 11 testcases.

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

        not true , you can just stop doubling a size when it crosses 10^9

        → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    ngl, F is hot trash. Why does this problem exist? Just a lot of casework.

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      It's not that bad.

      There are only 8 cases (which octant relative to the goal is the cargo?), most of which are similar to one another.

      If you do some transformations, there is only 1 case.

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

        I can't find Programming in middle of all this math..

        → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      It's all about modeling the task to not feel like hot trash. Honestly you wouldn't have had too many tricky cases if you had modeled it nicely.

      → Reply
    • »
      »
      »
      14 months ago, # ^ |
      ← Rev. 4   Vote: I like it +19 Vote: I do not like it

      It exists because it encourages contestants to figure out elegant ways to approach the problem that do NOT involve a lot of casework. If you were unable to do so, that's an issue with your skill and not on the problem design. The fact that it CAN be solved with heavy casework means weaker solutions can still AC with a higher penalty (coding time), which is an opportunity that is not often granted for problems beyond one's skill level.

      Some tips: you can flip the axes and/or rotate them to reduce the number of possible scenarios, you can use recursion to break the journey into smaller pieces, you can use a min function to compare between multiple options (like whether to move the block horizontally first or vertically first). The only "tricky" case (which should be really apparent to most contestants, so it's not likely to be overlooked) is when you're on the same row/column as the block and want to move to the opposite side, but this can be handled by simply adding 2 to the step count.

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        i didn't ask for an editorial sir, I solved it but didn't enjoy it.

        → Reply
        • »
          »
          »
          »
          »
          14 months ago, # ^ |
          ← Rev. 3   Vote: I like it +5 Vote: I do not like it

          To be fair you could even just compress the search space and use dijkstra on it. The number of "important" coordinates are at most $$$(3\times 3)^2=81$$$, and that immediately leads to a shortest-path problem with $$$81^2=6561$$$ states. It kinda is sad that this solution is longer, though.

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

            Could you please tell me more details about this solution?

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

              For each point given in the input $$$(x_p,y_p)$$$, the "important" lines are $$$x=x_p$$$, $$$x=x_p \pm 1$$$, $$$y=y_p$$$, $$$y=y_p \pm 1$$$. So, there are three points $$$(X_A,Y_A)$$$, $$$(X_B,Y_B)$$$, $$$(X_C,Y_C)$$$, and thus at most $$$9$$$ "important" lines for $$$x$$$ and $$$y$$$. The "important" coordinates are the intersection of "important" lines, and thus there are at most $$$81$$$ of them. Now everything can be compressed into a weighted grid graph with at most $$$81$$$ vertices. It is not hard to prove that the shortest solution using this weighted grid graph is equal to the actual solution of the problem. For convenience, we will call the $$$x=x_p$$$ and $$$y=y_p$$$ lines "very important" lines, and their intersection "very important" vertices.

              Now to the implementation details. Let us call $$$S=(v_t,v_c)$$$ the "state" we are in. $$$v_t$$$ is the vertex with Takahashi, $$$v_c$$$ is the vertex with cargo. On the weighted graph we have at most $$$4$$$ neighbors to any vertex. If the vertex we want to move Takahashi to is not $$$v_c$$$, just move Takahashi to the vertex. Otherwise, move both Takahashi and the cargo "two steps further" to that direction, so the cargo stays in a "very important" vertex.

              The rest is just a tedious implementation of dijkstra. As there are at most $$$81^2=6561$$$ states, it can't take too long.

              → Reply