FastestFinger's blog

Editorial — Codeforces Round #648
By FastestFinger, history, 4 years ago, In English

1365A - Игра с таблицей

Tutorial
Code

This problem was prepared by Ashishgup

1365B - Проблематичная сортировка

Tutorial
Code

This problem was prepared by Ashishgup

1365C - Соответствия поворотом

Tutorial
Code

This problem was prepared by Ashishgup and ridbit10

1365D - Решить лабиринт

Tutorial
Code

This problem was prepared by Vivek1998299

1365E - Максимальное значение подпоследовательности

Tutorial
Code

This problem was prepared by Ashishgup and ridbit10

1365F - Снова обмены

Tutorial
Code

This problem was prepared by FastestFinger, Ashishgup and Vivek1998299

1365G - Надежный пароль

Tutorial
Code

This problem was prepared by FastestFinger

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

Comments Comments (321)
| Write comment?
»
4 years ago, # |
← Rev. 4   Vote: I like it -36 Vote: I do not like it

..

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

    I don't know what is the point of making A is the hardest problem !

    UPD: after reading the editorial , problem A is easy but I understood it wrong

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

      I think A is simple, I misunderstood the statement, and I thought cells that share sides, and it was cell that share columns or rows (I assumed something that was not in the statement and that is my fault)

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -23 Vote: I do not like it

        Yeah,me too.And during the contest I felt stupid enough to come up with an approach for D and not A

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

        Can anyone solve this if we consider this variant of problem?

        It seems to be quite interesting one.

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

          deleted.

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

          I calculated a few Grundy numbers for small cases. Maybe someone can see some pattern in them.

          Table of Grundy numbers
          Code
          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        I did the same mistake, misread the statement

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

        I also assumed the same , and could not solve the problem A due to that .

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

        me too

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

      I too solved B, C and D and wasn't able to solve A :(

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

      It wasn't that hard, you just had to determine the number of totally unassigned rows and columns. Take the minimum of them. Ans by checking the number even of odd.

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

      yeah, I thought that the question was talking about boundary of claimed cells

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

      same here buddy

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    Video Tutorial of A,B,C,D,E

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

Wow, that was fast.

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

Good round! Thanks for fast editorial

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

Amazing contest! Had fun solving the problems ^_^

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

FastestFinger fastest editorial <3

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

It says tutorial is not available. Anyone else having same problem ?

UPD : It's working now

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

Hardest A ever seen.

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

Had 15min left for round so didn't try E and now I see this

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

    Ah!! I thought I am the only one who missed E thinking won't be able to solve and code it in 15 min.

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

    i had 28 mins :( as i have never solved E in contest i just went to sleep

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

    Can't believe an O(n^3) solution with n = 500 gets AC with Python. Just didn't attempt thinking it'll get a TLE.

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

      Yeah, it's nearly on edge, it took 1591ms !

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

.

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

    i am no better than you. but we all have bad days and also good days. just don't give up!

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

    It's fine. I also couldn't solve A,B,C during contest time. Be happy that, in this editorial you can learn something new more than those contest where you could solve more problems.

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

    And hence as a result, always stay beginners.

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

I feel so stupid after reading the editorial for problem B

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

those were some really interesting problems tbh rather than pure bash it's observation only (except D but that was fun too)

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

For C, isn't the time complexity still O(n) if you use a HashMap?

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

    Since we only need to consider shifts by 0,...,n-1, I think we should even be able to use an array/vector for the counting (but I used std::map in my solution during the contest).

    Edit: Yep, works (82880486). But doesn't seem to help much, only makes it run in 514ms instead of 608ms.

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

      Here is my solution using map and array, It made a huge difference in my case.

      Using Map (514 ms)

      Using Array (139 ms)

      P.S :- I submitted both accepted solutions during the contest so my previous solution (using map) got skipped

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

        Well your improvement is a lot larger because you had used maps for inverting the permutations as well (mp1 and mp2), whereas I only used one to count the differences. Also, I just did some tests, and it seems like my array-solution was so much slower than yours just because of the missing "ios_base::sync_with_stdio(false);" — guess that's not so useless after all xD

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

    Map works for O(logn) It is optimized binary search tree

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

      But HashMap (unordered_map in C++) has O(1) time complexity for adding and removing (with a high constant factor though)

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

i tried bubble sort in B when condition satissfies that is when A(i) >A(J) AND B(i)!=B(j) then swap it.And at last checked if its sorted or not? why its giving WA

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

    4 3 2 1 ``

    1 1 1 0

    `` try bubble sort on this

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

      thank you got it

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

        no problem :)

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

          Hey giorgtarkha, Can you please help debug my code? I think you will get the logic when you read the code. 82855417

          Thanks in advance :)

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

            imagine

            `` 5 7 4

            1 0 0 ``

            with your logic there will never be a swap, your logic implies that only neighbors can be swapped, but in the problem if two indexes have different b, you can swap them, so your solution won't check the case when you can swap 5 with 4, swapping b would work if you had swapped 5 with 4, then the state would become

            `` 4 7 5

            0 0 1 ``

            and then you would've swapped 7 with 5, but I think that kind of solution would be n^3 or maybe n^2 if optimized with some algorithm not sure

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

    because that doesn’t work. Check this input: 4

    1 3 5 4

    0 1 1 1

    Your solution will result in No. But it can be sorted

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

      can you explain this example , How it can be sorted?

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

        Sure. First swap 4 with 1 Then it will look like this 4 3 5 1 Then 1 with 5 4 3 1 5 Then 4 with 1 1 3 4 5

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

    Because you can't be sure that in single bubble sort you get the answer. I mean it is possible that when you are applying bubble sort and then checking whether the array is sorted or not and it gives not sorted, then also it is possible that if you apply bubble sort again by the method which you specified, it becomes sorted So exactly dont know how many times you have to apply bubble sort. That,s why you require some other approach for solving this

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

