FastestFinger's blog

By FastestFinger, history, 5 months 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

Tutorial of Road to CM(Round 7)
 
 
 
 
  • Vote: I like it
  • +626
  • Vote: I do not like it

»
5 months ago, # |
Rev. 4   Vote: I like it -36 Vote: I do not like it

..

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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)

      • »
        »
        »
        »
        5 months 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

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
          Rev. 2   Vote: I like it -89 Vote: I do not like it

          deleted.

        • »
          »
          »
          »
          »
          5 months 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
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        I did the same mistake, misread the statement

      • »
        »
        »
        »
        5 months 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 .

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        me too

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I also did the same

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I just ORed each row and column anc got count of 0's in each Now if mincount of 0's among those two is odd then Ashish wins otherwise Vivek

    • »
      »
      »
      5 months 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 :(

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for easy explanation...

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What if both unassigned rows and columns are equal?how to find min of them

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Then take any of them

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            There is a brute force O(n^3) solution too. Whenever you find zeros, traverse that particular row and column to check if there are no ones. In that case, increase the counter and set that particular a[i][j] to 1. At the end, if the counter is odd Ashish wins, else Vivek wins

    • »
      »
      »
      5 months 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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      same here buddy

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -27 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Wow, that was fast.

»
5 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Good round! Thanks for fast editorial

»
5 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Amazing contest! Had fun solving the problems ^_^

»
5 months ago, # |
  Vote: I like it +53 Vote: I do not like it

FastestFinger fastest editorial <3

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

One of the fastest editorial I'd say :-)

»
5 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Hardest A ever seen.

»
5 months 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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How is the solution to E is easier than the problem itself?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You understand me bro !!

  • »
    »
    5 months 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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

.

  • »
    »
    5 months 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!

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Exaxtly.we are not supposed to give up.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also can't solve any question in the contest. Some times its looks like I don't know anything. But it ok to take time to learn new concept. Coding needs much practice. Worst part of coding is to find your error in your code.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Never loose hope. One day you will.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    And hence as a result, always stay beginners.

»
5 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I feel so stupid after reading the editorial for problem B

»
5 months 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)

»
5 months 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?

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 months 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)

»
5 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Link your submission

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read the question carefully. It is not bubble sort but you can switch any two numbers if their type is different. I made the same mistake.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      thank you got it

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        no problem :)

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          Thanks in advance :)

          • »
            »
            »
            »
            »
            »
            5 months 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

            • »
              »
              »
              »
              »
              »
              »
              5 months ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              oh yeah! got it , thanks a lot

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try

    1

    3

    2 1 1

    0 1 0

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    try this test case:

    1

    3

    3 1 2

    0 1 0

    ans should be "YES". :)

  • »
    »
    5 months 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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 months 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

  • »
    »
    5 months 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

»
5 months 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 :(

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please find out the error in my code : https://codeforces.com/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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Damn I feel so stupid after seeing E's solution

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is __builtin_popcount?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is an in built function which is used to count setbits

»
5 months 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 :)

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

    Can you explain the proof you got?

    • »
      »
      »
      4 months 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.

»
5 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Where are the memes

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

To me A was harder than B.

Don't read stroy
»
5 months 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.

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

