Monogon's blog

By Monogon, history, 4 weeks ago, In English,

1345A - Puzzle Pieces

Tutorial

1345B - Card Constructions

Tutorial

1345C - Hilbert's Hotel

Tutorial

1345D - Monopole Magnets

Tutorial

1345E - Quantifier Question

Tutorial

1345F - Résumé Review

Tutorial

1344E - Train Tracks

Tutorial

1344F - Piet's Palette

Tutorial
 
 
 
 
  • Vote: I like it
  • +578
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

Thank you for great round and fast editorial

»
3 weeks ago, # |
Rev. 4   Vote: I like it +10 Vote: I do not like it

There is a typo in the editorial for D2C/D1A.

"This proves there is a collision if and only if all i + a_i are distinct" should be "This proves there is no collision if and only if all i + a_i are distinct".

UPDATE: It has been fixed, but in a way different from what this comment indicates. Please read carefully before making further downvotes.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +185 Vote: I do not like it

I feel really sorry for the problemsetter.. He must have worked hard to create those problems..also this was his first round as a setter..

The problems were great, thanks a lot :) :)

»
3 weeks ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

For Div2B we can optimize the solution by iterating the loop from floor(sqrt(n)/2), as substituting this value in the inequality (3*h+1)*h/2 <= n always satisfies it. P.S: I don't think it affects the asymptotic complexity so it seems pretty useless now lol.

»
3 weeks ago, # |
  Vote: I like it +379 Vote: I do not like it

I've read the problems and they're indeed very interesting. I congratulate you and thank you for your work, and really feel sorry about the issues that made this contest unrated.

I want to leave an idea that has been growing on my mind. I think that given the fact that there are much fewer Div. 1 contests than Div. 2 or Div 3., in the case of "long queue" issues, one should give a priority to the judgement of Div 1. submissions.

I know that if one interprets this as if it was "Div. 2 doesn't matter", it doesn't sound so nice. However, I think that there are much fewer participants in Div. 1 and it may be possible to at least try to "save that contest" when this issues occur.

Only that. A suggestion.

Cheers,

Roberto Esquivel Cabrera.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -75 Vote: I do not like it

    It might be a good idea to limit the number of participants so that codeforces would work well (around 10000). Div 2 people will participate more rarely on average, say once a week instead of twice, but without long queues. The only effect on div 1 is reducing queues.

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

      Mike is eagerly waiting for a contest with 30k registrations.

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

tbh kind of disappointed with it going unated...tried so hard and finally got the 2nd question right after a hour.

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

what will be the quadratic formula for B?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    For a given n:

    t = floor( ( -1 + sqrt( 1 + 24*n ) ) / 6 )

    then the tallest tower that can be built from n is : 2 + ( (t-1)*(3t+4) )/2

    keep subtracting this from n and recalculating 't' and tallest tower as long as n > 1

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      Why did you not take t = floor( ( -1 — sqrt( 1 + 24*n ) ) / 6 )?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it -6 Vote: I do not like it

        t cannot be negative, t represents the index of the sequence: 2 7 15 26 ... and floor to make sure that index doesn't point to a term > n

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          Thanks for clarifying :)

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

            thought of a recursive solution and a less mathematical one for problem 1345B Just Precalculate till 10^9 and then binary search for the index of the biggest smaller number of cards than n in each iteration. Code

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      How did you compe up with this formula?

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

        Series formula F(N) = N*(3*N + 1)/2..If you search you will able to find the series otherwise one can drive using the taking the test cases. I can able to find but made mistake in code I think so. Got wrong answer :'(.

        For reference of the series

        Link : https://oeis.org/A005449

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

        More practical method is to use the recurrence from the problem and let https://www.wolframalpha.com/ solve it for you so you get n(h) (number of blocks needed to build pyramid of height h). Then you can also let it solve for the inverse and floor it to get the maximum height h' you can build using n blocks. This works because the function is increasing. Then you just do n -= n(h'). And you repeat this while keeping count.

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

        If you look closely you can observe that in every structure there are complete triangles on every level except for surface. The no. of triangles are 1,1+2,1+2+3,1+2+3+4,....so on. so for nth structure there will be n(n+1)/2 no. of triangles, hence required card should be 3*n*(n+1)/2. But we know that we have to subtract base level no. of cards, hence final formula will be (3*n*(n+1)/2)-n. after rearranging this we get (3n^2+n)/2. Now you can reverse calculate highest tower n by making it equal to given number and solving the quadratic eqn.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      how those t and n equations obtained?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Can you please explain how 2 + ( (t-1)*(3t+4) )/2

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        we can even subtract t*(3*t+1)/2 from given till given >1 right

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

      t = floor( ( -1 + sqrt( 1 + 24*n ) ) / 6 ), i need proof of this formula,i didnt undrstand whole thing.

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

      But this show TLE on 10^9 test case 4. I don't understand why this is happening.

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

        you need to change 24*n to 24LL*n.

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

          Can you please elaborate upon how this works, what is the error in earlier choice It would be a great help

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

            Long in cpp has maximum value (2^31-1), so it's bad when n = 1e9 and 24*n is 1e10, it is leading to overflow. You should use long long for variables where you're not sure whether you might overflow using int/long.

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

      why can't the tallest tower be t

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

    a much easier to understand formula is (trng(n)*3)-n where trng is the nth triangular number. Notice that there are 1, 3, 6, 10... triangles in the structure and each triangle requires 3 cards. Then we subtract n cards, as we do not need cards at the bottom.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    I had a different solution for B, you can see that for pyramids of height 1,2,3,4.. you need 2,7,15,26..cards respectively and so on. Now if you see the difference between them it is 5,8,11-->this series is in A.P with Common difference of 3 so you can just precompute this array of needed cards and then start from back of this array, building the pyramid with 'ith' height if it is possible until you no longer can.

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

    I computed this: For the cards to be placed upright: n*(n+1) For the cards to be placed as base: n*(n-1)/2 So, to construct a pyramid of height n, cards required will be: n*(n+1) + n*(n-1)/2.

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

      After this, I precomputed upto 1e5 and the performed binary search for each test, solving it in O(logn).

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

    i know a better approach to find the formula

    for a height h there will be 2*h no. of cards at the base there will be total of (h-1)*((h-1)+1)/2 no. of triangles now just run a loop till n<2 https://codeforces.com/contest/1345/submission/79162987 link to my submission

