Codeforces Round #663 (Div. 2) Editorial

4 years ago, # ^ |

-30

How do you know what happened in 2019? you registered 2 months ago

→ Reply

IamSKK

4 years ago, # ^ |

Are you detective ?

→ Reply

4 years ago, # ^ |

No, I'm programmer.

→ Reply

parthsarthi

4 years ago, # ^ |

did they cancel the round after that?

→ Reply

1802042

4 years ago, # ^ |

Why would they? We are too loyal, u know :p

→ Reply

ashish_kumarsoni

4 years ago, # ^ |

lol :)

→ Reply

roshan_mehta

4 years ago, # |

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

→ Reply

fatemender

4 years ago, # |

+15

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

→ Reply

AbhayChandna

4 years ago, # |

← Rev. 2 →

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

krhythm32

4 years ago, # ^ |

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

→ Reply

AbhayChandna

4 years ago, # ^ |

Thanks.

→ Reply

fishy15

4 years ago, # ^ |

+15

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

AbhayChandna

4 years ago, # ^ |

Thanks for the explanation.

→ Reply

mrslowmo

4 years ago, # ^ |

Same mistake :(

→ Reply

fishy15

4 years ago, # |

the video editorials are very nice and easy to understand

→ Reply

4e1s3n8e7g

4 years ago, # |

← Rev. 2 →

-117

loved the contest

→ Reply

antontrygubO_o

4 years ago, # ^ |

+116

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

4e1s3n8e7g

4 years ago, # ^ |

← Rev. 2 →

-123

→ Reply

antontrygubO_o

4 years ago, # ^ |

+59

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

Submit_Galactic_Algo

4 years ago, # ^ |

Dude he literally said someone posted it during the round

→ Reply

SkyDreams

4 years ago, # ^ |

+30

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

→ Reply

Joker22

4 years ago, # ^ |

+13

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

→ Reply

NIGHTKING_291

4 years ago, # ^ |

+19

I think you only copied that question there. Xd

→ Reply

Flower08

4 years ago, # ^ |

+11

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

→ Reply

biranchi

4 years ago, # ^ |

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

→ Reply

4 years ago, # |

+38

Great round, fast editorial. Thank you!

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

→ Reply

triedodin

4 years ago, # ^ |

← Rev. 2 →

can you please explain the brute force approach?skittles1412

→ Reply

4 years ago, # ^ |

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

	public int solve(boolean[][] arr) {
		int n = arr.length, m = arr[0].length, x = min(n, m);
		if(x==2) {
			int ans = 0;
			for(int i = 0; i<m-1; i++) {
				int sum = 0;
				for(int a = 0; a<2; a++) {
					for(int b = i; b<i+2; b++) {
						if(arr[a][b]) {
							sum++;
						}
					}
				}
				if((sum&1)==0) {
					ans++;
					arr[0][i+1] ^= true;
				}
			}
			return ans;
		}else {
			int ans = 0;
			for(int i = 0; i<m-1; i++) {
				int sum1 = 0, sum2 = 0;
				for(int a = 0; a<2; a++) {
					for(int b = i; b<i+2; b++) {
						if(arr[a][b]) {
							sum1++;
						}
					}
				}
				for(int a = 1; a<3; a++) {
					for(int b = i; b<i+2; b++) {
						if(arr[a][b]) {
							sum2++;
						}
					}
				}
				boolean o1 = (sum1&1)==0, o2 = (sum2&1)==0;
				if(o1&&o2) {
					ans++;
					arr[1][i+1] ^= true;
				}else if(o1) {
					ans++;
					arr[0][i+1] ^= true;
				}else if(o2) {
					ans++;
					arr[2][i+1] ^= true;
				}
			}
			return ans;
		}
	}

→ Reply

4 years ago, # ^ |

← Rev. 5 →

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, # ^ |

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, # ^ |

Thanks!

→ Reply

4 years ago, # ^ |

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, # ^ |

Are you sure about that?

→ Reply

4 years ago, # ^ |

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, # ^ |

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, # ^ |

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

→ Reply

4 years ago, # ^ |

Yepp. That too

→ Reply

4 years ago, # ^ |

← Rev. 8 →

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:

(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

dytto

4 years ago, # ^ |

← Rev. 2 →

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 →

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

truesetu

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

No, we can't.

Check the constraint of n*m,

→ Reply

truesetu

4 years ago, # ^ |

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

→ Reply

lazy_and_slow

4 years ago, # ^ |

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

→ Reply

abdstar

4 years ago, # |

Such beautiful explanations in the 3b1b video editorials :)

→ Reply

pavlovoleg4889

4 years ago, # |

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

rchaves

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

+15

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

saurabh247

4 years ago, # ^ |

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

→ Reply

Letscode_sundar

3 years ago, # ^ |

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

→ Reply

rupav

4 years ago, # |

← Rev. 2 →

+16

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

→ Reply

Liviu2000

4 years ago, # ^ |

← Rev. 3 →

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

mrslowmo

4 years ago, # |

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

→ Reply

alegsandyr

4 years ago, # |

I can change tags in problems. Is it okay?

→ Reply

jo_on

4 years ago, # |

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

→ Reply

Monogon

4 years ago, # |

+179

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

Aggu_01000101

4 years ago, # ^ |

+27

ORZ

→ Reply

bc_mc_bsdk_mkc

4 years ago, # |

← Rev. 4 →

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.me/contest/1391/submission/89455694

→ Reply

amaturecoder

4 years ago, # ^ |

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

abhinash6g

4 years ago, # |

← Rev. 2 →

Thanks for the good round and superfast editorial!

→ Reply

Sonic_Master

4 years ago, # |

+13

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

→ Reply

tanishkgupta

4 years ago, # |

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

TheScrasse

4 years ago, # ^ |

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

→ Reply

zino_0

4 years ago, # |

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

→ Reply

biranchi

4 years ago, # |

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

→ Reply

Pradyumna_

4 years ago, # |

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

→ Reply

4 years ago, # ^ |

← Rev. 3 →

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

Pradyumna_

4 years ago, # ^ |

Thank you so much I understand now

→ Reply

4 years ago, # ^ |

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

Lazarusx2

4 years ago, # ^ |

← Rev. 4 →

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

anshikagarg

4 years ago, # ^ |

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

qpwoeirut

4 years ago, # ^ |

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

→ Reply

ETheHedgehog

4 years ago, # ^ |

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

→ Reply

amanjainnn

4 years ago, # |

← Rev. 2 →

→ Reply

4 years ago, # ^ |

Inputting the array takes O(nm) lol

→ Reply

mandh_bhudhi_huon_me

4 years ago, # |

← Rev. 2 →

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

Liviu2000

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Pradyumna_

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

GiangBang

4 years ago, # ^ |

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

→ Reply

grhkm

4 years ago, # ^ |

100 > 50 but 100%27<50%27

→ Reply

TheScrasse

4 years ago, # |

← Rev. 2 →

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

→ Reply

Celloboy

4 years ago, # ^ |

+27

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

→ Reply

4 years ago, # ^ |

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

→ Reply

GiangBang

4 years ago, # |

← Rev. 2 →

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

johnwick2b67

4 years ago, # |

← Rev. 3 →

+10

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

thesinhajee

4 years ago, # ^ |

Can you explain this please?

→ Reply

johnwick2b67

4 years ago, # ^ |

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

grhkm

4 years ago, # |

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

dulatcodes

4 years ago, # |

+21

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

Kognition

4 years ago, # ^ |

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

mihirarora

4 years ago, # |

← Rev. 3 →

-7

/*Deleted*/

→ Reply

4 years ago, # ^ |

But you didn't even participate.

→ Reply

arpansarangi

4 years ago, # ^ |

(Almost) Copied comment ✓

→ Reply

abhay_psr

4 years ago, # |

+18

Why the problem D named 505?

→ Reply

ekaerovets

4 years ago, # ^ |

+40

Maybe because this matrix is good

101
000
101

→ Reply

chaudhary_19

4 years ago, # ^ |

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

→ Reply

abhay_psr

4 years ago, # ^ |

Woah.. cool!

→ Reply

https://youtu.be/c3mjIQR902k

4 years ago, # |

Tag C as a combinatorics problem

→ Reply

dulatcodes

4 years ago, # |

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

→ Reply

notexpertcoder

4 years ago, # |

First 2 problems felt more like Div. 3 problems

→ Reply

qua_intrelle7

4 years ago, # |

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

arpansarangi

4 years ago, # ^ |

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

hk_sr

4 years ago, # ^ |

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

→ Reply

RockyB

4 years ago, # |

← Rev. 3 →

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

→ Reply

Stream_Cipher

4 years ago, # |

← Rev. 5 →

what is answer for

4 1

for question D

→ Reply

arpansarangi

4 years ago, # ^ |

Announcement during contest — Note that if there are no even-length square submatrixes, matrix is good by definition.

So answer should be 0.

→ Reply

Stream_Cipher

4 years ago, # ^ |

so why this solution https://codeforces.me/contest/1391/submission/89424055 accepted instead it failing on above test case

→ Reply

swapnil159

4 years ago, # ^ |

Your testcase is invalid. n<=m in constraints.

→ Reply

Stream_Cipher

4 years ago, # ^ |

thanks

→ Reply

chaudhary_19

4 years ago, # ^ |

0 (zero) if n = 4 and m = 1

→ Reply

ToxicPie9

4 years ago, # |

+14

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, # ^ |

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, # ^ |

Hello,

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

Spoiler

int n = opt<int>(1);
int m = opt<int>(2);
if(n == -1){
    n = rnd.next(1,1000000);
}
if(m == -1){
    m = rnd.next(1,1000000/n);
}

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, # ^ |

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

→ Reply

distinctlyaverage

4 years ago, # |

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

→ Reply

nayeem2021

4 years ago, # ^ |

To take input of the grid O(n*m) is triggered

→ Reply

nayeem2021

4 years ago, # |

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

→ Reply

RockyB

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

nayeem2021

4 years ago, # ^ |

What is the problem if l-r < 0

→ Reply

Brodicico

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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

→ Reply

kristja6

4 years ago, # |

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

→ Reply

anon143

4 years ago, # |

← Rev. 2 →

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, # |

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

Atul2608

4 years ago, # |

← Rev. 2 →

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

→ Reply

jbs1jbs1jbs1

4 years ago, # ^ |

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

Atul2608

4 years ago, # ^ |

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

→ Reply

bit_2

4 years ago, # |

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

jbs1jbs1jbs1

4 years ago, # ^ |

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, # |

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

→ Reply

BRCode

4 years ago, # ^ |

← Rev. 2 →

+19

Upvote SleepyShashwat instead :p

Problemsetting is a lot harder than making video editorials

→ Reply

shash42

4 years ago, # |

+74

Memes time.

A — Suborrays

C — Cyclic Permutations

Explanation

The editorial

E — Pairs of Pairs

→ Reply

yogi23

4 years ago, # |

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 →

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.me/contest/1391/submission/89535074

→ Reply

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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

→ Reply

alon276

4 years ago, # ^ |

Please explain.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

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.

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, # ^ |

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

nns2009

4 years ago, # ^ |

← Rev. 2 →

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, # ^ |

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

decrypto96

4 years ago, # |

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

TechNite

4 years ago, # ^ |

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

abhaypatil2000

4 years ago, # |

Please also add solution code

→ Reply

4 years ago, # ^ |

Added.

→ Reply

4 years ago, # ^ |

It doesn't work, shows "You are not allowed to view the requested page", please fix it...

→ Reply

4 years ago, # ^ |

Oops. I think it's fine now :)

→ Reply

paulmorenkov

4 years ago, # |

When do problems receive a rating tag?

→ Reply

ducati

4 years ago, # |

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

→ Reply

Fairicle

4 years ago, # ^ |

Me neither:(

→ Reply

17821147

4 years ago, # |

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

→ Reply

ducati

4 years ago, # |

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

→ Reply

Nesta

4 years ago, # |

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

→ Reply

gyan_p_t

4 years ago, # |

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

→ Reply

arwaeystoamneg

4 years ago, # ^ |

nf can be negative

→ Reply

baa_baa_blacksheep

4 years ago, # |

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

→ Reply

siyy

4 years ago, # |

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

rahulgoel

4 years ago, # |

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

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);
            }
        }
    }
}

