Thanks for the speedy editorial :)

Thanks for a good round!

Great round and SUPER fast Editorial, Thanks

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

And the award for the fastest editorial goes to..

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

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

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

the video editorials are very nice and easy to understand

loved the contest

Great round, fast editorial. Thank you!

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

Such beautiful explanations in the 3b1b video editorials :)

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?

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

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

I can change tags in problems. Is it okay?

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

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

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

Thanks for the good round and superfast editorial!

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

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

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

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

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

.

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

Is there anyone who printed something different from $$$[1, 2, \dots, n]$$$ in 1391A - Suborrays?

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

Recurrence relation for problem C

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

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.

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.

/*Deleted*/

Why the problem D named 505?

Tag C as a combinatorics problem

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

First 2 problems felt more like Div. 3 problems

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!

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

https://youtu.be/c3mjIQR902k

what is answer for

4 1

1

1

1

1

for question D

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)

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

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

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

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

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

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

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.

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

Memes time.

A — Suborrays

C — Cyclic Permutations

The editorial

E — Pairs of Pairs

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!

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

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.

Please also add solution code

When do problems receive a rating tag?

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

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

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

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

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

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

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

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.

for (ll i = 1; i < m; i++) {
    for (ll cmask = 0; cmask < 8; cmask++) {
        ll cost = (mat[0][i] != (cmask & 1)) + (mat[1][i] != ((cmask >> 1) & 1)) + (mat[2][i] !((cmask >> 2) & 1));
        for (ll pmask = 0; pmask < 8; pmask++) {
            if ((cmask ^ pmask) == 2 || (cmask ^ pmask) == 5) {
                dp[i][cmask] = min(dp[i][cmask], dp[i - 1][pmask] + cost);
            }
        }
    }
}