»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Not expecting such a technical problem from codeforces server. Even still many submissions are not judged.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -52 Vote: I do not like it

    Go cry to your Mama. No one asked you to come here. If you are here, just be grateful that so many intelligent people are trying to make interesting contests free of cost.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      You are not on the list of those intelligent people so why don't you practice your own advice.

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

loosed +160 delta

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

The problem set was really nice, looking forward for more rounds from you.

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I am totally confuse dev2 A question.... Plz somebody plzz help me....

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

    In this problem, when you take 2*3 grid you see that you can not solve that puzzle, therefore you can not solve similar grids which has higher dimensions than 2. That means, if either row or column is 1 it can be sokved and if both are 2 it can be solved. Otherwise not. I hope now you understand.
    Sorry for my bad english..

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Really great round but I am sad for this nice problem became unrated.

»
3 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

For F, I went with a much more natural approach to me, where for each position we have 4 variables $$$r_i, y_i, b_i, e_i$$$ (I hope their meaning is clear, e.g., $$$r_i=1$$$ if i-th position is red). YB operations etc are basically swapping variables. Since result of each mix operation is white if all colors occur with the same parity and a proper color if one of them has a different parity than the others two, each mix operations produces 2 equations modulo 2 corresponding to the difference between parities of some two colors. However we have a nasty condition that exactly one out of $$$r_i, y_i, b_i, e_i$$$ should be 1 that can't really be expressed modulo 2, which seems like a big problem. However, what happens if we put there an equation $$$r_i+y_i+b_i+e_i=1$$$? We can get a faulty solution where $$$3$$$ out of these bits are lit. BUT, this system of equations has a very peculiar property that for every $$$i$$$, every equations contains an even number of variables $$$r_i, y_i, b_i, e_i$$$, so if we flip all of them then this will still be a solution! Hence if 3 of these variables are true then we can change them so that 1 of them is true and if we do this for every $$$i$$$ where it is needed then we will get a solution of equation system corresponding to the valid coloring!

»
3 weeks ago, # |
  Vote: I like it +67 Vote: I do not like it

