Блог пользователя chokudai

Автор chokudai, история, 3 года назад, По-английски

We will hold AtCoder Beginner Contest 203(Sponsored by Panasonic).

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

We are looking forward to your participation!

  • Проголосовать: нравится
  • +43
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Oops...It's Clashing with May Starters on Codechef!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

Why is spacing of parentheses so weird on AtCoder?

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Somebody want to show how the dp works in D?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    I used binary search on the median.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      can you elaborate i was also doing same but did not got AC.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        I have elaborated the approach over here — https://codeforces.com/blog/entry/91245?#comment-797573

        I hope this helps, do let me know if anything is not clear.

        Here is the implementation of the same — Code

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Can you share your code?

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          can you please explain C

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            Sort the pairs $$$(A_i, B_i)$$$ according to $$$A_i$$$

            Start iterating through them, when you are on $$$A_i$$$, add $$$B_i$$$ to your $$$currentYen$$$, then check whether you can reach $$$A_{i + 1}$$$ using the yen you currently have or not, if not, break the loop, otherwise keep iterating.

            You can check the code for better understanding — Code

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Question — this only showed up as question D in a beginner's contest. which suggests probably E and F were even harder (I did not get to them yet). Question D seems quite hard already — is it representative of the level required at the beginner's contests? Is this question pretty standard / repetitive or are you expected to come up with the binary search approach when you see this for the first time?..

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            I have already seen questions where binary search is applied like this, that's why I was able to come up with the approach. While this technique is not very common, but you see questions based on this every once in a while. Honestly, I wouldn't be able to come up with this approach if I was seeing a question like this for the first time. Regarding E and F being difficult, in my personal opinion, I found E easier than D. Usually D is easier than this in ABCs

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

        For some $$$x$$$ check that if the answer is $$$\leq x$$$.

        Mark all the elements with value $$$\leq x$$$ to $$$1$$$, otherwise $$$0$$$.

        Let $$$t = \lceil \frac{k \times k}{2} \rceil - 1 $$$.

        Now if there exists some $$$k \times k$$$ square with sum $$$\geq t$$$ then Yes otherwise No.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      I thougt about if I can somehow use binary search... but actually have no clue how to do it in that problem.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        It was a kinda weird binary search, but what I did is I used prefix sums to query the sum in the square range, and the grid that I did prefix sum on was $$$1$$$ if a[i][j] <= check else $$$0$$$. If the sum in that square range is >= (k*k+1)/2, then it's a possible median. Otherwise it isn't.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

    Binary Search the answer. At each step of binary search make a binary array with 1 if $$$a[i][j]<=mid$$$ or else zero. If one of the all possible $$$k*k$$$ squares exceeds $$$(k*k)/2$$$, it means that a median <= mid is possible. You can check sum of each square using prefix sum

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    binary search for median.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    I used binary search to find the answer.

    Let $$$mid$$$ be the chosen value, I will modify my array, where any $$$a[i][j] > mid$$$ will be $$$1$$$ in and all others will be $$$0$$$, after that just check whether the sum of any $$$K*K$$$ block is less than $$$(K * K) / 2 + 1$$$, if it is, $$$mid$$$ can be a possible answer.

    To find the sum of a $$$K * K$$$ square, you can use prefix sums.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Only prefix sum, I needed kind of dp. How did you do that?
      https://atcoder.jp/contests/abc203/submissions/23059605

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you briefly explain why that is working ?

      if (val < medianValue) {
               retValue = true;
             }
      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        For a particular mid let's say mid1, if any block has a sum less than the medianValue, that means, if all the numbers which are currently assigned as 0, were equal to mid1, then mid1 would've been the median.

        We don’t know for sure whether this was the case or not, so we are considering mid1 to be a candidate for the answer.

        Now, when we consider a smaller value for mid, let's say mid2, if for the same block, even mid2 returns a sum less than the medianValue, then we can say that our assumption was wrong and instead of mid1, mid2 is the next possible candidate for the answer.

        This is also in accordance with the question which wants us to find the lowest median value.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      This is Awesome dude!

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Binary search + 2D prefix sum

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

We can solve E by maintaining a set of all possible column positions of the white pawn, then iterate the black pawns sorted by row.