→ Reply

SevenDeadlySins

4 years ago, # ^ |

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

→ Reply

rahulgoel

4 years ago, # ^ |

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

Thanos_I_am_inevitable

4 years ago, # |

← Rev. 3 →

UNDERSTOOD.

→ Reply

Shameek

4 years ago, # ^ |

can u please explain why?

→ Reply

Thanos_I_am_inevitable

4 years ago, # ^ |

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

Shameek

4 years ago, # ^ |

← Rev. 2 →

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

mohammedehab2002

4 years ago, # |

← Rev. 2 →

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

dan_nil

4 years ago, # |

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

SevenDeadlySins

4 years ago, # ^ |

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

→ Reply

dan_nil

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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

→ Reply

dan_nil

4 years ago, # ^ |

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, # ^ |

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

→ Reply

atul007ism

4 years ago, # |

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, # ^ |

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

→ Reply

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

4 years ago, # ^ |

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, # ^ |

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, # ^ |

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

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Ohk, I got it

→ Reply

4 years ago, # ^ |

Don't worry. Suposse you put a luggage in position (2,8)

→ Reply

chowdhuryan1999

4 years ago, # |

anyone please explain the solution of problrm D

→ Reply

4 years ago, # ^ |

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

→ Reply

chowdhuryan1999

4 years ago, # ^ |

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 →

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.

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

Tanmay414

4 years ago, # |

Solved D in O(m*n3). 89479757

→ Reply

sharath101

4 years ago, # ^ |

Can you explain your approach?

→ Reply

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

4 years ago, # ^ |

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

Check this, for clear and more brief understanding: Comment

→ Reply

Lakshh21

4 years ago, # |

← Rev. 2 →

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

Himu_G

4 years ago, # |

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

getdebarghya1025

4 years ago, # |

+16

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

VandanRogheliya

4 years ago, # |

Video editorials were really nice. Thank you!

→ Reply

Uchiha_Itachi_21

4 years ago, # |

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

Uchiha_Itachi_21

4 years ago, # ^ |

Ohh my bad. Didn't saw that n<=m.

→ Reply

Bisoye

4 years ago, # |

"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

aryanc403

4 years ago, # ^ |

Check difference between bitwise XOR operator and bitwise OR operator.

→ Reply

petrescu

4 years ago, # |

← Rev. 2 →

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

Nobody4931

4 years ago, # |

← Rev. 2 →

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

ziad_abdelkader

4 years ago, # ^ |

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

shadow9236

4 years ago, # |

My solution for Problem C

→ Reply

shashi_punia

4 years ago, # |

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