The setting of 1344C - Quantifier Question is very nice. Thank you for the problemset!

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can somebody explain div2C, I can't get my head around the proof ?

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

    consider a subset of rooms, from room 0 to n-1. let n = 5. CASE 1 let's assume a0 = 0, a1 = 1, a2 = 2, a3 =3, a4 = 4. Now, the guest in room 0 will go to -> 0 + a0 = 0 similarly guest in room 1 will go to -> 1 + 1 = 2 room 2 -> 2 + 2 = 4; room 3 -> 3 + 3 = 6; room 4 -> 4 + 4 = 8;

    room 5 -> 5 + 0 = 5; room 6 -> 6 + 1 = 7; room 7 -> 7 + 2 = 9; room 8 -> 8 + 3 = 11; room 9 -> 9 + 4 = 13; .... and so on.

    No guests get the repeating room {explained later}

    CASE 2 let's consider a0 = 5, a1 = 7, a2 = 5, a3 = 8, a4 = 6; for room 0 -> 0 + 5 = 5; room 1 -> 1 + 7 = 8; room 2 -> 2 + 5 = 7; room 3 -> 3 + 8 = 11; room 4 -> 4 + 6 = 10;

    room 5 -> 5 + 5 = 10; {gets repeating room} ******

    in both cases, we can observe an arithmetic progression is forming . after every n__

    Now if we observe both the cases, we can see that if, for a particular value of 'i' b/w 0 to n-1 if there exists a j, such that aj + j lies in the arithmetic progression of (ai + i), it implies that there will be a collision. This is because, a time will come when becomes (aj + j),

    for example in case 2,

    for i = 0 we can see that ai = 5 and i = 0; so the first term of the arithmetic progression is ai + i = 5 + 0 = 5; now we'll check for j = 1 to n-1, whether there is such a j for which aj + j lies in the arithmetic progression of ai + i with difference = n; so for j = 4, aj = 6, and aj + j = 10; so aj + j clearly lies in the arithmetic progression of ai + i ( 5 + 1*5 = 5) {ai + i + (x-1)*n = xth;}

    this way we have to check for every i, that, whether there is a number which is in ap with ai + i and diff = n; this will take O(n*n). To optimize it we can just check whether there are more than one such numbers such that (ai+i)% n == (aj+j) % n because ai + i + (x-1)*n = aj + j; taking modulo both sides we'll end up with (ai+i)% n == (aj+j) % n and hence O(n).

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

      Thanks a lot!! just one thing that arithmetic progression of n also means that one should also be a multiple of other. So we just need to check if the taking the mod of (i+a[i]) gives same value as any other index.

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

        suppose we take n =3, a0 = 0, a1 = 1, a2 = 2; room 0 -> 0 + 0 = 0

        room 1 -> 1 + 1 = 2

        room 2 -> 2 + 2 = 4

        room 3 -> 3 + 0 = 3

        room 4 -> 4 + 1 = 5

        room 5 -> 5 + 2 = 7

        room 6 -> 6 + 3 = 9 ........ and so on

        therefore room0, room3, room6, room9.....are in ap

        similarly, room1, room4, room7, room10 ..... are in ap

        and room2, room5, room8 .... are in ap

        if any of the rooms in 2nd and 3rd row in this example are common with any room in first row {means are present in ap of first row,} Collison will occur. similarly if any rooms in 3rd row are common with any room in second row {means they are present in ap of 2nd row.} Collison will take place.

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

        yes

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

      This comment is by moha.jain credit to him for the explanation. and I re-wrote it to make it more readable.

      Consider a subset of rooms, from room $$$0$$$ to $$$n-1$$$. let $$$n = 5$$$.


      CASE 1: let's assume $$$a_{0} = 0$$$ , $$$a_{1} = 1$$$, $$$a_{2} = 2$$$, $$$a_{3} = 3$$$, $$$a_{4} = 4$$$. Now, the guest in room $$$0$$$ will go to $$$0 + a_{0} = 0$$$ similarly guest in room $$$1$$$ will go to $$$1 + 1 = 2$$$ room $$$2$$$ go to $$$2 + 2 = 4$$$; room $$$3$$$ go to $$$3 + 3 = 6$$$; room $$$4$$$ go to $$$4 + 4 = 8$$$;

      room $$$5$$$ go to $$$5 + 0 = 5$$$; room $$$6$$$ go to $$$6 + 1 = 7$$$; room $$$7$$$ go to $$$7 + 2 = 9$$$; room $$$8$$$ go to $$$8 + 3 = 11$$$; room $$$9$$$ go to $$$9 + 4 = 13$$$; .... and so on.

      No guests get the repeating room explained later


      CASE 2: let us consider $$$a_{0} = 5$$$, $$$a_{1} = 7$$$, $$$a_{2} = 5$$$, $$$a_{3} = 8$$$, $$$a_{4} = 6$$$; for room $$$0$$$ go to $$$0 + 5 = 5$$$; room $$$1$$$ go to $$$1 + 7 = 8$$$; room $$$2$$$ go to $$$2 + 5 = 7$$$; room $$$3$$$ go to $$$3 + 8 = 11$$$; room $$$4$$$ go to $$$4 + 6 = 10$$$;

      room $$$5$$$ go to $$$5 + 5 = 10$$$; gets repeating room


      In both cases, we can observe an arithmetic progression is forming . after every $$$n$$$

      Now if we observe both the cases, we can see that if, for a particular value of $$$i$$$ b/w $$$0$$$ to $$$n-1$$$ if there exists $$$a_{j}$$$, such that $$$a_{j} + j$$$ lies in the arithmetic progression of ($$$a_{i} + i$$$), it implies that there will be a collision. This is because, a time will come when becomes ($$$a_{j} + j$$$).

      For example in case 2:

      for $$$i = 0$$$ we can see that $$$a_{i} = 5$$$ and $$$i = 0$$$; so the first term of the arithmetic progression is $$$a_{i} + i = 5 + 0 = 5$$$; now we will check for $$$j = 1$$$ to $$$n-1$$$, whether there is such $$$a_{j}$$$ for which $$$a_{j} + j$$$ lies in the arithmetic progression of $$$a_{i} + i$$$ with difference equals to $$$n$$$; so for $$$j = 4$$$, $$$a_{j} = 6$$$, and $$$a_{j} + j = 10$$$; so $$$a_{j} + j$$$ clearly lies in the arithmetic progression of

      $$$a_{i} + i$$$ ($$$5 + 1 \times 5 = 10$$$) => $$$a_{i} + i + (x-1)\times n$$$ $$$=$$$ $$$xth$$$

      this way we have to check for every $$$i$$$, that, whether there is a number which is in ap with $$$a_{i} + i$$$ and $$$diff = n$$$; this will take $$$O(n \times n)$$$. To optimize it we can just check whether there are more than one such numbers such that

      $$$(a_{i}+i)$$$ $$$mod$$$ $$$n$$$ $$$\equiv$$$ $$$(a_{j}+j)$$$ $$$mod$$$ $$$n$$$

      because $$$a_{i} + i + (x-1) \times n = a_{j} + j$$$; taking modulo both sides we'll end up with $$$(a_{i}+i)$$$ $$$mod$$$ $$$n$$$ $$$\equiv$$$ $$$(a_{j}+j)$$$ $$$mod$$$ $$$n$$$ and hence $$$O(n)$$$.

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

        if n = 5, in your case 2, does not room 0 goes to room 0 + a[0] % 5 = room 0 ? Why does guest in room 0 goes to room 5?

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

          I think you are missing that the mod operation is on the subscript and not on $$$a_{i}$$$

          if $$$n = 5$$$, then guest $$$0$$$ would go to

          $$$0 + a_{0 mod 5}$$$ $$$=$$$ $$$0 + a_{0}$$$ $$$=$$$ $$$0 + 5 = 5$$$

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

        A little typo in this line $$$a_{i} + i (5 + 1 \times 5 = 5)$$$.

        It should be $$$a_{i} + i (5 + 1 \times 5 = 10)$$$.

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

      I solved by your approach but getting the wrong answer. Can you please tell me where am I wrong? https://codeforces.com/contest/1344/submission/79319693

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

        you have to take into account the mod of negative number with n

        a[i] = a[i] + i; a[i] = (a[i])%n; if(a[i]<0){a[i] = a[i] + n;}

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

          still wrong

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

            int main() { int t;cin>>t;

            while(t--)
            {
            
            long long int n;
            
            cin>>n;
            
            long long int a[n],i;
            
            unordered_set<long long int>s;
            
            for(i=0;i<n;i=i+1)
            
            {cin>>a[i];a[i] = i + a[i];}
            
            for(i=0;i<n;i=i+1)
            {
            
                a[i] = a[i]%n;
            
                if(a[i]<0){a[i]=a[i]+n;}
            
                s.insert(a[i]);
            
            }
                if(s.size()==n){cout<<"YES"<<endl;}
            
                else{cout<<"NO"<<endl;}
            
            }

            } *****hope this helps

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

    Consider the number line divided into segments of size n i.e [-1*(n) -2 -1] [0 1 2 ...n-1] [n n+1 n+2...2*n — 1] so now when you add to i + a(imodn) each i converts to some j which will be a index of one of these segments definitely.. What i am trying to say is that.. For example 1)n==3 Consider applying shuffling operation of segment [0..2] and we have a1,a2,a3 such that after shuffling 0->3,1->7,2->11 now 3 is actually at 0th position in its segment [3,4,5] 7 at 1st in [6,7,8] and 11 at 2nd position in [9,10,11] so in this example above we can see that each element results into an unique positions ,whatever be the segment it settles

    So for such kind of example always the answer is YES!!

    But consider this example

    2) n==3 and we have a1,a2,a3 such that 0->3,1->6,2->11 so now 11 is still the 2nd position but 3,6 both are ones at 0th position Therefore such array a will result in generation of elements in which no 1st position element is ever created but the 1st position elements get converted to 0th position So Vacancy will be definitely created.. So for such kind of example the answer is NO!! * HOPE YOU UNDERSTAND..

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