For wrong answer on E, try this -> 2 12 6 . I got it after the contest :(

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

    Can you please find out the error in my code : https://codeforces.net/contest/1365/submission/82866772 I tried greedily since picking the max set bit would always be useful. I set k to the cnt of numbers having the max bit set. Now I went through all bit positions and checked if there cnt was more than max(1,k-2). If yes I added (1<<i) to my ans.

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

I thought we could only switch adjacent numbers in B..

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

    wasted my 1 try thinking this.then read the statement carefully xD

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

Damn I feel so stupid after seeing E's solution

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

What is __builtin_popcount?

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

    This gives total number of set bit in binary representation of number

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

Nice contest! Didn't quite get understand the proof for E while doing the contest, but proof by example and proof by AC is good enough for me :)

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

    Can you explain the proof you got?

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

      Proof by example means I just came up with examples I solved manually. This is not a rigorous way to prove things.

      Proof by AC means I coded a solution I think might work and tried to see if CodeForces would accept it. This is actually not a real way to test if your code works.

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

Where are the memes

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

Thanks for nice problems. Though I couldn't solve A,B,C during contest time, I am still happy. Cause Now I know what I should know that I don't know.

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

D was fun to solve.

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

    I am getting a RTE in problem D. My logic is the same as that used in the editorial. Can someone please help me in debugging: Link : https://codeforces.net/contest/1365/submission/82791264

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

      You must check for every index to be valid i.e, after you do this--> int xx = i + x[k]; int yy = j + y[k]; you must check xx>=1 && xx<=n && yy>=1 && yy<=m Also you have provided the wrong link for the solution ;p

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

        Hey, Thanks for the help, but it did not work Link : https://codeforces.net/contest/1365/submission/83055198 Because anyways i'm using 1 based indexing and the remaining cells are always filled by walls(the ones outside m*n matrix) so this condition xx>=1 && xx<=n && yy>=1 && yy<=m anyways gets checked in the base case of the check(dfs) function!

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

          Your check function is in infinite loop. Try this case:

          1 2 3 BBB GG.

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

No relevant memes this time? We need TheOneYouWant as Co-Author from next time ig.

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

Can someone tell me why my E fails? Feels like I've done the same thing

Code

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

    what if biggest number shouldn't be in the solution, for example 11000000 is the biggest, but it would be better to use 10011111, you always use the biggest number in your solution.

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

    You are doing a greedy solution. It's not always correct to select in this way.

    For example, consider the following test case (all numbers in binary)

    100010
100001
010010
001000

    The optimal solution selects rows 2, 3, 4. Yours selects row 1, 3 and 4.

    → Reply
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

This was completely Mathforces!

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

    I wish!

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

    Felt more like Thinkforces than Mathforces, nice easy implementations after you get the logic, but not that much Math.

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

      Thinking is mathematics. Olympiad combinatorics is mainly "thinkforces". Also, problem F was finding a strong invariant in the process.

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

Most probably I will be losing my rating in this Contest. But No worries, the questions were too good [Especially the E qn]. I definitely want Ashishgup to host contests more frequently.

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

Great contest with problems that focus on elegant observations. Look forward to more such!

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

Great contest and hands down the hardest A and B i have seen in a long long time.

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

Has the record for fastest editorial ever been broken?

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

As a low rated coder I enjoyed it too, thanks!

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

Can anyone explain why my solution for D failed? First, I checked if any B has G as a neighbor or not. Then, I replaced all empty spots around B as walls. Then I ran a dfs from the right-bottom. https://codeforces.net/contest/1365/submission/82867892 Thanks.

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

    In your dfs code why are you moving left and top only?

    1
    5 5
    G . . . .
    G . . . .
    # # G # .
    B B # # .
    B B B # .

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

I love how you separated the editorial into key idea and solution so people have a second shot at upsolving without looking at the solution

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

My idea for the solution to D is check if the bad guys can reach the end, if yes, then block all the neighbouring cells. Then check if all good guys can reach the end. Why does this fail on pretest 7?

Link to my submission : https://codeforces.net/contest/1365/submission/82872417

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

    B and G are next to each other is auto fail, since B can just hop onto whatever path G is on

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

      I have included that condition also

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

        if B and B are next to each other, u can't block off the adj B cell

        if not that then idk what other edge cases there are

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

          Yeah, my solution fails for that case. I am blocking off any adjacent cell which is not a wall. Thanks for replying.

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

        You have a typo, when you are checking for s[i][j-1]=='G', you are actually checking if i-1>0, and the same typo when checking for '#'

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

          Thanks for pointing it out. This is the punishment for copy pasting without checking properly

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

            Having a row and col array really makes the code a lot less messy and easy to debug

            Check out my submission link

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

              Yeah that makes a lot of sense. I'll try to do that from the next time. Thank you!

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

            I actually used a similar approach in the contest but I'm getting TLE on test case 16. Here's my code:82884958. Don't know what's wrong in it.

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

              Yeah after correcting the typo, my code also TLE's. So instead of checking if every good guy can reach the end, check if you can reach every good guy from the end. This requires only one traversal whereas the first approach requires one traversal for every good guy.

              If you want to look at the code: https://codeforces.net/contest/1365/submission/82879263

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

    You have a typing mistake in 1st and 2nd for loops 4th if condition. if(i-1>=0 && s[i][j-1] != '#') is definitely wrong. Other than this it looks ok, Even though you could've optimized your code A LOT. For example,

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

      Yeah, I copy pasted that part without checking properly. And thanks for the tips. I'll keep that in mind from the next time.

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

      [deleted]

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

    Why the editorial solution only checks for maze[n][m] == '.' before enqueue? Shouldn't be != '#'?

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

      I think it doesn't matter. As long as you have the escape cell empty, you can reach every good guy if it's possible with only one cell in the queue initially.

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

        That's the point. He just adds the scape cell, but only if it is empty. So if there's a good guy on the scape cell, the code doesn't even run the BFS

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

          It is mentioned in the problem that the escape cell is empty. So unless you build a wall there in which case nobody can escape, the escape cell is empty.

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

The intended solution to problem G is pretty. Unfortunately for me, the solution I found was much uglier, and was a slight modification of the binary search idea.

Given two integers $$$i \neq j$$$, either there is a bit set in $$$j$$$ which is not set in $$$i$$$, or $$$\mathrm{popcnt}(i) > \mathrm{popcnt}(j)$$$ (where $$$\mathrm{popcnt}(k)$$$ is the number of bits set in $$$k$$$), in which case there is some bit un-set in $$$\mathrm{popcnt}(j)$$$ which is set in $$$\mathrm{popcnt}(i)$$$. Applying this directly would require 10 queries that examine values of $$$i$$$ with various set bits, and 4 queries that examine values of $$$i$$$ with various unset bits in $$$\mathrm{popcnt}(i)$$$, which doesn't quite fit within the bounds of the problem. But there are enough 10-bit values of $$$j$$$ with $$$2 \leq \mathrm{popcnt}(j) < 10$$$ (to enable using only 3 queries based on $$$\mathrm{popcnt}(j)$$$) to barely nudge this idea across the finish line by first mapping into that pool of values.

EDIT: Now that systests are over, I was able to produce a submission demonstrating this approach. (82885957)

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

Oh my god, I feel so stupid. I got the observation for E, but for some reason I thought n^3 was too slow. I spent almost an hour trying to figure out how you can know which 3 give the largest value. Well, at least I won't make this mistake next time (hopefully).

Other than that, I really liked the contest. Fun problems.

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

    I'm still stuck at the point where I can't reach why a subset of 3 is enough. Can you help with a better explanation?

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

      Let's say we have a subset with more than 3. We can call the numbers in the subset a1, a2, a3, ..., an. The value of the subset is the sum of all the bits present in at least k-2 of the ai. But, if a bit is in k-2 of them, it must be present in at least one of a1, a2, a3. If it wasn't, we'd have at most k-3 ai with that bit. This means: any bit which contributes to the value of a1, a2, ..., an, also contributes to the value of a1, a2, a3. So in fact, the value of a1, a2, a3 is at least as large as the value of the whole subset. Thus you can always reduce the subset to one of size 3.

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

My performance timelapse: Link. Hope you enjoy :)

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

