SleepyShashwat's blog

Codeforces Round #663 (Div. 2) Editorial
By SleepyShashwat, history, 4 years ago, In English

Thank you for participating, and I hope you enjoyed the problems!

Also, here are video editorials by BRCode:

Tutorial is loading...

Code: 89479484

Tutorial is loading...
Code: 89479603
Tutorial is loading...
Also, thanks to shash42 for the construction using deque idea!

Code: 89479612

Tutorial is loading...
Code: 89479627
Tutorial is loading...
Code: 89479649
  • Vote: I like it
  • +507
  • Vote: I do not like it

Comments Comments (209)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

Thanks for the speedy editorial :)

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

Thanks for a good round!

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

Great round and SUPER fast Editorial, Thanks

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

Question C was really a good one! Keep it up!

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

And the award for the fastest editorial goes to..

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

Enjoyed the Round. Problem D was really nice although I didn't manage to solve in the contest

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

Great balanced round, very nice problems. Thanks to the authors!

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

Problem C: I did the same n! — 2^(n-1) but got wrong answer on pretest 6. Can anyone tell me what's wrong? Here is the link to my solution

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

    (n! + 1e9+7 — 2^(n-1))%(1e9+7)

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

    one possible issue is if (n! % mod) < (2^(n — 1) % mod), then the difference will give you a negative value, so you should output ((n! % mod) — (2^(n — 1) % mod) + mod) % mod

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

    Same mistake :(

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

the video editorials are very nice and easy to understand

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

loved the contest

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

    It's the opposite, some idiotic cheater posted this question during the round, you couldn't have done it 2 days ago. And there is no solution there

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

      .

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

        I say that it's not we who copied the question, it's this guy who copied this question from this contest during the contest, lol. How dare you?

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

        Dude he literally said someone posted it during the round

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

          Guess after ponies round, he has refused to understand anything in english lol

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

        if you solve this 2 days ago then why you unable to solve this during contest

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

        I think you only copied that question there. Xd

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

    Why don't you provide the link to the problem, which you did 2 days ago? That would be helpful.

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

    It is done during the contest. Why people are doing this nonsense?

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

Great round, fast editorial. Thank you!

For D you can also bruteforce the first column and then greedy the rest.

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

    can you please explain the brute force approach?skittles1412

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

      The main idea is greedy. You go from left to right, and for each submatrix, you toggle the rightmost bit if necessary. The brute force part is only to brute force the first column, as that isn't accounted for in the greedy solution. I think this is better explained with code. (I have only attached the greedy part, but I think it suffices)

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

        Hey, Can you explain the brute force part too? I am getting same WA as you did on your initial submissions, and I am unable to figure out the brute force.

        Do you mean to say try all possible masks for first column, and for each one of them, do greedy for the rest, and finally select the minimum?

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

          Yes. By the brute force part, I mean that you need to try all possible masks for the first column and then greedy the rest. An counterexample to a non-bruteforce approach would be:

          2 3
          100
          010

          In this testcase, the optimal solution is to toggle one of the bits in the first column, but the greedy approach without brute forcing will give the answer 2, toggling a bit in both the second and third column.

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

            Thanks!

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

              Also notice that you don't have to completely brute force.

              For the 1st column, you only need to try to toggle 0 bits and 1 bit, anything more than that is unecessary and unoptimal.

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

                Are you sure about that?

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

                  Yes. I'll give a brief proof here. So, the only point of toggling bits in the first column is to alter the parity of the submatrices in the first column.

                  Now, say that we have 2 rows, clearly toggling 2 bits is unoptimal as the parity stays the same as if we were to toggle 0 bits. On the other hand, toggling 1 bit change the parity so we need to try that.

                  Now, say that we have 3 rows. Toggling the bit at row 1 toggles the parity of the first submatrix. Toggling the bit at row 2 toggles the parity of both submatrices. Toggling the bit at row 3 toggles the parity of the last submatrix. Clearly, anything more than this is just extra toggling that we don't need.

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

                  Right. Thanks for the explanation!

                  So, for n = 3, we'll greedy the rest a total of 4 times, once without toggling any of the bits, once with toggling the bit at row1, row2, and row3 each.

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

                  Correct! And for n = 2 we only need to greedy twice, not toggling and toggling the first/second row.

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

                  Yepp. That too

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

      I used Greedy Approach, too!

      My Logic:

      See, if for n=2, all sub-matrices of (2x2) should have "odd" number of ones, then each pair of alternate columns should be of the form (odd-even) or (even-odd). Find Greedy ans. for both cases and the minimum of both, should be the final answer.

      For n=3, there are 4 cases:

      1. (Odd-Even) in above 2 columns & (Odd-Even) in below 2 columns

      2. (Odd-Even) in above 2 columns & (Even-Odd) in below 2 columns

      3. (Even-Odd) in above 2 columns & (Odd-Even) in below 2 columns

      4. (Even-Odd) in above 2 columns & (Even-Odd) in below 2 columns

      Then, greedily find the answer in all cases, and your final answer will be the minimum of all the 4 answers.

      My Submission, for more reference: Submission

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

        Great explanation!!!!

        ...............................

        if(m<n) { char ch2[n][m]; loop(i,0,n) { loop(j,0,m) { ch2[i][j]=ch[i][j]; } } loop(i,0,n) { loop(j,0,m) { ch[i][j]=ch2[j][i]; } } }

        ..........................................

        but i didn't understand this part. could you please explain?

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

          Actually, I didn't read n<=m constraint in the Problem, before I submitted my code.

          So, for the case, (m<n) (If it would have been there in the Test cases), I swapped the Rows & Columns, i.e., I took the transpose of the Current Matrix ch in the same 2-D Array ch, using a temporary 2-D Array (Matrix) ch2.

          Although, since n<=m is given in the Problem, you can just skip that part in the implementation.

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

        hey! cant we generate all possible permutations(O(2^(mn))),and then find minimum of all.

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

          No, we can't.

          Check the constraint of n*m,

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

            yeah,but neither of them can be greater than 3, right??

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

Such beautiful explanations in the 3b1b video editorials :)

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