Can anyone explain why all numbers being distinct will not affect values of k>n?

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

    k refers to any integer and not any index of the array

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

      As because the rooms were infinite, my question was whether rooms with k>n would collide with those with k<n. It's sorted now. Thanks BTW.

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

Can someone explain C again?

The shuffle isn't k + a[k mod n]?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    The shuffle is k + (a_k mod n). So, for example, if a_1 = 12 for n = 7, room 1 will go to room 1 + (12 mod 7) which is room 6. Room 8 will also go to 8 + (a_1 mod 7) since 8 = 1 mod 7, so room 8 will go to room 8 + (12 mod 7) which is room 13. In general, room 1 + kn will go to room 1 + kn + (a_1 mod 7) = 1 + kn + 5 = 6 + kn. Hope this was helpful.

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

      Oops, I made a slight error. It is actually k + a_(k mod n). So in the example I gave where a_1 = 12 and n = 7, room 1 goes to room 1 + a_(1 mod 7) = 1 + a_1 = 13, and room 8 goes to room 8 + a_(8 mod 7) = 8 + a_1 = 20, and in general room 1 + kn goes to room 1 + kn + a_((1 + kn) mod n) = kn + 1 + a_1 = kn + 13.

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

    Yes, but notice that he is taking $$$0 \leq i < n$$$ so we have $$$i$$$ $$$mod$$$ $$$n = i$$$. The same goes for $$$j$$$.

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

      I know that, but that proof from the tutorial: i+ai≡j+aj(modn), why everything mod n ?

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Solved 3 problems before round was announced to be unranked. Never started that good :(

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Same with me. Solved A,B,C within 20 minutes. I had a significant increase in rating even if I hadn't solved any other problem.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      same to me haha,long time to escape from the level 'pupil' qvq

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

In Div2C, I have a doubt. What I did was, for each a[i], found (k+a[k mod n]), till all are positive, i.e., for every number a[i], found what (k+a[k mod n]) will be if positive and kept pushing these values to a vector. Now,if the vector has a GCD greater than 1, it means, there will be duplicates. Else, no. Can you tell what is the flaw with this?

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

The decision of making this round unrated is highly appreciable. Many of us waited to check if our solution was correct before solving a new one. Feeling sorry for the problem setter/s. He/they must have worked so hard but a bug ruined all. Hope mike will find a way through this.

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

Could anyone please tell the approach using binary search for 1345B?(card construction)

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

    Idea : I will try to find the max height possible with given cards. If all of the cards are used my answer is 1, else I will find nearest height to make possible. It's not hard to derive the formula for number of cards vs height. I think my implementation is very understandable so check out my solution, I have used goto function.

    https://codeforces.com/contest/1345/submission/79190502

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

      Thanks for the solution! Got the idea:)

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

Thanks a lot for a quick editorial :)

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

Can someone explain E in simpler terms? The concept of topological sorting is confusing me here. I understood the part of the graph being acyclic, but didn't get what they did next.

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

    Topological sorting isn't needed in this problem. The idea is, look at the numbers from a_1 to a_N in order. When you get to an index k, how do we know if we can put an A there? It's only possible if a_k is "not comparable" to any other a_i where i<k. So my solution is whenever we process an index i, we do two dfs traversals — one to mark all indices j where a_i<a_j, and one to mark all j where a_j<a_i.

    This way, when we get to a_k, we checked if it was marked in one of the two ways. If it was marked, we have to put an E at k. If it wasn't marked, we put an A. In either situation, we do the two traversals.

    In order to keep track of this, I kept two "seen" arrays — one array to mark seen vertices when going "up" the graph, and one for going down. As a result the solution was very clean.

    I also checked for cycles in the same traversal, but you don't need to do that if it's too confusing — you can do it in a separate pass.

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

      why we can not fill all cell with south pole question D/B Div2/Div1

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

        I think you replied to the wrong comment. But to answer your question:

        Your solution has to have the property that all white squares are unreachable. If you put south pole magnets everywhere, then every square will be reachable by a north pole magnet, which is bad.

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

          thanks for your reply i got my mistake . yes i replied to wrong comment because before this i asked two times and no one replied so i find random people who was online ,and u was the first one

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

      Thank you so much. That was a great explanation.

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

      Thanks, I was thinking the same way but topological sorting got me really confused that what if I'm wrong. Now it's clear.

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