Problem D video editorial: sOlUtiOn

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

We all should appreciate them for this quick editorial

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

consider for question A, m =5 and n =2 and filled with all 0s. min(m,n) is 2, so as per question Vivek should win. but, actually ashish will win this.

first step,ashish,

row 1 :1 0 0 0 0,

row 2 :0 0 0 0 0

second step,vivek,

row 1 :1 1 0 0 0,

row 2 :0 0 0 0 0

3rd step ,ashish,

row 1 :1 1 1 0 0,

row 2 :0 0 0 0 0

4th step vivek,

row 1 :1 1 1 1 0,

row 2 :0 0 0 0 0

5 th step ashish,

row 1 :1 1 1 1 0,

row 2 :0 0 0 0 1

The question said row or column. so, this must be optimum, just a doubt,please clear

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

    Here it's clearly written that no row or column should be picked by anyone if already have 1 in any cell. So your approach is not following the given constraint . Please read it carefully, I think you misinterpret .

    Anyway I also faced same but got green at last

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

      i got my mistake, i misinterpreted the question and wasted 1 hour thinking why i am getting wrong ans.thank you i considered if either row or column is not filled ,u can consider it

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

I felt like dumb.. even though it's stupid for me to think so but I am glad others found A and B hard..

Nice problemset. Anybody else know where can I practice such bit manipulation problems?

Ashishgup is the hardest problemsetter for me till date. It's a given now..

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

I want to know what is the story behind FastestFinger's handle

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

how to solve A if cell having common edge with claimed one are not to be taken ??

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

Gotta be careful with these maps.

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

F is a truly beautiful problem. Love this kind of problems where you don't have to even know some complex data structures or algorithms. Even someone inexperienced with deep insight could solve it and the solution is brilliant. This contest once again reminded me that solutions themselves can sometimes be the simplest (as in E and F).

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

Feeling very dumb of me, right now. I got to the intended O(n^3) solution of Problem-E. But, thought, it would give TLE (So dumb of me) and so, tried a greedy approach to solve it, but was't able to pass the pretests! :(

Problems were too amazing. You just get the basic approach, and that's it! No heavy implementation. (Except D, but that was fun too).

Thanks to the authors.

