SleepyShashwat's blog

By SleepyShashwat, history, 7 weeks 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

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

Thanks for the speedy editorial :)

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

Thanks for a good round!

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

Great round and SUPER fast Editorial, Thanks

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

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

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

And the award for the fastest editorial goes to..

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

Thanks for the video editorials.

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

Editorial is so fast!!

»
7 weeks 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

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

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

»
7 weeks 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

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

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

  • »
    »
    7 weeks 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

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

    (fast-two)%mod can be negative if (fast-two) is negative

    correct : (fast-two+mod) %mod

    I think this would do

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

      Can you please prove why adding mod will give correct result?

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

        Normally, n! would always be greater than 2^(n-1) however since we are modding both, there are cases when n! < 2^(n-1) is true.

        Therefore, (n!-2^(n-1)) can be negative. How can we fix this? Well, all MOD does is find the remainder of values during division. So, if we add mod to something, its remainder shouldn't change.

        Thus, we can add mod to negative numbers so the result is positive, how we want it, and adding mod to positive numbers won't affect the answer so...

        ((n!%MOD)-(2^(n-1)%MOD)+MOD)%MOD will output the correct answer for all cases.

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

    Same mistake :(

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

the video editorials are very nice and easy to understand

»
7 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Question C can be googled....Though I couldn't solve it...

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

Great round and short problem statement and thanks for speedy tutorial!

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

loved the contest

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

    angelina karel

  • »
    »
    7 weeks 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

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

      .

      • »
        »
        »
        »
        7 weeks 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?

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

        Dude he literally said someone posted it during the round

        • »
          »
          »
          »
          »
          7 weeks 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

      • »
        »
        »
        »
        7 weeks 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

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

          He said he couldn't attend the contest...

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

        I think you only copied that question there. Xd

  • »
    »
    7 weeks 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.

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

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

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

    The question is posted during the contest. so some person pasted it not that it was there! and its impossible you saw the same question 2 days agp

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

    It is posted during the contest by someone and how could you see it two days ago?? stop blaming the problem setter ,they have that much of brain that they can make a unique question everytime.

»
7 weeks 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.

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

    can you please explain the brute force approach?skittles1412

    • »
      »
      »
      7 weeks 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
      • »
        »
        »
        »
        7 weeks 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?

        • »
          »
          »
          »
          »
          7 weeks 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.

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

            Thanks!

            • »
              »
              »
              »
              »
              »
              »
              7 weeks 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.

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

                Are you sure about that?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks 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.

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

                  Yepp. That too

    • »
      »
      »
      7 weeks 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

      • »
        »
        »
        »
        7 weeks 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?

        • »
          »
          »
          »
          »
          7 weeks 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.

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

            okay okay got it ..thanks

      • »
        »
        »
        »
        7 weeks 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.

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

          No, we can't.

          Check the constraint of n*m,

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

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

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

              If one is less than 4 other can go upto 10^6

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

Such beautiful explanations in the 3b1b video editorials :)

»
7 weeks 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?

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

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

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

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

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

  • »
    »
    7 weeks 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!

»
7 weeks 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 :(

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

I can change tags in problems. Is it okay?

»
7 weeks 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.

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

Problem C is just too cool and good! Enjoyed the contest and thanks for the tutorial

»
7 weeks 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).

»
7 weeks 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.com/contest/1391/submission/89455694

  • »
    »
    7 weeks 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.

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

Thanks for the good round and superfast editorial!

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

This is really a good round but still I was not able to clear B

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

    I thought dp solution for B, my bad luck.

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

      same here but realize that I have change in the last column or last row at 50 secs before ending

»
7 weeks 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.

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

The round and its editorial are very nicely designed.

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

Thank You for the super fast editorial :)))

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

I have thought the solution in problems C but I don't believe that solution is true T___T . Too bad

»
7 weeks 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

»
7 weeks 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

»
7 weeks 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.

»
7 weeks 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

  • »
    »
    7 weeks 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)

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

    Because the number of non-cylic ways are 2^(n-1).

    Take total ways: n! and subtract noncyclic: 2^(n-1).

    Why? Because decreasing numbers need to be adjacent to its higher number for there to be no cycles. for size four.

    1234

    1 way to arrange 4. 2 ways to arrange 3 around 4 (34,43) 2 ways to arrange 2 around 34/43 (2[34/43],[34/43]2) 2 ways to arrange 1 around 234 (1[234],[234]1)

    So therefore number of no cycles will be the (2^(n-1)). Did everyone else think the same?

  • »
    »
    7 weeks 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)

  • »
    »
    7 weeks 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)
    
    • »
      »
      »
      7 weeks 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}.

      • »
        »
        »
        »
        7 weeks 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.

    • »
      »
      »
      7 weeks 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

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

.

»
7 weeks 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??

  • »
    »
    7 weeks 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

  • »
    »
    7 weeks 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

  • »
    »
    7 weeks 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

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

    100 > 50 but 100%27<50%27

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

    2^(n-1) could be larger than ans. Its very large for 10^6. The worst case.

    So possible solution is to take 2^something with loop, taking modulo 10^9+7 in every iteration.

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

HaPpY to see the official video editorials, great, thanks

»
7 weeks 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 - Орные подмассивы?

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

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

  • »
    »
    7 weeks 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.

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

Has anyone got wrong answer on testcase 25 in question B

»
7 weeks 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

»
7 weeks 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$$$

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

    Can you explain this please?

    • »
      »
      »
      7 weeks 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)$$$.

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