Div 2 C

Example:

3

3 2 1

In the fourth test case, guests 0 and 1 are both assigned to room 3.

2

0 1

In the test case, guests 1 and 2 are both assigned to room 2.

Why we have guest 2? I see only 2 rooms — 0 and 1. If k=0 and n=2, k+a[k mod n]=0+a[0]=0, so guest 0 still sit in room 0. And other guest assigned to room 2. Where is my mistake?

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

    Read the problem statement carefully. There are infinite rooms.

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

      guests 1 and 2 are both assigned to room 2 It means, that we have 3 guests: a[0],a[1],a[2], but at the beginning we have only a[0] that will be assigned to room 0 and a[1] that will be assigned to room 2.

      Each of the two guests has their own room so we must return YES, but in example true answer in NO,because extra 3rd guest are in room 2 with guest 1

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

        in fact,we can assume that we have infinite room,each room contain a guest at the beginning.(we could think that there are infinite guests as well},so once we use the constraint to re-organize the position,all of the guest (infinite of course) will change there position by k+a[k mod n].so the example is ok whatever

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

Can someone help me in figuring out why Div2D test 50 fails? Seems like I'm counting connected components incorrectly, but I can't seem to figure it out.. .

https://codeforces.com/contest/1345/submission/79197607

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

In div2 E, let's say we add egde from j's->k's(in_degree[j's]++. Assuming resulting graph is acyclic then we can make those vertices as universal if their in_degree is equal to 0. Can someone tell me what's wrong with my logic? Below is the link to my code. https://codeforces.com/contest/1345/submission/79209006

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

    Suppose I have a graph with two nodes and an edge $$$2\to 1$$$. Node $$$2$$$ has indegree $$$0$$$, yet the statement $$$\exists x_1,\forall x_2, x_2 < x_1$$$ is false.

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

      Thanks,I didn't focused on order of xi's.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

For Div2.C, I tried a (supposed) N^2 solution and it got accepted: https://codeforces.com/contest/1345/submission/79212988 I suppose it can be proved that it will never actually do so many iterations. Otherwise, maybe test cases are not strong enough.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Does anyone know why in div1C,the answer of the testcase below: 3 2 1 2 3 2 is 1 AEE ?

shouldn't it be 2 AEA???

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

    The problem is that, x3 < x2 Now you have fixed x2, (As There exists x2 comes first in order) , so not all x3 holds x3 < x2.

    A requirement for universality is that the variable is only comparable with larger-indexed variables. It is mentioned in the 2nd paragraph of editorial.

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

In the sol. for Div2E/1C, I don't understand this

For each variable, we can find the minimum index of a node comparable to it by doing DP in forward and reverse topological order.

Please explain this.

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

    The requirement for a variable x(i) to be universal is that, In the directed acyclic graph, No node x(j) with j < i can reach x(i) and x(i) also cant reach such x(j). In other words, all nodes reachable from x(i) and reachable to x(i) should have higher labels.

    To check that, we do DP and find minimum below and minimum above in reversed graph.

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

      Can you explain this testcase:

      5 4

      1 2

      1 3

      5 1

      4 1

      The correct answer is: AEEEE.

      I can make x2 and x3 anything and set x1 as min(x2,x3), I can set x4 and x5 according to x1 , So won't the answer be 2 EAAEE. What am I missing here?

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

        Problem Statement says :

        Note that the order the variables appear in the statement is fixed. For example, if f(x1,x2):=(x1<x2) then you are not allowed to make x2 appear first and use the statement ∀x2,∃x1,x1<x2. If you assign Q1=∃ and Q2=∀, it will only be interpreted as ∃x1,∀x2,x1<x2.

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

      Can I rephrase it as

      The element with the smallest index in every chain of the poset gets 'A' rest all 'E'?

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

Dang, I really like Div2F. I had the right idea for it but didn't implement because I thought it was wrong and it was unrated anyways.

Great problems...too bad there were technical difficulties.

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

    Could you please explain the idea behind this question?

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

      Which part of the tutorial don't you understand?

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

        Simply binary search on the value of A so that we increment exactly k times. To compute the cutoffs for the x values, we can either use the quadratic formula or do another binary search. There may be ties for the Δi(x) values, but this can be handled without too much trouble. -> this part..

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

Started well off however for some reason, for div2D my submission solves all the test cases correctly on my IDE however does not seem to even get the correct answer for the very first test case when I submit it to the online judge. Any help would be appreciated — cheers

https://codeforces.com/contest/1345/submission/79218763

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

    I get two warnings when compiling that, both which might lead to undefined behavior (I got the answer 6 when running it on my computer). One is that size is ambiguous (size is a std function you included) and the second is that k isn't initialized. I compile with -Wall -Werror -Wpedantic (and I have it so Vim + YouCompleteMe highlights such errors).

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

can someone tell why is this not optimal solution Question D div 2

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

    please some one reply

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

    What's your meaning, The 3*3 grid is all colored white?

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

      that image is solution (according to me) of first sample test case

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

        This is wrong answer. Because it's not possible for a north magnet to occupy black cell after some sequence of operations from the initial placement.

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

          yup i got my mistake thanks

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

          Why in the first place do we need to place north poles in the grid? Or did I missed something? Can't the minimum no. of north poles be 0 in all cases except -1?

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

            The 0 is a acceptable answer. We need minimum the number of North poles.

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Poor Monogon.But the problems are really great.Thanks!

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

I think there is something wrong with the Div2 C for it's type. $$$(k+a_k){\bmod n}$$$ instead of $$$k+a_{k\bmod n}$$$