Awaiting more such rounds on CF.

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

    Feeling sad for E

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

    Yeah,I'm still wondering how an n^3 solution works for n=500. I thought that 10^6 iterations meant one second of runtime and that this would overshoot it by a lot. Ended up selecting the max everytime and iterating over the other n^2 possible pairs.:(

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

      A good rule of thumb is 4 * 10^8 easy operations (nothing like mods or pows) will take 1 second.

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

      Most CPU can run at 3GHz-4GHz (There's 3e9-4e9 Clock Cycle Time in a second). Different operation will cost different Clock Cycle Time: add, minus, multiply, bitwise operation usually cost 1-3 Clock Cycle Time while divide cost more than 10 Clock Cycle Time. If data is at RAM, read and write will cost about 100 Clock Cycle Time. If data is at CPU cache, read and write will cost only 1-10 Clock Cycle Time. Most CPU have a 4-16Mb L3 cache, so our program which use little consequent memory will run rather quickly, especially DP. And there's many other optimization such like out-of-order execution.

      For ordered pairs, $$$C_{500}^3 = 2e7$$$. Our program use about 500*sizeof(int)=2-4kb memory, this is very small. Our array will be placed at CPU L1/L2 Cache entirely and has a very fast read write speed. Suppose read and write use 3 cycles, bitwise operation use 1 cycle, our program will cost about 2e7*3/4e9 = 0.015s.

      You can use these rule to evaluate time usage of your code.

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

today i face very unique problem during contest on problem D . I run same code on 3 different ide and i get 3 different output on each ide for first test case. anyone know how it is possible? https://codeforces.net/contest/1365/submission/82870625

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

    Your use of memset is wrong, the second and third parameter switched. Such things happen much less often if using vector instead of arrays.

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

can some one tell test case where my solution of problem D fails . I solved for finding the path recursively instead of bfs .submission

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

    In your main method, you have a condition 

    j+1 <= m

    It should've been j+1 < m

    Ok. nvm .You were storing the values from 1 to n instead of 0 to n-1. My bad.

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

    Your code will fail the consecutive Bad guy case. For example, 

    1
3 3
BB.
BG.
...
    → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

https://codeforces.net/problemset/problem/1174/B B was the same problem as above with just a slight change in statement, now i see why practice helps.

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

In B, I considered swapping only adjacent elements with given properties. That was SAD!!!

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

Can anyone tell me what is wronge with my code Trouble Sort https://codeforces.net/contest/1365/submission/82849016

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

Tricked me in E. If problem E was placed at C, I would have solved it. Regret missing on such a simple logic.

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

    Yes! I realised that you don't need more than three elements and I noticed that $$$O(N^3)$$$ would pass, but somehow I just didn't think of checking all triples...

    Who knew the correct solution to problem E could be a simple brute force?..

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

Where are the memes?

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

Easiest Div2E I have ever seen. For me it was simpler than all other problems in this contest.

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

Great editorial !!**I think Every editorial must contain Key Idea.so that we can proceed by ourselves**

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

this was an unfair contest question F was easier compared to earlier questions

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

Could anybody please explain me why in Div .2 B array can always sorted if 0 type and 1 type is present

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

    Suppose you want to swap positions i and j where b_i = b_j = 1. Now suppose there is some index k such that b_k = 0. The following sequence of swaps will do the job —

    (i, k), (i, j), (j, k).

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

I can't think how my E failed , I just grouped and sorted numbers by the last set bit and took the or of three largest numbers in the top 3 bits...should not it be correct

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

    Try this case.

    4 34 33 8 14

    The optimal solution is 59, here (33 | 8 | 14)

    But, your solution will give 51.

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

    No. Consider the following case:

    Array is: [1,2,6,8]

    According to you, the output should be 8|6|2 = 14.

    But the answer is: 8|6|1 = 15

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

    There are two problems —

    1) Your code doesn't follow your logic exactly. I think you have made a typo in "sort(all(lb))". It should be "sort(all(lb[i]))".

    2) Your logic will give wrong answer for the following test case.

    4

    12 4 2 1

    According to your logic, you will pick (12, 4, 2) while the optimal choice is (12, 2, 1).

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

    Consider these 4 numbers

    11100 1100 100 11

    Your code will ignore '11' but that's not the optimal solution

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

Very nice problemset, not as a CP contest, but they are very beautiful indeed.

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

fuuuuuuuuuuuuu,.... , this C , damn itttt.

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

I solved the Problem D using DP. At first I make all the side of bad person("B") to "#"(except if the side has a bad person("B")).After that I will make all the remaining "B" to "#".So I get rid of that "B". Check that if we made the (n,m) cell to "#" then the answer is "No". Otherwise we now backtrack from (n,m) cell to all the possible direction cell we can go.As we can go to same cell many times so we will save that information in an array.If we visit that cell make dp[i][j]= true otherwise false.Beside that If we get a good person("G") through backtracking, we will save that. After backtracking we now check how many good person we get through backtracking.If the number is the same as all the good person then our ans is "Yes" otherwise "No". My code is here:82880358

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

If someone can really tell me why is this runtime error on Test Case 28 ! I will be thankful

HERE

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

If you scored less points for problem d than for c....... Welcome to the club.....

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

G is brilliant! Looked impossible at first.

Miss the memetorials.

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

How to solve problem C ,if we have repeated elements in array a and b?

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

In A, Dry running the editorial code should return "Ashish" for this test case, but the answer given is "Vivek". Here mn = min(5-1,10-1) = 4 (which is even, should return "Ashish"), or am I making some mistake?

5 10

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

    Hey, if mn is even, then Vivek is the one, who wins the game and not Ashish.

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

Amazing problems! $$$G$$$ is really nice and unique.

BTW problem $$$F$$$ in OEIS — https://oeis.org/A037223

