AtCoder Beginner Contest 246 Announcement

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!

• 15 hours ago, # ^ |

  ← Rev. 3 →  

  -8

  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 00 or 11. So, instead of always pushing to the queue tail as we do in the normal BFS, when encountering an edge with weight 00 we can push it to the queue front. This guarantees that costs are processed in non-decreasing order.

• 15 hours ago, # ^ |

  ← Rev. 5 →  

  0

  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.

• 15 hours ago, # ^ |

  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.

  • 15 hours ago, # ^ |

    thanks got it.

• 15 hours ago, # ^ |

  Note that the largest number whose cube ≤1018≤1018 is 106106. We can iterate on all the 106106 values, assume the current value is aa, then use binary search to get the lowest bb giving answer ≥≥ nn.

  • 15 hours ago, # ^ |

    I was thinking of a similar approach but got TLE

  • 14 hours ago, # ^ |

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

• 15 hours ago, # ^ |

  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?

  • 14 hours ago, # ^ |

    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

• 15 hours ago, # ^ |

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

  • 15 hours ago, # ^ |

    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 \

    • 14 hours ago, # ^ |

      ← Rev. 2 →  

      0

      F. Neat observation. Arigatou gozaimas!

• 15 hours ago, # ^ |

  18o3 Tampere nagaraj41 Try this testcase.

  Input

  Expected Output

  Your Output

  • 14 hours ago, # ^ |

    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 :)

  • 11 hours ago, # ^ |

    does CF stress works for atcoder problems too?

    • 11 hours ago, # ^ |

      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.

  • 3 minutes ago, # ^ |

    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?

• 15 hours ago, # ^ |

  ← Rev. 3 →  

  0

  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 00 or 11. So, instead of always pushing to the queue tail as we do in the normal BFS, when encountering an edge with weight 00 we can push it to the queue front. This guarantees that costs are processed in non-decreasing order.

  • 14 hours ago, # ^ |

    My solution passed with normal BFS (not 01).

    See my post above.

• 13 hours ago, # ^ |

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