My D semi-bruteforce submission: https://codeforces.com/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.

»
7 weeks 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.

  • »
    »
    7 weeks 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.

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

/*Deleted*/

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

Why the problem D named 505?

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

    Maybe because this matrix is good

    101
    000
    101
    
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      horizontally and vertically...both ways read the binary representation of 505...cool

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

      Woah.. cool!

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

    Can you please provide an intuition for problem D

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

Tag C as a combinatorics problem

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

Adding implementations to the editorial looks better understanding.

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

For C ,i came up with the logic that bitonic sequences will not result in any cycles. So we just have to subtract them from n! . Is this logic correct??

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

For those who are wondering how 2^(n-1) comes in the editorial, first see this figure to convince yourself that the cycle will not exist only when the permutation will have one maxima,

Now we are going to find all the permutation with one maxima ,

  • We can divide the plot into 2 parts ie, left of maxima and right of maxima.
  • elements on the left will be strictly increasing and right will be strictly decreasing
  • We will take all the 2^(n-1) sub-sequences of the remaining (n-1) elements.
  • We will place each sub-sequence on the left in increasing order and remaining elements on the right in decreasing order.
Eg.
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    basically number of bitonic permutations ,right!!

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

      Yes , that's a nice way to put it, I didnt knew the terminology tbh.Thanks

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

How do you figure out these formulas, especially weird and obscure ones (in my opinion) in contest? Is there any hints as to what made you think that way and get it?

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

    when nothing strikes just make a simple brute force program of what is happening in that questn and try to observe the pattern it helps in many cases...

»
7 weeks 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.

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

    exactly, long problem statements frustates me.

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

First 2 problems felt more like Div. 3 problems

»
7 weeks 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!

  • »
    »
    7 weeks 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.

»
7 weeks 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

»
7 weeks 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

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

Thanks for the video editorials, I think sometimes it is more useful than the normal editorials.

»
7 weeks 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)

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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

»
7 weeks 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)?

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

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

  • »
    »
    7 weeks 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.

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

      What is the problem if l-r < 0

      • »
        »
        »
        »
        7 weeks 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.

  • »
    »
    7 weeks 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.

»
7 weeks 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!

»
7 weeks 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

»
7 weeks 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

»
7 weeks 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!!

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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

»
7 weeks 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.

  • »
    »
    7 weeks 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"

»
7 weeks 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

»
7 weeks 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

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

    LOL, I scanned the page super fast and didn't see permutation on the top of problem A ._.

    I just outputed all Intger.MAX_INT's. ):. Yes, I fixed it... but still ):.

»
7 weeks 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!

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

    any cycle, be it 3 or n (and anything in between obv.). They wrote any simple cycle would work.

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

Can anyone explain why my C solution failed pretest 6 when I used unsigned long long instead of long long ?

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

ok. Got it video is little helpful

»
7 weeks 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.com/contest/1391/submission/89535074

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

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

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

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

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

    Please explain.

    • »
      »
      »
      7 weeks 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

    • »
      »
      »
      7 weeks 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.

      • »
        »
        »
        »
        7 weeks 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

        • »
          »
          »
          »
          »
          7 weeks 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.

»
7 weeks 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.

  • »
    »
    7 weeks 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.

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

Please also add solution code

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

When do problems receive a rating tag?

»
7 weeks 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!"

»
7 weeks 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.

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

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

»
7 weeks 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".

»
7 weeks 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.com/contest/1391/submission/89473526)

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

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

»
7 weeks 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

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

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

    • »
      »
      »
      7 weeks 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.

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

UNDERSTOOD.

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

    can u please explain why?

    • »
      »
      »
      7 weeks 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.

      • »
        »
        »
        »
        7 weeks 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

»
7 weeks 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

»
7 weeks 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.

  • »
    »
    7 weeks 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...

    • »
      »
      »
      7 weeks 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

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

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

        • »
          »
          »
          »
          »
          7 weeks 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

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

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

»
7 weeks 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.

  • »
    »
    7 weeks 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)

    • »
      »
      »
      7 weeks 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?

      • »
        »
        »
        »
        7 weeks 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.

        • »
          »
          »
          »
          »
          7 weeks 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

          • »
            »
            »
            »
            »
            »
            7 weeks 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?

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

      oh sorry, you are right!!

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

anyone please explain the solution of problrm D

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

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

    • »
      »
      »
      7 weeks 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

  • »
    »
    7 weeks 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

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

Solved D in O(m*n3). 89479757

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

    Can you explain your approach?

    • »
      »
      »
      7 weeks 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

»
7 weeks 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 :)

»
7 weeks 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

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

Test cases for task $$$E$$$ were pretty weak, several test cases that had potential to give TLE verdict were missing

»
7 weeks 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 :)

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

Video editorials were really nice. Thank you!

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

Not unimodal,but arc permutations. In C.

»
7 weeks 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?

»
7 weeks 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.

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

    Check difference between bitwise XOR operator and bitwise OR operator.

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

      oh.. I guess I really didn't understand both tbh.

      Thanks so much for the response...

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

Codeforces editorials are getting better day by day...This time with video explanation. Hope to see more contest like this.. :)

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

Hope to get video editorials like these for every contest !! Would be really helpful for beginners to understand D,E problems easily !!

»
7 weeks 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..

»
6 weeks 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.

  • »
    »
    6 weeks 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.

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

      oh i see, looks like i didnt read the problem carefully. thanks

»
6 weeks ago, # |
  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

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?

  • »
    »
    3 weeks 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.

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

Problem D is soo hard