If the given numbers are unique that is, assume $$$A$$$ is a $$$[1..N]$$$ and $$$B$$$ is a permutation of $$$A$$$. But it can be easily generalized to something like this:

for _ in range(int(input())):
    q,f=lambda:list(map(int,input().split())),lambda x:sorted(zip(x,x[::-1]))
    q(),print(['no','yes'][f(q())==f(q())])
→ Reply
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Video Tutorial for problems A,B,C,D,E

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

Can someone suggest what changes I can make to my submission D in python (I used pypy compiler), it gives TLE for test 13. I have implemented the same as editorial to my knowledge. https://codeforces.net/contest/1365/submission/82883245

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

    You are applying dfs from every good vertex. worst case it would take >1 second.

    What you can do is just do a single dfs from n,m and then check if every good vertex is visited and bad isn't like stated in the editorial

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

Why were the constraints for f so low ? Given that we can solve in nlogn ?

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

Would be awesome if someone can let me know why my same exact idea/concept TLEs when implemented in DFS but somehow passed in BFS :/ https://codeforces.net/contest/1365/submission/82870178 https://codeforces.net/contest/1365/submission/82883583

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

Weird constraints. It taught me a lesson though.

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

wow! editorial come so early

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

Hey everyone, I am hoping to get some help on why my submission to problem F fails. What am I doing wrong here? Thanks in advance.

82883731

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

    Are you aware of what the count method does?

    Try this case:

    1
5
1 2 2 1 1
1 1 2 1 1

    Your code outputs "Yes"

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

      Apparently not as well as I thought lol Thanks for the comment!

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

      Can u please help me why i am getting WA at test 38 for problem F. My logic is same as explained in the tutorial. Link to my submission https://codeforces.net/contest/1365/submission/83329650

      Thanks in advance for your reply:)

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

        Try this:

        1
11
2 1 1 1 2 2 2 1 1 2 2
2 1 2 2 1 2 1 1 1 2 2

        Also, your logic isn't exactly the same, the editorial says "so we only need to check if the multiset of these pairs in $$$b$$$ is the same as the multiset of pairs in $$$a$$$."

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

          Thanks for your reply. I got it now, i was using set because of which i was not able to chk the count of same pairs. ;)

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

Thanks for nice problems, as well as quick and detailed editorial as well. Couldn't solve much during contest but learned a lot:)

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

There is something wrong with the codes.

#include
using namespace std;

and

map, int> pairs;

in problem F

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

In problem C. Now for each shift, we can find the number of matching pairs and take the maximum.

Can someone please explain this line and in which step it is happening in editorial code?

for(int i = 1; i <= n; i++)
	{
		int cur = pos[b[i]] - i;
		if(cur < 0)
			cur += n;
		offset[cur]++;
	}
	int ans = 0;
	for(auto &it:offset)
		ans = max(ans, it.second);
	cout << ans;
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    int ans = 0;
for(auto &it:offset)
	ans = max(ans, it.second);
cout << ans;

    basically 'curr' is obtaining the number of shifts required for element at ith position to match. and then its frequency is being stored.

    then in the above part of code the maximum frequency is obtained and is the answer.

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

      how the maximum frequency of shifts is answer?

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

        Because if you shift the array by the amount of positions the result is that much number of positions with same value. Because you want to have the shift with maximum such positions, you choose the one with max freq.

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

    First, you calculate the offset between the positions of $$$x$$$ in $$$a$$$ and $$$b$$$, for all $$$x$$$. Let $$$d$$$ be the offset that appears more often. Then you shift the sequence $$$d$$$ times, and have the maximum number of correct digits. See my code:

    for (int i = 1; i <= n; ++i) {
	++diffs[(digita[i] - digitb[i] + n)%n];
}
	
int maxi = 0;
for (int i = 0; i <= n; ++i)
	maxi = max(maxi, diffs[i]);

printf("%d\n", maxi);

    The offset is (digita[i] — digitb[i] + n)%n, because digita[i] — digitb[i] can be negative.

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

I'll have to go with antontrygubO_o here. Problem G stands for Problem Genius!

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

Thanks for a fun contest! Well written problem statements — brief, good grammar etc. — to the point and very effective. Thanks for making this about solving the problem, rather than understanding the problem statements.

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

I liked the way of mentioning the Key Idea in the beginning of the tutorial :)

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

how can div2E pass n^3 solution? isn't that 10^8 for n=500

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

    it can further narrowed down to 500^3/6 bc of permutations

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

    $$$\sum ^{n}_{i=1}\sum ^{n}_{j=i+1}\sum ^{n}_{k=j+1}1=\dfrac 1 6 n^3-\dfrac 1 2 n^2+\dfrac 1 3 n$$$. Plug in $$$n=500$$$ the result is about 2e7.

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

E is too easy, I think it should just be B or C, or should increase the limit

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

Why did we choose bfs instead of dfs in D?

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

My solution for D:

Make sure every bad person is surrounded by a grid of walls, something like this

...     .#.         ...     .#.
.B. --> #B#    or   .BG --> .BG 
...     .#.         ...     .#.

After that, run a DFS from (n,m) and count the number of G's (count_G) and B's (count_B) on your path without crossing any #(wall). 

 if(count_G == total_G_in_the_matrix && count_B == 0) return YES
 else return NO
Code
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

2 2 BG #.

can anyone explain how its answer is no please

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

    You can only block the path of $$$B$$$ if you place a wall on the cell $$$(2,2)$$$, which would also block the path of $$$G$$$. Hence, it is not possible.

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

    in this case, it is not possible to block the bad person to go to the destination cell (2, 2) if the good person can go in the destination cell (2, 2). The bad person will just follow the path of the good person as there is no way to separate them by using some walls.
    NB. You have to perform the blocking operation before moving any person i.e before the journey starts.

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