Just wondering, most people who solved quesition C firstly generated answer for small $$$n$$$ (say up to $$$10$$$) and then used OEIS or solved problem completely without OEIS?

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

    In my case, I derived the formula. Maybe not fast enough though :)

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

    In my opinion, generating the answer for small $$$n$$$ is harder than actually solving the problem. Any hi-lo-hi will have a cycle. So, to NOT have a cycle, the numbers will have to be continuously decreasing as moving further from the highest number, $$$n$$$. This directly led me to the solution.

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

    I was wondering why so many people were using while(next_permutation(all(a)); And now I got to know why.

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

    I can't understand the question nor the editorial. Can you please explain me ?

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

Problem D: Brute submission. (Time: O(n * m))

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

    for n=3 why you cant have some odd-odd and then even-odd not odd-even ?

    Edit: i got it never mind. nice solution!

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

My C got wrong because I forgot to take (+ mod) while subtracting 2 quantities :(

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

I can change tags in problems. Is it okay?

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

Concise descriptions, decent problems (at least for me), fast system testing, and fast editorial.

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

Problem E has an interesting alternative solution. At each stage of a DFS traversal, you can split the nodes into three sets A, B, and C. Nodes in A are visited and exited the DFS call, nodes in C are unvisited, and nodes in B are visited but haven't exited the DFS call yet. Importantly, there is no edge connecting a node in A with a node in C. And the set B is a path.

We can use these properties like this. Let's DFS until A has at least n/4 nodes. If B has n/2 nodes, we found our path. Otherwise, we can pair nodes in A with nodes in C. Then for any pair of pairs, there are at most two edges (one that stays in A, and one that stays in C).

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

In D, Can anyone please find mistake in my code I tried it by generating all possible matrices of 0s and 1s but it giving wrong answer for all m,n<=4 https://codeforces.net/contest/1391/submission/89455694

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

    You are printing the generated matrices to stdout, so the grader thinks that the matrices are your intended answer, when you should only print a single number.

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

Thanks for the good round and superfast editorial!

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

Nice problems. Better than some previous contests. Any suggestions on approach to general C and D problems are welcome.

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

My solution for B has passed all pretest during contest but it gives wrong answer in testcase 25 .plz correct my solution if there is any mistake 89428467

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

    rep(i, 0, c) in the loop with c == 1 is wrong, it should be rep(i, 0, r)

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

Problem C can be solved using the recurrence : f(n) = n! — 2*(n-1)! + 2*f(n-1) Submission : 89440460

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

I loved your round SleepyShashwat. Its short, straight-forward statements saved me from unnecessary thought processes. You killed it, man.

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

I still didn't get why are we using 2^(n-1) in problem C

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

    We only need to involve the cases where there is at least one number which is surrounded by larger number on both sides. e.g. 4,2,5 or 2,1,3. So all those cases need to be removed where we don't have any number like that. That is possible if we fix the largest number and then choose some numbers and put it in its left in ascending order and put others in its right in descending order. That is, lets say we have 1,2,3,4,5,6. We will fix 6. Now we will choose some numbers, say 2 and 5 and make permutation like this: 2,5, 6,4,3,1. That way we can't have any number surrounded by larger number on both sides. In this case we chose two numbers 2 and 5 but we could choose any, even 0. which would result into 6,5,4,3,2,1 So we choose any number of numbers from these 5 numbers. In general, C(n-1, 0) + C(n-1, 1) + C(n-1, 2) +...+ C(n-1, n-1) = 2^(n-1)

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

    Another way to think that (The editorial's way): Take example of 6 numbers. Put 6 anywhere. Now take numbers in decreasing order i.e. 5, then 4 then 3...so on. For every number, you can either add it to the left side of 6 or right side. say I add 5 to the right side -> 6, 5. Now take next number (4). Add either left side or right side... Do this for all. That way we can construct the permutation and we need to avoid all these permutations. For every number except 6, we had 2 choices: either left or right. So total number of these permutations = 2^(n-1)

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it 
    consider Example n=4: 
formula: total num permutations(cycle) = total permutation — total non cyclic permutation, 
total permutation : n! -> 4!; 
total non-cycle permutation for 4 are: 
1 2 3 4 ,
1 2 4 3 ,
1 4 2 3 ,
1 4 3 2 ,
2 4 3 1 ,
2 3 4 1 ,
4 2 3 1 ,
4 3 2 1
  which is 2^(n) for a number --> 



ans = n!-2^(n-1); (P.S. : correct me if I am wrong)
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Can anyone clear one doubt of mine...we need to find number of cyclic permutations of length n. So, if i have n=4 and if i consider permutation [2,1,3,4] this is not unimodal. But still it doesn't contain a cycle of length 4 as the connected edges are [{1,2} {2,3} {1,3} {3,4}] which forms just a cycle of length 3 {1,2,3}.

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

        n refers to the length of the permutation, not the length of the cycle.

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

      1 , 4 , 2 , 3 and 4 , 2 , 3 , 1 are both cyclic you actually missed : 1 , 3 , 4 , 2 3 , 4 , 2 , 1

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

.

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

for C i tried it this way 

ll n; cin >> n;
	ll ans  = 1;
	for (ll i = 1 ; i <= n; i++) ans = (ans * i) % mod;
	
	cout << (ans - (1ll << (n - 1)) + mod ) % mod << endl;

this code prints negative number can anyone tell why??

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

    if n is bigger them 64 ,(1<<n-1) will give a very strange result

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

    Replace this cout << (ans — (1ll << (n — 1))%mod + mod ) % mod << endl; As the (1<<(n-1)) will cross 32-bit integers

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

    n can be very large (about 1e6) so it will get overflow with long long type

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

    100 > 50 but 100%27<50%27

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

Is there anyone who printed something different from $$$[1, 2, \dots, n]$$$ in 1391A - Орные подмассивы?

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

    Yes I printed n, n-1... 2, 1

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

    Printed them in reverse, just to make the OR large very quickly just to be safe.

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

wow, the explaination in q3 was really nice, i did waste a lot of time doing the math to just come up with the formula

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

Recurrence relation for problem C

$$$ dp(i) = 2 \times dp(i -1) + (i - 1)! \times (i - 2) $$$

If $$$1$$$ is not placed at the corners there always exists a cycle else we are solving the same problem again by fixing $$$1$$$ at one of the corners.

UPD: $$$dp(i) = 0$$$ if $$$i < 3$$$

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

    Can you explain this please?

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

      If $$$1$$$ is fixed at some position $$$i$$$ where $$$1 < i < n$$$ i.e, $$$\exists$$$ at least one element to its right and left. Let $$$j$$$ be the greatest element index in the left and $$$k$$$ be the greatest element index to the right of $$$1$$$, it can be proved that $$$k$$$ and $$$j$$$ are always connected. This implies that $$$i, j, k$$$ always form a cycle. When $$$1$$$ is fixed at one of these $$$(n - 2)$$$ positions remaining can be permuted in $$$(n - 1)!$$$ ways. Else if $$$1$$$ is fixed at one of the two corners we pick the next minimum element($$$2$$$) and do the same in the remaining sub-array of size $$$(n - 1)$$$.

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

My D semi-bruteforce submission: https://codeforces.net/contest/1391/submission/89444411

just notice that the first column determines the next column's xor of first two and last two rows. Then simply go through all possible first column and calculate the minimal cost.

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

D can be solved without DP.

If n==1 or m==1 output 0. If n>=4 or m>=4 output -1. Now there are two cases n by 2, and n by 3.

For n by 2 case. Let s[i] be the sum of elements in the ith row. Then s[i] and s[i+1] must have different parities as they together form a square of side 2. Then simply consider two cases, s[0] must be odd, s[0] must be even. The first row's parity defines the parity of the whole matrix. Then for each row calculate the fastest way to achieve the needed parity.

For n by 3 case. The approach is similar to n by 2. Let a[0],a[1],a[2] be the elements of some row i. Then let's denote l[i]=a[0]+a[1], and r[i]=a[1]+a[2]. Then there are four cases to consider: l[0] is even, r[0] is odd, similarly (odd,even), (odd,odd), and (even, even). Again, the first row defines everything. If r[i] is (even,even) r[i+1] has to be (odd,odd). If r[i] is (odd,even) the next must be (even,odd). For each of the four cases there exist two quite obvious strings. For example, for (odd,even) it is 100 and 011.

I believe this approach is fundamentally the same with the solution in the editorial, however, I guess my solution cannot be categorized as DP but rather as kind of a brute force which is maybe easier for some people to understand.

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

    Yes, I also thought the solution was DP but then I realized while implementing that there is no actual choice in the recurrence, you are simply doing what you are forced to do after the first choice has been made. I don't think it can really be called a DP problem.

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

/*Deleted*/

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

Why the problem D named 505?

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

Tag C as a combinatorics problem

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

With all the respect to the aesthetics of writing problem statements, I am now convinced that short formal statements are the best.

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

First 2 problems felt more like Div. 3 problems

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

Can anyone please explain this, in the cyclic permutation what does it mean by "If for any i,we make edges on both sides of it, this will create a simple cycle of length 3"? Thanks in advance!

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

    Suppose we make edges to indices j and k, there will also be an edge from j to k or k to j, as the values are distinct.

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

      You really worked hard on your photo there, didn't you? XD

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

Nice problemset, here's my video solutions for all problems + very funny moment at the end :)

https://youtu.be/c3mjIQR902k

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

what is answer for

4 1

1

1

1

1

for question D

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

In my opinion the tests for D are not very good because there are no tests with $$$\min(m,n) > 3$$$ except the example.

I think the observation that $$$n \ge 4 \Rightarrow$$$ no solution is very important, and there should be some test that checks if a submission correctly handles this, like test #48 (which is my hack)

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

    Agreed. A solution that simply brute forces all possible even sub matrices could also (possibly) pass, as there aren't any testcases with n = 1000, m = 1000, which has too many even length sub matrices to enumerate.

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

    Hello,

    I just realized that I did something very dumb. This is the part of the random generator which sets $$$n$$$ and $$$m$$$.

    Spoiler

    Most of the cases had parameters as $$$\text{(2 -1)}$$$, $$$\text{(3 -1)}$$$, $$$\text{(3 333333)}$$$ etc. Additionally, I had some cases with $$$\text{(-1 -1)}$$$ which I thought would print matrices where the answer is -1, but I completely forgot that I pick $$$n$$$ between $$$1$$$ and $$$10^6$$$, not $$$1$$$ and $$$10^3$$$.

    I am sorry for this, and I hope not many people were affected.

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

    I came up with the n>=4 observation but could not figure out how to approach for n<4 :D

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

Shouldn't the time complexity of B be O(n + m) instead of O(n * m)?

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

Why we need to add MOD with (l-r)

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

    Because (l-r) might be less than 0 and if you take modulo, it would still be negative.

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

      What is the problem if l-r < 0

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

        try to extract mod from negative numbers and you'll see the difference.

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

    Because (l-r) can be negative and modulo of negative would be negative. but the answer would instead be positive.

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

Very good work of the problem setters, C and D were very interesting. Thank you for the contest!

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

In problem D, I used the logic of alternating same and opposite bits, but got wrong answer in pretest 9, can anyone explain what's my mistake, my solution is here

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

Very nice contest. And video editorials are awesome. Thanks for them.

Loved Problem C. One of the rarest times when my thought process for this type of problems matched with others :P

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

The constraint in problem 4 is pow( 10, 6) but editorial is using bit masking... I am unable to understand >> Need help!!

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

    If both n and m are greater than 4, then there exists a 4x4 submatrix. This is made of 4 2x2 submatrices, and they're all supposed to have an odd number of ones. Odd + odd + odd + odd = even, so the 4x4 submatrix does not have an odd number of 1s.

    So if n > 3, and m > 3, then just output -1 without running the bitmask DP.

    Run the bitmask on the dimension which is less than 4 so there are only 2^3 combinations.

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

      Yes, I got it when I read it again That's a nice problem. And thank YOu also for replying

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

Regarding Problem C, I came to the conclusion that the answer is (n! — number_of_permutations_which_have_a_peak).

A permutation which has a peak can be stated as having some initial part of it sorted in ascending order and remaining part in descending order. Although, I couldn't really figure out how to calculate that number, the number of above-described permutations. I would really appreciate it if someone could explain how this can be done. Or if you didn't think of this approach, how else were you able to come up with the solution.

Thanks.

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

    This is also how I thought of the solution.

    Such a permutation with a peak you describe can be defined entirely by the ascending part. For example, if I told you that N=5 and the ascending part is {3, 1}, then the permutation must be [1, 3, 5, 4, 2]. In other words, you take the ascending part and sort it in ascending order, and then you take the remaining numbers and sort them in descending order.

    Any subset of the N numbers can be the ascending part.

    However, there is some ambiguity at the boundary between the ascending and descending parts. If the peak is bigger than both of its neighbours, is it part of the ascending part or the descending part?

    Firstly, the peak will be the number N (i.e., the largest number in the permutation). Let's decide that it will always be part of the ascending portion.

    Then we have to count how many subsets there are of {1..(n-1)} and for each one we will insert N into it. There are 2^x subsets of a set of size x, so there are 2^(n-1) subsets and so there are 2^(n-1) such "unimodal permutations"

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

BRCode Comment or post smth so that we can give you a contribution for your amazing work

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

Memes time.

A — Suborrays

117383277-361989664806569-3264014906958247775-n 117414246-1365836310291930-5767417289544658137-n

C — Cyclic Permutations 117427957-631798980774245-59686289827328330-n

Explanation

117329244-1757742091042989-4683920501538199287-n

Explanation

The editorial
117294834-746360439515480-2424750076150834485-n

E — Pairs of Pairs 117339984-718618315370218-649824027994725929-n

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

Problem C:In a cyclic permutation of length n ,what should be the length of the graph cycle? is it only 'n' or in the range [3,n]?can someone plz clear my doubt? Thank in advance!

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

Here's a solution for D in O(n*m) without DP with much shorter code then I've seen in other posts (main part is basically 10 lines) https://codeforces.net/contest/1391/submission/89535074

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

    n<=m is always true, so you can make it even shorter

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

      Ah thx, I didn't notice that. I updated the code.

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

    Please explain.

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

      I also solved D, without DP, in O(n*m)

      My Logic:

      n<=m (Given in the Problem)

      If n=1, then the Matrix is Good, so, answer=0.

      If n>3, then we can't make the Matrix Good in any way, so answer=-1.

      See, if for n=2, all sub-matrices of (2x2) should have "odd" number of ones, then each pair of alternate columns should be of the form (odd-even) or (even-odd). Find Greedy ans. for both cases and the minimum of both, should be the final answer.

      For n=3, there are 4 cases:

      (Odd-Even) in above 2 columns & (Odd-Even) in below 2 columns

      (Odd-Even) in above 2 columns & (Even-Odd) in below 2 columns

      (Even-Odd) in above 2 columns & (Odd-Even) in below 2 columns

      (Even-Odd) in above 2 columns & (Even-Odd) in below 2 columns

      Then, greedily find the answer in all cases, and your final answer will be the minimum of all the 4 answers.

      My Submission, for more reference: Submission

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

      For n=3: Split a 2x2 square in half. If one half is even, the other had to be odd and vice-versa. So a[1][i]+a[2][i]=/=a[1][i+1]+a[2][i+1] mod 2.

      Also a[1][i]+a[1][i+1]=/=a[2][i]+a[2][i+1]=/=a[3][i]+a[3][i+1] so a[1][i]+a[1][i+1]=a[3][i]+a[3][i+1] so a[1][i]+a[3][i]==a[1][i+1]+a[3][i+1] mod 2.

      So a[1][i]+a[2][i] alternate while a[1][i]+a[3][i] stay the same, so everything depends only on the first column. Also, you can show these are sufficient conditions for the whole matrix to be good. You can fix any column that doesn't satisfy these conditions in just 1 move. So just look for which initial first row you have the least columns to fix.

      n=2 is same but only with the alternating condition.

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

        I still don't get your solution. Can you please briefly comment your code:

        for(int i=1;i<=m;i++){
    x[i]=(a[1][i]+a[2][i]+i)%2; // 1-2 row alternation
    if(n==3) y[i]=(a[1][i]+a[3][i])%2; // 1-3 row sameness
    cnt[x[i]][y[i]]++; // ?????
}
cout << m-max(max(cnt[0][0],cnt[1][0]),max(cnt[0][1],cnt[1][1])); // ?????

        so everything depends only on the first column

        No, everything depends on the first column And the first row

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

          In the final array after doing changes, x[i] has to alternate between 0 and 1 while y[i] has to stay constant. So fixing x[1] and y[1] fixes what all other x and y values have to be. So cnt[a][b] is the number of changes we have to make if x[1]=a and y[1]=b. To find cnt[a][b]: for every i, we have 4 possibilities:

          • x[i] is correct, y[i] is correct, 0 changes
          • x[i] is wrong, y[i] is correct, change a[2][i], 1 change
          • x[i] is correct, y[i] is wrong, change a[3][i], 1 change
          • x[i] is wrong, y[i] is wrong, change a[1][i], 1 change

          So we always can fix a column in 1 change, so just look for which initial x[1] and y[1] we have to make least changes.

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

For Problem D: Can someone help me figure out the non-bitmask DP solution for n x 2 case? Also, let me know if this case is equivalent to this problem: You are given a binary string. An operation comprises of selecting an index i and then toggling the bits of ith and i+1th index. find the minimum number of operations to make all 1s.

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

    Realize that if 1st column has odd number of ones then 2nd column would have even number of ones and 3rd column would have odd and so on. So there are 2 cases in the optimal case either 1st column would have odd number of ones or even. So just workout for these 2 cases. ig they are not equivalent.

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

Please also add solution code

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

When do problems receive a rating tag?

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

I wonder why I can't read the code for learning and it said "You are not allowed to read the page!"

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

It says "you are not allowed to view the requested page" when I click on the solution code.

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

Can someone give the solution code of E to me? Thanks

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

Unable to view the solution codes. It says "you are not allowed to view the requested page".

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

PROBLEM C. Why is it giving WA. can anyone help me? [submission:89473526][My Submission code](https://codeforces.net/contest/1391/submission/89473526)

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

I love Indian round because their tutorials are fucking fast. Love U.

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

if standard time complexity of problem D is 8*8*m, it is does not matter for c++ whit time limit 1 or 2 second. But python can not pass in O(8*8*m), it is unfair. The tester should test problems under serval languages to decide time limit, as far as this problem, 2s is reasonable for all players

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

In problem D, there isn't any need to explicitly calculate the transition states from $$$pmask$$$ to $$$cmask$$$. In the case when $$$n=2$$$, the transition occurs only when $$$pmask \oplus cmask$$$ is equal to $$$1$$$ or $$$2$$$ i.e. $$$01$$$ or $$$10$$$ in binary representation respectively. Similarly in the case when $$$n=3$$$, the transition occurs only when $$$pmask \oplus cmask$$$ is equal to $$$2$$$ or $$$5$$$ i.e. $$$010$$$ or $$$101$$$ in binary representation respectively.

Reason
Transition Snippet when n = 3
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What are pmask and cmask?? what do those variables represent??

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

      It is the same as mentioned in the editorial above. $$$pmask$$$ is the bit-mask for the previous column and $$$cmask$$$ is the bit-mask for the current column.

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

UNDERSTOOD.

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

    can u please explain why?

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

      i understand taking some cases, i put 1 in four corner of 4 x 4 matrix then when i try to make other 2 x 2 matrix to make odd then i end up making other matrix even, also try others combination of putting 1 in different location. i would suggest you to take 4 x 2 matrix try to make it odd you will understand.

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

        sorry i thought you meant that there are only four 2*2s in one 4*4 because that is what the video editorial says as well

        i can prove by code https://ideone.com/oaaysP

        this prints all 4*4s such that all 2*2s inside of it have odd number of 1s in it

        also, none of the 4*4s i printed have an odd number of ones

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

My overkill for E without dfs trees:

A natural idea to get long paths is: start with a node, and keep trying to extend the path by picking a node outside the path adjacent to its endpoint, and making it the new endpoint. Let's call the path $$$p$$$ and the set of nodes outside it $$$s$$$. After you're done extending, the endpoint of the path is not adjacent to any node in $$$s$$$. So maybe we can try this: if $$$s$$$ is empty, terminate. Otherwise, pair our endpoint with any node from $$$s$$$, remove the endpoint from $$$p$$$ and its pair from $$$s$$$, and try extending again.

After we're done, every node is either in a pair or in $$$p$$$, so one of them has size at least $$$\lceil\frac{n}{2}\rceil$$$. If it's the path, it's indeed a simple path and we can print it, but what about the pairing?

Let's look at 2 pairs $$$(a,b)$$$ and $$$(c,d)$$$. WLOG, assume the first node in the pair is the one we got from $$$p$$$ and the second is the one we got from $$$s$$$. Also, assume $$$a$$$ was paired before $$$c$$$. We know the edges $$$(a,b)$$$ and $$$(c,d)$$$ can't exist. We also know $$$(a,d)$$$ can't exist because when $$$a$$$ was in the path, $$$d$$$ was in $$$s$$$ and we couldn't extend with it. The other edges can sadly exist, so this only solves a weaker version of the problem with $$$3$$$ edges.

Let's see how to fix this. If $$$c$$$ wasn't in the path when $$$a$$$ was, the edge $$$(a,c)$$$ doesn't exist and we're golden. Otherwise, $$$c$$$ is in the path, so maybe we can try to guarantee $$$(c,b)$$$ doesn't exist. Instead of picking an arbitrary pair for $$$a$$$, let's define $$$o_i$$$ as the index of the last node in $$$p$$$ adjacent to $$$i$$$. We'll pair $$$a$$$ with the node in $$$s$$$ that has minimal $$$o_b$$$. What does that do? By the time our algorithm reaches node $$$c$$$ in the path, $$$s$$$ has to be empty, because every single node in $$$s$$$ is connected to something that appears later in the path, and the something will necessarily remove it from $$$s$$$ before we get to $$$c$$$, so if the edge $$$(c,b)$$$ exists, $$$c$$$ can't actually be in the pairing, and we have a contradiction!

Code: 89478031

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

Can anybody help me with C?? For n=4; I can only think 4123,4213,3124,3214 which have simple cycle. May be i m mistaking in understanding simple cycle. please can anybody tell me how answer is 16.

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

    write a code to calculate all permutations... and find the graph and check for cycles in each graph...

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

      can u please tell me just 1 more permutation of length 4 other than above 4

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

        4123, 4132, 4231, 4213 And reverse of them.

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

          i m still confused. In question it was written that there should be a edge b/w ai and ak but, in 4231 And 4132 there is no such edge b/w first and last indices

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

            What is the definition of k? Why can't k be 3?

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

Time complexity for Problem B should be O(m+n) and not O(m*n) (as given in the editorial). Correct me if I am wrong.

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

    Before calculate the answer you have to read the whole matrix, it takes n*m (it's size)

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

      Hey please help me with this doubt-> why not dp solution for B?

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

        Because it's not necesary, you don't need to change anything inside the matrix, the best choice is always change the last row and the last column, if the last has the form "RRR..." and the last column "DDD..." then doesn't matter the configuration of the remain matrix, any luggage will reach the end eventually.

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

          what if our matrix is

          RRRRRRRR
RRDRRRRR
RRRRRRRC

          Here we only have to change one R to D, but answer will be 2 according to editorial

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

            You have to change the two R's of the last column. What R do you would change?

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

anyone please explain the solution of problrm D

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

    Bro, help me with B, why not dp solution?

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

      You can move right and down only..So,no matter from where do u start initially u must come either down most row or right most column.So every cell in the right most column should be 'D' and every cell in down most row should be 'R' to reach (n,m) cell

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

    I used Greedy Approach.

    My Logic:

    n<=m (Given in the Problem)

    If n=1, then the Matrix is Good, so, answer=0.

    If n>3, then we can't make the Matrix Good in any way, so answer=-1.

    See, if for n=2, all sub-matrices of (2x2) should have "odd" number of ones, then each pair of alternate columns should be of the form (odd-even) or (even-odd). Find Greedy ans. for both cases and the minimum of both, should be the final answer.

    For n=3, there are 4 cases:

    (Odd-Even) in above 2 columns & (Odd-Even) in below 2 columns

    (Odd-Even) in above 2 columns & (Even-Odd) in below 2 columns

    (Even-Odd) in above 2 columns & (Odd-Even) in below 2 columns

    (Even-Odd) in above 2 columns & (Even-Odd) in below 2 columns

    Then, greedily find the answer in all cases, and your final answer will be the minimum of all the 4 answers.

    My Submission, for more reference: Submission

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

Solved D in O(m*n3). 89479757

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

    Can you explain your approach?

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

      I solved it Greedily in O(n*m).

      Check this, for clear and more brief understanding: Comment

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

I was able to figure out the solution for 3rd problem but couldn't figure out what to do with -ve values.. why do we add MOD to result if it is -ve?

UPD I got it :)

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

I had a different solution for Problem C. Observe that if one is not at the ends of the array, then it will definitely have a left and a right neighbour connected to it. One of this neighbour will definitely be connected to the other and hence we get a cycle. If one is at the left or the right end, there will be no edges to it and the problem is effectively reduced to that of size one less than original.

Hence, we get the recursion F(n) = (n-2)*(n-1)! + 2*F(n-1). Submission:89426244

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

SleepyShashwat BRCode Thank you for making the editorials much dynamic and easy to understand, as a newb, I always search for a complete problem set video editorials. Hope it'll be continued in upcoming contests also. Great Work :)

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

Video editorials were really nice. Thank you!

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

Hey i just noticed that for problem D there isn't a test case where n>3 and m<=3. I mean in that case min(n,m) <= 3, so a answer should exist. So, i tried running one test case on my own —

4 3

101

111

000

001

Here ans should be 2. But i tried to run SleepyShashwat's code with this test case and it gives answer as 0. Can someone explain to me why that's happening?

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

"We use the fact that for any set of numbers, it's bitwise OR is at least the maximum value in it"

The above statement is confusing for me. 1 ^ 2 ^ 3 = 0 which contradict the statement... Please I need someone to help clarify.

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

    Check difference between bitwise XOR operator and bitwise OR operator.

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

Were the test cases hard to prepare for div1B? How did you go about it? Also, is there any test case where both a. for any out degree from 1 to k, there is at least one vertex having that out degree b. the answer is big (i.e. > 1000, say) hold? I can't think of any test case like this, but I find it a relevant question: If there are only a few solutions, some more permissive heuristics + brut-force check would also solve the problem. UPD: Ups, sorry, this was meant to be a message for the 664th round..

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

why would the solution for problem B work? for example, given a test case like the following:

4 4
RDRR
DDRR
DRRD
DDDC

it would scan the edges, but there is already a path that exists that takes the luggage to the "C" slot, giving the output of 5, when the correct answer is 0.

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

    It says in the statement that initially luggage could be placed in any cell.

    So , if luggage starts on wrong edge , it would be thrown out directly.

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

My solution for Problem C

https://www.youtube.com/watch?v=iGF1XfxtA74

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

When we are creating the total no of unimodal permutation, we will have n choices for the large element n to put in the permutation and then we further have 2 choices for rest of the elements.So the total no of unimodal permuation should be n * 2^(n — 1). Why you are not considering n?

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

    The position of $$$n$$$ can be uniquely determined by the number of times you add a number to the front of the deque, so if you fix the position of $$$n$$$ to be $$$i$$$ at the start, we should only consider those ways of adding numbers to the deque where we perform exactly $$$i-1$$$ front operations.

    → Reply