Foreach black pawn, we can move to the column of the black pawn if the col of it +-1 is in the current list of columns, and we need to remove the column from our list if both of the +-1 columns are not in the list.

We need to take care that there can be multiple black pawns in one row, we need to consider them "all at once".

submission

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Damn, that is exactly what I did. I wonder what went wrong Submission

    Edit: Thanks guys, I realised I should've erased after going through all elements in a particular x coordinate :(

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      You are erasing from s while iterating over c, which can lead to erasing of an element that might be helpful for some future element in c.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Consider two black pawns next to each other, and the col of the left one in the current list.

      You remove the left position, then cannot consider that it can be moved to the right position.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      From a quick glance, I think about a case where we have 2 black pawns ( 1, N ) and ( 1, N.+ 1). Currently, we remove ( N ) from the relevant list before ( 1, N + 1 ) is processed

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Before, I saw your code, I thought it would be quite implementation heavy. Thanks for the brillaint short code!

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Got it thanks

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The rules of moving the white pawn are like in the chess game. A black pawn is not like a rock, it is a pawn that can be captured. The rule says that this is possible if going diagonal, like from 0,2 to 1,1.

      In the case we want to go from 0,1 to 1,1, a black pawn acts like an obstacle.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you please help me out. I am not able to find my mistake. code Thanks!

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          "...we need to consider them "all at once".

          Cosider two black pawn next to each other in one row. That does not work in your code.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

How to do F?

I tried dp[i][j]: max elements takahashi can take from first i smallest elements in j steps, not sure what went wrong.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Max Number of moves is less than $$$30$$$. We can make the number of moves as one of the dimensions of dp and calculate the minimum possible removals required for a fixed number of moves.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

UPD: Fixed, it was a problem with the Comfortable Atcoder extension, I removed it and then everything worked like normal.

Not sure if this is a bug or something on my end, but whenever I open a page on Atcoder (except for a few exceptions), it open it in Japanese and I have to change it every time. I checked my settings and I have "USA" selected, so I'm not sure if I have to change anything else.

I looked at the link differences, and there's a ?lang=en at the end when a page is in English.

Maybe there could be a setting, like "Preferred language"?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The language preference seems to be stored in a Cookie (namely language cookie), so there may be a issue with the Cookie settings.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Did someone solve D by maintaining a set/multiset for each square and finding kth largest for each query using pbds or something?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I tried to do bfs in E, from any pawn to any other reachable pawn. This costed me heavy implementation and of-course, 2 minutes passed after the contest sadly.
https://atcoder.jp/contests/abc203/submissions/23074189
Edit: I accidentally copied another submission lol

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody explain the last test case of problem F Weed

3rd test case
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Aoki can choose Weeds 137, 133, 28 and 27. Then Takahashi will take 60, 56, 56, 55, 55 in one go. So the answer will be 1 4.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In prob C, I call vis the current village Taro is standing in, k is the amount of money he has, why is the furthest village he can go to is vis+=k but not k+= vis ?

I got AC with vis+=k in submission:

but WA with k+=vis in submission:

in both cases, all examples tests are passed.

Please give me a clue, thank you.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is there a way to see test cases for this contest (atcoder beginner 203)?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

When will the editorial be publish ?
The Editorial page is still blank.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can we do problem D using a sliding window? I tried using ordered_set but got TLE.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well, did you take care of the fact that ordered_sets only keeps the unique elements in ascending order? And if you did, could you share me a link to your submission? I found a link on GfG that takes care of that using Fenwick tree but turned out it was an incorrect implementation!

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      To break ties you can compare indices, those are always unique

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can also use ordered multiset , I did that Time complexity was O(N^2 Log(N^2)) Not sure on complexity though .

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        Actually to be precise N = (n — k) from the problem. n x n grid and fitting k x k squares in we have (n — k) * (n — k) possible placements.

        And I think O(N^2 Log(N^2)) does not factor the transition cost. We're doing a rolling median across N^2 possible squares with transition cost N each time so an extra N factor and we get O(N^3 Log(N^2)).

        So worst case we have about 400 ^ 3 * (log 400^2) = 1280000000 ~ 1.3e9 operations. I think this takes about 10 seconds in a fast language