Video Solutions for A to E:

https://www.youtube.com/watch?v=1s0bDFWTArY

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

assign the masks in such a way that no two masks assigned to two indices are submasks of each other. Anyone please explain. Problem G

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

FastestFinger In the code section of problem F "map, int> pairs; " should be "map<int, int> pairs;" I think.

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

Problem A

n=2, m=3

0 0 0

0 1 0

For this test case, shouldn't the answer be Vivek? Correct me if I have understood it wrong.

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

    initially, there are only 2 possible moves for Ashish, either choose the cell(1, 1) or cell(1, 3). After one of these two moves, the grid will be looked like 

    1 0 0
0 1 0

    or 

    0 0 1
0 1 0

    After this, there is no way to choose a cell following the criteria described in the statement.
    Hence the result is "Ashish" .

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

Test cases for F is not strong enough.

I believed I hacked some AC submissions using this data set. Obviously the right answer is No, but they all returned Yes.

1 3 8 9 8 9 8 9

Submissions:

https://codeforces.net/contest/1365/submission/82823958 https://codeforces.net/contest/1365/submission/82854157

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

    Uphacking on that problem caused an unexpected verdict.

    It seems that the validator(or checker) crashed :(

    FastestFinger Please try to fix this, thanks.

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

Is it just me or does anyone else also feel that problem C is the new B and Problem D is the new C in the recent rounds?

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

I am getting memory limit exceeded in test case 4 of problem D. The link to my solution is https://codeforces.net/contest/1365/submission/82901871. Can anyone help me in knowing where I am going wrong.

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

For problem E , Why maximum element isn't always considered in finding or?

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

    Consider a[] sorted max element first, descending. Let $$$b(x)$$$ be the set of bits in x.

    If $$$b(a_1)=b(a_2 + a_3)$$$ then it is always better to not choose $$$a_1$$$, because all bits of it a covered by the other two elements. And we can add $$$a_4$$$ instead of $$$a_1$$$ to getter a better result.

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

Can we solve $$$E$$$ using $$$DP$$$? I tried solving using $$$DP$$$ in the contest time but got $$$wa$$$ on pretest $$$6$$$. My $$$DP$$$ idea was pretty simple.

code

Still not understanding why got $$$WA$$$. Please help

N.B: It is failing on cases like

6

18 8 1 4 6 16

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

    Consider input

    4
6 4 2 1

    The bits of second and third element of the array equals the first one. If you start adding from left to right, you would need to find that 6 is covered by 4 and 2, so you can remove it to add 1 instead.

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

Can someone please find out the error in my code : https://codeforces.net/contest/1365/submission/82866772 I tried greedily since picking the max set bit would always be useful. I set k to the cnt of numbers having the max bit set. Now I went through all bit positions and checked if there cnt was more than max(1,k-2). If yes I added (1<<i) to my ans. Giving wrong answer on 6th pretest.

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

    Your idea is wrong, try with this case:

    7
8 8 4 4 2 2 1

    Ans should be 14.

    The reason is that if you pick the two 8s, your code would check if it could pick one 4, then if it could pick one 2... but if you pick 4 numbers then the 4 and the 2 won't be taken into account, as there isn't at least 2 of each type.

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

what was the point of making so small constraints for F when expected solution was O(n*logn)?

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

    To trick someone that solution is not that easy as it is. Check the ashishgup’s last contest’s C question. No point there also of giving such low constraints even the solution just have linear time complexity.

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

    In this case, notice that the sum of $$$n$$$ over all test cases is unbounded, i.e. there can be test files where $$$t=500$$$ and $$$n=500$$$, for each $$$t$$$. Hence, you'll have to account for number of test cases while computing time complexity (in this case, the intended solution has complexity $$$O(t*n*logn)$$$ for each test 'file', which is reasonable for 2 seconds).

    I think it was set this way to increase the number of possible test cases on which the solution runs (expected answer was simply a "Yes/No", so you'll require more test cases to verify solution's correctness), while keeping the number of test files same.

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

https://codeforces.net/contest/1365/submission/82955051 In my code for question D I have used only one 2D array of size 51*51 though in the test case 8 it is showing MEmory limit exit . What is the reason?

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

    Most likely one of the while loop runs and grows infinite.

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

      Even I am getting memory limit exceeded on test case 4. Still not able to figure it what is wrong. Help will be highly appreciated. Link to my latest submission: https://codeforces.net/contest/1365/submission/83106539

      Got the reason for Memory limit exceeded.

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

        Looks like the dfs runs in infinite recursion if there are two "." next to each other.

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

          Can you check mine once? I used dfs and marked visited all the G whenever I encounter B then I return back and after the dfs is completely executed, I checked whether there is any G left to be unvisited. I also checked for the condition whether there is any G adjacent to B. Thanks!

          Link to my solution: https://codeforces.net/contest/1365/submission/82868517

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

            Why this?

             	if(good==0)
    		cout<<"Yes\n";

            If there are no G there still can be unblockable B, then answer would be No.

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

              If there is no G present then we can directly block the destination as the problem statement says

              "It is guaranteed that the cell (n,m) is empty. Vivek can also block this cell."

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

                Good point, I did not see that.

                Edit: Ah, got it. Assume grid like

                .G..
....
BBB.
....

                The G will never reach Escape, but your dfs will reach the G.

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

Hi can someone please point out the mistake in https://codeforces.net/contest/1365/submission/82922169 I am getting WA on pt3 and can't understand why. Thank you.

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

    if(g==0||b==0){cout<<"Yes\n";continue;} It is possible that the goods cannot escape because the escape cell is blocked, even if there are no bad ones.

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

      But the last cell is guaranteed to be empty

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

      Oh sorry ..I get it.... it's possible that last cell is surrounded by walls Thanks a lot..

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

In A,does it make a difference if I directly declare the array like int a[51][51] instead of declaring a constant int N and using it as a[N][N] ?

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

I have doubt in 1365A if mn is odd then Ashish win and if it is even than Vivak win then why sir Ashishgup use this if(mn % 2) cout << "Ashish" << endl; else cout << "Vivek" << endl; If I am thinking wrong please tall me, I am beginner in coding.

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

During Contest Time:

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

In E, the values can be upto 10^18, isnt the complexity actually (n^3).log(10^18), and that seems off the limit for 2 seconds. Where did i go wrong?

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

    Complexity is is O(n^3). For what you would need the log part?

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

      Bitwise or, max

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

        The bitwise or is in all common programming languages a simple operation, like for example addition.

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

          but they do take O(digits) time

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

            No, they take O(1) time.

            Of course all operations take some more time on "bigger" datatypes, but usually we ignore this fact when referring to the big O notation. This is because it does not make sense to multiplicate everything by 8.

            And in fact, processors do ORs in one tic, even on 64 bit types.

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

      i used to think that is the reason why most problems of O(n) have inputs of size <= 10^6 (and not 10^7 or 10^8) so that these factors could be accommodated

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

Why left shift of $$$a$$$ is same as right shift of $$$b$$$?

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

    Because they are shiftet relative to each other.

    Assume shift of a by x to right. Then the element a[i] fits to the element b[i+x].

    Assume shift of b by x to left. Then the element b[i-x] fits to a[i].

    Clearly $$$i+x-x=i$$$

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

      Does it mean that after shifting arrays one by one to the left/right, they will be the same?

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

Can anyone help me with D? I think i've checked every possible cases.Please help me with what i am missing. https://codeforces.net/contest/1365/submission/83117062

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

    This loop in dfs is wrong. That way implemented your people can go diagonal, too. You should simply omit the inner for loop.

        for(int i=0; i<4; i++)
        for(int j=0; j<4; j++)
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

83114496 can anyone tell me why am i getting a WA

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

Am I the only one who read E multiple times but still couldn't understand the problem?

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

Can someone tell me what is wrong with my approach for the E problem? I am first finding the largest value and then using 2 separate loops finding 2 other values such that the bitwise OR of all the three values is maximum.

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

Problem F was an absolute beauty. Kudos to the setters !! Can someone suggest problems similar to F involving some beautiful observations and then pretty straightforward implementation?

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

can anyone suggest some problems like this problem C .?? It will be helpfull for me .

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

In Problem B , Do we require to swap the type also after swapping the elements. If yes then the solution given will be wrong , else it will be Correct.

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

    According to the problem statement we do not swap the type too. meaning type is bound to the element (does not get exchanged when swapping).

    but lets say we have to swap the types even, even then if we have atleast one element with a different type. lets say elements a,b,c, types t1 and t2, position i,j,k.

    • a t1 i
    • b t2 j
    • c t1 k

    If we want to swap a and c of the same type. we can do the following

    swap(a,b) -> (a t2 j) and (b t1 i)

    swap(b,c) -> (b t1 k) and (c t1 i)

    swap(a,b) -> (b t2 j) and (a t1 k)

    so finally

    • a t1 k
    • b t2 j
    • c t1 i

    a and c have swapped positions while b remains same, in the end we swap b to its correct place and thus the element would be in sorted order.

    Conclusion — It doesn't matter if type's are swapped or not.

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

      It matters in this case eg: — (25 , 1 ) (45 , 1) (48, 0) (421 ,1) Here (num , type)

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

        i didn't get what you are trying to say.

        isn't it already sorted? 25 45 48 421.

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

          To add -

          lets consider (45, 1) (25,1) (421,1) (48, 0)

          You can swap the first two using 48,0 like i mentioned before in the above post. it wouldn't affect (48,0)

          so we have (25, 1) (45, 1) (421, 1) (48, 0). and now swap (48,421) leading to final sorted array

          (25, 1) (45, 1) (48, 1) (421, 0)

          Try it out on paper for various cases. it is as the editorial stated. since even if types are swapped it is possible to swap(a,c) of same types if we have b of different type. so the ans would be 'yes' if such a b exists. else we check is its already sorted or not.

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

Please help me understand problem E.. i didnt get what we have to do in the problem(not the logic) but what the question means

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

    Same here! Please help us.

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

    Suppose you have chosen k elements from the sequence a. List them down after writing them in base 2. Now for each non-negative i, check how many of these numbers have the ith bit set (i.e., the ith bit from right is 1) and call this number num(i) for now. If num(i) > max(1, k-2) then you have to add 2^i to the answer. Do this for each i from 0 to 63.

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

The best editorial I have seen ever. Tutorials and codes are easy to understand. Thank you all authors of this round.

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

Video Solution to D: https://youtu.be/R4aj3I7yxg0

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

Can anyone say why my submission of D is getting TLE.. submission link: https://codeforces.net/contest/1365/submission/83147673

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

    You do the bfs() for every G in the grid which are up to $$$m*n$$$, and the bfs twice iterates the grid which is again $$$m*n$$$, so it is $$$O(n^4)$$$.

    Since it is up to 100 testcases, it gets basically $$$O(n^5)$$$ which is to much.

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

Really liked the idea behind problem E.

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

Can anyone pls see my code of problem C why am i getting WA? i have done as the tutorial says. here is my submission link : https://codeforces.net/contest/1365/submission/83156137

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

    I think the last loop is not correct. In array shift[] you have the shifts of the positions, so shift[j] is the number of positions element a[j] must be shifted to fit with b[i]. In array cnt[] you have the frequency of shift[]. And your loop is 

           for(int i = 1; i <= n; i++)
            ma = max(ma, cnt[shift[i]]);

    It should be something like 

          for(int i=0; i<n; i++)
          ma=max(ma, cnt[i]);

    Funny thing is that the first 12 testcases work either way.

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

Anyone plz tell me what is wrong in my code for D anyone please help me out. https://codeforces.net/contest/1365/submission/83125707

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

    In dfs you need to travers not only up/left, but also down/right. And if you do, you need to prevent endless loops by checking the vis[][] array.

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

In Probem D Solve the Maze Tutorial, the following test case is not working..why?

1 2 2 .. .G

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

What is wrong in my code for problem E , anyone please help me. https://codeforces.net/contest/1365/submission/83165332

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

    It is wrong logic. The question is why you think this would work? Did you check tutorial for the simple solution?

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

      I am finding all possible subsets having set bits satisfying the given conditions using dynamic programming. Can you tell me what is wrong in this logic?And in editorial it is given time Complexity of Solution is O(n^3) which is going beyond 10^8 operations thats why i was thinking for a better approach please help me sir.

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

        In spite of the downvotes... it is wrong logic.

        That your implementation is some kind of dp is obvious. But what is your recurrence, I do not understand the idea of your code, and cannot think of a working dp solution at all.

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

          Ohk, I got my mistake. But please tell me why O(n^3) approch is working here. As n is of range 500 and 500^3 is 125000000 which is above 10^8 operations.

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

            $$$10^8$$$ is just a guess. If it is fast operations (often referred to as a small 'constant factor') $$$10^9$$$ or even more is ok, too.

            Here we got very simple operations.

            Edit: And just to be right, If we calc with these numbers, it would be $$$\frac{500^3}{2}$$$

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

              Ohk i got it , thank you very much for your time:)

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