D was fun to solve.

  • »
    »
    5 months 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.com/contest/1365/submission/82791264

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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.com/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!

        • »
          »
          »
          »
          »
          5 months 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.

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks!! I figured out the problem.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hey, I am having some trouble understanding why my solution is not working ! (problem D ) https://codeforces.com/contest/1365/submission/94191073

    Can someone please point out what I'm doing wrong? Thanks in advance! :D

    EDIT: My approach is this -

    Initially, bool yes=1;
    1. If no good cell, yes=0;
    2. If a bad cell is adjacent to a good cell, yes=0;
    3. If a bad cell is adjacent to {n-1,m-1}, yes=0;
    4. For each bad cell, block all its neighbors that are blank.
    5. Now for each good cell, check if {n-1,m-1} is reachable from that cell
       If for any good cell, {n-1,m-1} is not reachable, yes=0;
    6. if(yes) print("yes") else print("no"); 
    

    What am I missing here?

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one explain problem (E. Maximum Subsequence Value not the solution just the statments.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Here, if we OR the elements, then we'll get all the set bits, but we need to get the bits that are in at least k-2 elements in a subseq of size k(k>3 else 1) so when we go throught the binary repr of the numbers, we find out that not all bits are contributing towards max (cases with dense set bits is exception to this obsv) but when we decrease the size of the array (ie get a subseq), our k-2 decreases and narrowing down to large numbers while also aiming to make it denser(ie in [1,2,4,8,10], 10,1,4 cover all bits), our value increases. So, how long do we need to decrease this subseq size, that goes down to that atleast max(1,k-2) must be set, therefore for k<=3, we have that any set bit contributes and at k=3 our subseq size is max.

    example: [2,4,8,16,32,64] => [16,32,64] 112
    [1,2,4,8,10] => [10,1,4] 15

»
5 months 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

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it -16 Vote: I do not like it

This was completely Mathforces!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wish!

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

»
5 months 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.

»
5 months 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!

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Has the record for fastest editorial ever been broken?

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
5 months 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.com/contest/1365/submission/82867892 Thanks.

  • »
    »
    5 months 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 # .

»
5 months 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

»
5 months 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.com/contest/1365/submission/82872417

  • »
    »
    5 months 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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have included that condition also

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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.

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

          Hey, I am having some trouble understanding why my solution is not working ! (problem D ) https://codeforces.com/contest/1365/submission/94191073

          Can someone please point out what I'm doing wrong? Thanks in advance! :(

          EDIT: My approach is this -

          Initially, bool yes=1;
          1. If no good cell, yes=0;
          2. If a bad cell is adjacent to a good cell, yes=0;
          3. If a bad cell is adjacent to {n-1,m-1}, yes=0;
          4. For each bad cell, block all its neighbors that are blank.
          5. Now for each good cell, check if {n-1,m-1} is reachable from that cell
             If for any good cell, {n-1,m-1} is not reachable, yes=0;
          6. if(yes) print("yes") else print("no"); 
          

          What am I missing here?

      • »
        »
        »
        »
        5 months 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 '#'

        • »
          »
          »
          »
          »
          5 months 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

          • »
            »
            »
            »
            »
            »
            5 months 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

            • »
              »
              »
              »
              »
              »
              »
              5 months 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!

          • »
            »
            »
            »
            »
            »
            5 months 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.

            • »
              »
              »
              »
              »
              »
              »
              5 months 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.com/contest/1365/submission/82879263

  • »
    »
    5 months 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
  • »
    »
    5 months 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 != '#'?

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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.

»
5 months 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)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

After reading the editorials for all problems that I tried solving but could not solve, I am feeling dumb for not thinking the way it is mentioned in the editorial. SMH

»
5 months 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.

  • »
    »
    5 months 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?

    • »
      »
      »
      5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My performance timelapse: Link. Hope you enjoy :)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D video editorial: sOlUtiOn

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

We all should appreciate them for this quick editorial

»
5 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if n = 2 and m = 5, it should look like this

    0 0 0 0 0
    0 0 0 0 0
    

    Ashish can pick any position

    '1 0 0 0 0
    0 0 0 0 0 '
    

    Now Vivek has the option of picking in the bottom row except the first column. So,


    '1 0 0 0 0 0 1 0 0 0 '

    Now, Ashish has no options. So, Vivek wins.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any one explain E ? As i not understand why can not we xor of all element . I think it will automatically fetch all max ? But as here is condition that you need at least k-2 element with bit 1 in binary representation. So any other proof which gives this answer.?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Saw E thought it would be much harder and tried D and now I am here crying.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Really it's looks easy but for that you need one tick which is 3 in mind . Bro don't worry . But if you had solved D then you are awesome.

    Just Chill.We are on way to learning by making mistakes.

»
5 months 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..

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
5 months 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 ??

»
5 months ago, # |
  Vote: I like it +35 Vote: I do not like it

 Gotta be careful with these maps.

»
5 months 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).

»
5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Feeling sad for E

  • »
    »
    5 months 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.:(

    • »
      »
      »
      5 months 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.

    • »
      »
      »
      5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What should be the difficulty of B?

»
5 months 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.com/contest/1365/submission/82870625

  • »
    »
    5 months 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.

»
5 months 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

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.
    ...
    
»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
5 months 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!!!

»
5 months 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.com/contest/1365/submission/82849016

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    consider

    1 3 4 2

    0 1 1 1

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for replying Having at least one element of each group is the only condition for above problem?

»
5 months 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.

  • »
    »
    5 months 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?..

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you help me with my logic, I have posted my doubt below...

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Haha. Same Happened with me. I was trying to solve E in O(N^2). Finally managed to solve it(after the question). Link to my solution: 82882054

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Where are the memes?

»
5 months 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.

»
5 months 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**

»
5 months 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

»
5 months 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

  • »
    »
    5 months 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).

»
5 months 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

  • »
    »
    5 months 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.

  • »
    »
    5 months 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

  • »
    »
    5 months 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).

  • »
    »
    5 months 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

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1365/submission/82842665

what is the use of function check() and asdasd() in this solution for E.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me in my code why i am getting runtime error on one particular line https://codeforces.com/contest/1365/submission/82879289

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months 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

»
5 months 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