And does anybody tell me why k is in[0,n — 1]?

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

    actually k is included in R.because we have infinite room.once we reorganize the position,we are able to let the k pos guest move to k+a[k mod n] position

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

      o,It's my fault. But I cannot understand this code

      why need we mod n in (i + a[i] % n + n) % n; and why i in [0, n — 1]

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

        Let's divide the R into segments,each segment contain n elements;

        We find that for each ith element,it transforms to the (i + a[i] % n + n) % n th in one segment;

        if every i in [0,n-1] obey the rule -- each transformation make unique pos in those segment,then for each new position of element,it won't be the same place(not violate the rule the problem statement show)

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

          as for i in [0,n-1],we can make sure that the other segment(such as [n,2n-1])is also follow the rule

          actually,the range of i we choose could be the set which contain n successive integer

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

I had the right idea for Div2 C. Not sure where my error is, I'm pretty sure this checks if all the rooms are distinct, and it works for almost all the test cases, but fails on a couple for some reason...

http://codeforces.com/contest/1345/submission/79207288

Any help would be appreciated.

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

    Fixed your code the number you module is negative,which may cause problems

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

      Thank you! That was in fact the problem. I fixed it by replacing the insert line with

      toAdd += j; toAdd %= n; if(toAdd < 0) toAdd += n; a.insert(toAdd);

      I'm still a little confused though, because I thought my conditional (toAdd + j < 0) ? ((toAdd + j) % n) + n : (toAdd + j) % n took care of negatives. I'm new to C++ so maybe I'm misunderstanding what that expression does or how the % operator works. How was it possible for my previous code to return a negative mod?

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

        % doesn’t do the mathematical mod, it does remainder. you have to add in the modulus to get it to be the mathematical modulus.

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

          What do you mean by add in the modulus? Isn't n the modulus there? Sorry I'm a little new to programming lol.

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

            The modulus is the number that you're "modding" by. It's like the divisor in division; when you do $$$15\ /\ 5$$$, you call $$$5$$$ the divisor.

            What I mean by adding it in, is consider $$$-9\ \%\ 5$$$. The result of this expression in C++ is $$$-4$$$, but in math terms, what we want is $$$1 \equiv -9 \pmod{5}$$$. So what we can do, is when we can add $$$5$$$ to the original expression (that resulted in $$$-4$$$) to get what we want, which is $$$1$$$.

            Basically, if you want to compute $$$a \pmod{b}$$$, where $$$a$$$ can be negative, you write ((a % b) + b) % b

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

              But the expression a % b only returns the wrong value if a is negative, right? So if I have the conditional (toAdd + j < 0) ? ((toAdd + j) % n) + n : (toAdd + j) % n it checks if a is negative (in this case a is toAdd + j), and returns the bolded part where I do in fact add n (the modulus). If it's not negative I don't need to add it, I think. I'm still slightly confused. But thanks for your help!

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

    Like this? 79238791.

    I guess the problem is toAdd + j can't be negative, which makes the statements behind that meaningless.

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

Div2E/Div1C:
WA on pretest 5 -
I tried my to make a directed graph and check for a cycle. If it is acyclic, if some vertex has non-zero indegree, I give it an E, else it has an A. What is wrong with this logic? https://codeforces.com/contest/1345/submission/79197644

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

    Check this out. Link

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

    I also WA on pretest5 in contest. When I look other's AC code, I am wonder about test 15. In my program I get

    3
    AEAEA
    

    Look at pretest 3, and 1 2 is can be ignored. I wonder why test15's answer is like

    2
    AEAEE
    
»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

So unfortunate that the contest had to be unrated. The problems felt good and interesting. Hope the problem gets fixed today

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

In Div1B/ Div2D, why can't we fill all cells with South pole? Monogon

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

    yes i have the same question

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

    We can put a south pole magnet in any black cell. Out of the white cells, we can only put south pole magnets at intersections of completely white rows with completely white columns. If a row (or column) contains at least one black cell and we put a south pole magnet in one of its white cells, then the south pole magnet will be able to pull a north pole magnet from the black cell to the white area at some point, since each black cell must be reachable by a north pole magnet by the problem requirement. While all white cells must be unreachable by north pole magnets in any possible sequence of moves.

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

      Nicely explained!!

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

      Why in the first place do we need to place north poles in the grid? Or did I missed something? Can't the minimum no. of north poles be 0 in all cases except -1?

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

        Because every black cell must be reachable by a north pole magnet, it is rule #2 from the problem statement. So we need at least one north pole in each black connected component (area composed of adjacent black cells). The only case when 0 north pole magnets is the right solution is when the entire grid is white.

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

          Thanx for responding. It was written that it is possible for the N pole to reach the black cell and not must, and that's why I had such doubt.

          Don't you think the problem statement was a bit confusing in the way that it used possible instead of must there?

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

    Because North pole can't occupy white cell, and North pole can reach the cell which be occupied by South pole if they are in same Column or Row.

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

    Consider this situation.

    Spoiler

    If you fill all cells with South pole and put a North pole in the centre cell, you cannot satisfy rule 3.

    Actually pretest 2 is a good example and you should check it out.

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

    because a sequence of operations must exist for every black cell such that it ends up being occupied by a north magnet

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I think it's better to add a link below the contest announcement. Just personal advice.

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

Resume Review has some problem in explanation

"However, we can observe that this process increments the values as long as Δi(x)≥A for some constant A"

Shouldn't it be "However, we can observe that this process increments the values as long as Δi(A)≥0 for some constant A."