solution with explanation to problem D solution

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

    First Look for B first and block all neighbors of B that have '.' by replacing with wall. If any B has neighbor 'G' then it will return No

    Than DFS/BFS to check if all G can go to n,m

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

I got Memory limit exceeded on test 8 on problem D. My code here. Please, someone, explain this. Thanks in advance.

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

    Try making global array rather than making new array for each test case. This can help!

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

    You are doing wrong BFS. You have to make visited true when you push in queue not when you pop it from queue. You are pushing the same value in queue therefore using extra space. I hope this will help.

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

In D my code getting TLE for test case — 16. I've tried several hours to find bug but can't.I will be glad a lot, If anyone make me understand why getting TLE.

my submission: 83191177

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

My solution for A was pretty straightforward — traverse the grid, if there is a 1 anywhere, mark that row and column as unusable. Next, traverse the grid again, if a column and row is usable, place advance to the next turn and mark this row and column unusable. I just kept on incrementing a count and printed the result on the basis of wether the count was odd or even.

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

char arr[N][N]; for (ll i = 1; i <= n; i++) { cin >> (arr[i] + 1); }

1365D — Solve The Maze How is this code working ? Someone please explain it ?

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

    The arrays are $$$0$$$-indexed, where you are trying to use the $$$N^{th}$$$ row or column which is out of memory. You can do for (ll i = 0; i < n; i++) to avoid this problem.

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