»
5 months 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.....

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, I am new at CP. So I am quite confused. The "game" tag for A is it because A is a game theory problem? I solved A using brute force and it passed successfully. But I am in doubt. Is A game theory problem?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it has game tag because the question is who will win or lose.

»
5 months ago, # |
  Vote: I like it +22 Vote: I do not like it

G is brilliant! Looked impossible at first.

Miss the memetorials.

»
5 months 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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It isn't supposed to have them be repeated. "Note that a permutation of n elements is a sequence of numbers a1,a2,…,an, in which every number from 1 to n appears exactly once."

»
5 months 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
  • »
    »
    5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The answer is "Vivek".

»
5 months 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 OEIShttps://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())])

»
5 months 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.com/contest/1365/submission/82883245

  • »
    »
    5 months 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

»
5 months 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 ?

»
5 months 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.com/contest/1365/submission/82870178 https://codeforces.com/contest/1365/submission/82883583

»
5 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Weird constraints. It taught me a lesson though.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody tell me why my submission is getting WA 82884730

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wow! editorial come so early

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

There is a typing mistake in F code

map,int> pairs instead of map<int> pairs
»
5 months 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

  • »
    »
    5 months 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"

    • »
      »
      »
      5 months 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!

    • »
      »
      »
      5 months 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.com/contest/1365/submission/83329650

      Thanks in advance for your reply:)

      • »
        »
        »
        »
        4 months 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$$$."

        • »
          »
          »
          »
          »
          4 months 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. ;)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell why my approach is giving TLE? I first made walls to bock all the B. Then I checked if any B could reach (n, m). If they can reach, ans will be "No". Otherwise, I checked if all the G get to (n, m) or not. Please help. This is my submission.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you check separately for each G then it will lead to TLE since worst case lets say there are approximately n*m G's. (can ignore the -1 due to last being '.')

    Now dfs/bfs from each vertex would take approx n*m*4 steps.

    so it would lead to net worst case time complexity of t*n*m*n*m*4 which would take >1 second.

    I had made the same mistake initially. What you can do is just perform dfs/bfs from n,m and then check if each 'G' vertex is visited.

»
5 months 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:)

»
5 months 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

»
5 months 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;
  • »
    »
    5 months 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How offset[cur]++ is storing the no. of matching pairs in each shift?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how the maximum frequency of shifts is answer?

      • »
        »
        »
        »
        5 months 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.

  • »
    »
    5 months 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.

»
5 months 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!

»
5 months 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.

»
5 months 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 :)

»
5 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    time limit is 2 seconds.

    (500)^3 = 1.25 * 10^8

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    5 months 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.

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why this doesn't work? -

https://codeforces.com/contest/1365/submission/82893654

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did we choose bfs instead of dfs in D?

»
5 months 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
»
5 months 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

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    since you can't put a wall on G's, the B will just be able to go along the path the G would go to.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem setters need to understand one thing that the questions difficulty must be maintained in increasing order because in last to last contest also, problem A was difficult to solve than as compared to B and C. Who else agrees with the fact?

»
5 months 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.

»
5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ashish can claim either cell (1, 1) or (1, 3) (since he goes first); then Vivek won't have any cell to choose (since the cell chosen by Ashish will make any other cell on line 1 unable to be chosen, and the other cells also can't be chosen), thus according to the statement of the problem, Vivek will lose and Ashish will win.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh so it is entire row then. I understood it as a row border/column border. So I thought after Ashish make a choice

      0 0 1

      0 1 0

      Vivek can choose (1,1). And then Ashish has no choice. So he loses. My bad.

      Thanks though!

  • »
    »
    5 months 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" .

»
5 months 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.com/contest/1365/submission/82823958 https://codeforces.com/contest/1365/submission/82854157

  • »
    »
    5 months 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.

»
5 months 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?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why my solution for D failed? 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. Please help!

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

»
5 months 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.com/contest/1365/submission/82901871. Can anyone help me in knowing where I am going wrong.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me figure out what i am doing wrong in div2-D? 82900500

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain this for DIV2B question, By swapping any two elements at indices i and j, their b[i] and b[j] are also swapped? Or only element values are swapped at indices i and j not b[i] and b[j].

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes both the value as well as b[i] and b[j] will get swapped Consider each value-key pair as one unbreakable unit.

»
5 months 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?

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i was wondering if it was possible to use a comparator function in B. If someone has done it, please share the solution.

»
5 months 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

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In solution of E:

"Let i be any number such that the i-th bit is set in at least k−2 elements of s"

What does it mean by "let i be any number" ? the ith element from the sequence ?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

could someone help me debug my solution for D

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please find out the error in my code : https://codeforces.com/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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same here

  • »
    »
    4 months 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.

»
5 months 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)?

  • »
    »
    5 months 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.

  • »
    »
    5 months 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 corr