chokudai's blog

AtCoder Beginner Contest 246 Announcement
By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 246.

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

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

Comments Comments (43)
| Write comment?
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

as always looking forward to participate

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it -8 Vote: I do not like it

    Using Dijkstra with adjacency between each cell and the four next to its corners. Note that the cost does not increase when you make 2 moves using the same position change, e.g., up right. So the last position change needs to be maintained as well in the set / priority queue.

    EDIT: 01-BFS works as well because edge weights can be only $$$0$$$ or $$$1$$$. So, instead of always pushing to the queue tail as we do in the normal BFS, when encountering an edge with weight $$$0$$$ we can push it to the queue front. This guarantees that costs are processed in non-decreasing order.

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

    https://codeforces.net/problemset/problem/877/D similar problem.

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

    You can use normal BFS too (not just 01-BFS).

    Keep a 'seen' dictionary/map (seen[pos] = c where c is the min cost of getting to pos from (ax,ay) (the cost of the first time you get there since it's BFS)). Then for each pos loop on each diagonal adding (x,y,c+1) to the queue/deque (and to 'seen') until you reach a pos either outside the board or with a pawn OR in 'seen' with seen[pos]<c+1 (in order words you can reach that pos earlier from somewhere else so on the next move you'll have access to the rest of the diag).

    I haven't proven the complexity but it passed.

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

Problem C: Why priority queue got AC but the sorted array got WA on 6 test cases? Any suggestions

Update: Fixed Sorted Array. Got AC

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

    Hi! You seem to terminate your loop when m == 0, but doing so you won't add a[i] (when you have 0 coupon left, you still need to pay for the item :) ) to your sum value.

    → Reply
»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

The definition of bad luck:

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

Can anyone provide a more detailed explanation for D? The editorial feels incomplete. Edit — Understood the approach. Thanks mohamedeltair

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

    Note that the largest number whose cube $$$\le 10^{18}$$$ is $$$10^{6}$$$. We can iterate on all the $$$10^{6}$$$ values, assume the current value is $$$a$$$, then use binary search to get the lowest $$$b$$$ giving answer $$$\ge$$$ $$$n$$$.

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

      The editorial uses the same general idea but with 2 pointers instead of binary search. Suppose for specific $$$i$$$ we got the lowest $$$j$$$ such that $$$(i, j)$$$ gives solution $$$\ge$$$ $$$n$$$. For $$$i+1$$$, the other value for sure is $$$\le j$$$. So we can keep decrementing $$$j$$$ until we get the lowest one giving a valid solution. And so on.

      → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone give an example of a test case where bfs would fail in problem E. My bfs implementation fails on 8 test cases but I am unable to find a case where it fails

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

    I use this method as well, and get WA, but don't know why.

    The main idea is that we stop as soon as we meet a block or a cell which has beem visited or it is outside of board.

    Still have no idea why this is not correct. Can anybody tell why and provide some counter example?

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

      we stop as soon as we meet a block right

      or a cell which has beem visited wrong

      or it is outside of board right

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

    same approach. came here to post the same comment to get an answer. Can someone please answer?

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

      don't stop when a cell has been visited

      because it may be visited when the diagonal looks like / instead of \ when we bfs \ lines

      instead stop when bfs / and visited / also when bfs \ and visited \

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

    18o3 SummerSky nagaraj41 Try this testcase.

    Input
    Expected Output
    Your Output
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice counter example! Thank you so much for your kind help!

      Now I have realized that it is not correct to stop as soon as we meet a node which has been visited before.

      Such an unblievable problem! I have learned a lesson that, when we use bfs, it is much better and safe to move only one step forward, rather than several steps at one time :)

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

      does CF stress works for atcoder problems too?

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

        Lol, It'd be kinda ironic if it did. (The name's literally CF Stress).

        But I do have some workaround on my local server to support Atcoder problems, not really sure if I'll officially support Atcoder in future. (As they already provide the testcases on Dropbox, so my website would be redundant).

        If you're interested in Problem E of today's contest, let me know, I can run your submission on my local server.

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

      Come here for saying thanks again, after I finally get accepted.

      But now, I feel quite confused :(

      For instance, given a board and each time we could move one step up/down/left/right, and we are asked to find the minimum steps after which we could reach [tx,ty], starting from [sx, sy]. I think this is a classic problem, and when we use bfs, we could stop as soon as we meet a node that has been visited before.

      But why, this is not correct in this problem? What is the essential reason behind this, and what is the essential difference between these two problems?

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

        Read the comment above. this scenario does not occur in a one-step bfs. that's the only difference.

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

        There is nothing special about this problems. BFS will 100% work, regardless of whether you are using a single step process, or traversing the entire level in one go. You just need to remember one philosophy of BFS, Every unvisited adjacent vertex must be added to the queue with a level difference of 1. (From your implementation, I can say that you've missed out on the every+adjacent keyword, let's see why do they matter).

        You are correct in assuming that whenever you see problems containing a grid with moves, BFS is applicable. However, remember that BFS was originally intended to be applied on an unweighted graph.

        How does our graph look like in this case? There are $$$n^2$$$ vertices, and there are some edges between them. Note that we need to add all the direct edges from the matrix in this graph.

        The resulting graph for the counter example I provided above

        Note that while performing BFS, on Level 2, you forgot about two adjacent edges that existed in the original graph and on Level 3, you forgot about one adjacent edge from the original graph. (I've marked them with Forgot keyword). Since you ran your BFS on a wrong graph, you got an incorrect answer.

        Try to run your algorithm on the graph I shared, it should produce the correct result.

        In conclusion, for matrix based problems, always visualize what the hidden graph looks like (by adding ALL direct edges) and then, all usual graph algorithms would work on it.

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

          oh my god!!!!

          I thought that I have truly understood everything about bfs, but I was wrong :(

          I really benefit a lot from your words "every unvisited adjacent vertex must be added to the queue with a level of difference 1", and get a better understanding from the Forgot word in your graph.

          It seems that this is not your main account, but anyway, thank you so much for your paticient help, precise and clear arguments, and detailed examples. I believe that you are not only a great coder, but also a great teacher :)

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

    BFS is not correct because moving one cell sometimes will increase the cost by 1 (when position change has changed, e.g., up right then up left) and sometimes will not increase the cost (when position change has not changed, e.g., up right then up right).

    So, it may happen that for the same cell it has been put in the queue earlier using the cost change 1 and then we encounter it again but with cost change 0, where it should be put and processed before the earlier one.

    EDIT: 01-BFS works as well because edge weights can be only $$$0$$$ or $$$1$$$. So, instead of always pushing to the queue tail as we do in the normal BFS, when encountering an edge with weight $$$0$$$ we can push it to the queue front. This guarantees that costs are processed in non-decreasing order.

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

      My solution passed with normal BFS (not 01).

      See my post above.

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

You can check my video editorials of D and F if you want. I will upload E in a while

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Binary search + Brute force was an obvious approach for D wonder why editorial didn't include it

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

    Same way passed in the contest. I added the editoral, click here.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why My BFS got WA (problem E)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know how to solve G? I try to read the editorial but got lost in the DP on tree part and wonder why that works

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

    I solved it the same way as editorial but don't really understand why it works... I was just using intuition

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

Can anyone please point out what is wrong with my approach in Problem E? I have implemented a 0-1 bfs solution Submission

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Input
    Expected Output
    Your Output
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what about this submission?

      Spoiler
      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc246/submissions/30780042 im getting wa for 10 cases out of 60 -_- . help , what im missing ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Input
    Expected Output
    Your Output
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot . You are great at finding bugs :)

      → Reply