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
Thanks for the speedy editorial :)
achievement unlocked.
Thanks for a good round!
A CHO UCHAVSTVOVAT V RAUNDE ZASSAL?? LOXX
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..
Radewoosh once posted editorial before the contest !! (dont remember which contest)
It was Hello 2019
How do you know what happened in 2019? you registered 2 months ago
Are you detective ?
No, I'm programmer.
did they cancel the round after that?
Why would they? We are too loyal, u know :p
lol :)
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
(n! + 1e9+7 — 2^(n-1))%(1e9+7)
Thanks.
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
Thanks for the explanation.
Same mistake :(
the video editorials are very nice and easy to understand
loved the contest
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
.
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?
Dude he literally said someone posted it during the round
Guess after ponies round, he has refused to understand anything in english lol
if you solve this 2 days ago then why you unable to solve this during contest
I think you only copied that question there. Xd
Why don't you provide the link to the problem, which you did 2 days ago? That would be helpful.
It is done during the contest. Why people are doing this nonsense?
Great round, fast editorial. Thank you!
For D you can also bruteforce the first column and then greedy the rest.
can you please explain the brute force approach?skittles1412
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)
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?
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.
Thanks!
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.
Are you sure about that?
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.
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.
Correct! And for n = 2 we only need to greedy twice, not toggling and toggling the first/second row.
Yepp. That too
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
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?
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 Arraych
, 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.hey! cant we generate all possible permutations(O(2^(mn))),and then find minimum of all.
No, we can't.
Check the constraint of
n*m
,yeah,but neither of them can be greater than 3, right??
If one is less than 4 other can go upto 10^6
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?
In my case, I derived the formula. Maybe not fast enough though :)
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.
I was wondering why so many people were using while(next_permutation(all(a)); And now I got to know why.
I can't understand the question nor the editorial. Can you please explain me ?
Problem D: Brute submission. (Time: O(n * m))
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!
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).
ORZ
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://mirror.codeforces.com/contest/1391/submission/89455694
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.
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
rep(i, 0, c)
in the loop withc == 1
is wrong, it should berep(i, 0, r)
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
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)
Thank you so much I understand now
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)
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}.
n
refers to the length of the permutation, not the length of the cycle.1 , 4 , 2 , 3 and 4 , 2 , 3 , 1 are both cyclic you actually missed : 1 , 3 , 4 , 2 3 , 4 , 2 , 1
.
Inputting the array takes O(nm) lol
for C i tried it this way
this code prints negative number can anyone tell why??
if n is bigger them 64 ,(1<<n-1) will give a very strange result
Replace this cout << (ans — (1ll << (n — 1))%mod + mod ) % mod << endl; As the (1<<(n-1)) will cross 32-bit integers
n can be very large (about 1e6) so it will get overflow with long long type
100 > 50 but 100%27<50%27
Is there anyone who printed something different from $$$[1, 2, \dots, n]$$$ in 1391A - Suborrays?
Yes I printed n, n-1... 2, 1
Printed them in reverse, just to make the OR large very quickly just to be safe.
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$$$
Can you explain this please?
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)$$$.
My D semi-bruteforce submission: https://mirror.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.
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.
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.
/*Deleted*/
But you didn't even participate.
Why the problem D named 505?
Maybe because this matrix is good
horizontally and vertically...both ways read the binary representation of 505...cool
Woah.. cool!
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!
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.
You really worked hard on your photo there, didn't you? XD
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
Announcement during contest — Note that if there are no even-length square submatrixes, matrix is good by definition.
So answer should be 0.
so why this solution https://mirror.codeforces.com/contest/1391/submission/89424055 accepted instead it failing on above test case
Your testcase is invalid. n<=m in constraints.
thanks
0 (zero) if n = 4 and m = 1
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)
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.
Hello,
I just realized that I did something very dumb. This is the part of the random generator which sets $$$n$$$ and $$$m$$$.
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.
I came up with the n>=4 observation but could not figure out how to approach for n<4 :D
Shouldn't the time complexity of B be O(n + m) instead of O(n * m)?
To take input of the grid O(n*m) is triggered
Why we need to add MOD with (l-r)
Because (l-r) might be less than 0 and if you take modulo, it would still be negative.
What is the problem if l-r < 0
try to extract mod from negative numbers and you'll see the difference.
Because (l-r) can be negative and modulo of negative would be negative. but the answer would instead be positive.
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!!
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.
Yes, I got it when I read it again That's a nice problem. And thank YOu also for replying
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.
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"
BRCode Comment or post smth so that we can give you a contribution for your amazing work
Upvote SleepyShashwat instead :p
Problemsetting is a lot harder than making video editorials
Memes time.
A — Suborrays
C — Cyclic Permutations![117427957-631798980774245-59686289827328330-n](/predownloaded/ed/d1/edd12fb7eb0affb48bf95aafe4c0468f1d8e0d68.jpg)
Seems to be hard to get for some so: Relate the height of the prisoners with the permutations. The small prisoner leads to a cycle.
Mainly because the graph in the stonks meme itself has too many troughs.
The editorial
![117294834-746360439515480-2424750076150834485-n](/predownloaded/04/73/04738ead0b3e614cbf0d9dd2f5155a3fd2a27896.jpg)
E — Pairs of Pairs![117339984-718618315370218-649824027994725929-n](/predownloaded/bc/f9/bcf96b0ccbf467c99ecfa3ea7c955f556f0aef49.jpg)
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://mirror.codeforces.com/contest/1391/submission/89535074
n<=m is always true, so you can make it even shorter
Ah thx, I didn't notice that. I updated the code.
Please explain.
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
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.
I still don't get your solution. Can you please briefly comment your code:
No, everything depends on the first column And the first row
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:
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.
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.
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.
Please also add solution code
Added.
It doesn't work, shows "You are not allowed to view the requested page", please fix it...
Oops. I think it's fine now :)
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!"
Me neither:(
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://mirror.codeforces.com/contest/1391/submission/89473526)
nf can be negative
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.
$$$pmask \oplus cmask$$$ tells us about the parity of the adjacent columns.
So in the case when $$$n=2$$$, there is only one square matrix formed in adjacent columns, so the parity should be odd. Since $$$01$$$ or $$$10$$$ have only one bit set, their parity is odd.
In the case when $$$n=3$$$, there are two square matrices formed in the adjacent columns, so the parity should be odd for both the blocks. In $$$010$$$ both the blocks share the same parity bit (middle bit). In $$$101$$$ both have different parity bit (the least significant and the most significant bits). When $$$n=3$$$, these are the only cases when the property of every $$$2$$$x$$$2$$$ matrix having odd sum is satisfied.
What are pmask and cmask?? what do those variables represent??
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.
UNDERSTOOD.
can u please explain why?
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.
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
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
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.
write a code to calculate all permutations... and find the graph and check for cycles in each graph...
can u please tell me just 1 more permutation of length 4 other than above 4
4123, 4132, 4231, 4213 And reverse of them.
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
What is the definition of k? Why can't k be 3?
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.
Before calculate the answer you have to read the whole matrix, it takes n*m (it's size)
Hey please help me with this doubt-> why not dp solution for B?
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.
what if our matrix is
Here we only have to change one R to D, but answer will be 2 according to editorial
You have to change the two R's of the last column. What R do you would change?
Ohk, I got it
Don't worry. Suposse you put a luggage in position (2,8)
anyone please explain the solution of problrm D
Bro, help me with B, why not dp solution?
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
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
Solved D in O(m*n3). 89479757
Can you explain your approach?
I solved it Greedily in
O(n*m)
.Check this, for clear and more brief understanding: Comment
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 :)
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
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 :)
Video editorials were really nice. Thank you!
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?
Ohh my bad. Didn't saw that n<=m.
"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.
Check difference between bitwise XOR operator and bitwise OR operator.
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..
why would the solution for problem B work? for example, given a test case like the following:
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.
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.
My solution for Problem C
https://www.youtube.com/watch?v=iGF1XfxtA74
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?
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.