chokudai's blog

Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 289） Announcement
By chokudai, history, 21 month(s) ago, In English

We will hold Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 289）.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

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

Comments Comments (40)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +41 Vote: I do not like it

Hi, atcoder contests are awesome. Thx you.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +50 Vote: I do not like it

Why is there no Discuss tab on ABC's (linking to the codeforces blog)? even though ARC have them. It makes it harder to find the blogs otherwise.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    I agree with you, but they already share it there. But there is a situation like this: people usually join the atcoder to enter contests. There are no such things as problemsets, tags. That's why competitive programmers study from codeforces. 'here'. And people may forget to check atcoder.jp contest section. So they publish blogs here.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I am not talking about a Discuss section built into atcoder. These blogs get lost after a while when new blogs come up and its hard to find a particular blog. ARC have a link built into the contest linking to the codeforces blog, so one can easily find the blog at a later time. I was asking why a similar thing is not done for ABC.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I debugged D for 15 minutes only to find out that the upper bound on N and M were different :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone tell me if G uses any harder concepts like FFT, etc. Or it can be solve using basic Data Structures and some observations.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It uses something known as Li Chao Tree.
    After some playing with equations, G just boils down to this.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why would Beginner contest have FFT ? you are complicating even though I did not read question. I am guessing it

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 5   Vote: I like it +7 Vote: I do not like it

      yes it does (i meant past contests). atcoder beginner contest is not equivalent to a typical beginner contest. please view past atcoder contests for more reference.

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Usually F or G or Ex used to contain some advanced DSA but they used to be standard.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    it can be solved by basic math and basic STL: 38820861

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can also just use divide and conquer.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for that hint. I solved it using divide and conquer.
      Can you provide a link to your solution using divide and conquer?

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How stupid am I!!!

For problem F I get AC in the last second.

To make debugging easier, I set limit=4 ($$$10^6$$$ in the original problem). And I forget to change it and get WA 3 times. After that, I find limit=4 is wrong and change it to limit=100000, and get another 3WA. Finally I realize that it should be limit=1000000 and get AC in the last minute: https://atcoder.jp/contests/abc289/submissions/38816912

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How lucky you are!

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you solved it?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Even though I didn't solve F during the contest, I solved it afterwards. I solved for x axis and y axis seperetly. When I solved let's say for example for the x axis, I just run simple bfs, and checked if it's possible to reach $$$i^{th}$$$ coordinate in even or odd moves. And at the end I check if it's possible to reach both $$$t_x$$$ and $$$t_y$$$ in even or odd moves, and if the number of moves for some of them is smaller, then I just repeat any move twice to equalise the number of moves.

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Almost the same as https://atcoder.jp/contests/abc289/editorial/5739.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Found out solution of F but failed to AC within the contest time.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

My week: "B is for Brick"

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how to solve E?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    BFS on the pair (Takahashi, Aoki): https://atcoder.jp/contests/abc289/submissions/38804839

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used BFS but I thought it wouldn't be so straightforward. So, I pre-computed all the valid transitions in advance. It turns out to be TLE. Then I moved on to try DFS and couldn't get it to work. I couldn't believe the most straightforward solution is a fast one in this case.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think it is just BFS on the tensor product of graph $$$G$$$, i.e., $$$G \otimes G$$$.

        I could debug your submission if you would like to.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I got AC after moving the logic of looking for the next valid move inside the BFS queue.

          At first, I thought checking for the next valid move inside the BFS queue would be slower than pre-computing all the valid moves in advance.

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah when expanding a node we should always check whether it is valid and it is visited before pushing it into the queue.

            → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

I have different approach for G

Let's say $$$B[1] \geq B[2] \geq ... \geq B[N]$$$ and $$$C[1] \leq C[2] \leq ... \leq C[M]$$$

$$$f(i, j) = (B[i] + C[j]) \cdot j$$$

We can notice that $$$ans[1] \leq ans[2] \leq ... \leq ans[M]$$$

I divided array into two halves, finding optimal $$$i$$$ for middle element, and recursively solved two halves with $$$opt \leq i$$$ and $$$opt \geq i$$$.

I think its complexity can be $$$O(nm)$$$, but it passes in 98 ms.

Can anyone please hack my solution: https://atcoder.jp/contests/abc289/submissions/38809712

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    sum of $$$optr - optl$$$ is $$$O(n)$$$ on each recursion depth, isn't it?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right, so overall complexity is $$$O(nlogm)$$$. Thanks!

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it 
1
10
1
9
10

It can hack this code:https://atcoder.jp/contests/abc289/submissions/38800008.

My friend read the problem by error.This code prints No with this test case.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

Spent way too much time understanding B's statement. It's written badly and the weird formatting doesn't help either.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do C?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Just came here to point people to the beautiful codes A-F of jiangly. Link

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

any1 check the solution for G? for each j, use a ternary search to search the answer, and what we should do is:

find how many $$$i$$$ such that $$$a_i \ge x$$$.

which can be easily done by binary search. Time complexity is $$$O(m \log^2 n)$$$. Is it right?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    try doing what you said and printing out for every i. you'll see that it's not parabolic (it's a function of higher degree), so you can't use binary or ternary search

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain solution of F? I can't find it anywhere.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello, I wonder when the test data will be available on dropbox?

It was so surprising to find abc289 absent on dropbox after sticking on 4 testcases in F for three hours.

→ Reply