I.E. We find a value for 'x' such that the change function Δi(x), is positive till that value of x

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

    I TOO DIDN'T UNDERSTAND THE TUTORIAL CLEARLY

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

    See whatever i observe i think it is right for some constant A not 0 exactly cause there is this constraint sum of all b[i]'s should be exactly k , that's y As can be seen in the first test case example the value of A comes out to be -32 so it justifies

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

I don't understand this statement. Please help me.

"For each variable, we can find the minimum index of a node comparable to it by doing DP in forward and reverse topological order. Then for every variable not comparable to a smaller indexed variable, let it be universal. All other variables must be existential. Our requirement of universality proves this is optimal."

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

    I'm assuming you are familiar with the application of dynamic programming on DAG. First, you need to find a topological sort of the graph (it exists only if the graph doesn't contain any cycle). Now do a forward traversal on the topological sort and for every value 'i' calculate the minimum value of the node that appeared on a path that ends at vertex 'i' (while moving forward). This can be calculated easily by DP. Now do a backward traversal on the topological sort (also reverse the edges) and separately calculate the minimum value of the node that appeared on a path that ends at vertex 'i' (while moving backward). Now for each node, you have the minimum value of the node that is somehow connected to this node. If this minimum value is less than the value of the node then you cannot assign a universal quantifier to the node (let's say a node is 2 and the min value is 1, then either x1 < x2 or x2 < x1. In either case you cannot assign A to 2), otherwise you can assign the universal quantifier to this node. See 79647809

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

Though I got the tutorial and the logic for prob B but I'm not able to come up with the code to implement the logic. If anyone could provide their code if they have done it the way described in the tutorial.

»
3 weeks ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

[contest:Codeforces Round 639 Div B] 1345B - Card Constructions I have a very easy approach for this problem !!

formula for no. of cards with height (h) = (n*(3*n + 1))/2

This formula takes you to the status accepted : How ?

Link to my solution :

Do watch the solution , it's damn easy with efficient approach !!!

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

https://codeforces.com/contest/1345/submission/79177038 I got wa in this and it gets accepted as soon as I put (n+(i+a[i]%n))%n here https://codeforces.com/contest/1345/submission/79242347 can anyone tell me why is that I mean n+(i+a[i])%n should always give the same value as (n+(i+a[i])%n)%n can anyone help me with this

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

    what if n = 3, i = 1, a[i] = 2?

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

      it will only go in the condition when (i+a[i]) is less than zero

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

        Ok what about i=1, a[i]=-4, n=3? My point is that you are ignoring the case when I+a[I] is divisible by n.

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

    In C++ (-1%5) will be -1.

    That is why you have to compute ((-1%5) + 5)%5 which will give 4 as output.

    More on it here

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

      but 5+(-1%5) will give the same output

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

        This is what you have done one the wrong submission.

        m[n + (i + a[i]) % n];

        This is your code from the correct submission

        m[(n + (i + a[i]) % n)%n];

        Assume n=10,a[i]=10,i=0.

        You would end up getting 10 for the incorrect code, and 0 for the correct one :)

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

Thanks for your great problems. Your probs and solutions are wonderful. Keeps it up!

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Is it only me or did someone else also found div2C confusing? I loved the question but took me a long long time to decode the meaning.

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

can any one help me out why i am getting wa on 17th test case??

79245621

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

    I think you have not considered the case where some rows and columns might be empty

    Test case
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Then the shuffling works as follows. There is an array of n integers a0,a1,…,an−1. Then for each integer k, the guest in room k is moved to room number k+a [k]modn.

this is written in problem C, does this mean (k+a[k]) mod n, k + a[k] mod n, or k + a[k mod n]?. I read the editorial, it's supposed to be (k+a[k]) mod n. but k mod n has the same font size which makes it a bit confusing.

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

I am not able to find the error in my solution for 1345D. My Solution Link = https://codeforces.com/contest/1345/submission/79249181

It is giving WA on test 17 Please Help Thanks

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

    I think you have not considered the case where some rows and columns might be empty

    Test case
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

can someone explain me fifth test case of input given at div2 C problem. How the first and second guest are having the same room no. 2 after suffling?

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

    guest 1: $$$1 + a_{1 \bmod 2} = 1 + a_1 = 1 + 1 = 2$$$

    guest 2: $$$2 + a_{2 \bmod 2} = 2 + a_0 = 2 + 0 = 2$$$

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

I am asking about the fifth test case of the first test case which is given in question?

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

I got stack overflow error in Div2D during the contest, then I tried using thread as I read it somewhere. That too isn't working for me.Maximum recursion depth in my code is 10^6. Can anybody tell me how to resolve this in java!

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

that description of fifth test case of 1st test case is given wrong in question i think!!

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Div2 C detail explanation with example and code here in case anyone need :)

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

    Amazing buddy it helped so much to solve this problem :) Keep going on like this for every difficult problem . thanks for this

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

Why is this MLE? Monogon

Isin't the answer same as the editorial : 79185068

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

Div2F ai−3x2+3x−1!=ai-3x(x+1)-1 but why do work ai-3x(x+1)-1?? anyone help please

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

Can someone please explain div 2 problem F?

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

    I also need the detailed explanation on div2F/div1D. Please someone explain this problem..

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

https://codeforces.com/contest/1344/submission/79310940 (1345D Monopole Magnets)

Does anyone know what exit code -1 means? I'm not sure what is causing the runtime error. Please help. I seem to be outputting the correct answer so I am very confused.

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

    Change return -1 to return 0. Exit code is whatever the main function returns. If it does not return 0, then it becomes a runtime error.

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

      Omg, thank you! I don't think I would've figured that out, and the internet wasn't being much help.

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

For the problem — Monopole Magnets, it is written:- "every row and every column has exactly one segment of black cells or is all-white"

