chokudai's blog

AtCoder Beginner Contest 265 Announcement
By chokudai, history, 20 months ago, In English

We will hold AtCoder Beginner Contest 265.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

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

Comments Comments (27)
| Write comment?
»
20 months ago, # |
← Rev. 4   Vote: I like it +6 Vote: I do not like it

Great Contest! enjoyed it... Finally I can now become Cyan on atcoder as well :P

UPD: Became Cyan (1200+) :P

Now I can participate in AGCs as well.

→ Reply
»
20 months ago, # |
  Vote: I like it +25 Vote: I do not like it

pls name tasks next time like DP1, DP2, and so on

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

    Agree. XD

    Btw can you tell me how to solve F if you solved?

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

      DP[i][d1][d2] = count of prefixes with d1 <= D and d2 <= D

      you can go from DP[i][d1][d2] to DP[i+1][d1 + |x — pi][d2 + |x — qi|]

      last part is prefix sums for fast transform

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

        Since time limit is 6 second it actually works also without any prefix sums.

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

          hmm, I added it because of tle with $$$O(n D^2 \times 1000)$$$

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

          Your code fails after_contest tests

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

            Yes, I saw that. Guess it my lucky day ;)

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

Did any other person get $$$20$$$ AC and $$$1$$$ TLE in $$$G$$$?

→ Reply
»
20 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Nice contest again, thanks.

But text of B was not optimal. The "time limit" is actually not a time limit, but the remaining time. Usually if we need x time units to do a step, and remaining time is x, then it is ok to do the step. But here it was not, we needed timelimit=x+1. I needed 4 submission to understand.

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

New to atcoder, Apologies if its previously answered. Is there anyway we can see the testcase on which our code is failing?

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

We realized tests of F are weak. (The code that generated tests contained a bug.) We added some tests like 99_after_contest_01.txt.

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

Let’s get back to the original problem. This case, the possible values of (x,y) is relatively small, so we can solve it in a total of $$$O(N^3(logN+logM))$$$ time by storing the DP table in a dictionary. If you use a fast language, your code will be accepted.

Can someone explain why the possible values of (x, y) are relatively small in problem E??

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

    While contest I assumed, since in each step we can make one of three choices, we can reach up to $$$3^n$$$ points.

    But that is misleading, since there are only 3 kinds of steps, and order of the single steps does not matter, it is less than $$$n^3$$$ different points possible.

    They can be described by dp[x][y][z] where $$$x+y+z\leq n$$$

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

      But that is misleading, since there are only 3 kinds of steps, and order of the single steps does not matter, it is less than $$$n^3$$$ different points possible.

      Can you explain this statement again? Thanks in advance.

      → Reply
»
20 months ago, # |
  Vote: I like it +21 Vote: I do not like it

I think it was my first time solving G in the new ABC format, really happy about that, no longer stuck between 1600 and 1700. and interesting problems overall.

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

There is an error in the problem statement for Ex (No-capture Lance Game)

It says "The first player can move the piece at (1,7) to (1,4), (1,5), or (1,6); the second player can move the piece at (3,4) to (3,1), (3,2), or (3,3). The first player cannot move the piece at (2,1).", but the piece at $$$(3,4)$$$ belongs to the first player.

→ Reply
»
20 months ago, # |
  Vote: I like it +76 Vote: I do not like it

Just realized (from Twitter) that sample input 3 of ABC 265 question C was not some random inputs. It is an ASCII art:

Move your head further away to see the ASCII art.

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

    I hadn't noticed it at that time but I noticed it now. ABC 265 is hidden under the test case. Hats off to the author/tester for the test case.

    → Reply
»
20 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Does anyone have idea about ? Seems to be O(n^2D)

→ Reply