Wow, solution for G is actually really clean. Really nice problem.

One tip for the editorial, though: it is really confusing that the example for the optimal solution has $$$n=4$$$ AND $$$q=4$$$. If you had something like $$$n=6$$$ and $$$q=4$$$ using the same masking mechanism, it would've been much easier to follow. It took me a while to realize that there were $$$n$$$ different $$$q$$$-bit masks, not $$$q$$$ different $$$n$$$-bit masks. In hindsight this should've been more clear from the complexity, but it would've been nice to have been explicitly stated somewhere.

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

Problem G is insanely awesome!

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

If anyone need Div2 D detail explanation Here

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

My proof for DIV2 E

Let us define bar as the minimum no of elements that should have a bit,for that bit to be added to the result, for a size of k, bar is k-2.

First observation, when we add more elements,bar also increases(for k>=3), hence some of the bits may get excluded, if we add more elements, and this is the reason why the result may decrease if we add more elements.

Let's assume the optimal answer has k elements, now let's remove one element, the result will now decrease if and only if there was a bit i, which was added to the result before, but now cannot be added after removing, because it doesn't satisfy the bar,i.e earlier the bit i must have been set in exactly k-2 elements, and after removing it doesn't satisfy the bar, but the bar also decreases to k-3 for k>3(as the current number of elements is k-1) ,hence removing an element doesn't decrease the result for k>3.But for k<=3, bar doesn't decrease upon removing an element,it always stays as one.Hence the optimal answer can be achieved with k<=3.

Let us also prove that when k<3 adding an element will not decrease the result. When k=1 or k=2 bar is 1, it remains 1 for even k=3 hence adding an element will not increase the bar,hence will not decrease the result(refer "First oberservation").

Hence optimal answer can be achieved by choosing an appropriate subset of size 3

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

D don't deserve to be 1700. haha

→ Reply