From what I'm understanding, there should be continuous black cells within a row or a column. No white between them.

So, if I have a 3x3 square with the middle cell (1,1) white and all other cells black. Then I can have a solution with four south magnets at the four corners ((0,0), (0,2), (2,0), and (2,2)).

Can anyone tell me if it's correct or I'm making some mistake?

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

    You are forgetting that there has to be at least one south magnet in every row and every column. In your solution, there is no south magnet in neither row 1 nor column 1. Also, both of these have two segments of black cells, so answer should be -1.

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

      Yeah, thanks. I don't know why I was forgetting this condition for this test case.

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

Thanks for the great contest And yes, feeling sad for Monogon as this contest became unrated. Sorry for the comment. BUT Am i the only one who got think the problem div2C was written wrong? As it was written in problem that guest in room k will be shifted to room k+a[k mod n] but after seeing the tutorial, i come to know that it should have been ((k+a[k]) mod n). Sorry for poor english. Plz reply Monogon

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

In Div2F/ Div1D Resume Review Problem, """Simply binary search on the value of A so that we increment exactly k times""". How exactly the binary search is giving us the optimal solution? Can anyone please explain it with some example testcases?

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

    You can think of it as what is the minimum increase we are willing to use a move for. If it's too high, than we are not using all our moves, and if it's too low, then we are wasting moves.

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

      For example, if we take a = 5 what value of (bi) I should take and why because it is always decreasing and there is no minimum ? What is the basis of minimum ? Is it value of K?

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

        The value of $$$b_i$$$ depends on $$$a_i$$$ for other types also. Try the sample test case. For each type of project, find the score for each value of $$$b_i$$$. Then find the answer for each value of $$$k$$$ from $$$1$$$ to $$$\sum a_i$$$.for each value of k find the minimum increase you got from a project you added. You'll then understand how binary search was used here.

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

I think problem B can be solved more easily. I just formed a formula, 3(n+1)n/2-n. Suppose n=1, then the 1st highest pyramid will consist of 3(1+1)1-1 = 2 cards. Here n is the number of i'th pyramid. The 2nd highest pyramid will consist of 3(2+1)2-2 = 7. You can see my code and will get the general idea. https://codeforces.com/contest/1345/submission/79398607

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

Can anyone explain why in div 2 problem c solution after getting i + a[i] , we find modulus of this term? Why is it required even one number is negative it will be on left side and not repeated please if anyone can explain this properly.

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

In Div 2 F, what if there isn't an $$$A$$$ which can make $$$b_i$$$ increase exactly $$$k$$$ times?

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

In question Hilbert and Hotel What's the difference in value of q between q=((i+p)%n+n)%n; and q=(i+p)%n;

when I am writing q=((i+p)%n+n)%n it passes all cases but with q=(i+p)%n it is not passing all test cases.

This is my Code unordered_map<ll,int> m; ll p; int flag=1; for (ll i=0;i<n;i++){ cin>>p; ll q=(i+p)%n;
if (m[q]==1)flag=0; else m[q]=1;

if (flag)cout<<"YES\n";
    else cout<<"NO\n";

Thanks in Advance!!

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

Hello! I'm new here. Don't know if this is the best place to post this but I'm having wrong answer on test case 43 for D. Haven't been able to debug. Thanks for any help! https://codeforces.com/contest/1345/submission/79673927

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

This was a very nice contest with very nice questions. Here are my solutions.

I have two questions for Monogon

  • The editorial for $$$E$$$ was a little confusing. Am I right in saying that the number of universal identifiers is equal to the number of connected components as each connected component can have exactly 1 universal identifier ?
  • Can you share the process behind how you came up with the Div $$$2$$$ $$$F$$$ ? How you formulated it and arrived at the quality function ? It was quite nice.
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Problems Well done Monogon Please write more problems on dsa you are a great setter!

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

In Hilbert's Hotel problem.... I looked at the fifth case where n=2 and the guest array is [0, 1]

here after reshuffling both do not fall on the same room no 2 i think see the calculation below: ____ for guest 0: new position is 0+ a[0 mod 2] = 0 + a[0] = 0 + 0 = 0___ for guest 1: new position is 1+ a[1 mod 2] = 1 + a[1] = 1 + 1 = 2___

ie both are not falling in the same room.

but the answer given is NO. why? they both are in 2 different rooms... the answer must be YES. please help me

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

Simplified logic for Div2C:

Basically

There are infinite elements

-INF to INF

let K goes from (-INF to INF){

let x = k + a[k % n];

which means room k goes to room x;

}

If (every k goes to different x) ans="YES" else ans="NO"

which means k1==>x and k2==>x then ans="NO"

vi b(n);

Let us consider K running from 0 to n-1{

b[k] = k + a[k];

since k % n = k

}

case1:

if b[i]==b[j]:

    x values are same in the range (0 to n-1)

    x1==x2

    where


    x1=k1+a[k1%n]  where k1 lies in (0 to n-1)
    x2=k2+a[k2%n]  where k2 lies in (0 to n-1)

    ans=NO

case2:

if b[i]%n == b[j]%n :

b[i]=i+a[i]
b[j]=j+a[j]

 if (b[i]%n == b[j]%n):
    (i+a[i])%n = (j+a[j])%n

    (i+a[i]) = i+a[i]=j+a[j]+tmp*n

    (i+a[i]) = (j+tmp*n)+a[(j+tmp*n)%n]

     (j+tmp*n)+a[(j+tmp*n)%n] is x value for k=(j+tmp*n)
     (i+a[i])                 is x value for k=i


     same x value for two k values 

     ==> ans=NO

case3:

    other than case1 and case2:
    ans=YES

    x1==x2 is not possible