### SleepyShashwat's blog

By SleepyShashwat, history, 22 months ago,

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

Also, here are video editorials by BRCode:

Code: 89479484

Code: 89479603
Also, thanks to shash42 for the construction using deque idea!

Code: 89479612

Code: 89479627
Code: 89479649

• +507

 » 22 months ago, # | ← Rev. 2 →   +30 Thanks for the speedy editorial :)
•  » » 22 months ago, # ^ |   +1 achievement unlocked.
 » 22 months ago, # |   +51 Thanks for a good round!
•  » » 22 months ago, # ^ | ← Rev. 2 →   -91 A CHO UCHAVSTVOVAT V RAUNDE ZASSAL?? LOXX
 » 22 months ago, # | ← Rev. 2 →   +8 Great round and SUPER fast Editorial, Thanks
 » 22 months ago, # |   +48 Question C was really a good one! Keep it up!
•  » » 18 months ago, # ^ |   0 Can you please explain it bro?
 » 22 months ago, # |   0 And the award for the fastest editorial goes to..
•  » » 22 months ago, # ^ |   +60 Radewoosh once posted editorial before the contest !! (dont remember which contest)
•  » » » 22 months ago, # ^ |   +6 It was Hello 2019
•  » » » » 22 months ago, # ^ |   -30 How do you know what happened in 2019? you registered 2 months ago
•  » » » » » 22 months ago, # ^ |   0 Are you detective ?
•  » » » » » » 22 months ago, # ^ |   0 No, I'm programmer.
•  » » » 22 months ago, # ^ |   0 did they cancel the round after that?
•  » » » » 22 months ago, # ^ |   0 Why would they? We are too loyal, u know :p
•  » » » » 22 months ago, # ^ |   0 It was a rickroll.
•  » » » » » 22 months ago, # ^ |   0 lol, this one.
•  » » » 22 months ago, # ^ |   0 lol :)
 » 22 months ago, # |   0 Thanks for the video editorials.
 » 22 months ago, # |   0 Editorial is so fast!!
 » 22 months ago, # |   0 Enjoyed the Round. Problem D was really nice although I didn't manage to solve in the contest
 » 22 months ago, # |   +15 Great balanced round, very nice problems. Thanks to the authors!
 » 22 months ago, # | ← Rev. 2 →   +4 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
•  » » 22 months ago, # ^ |   +5 (n! + 1e9+7 — 2^(n-1))%(1e9+7)
•  » » » 22 months ago, # ^ |   0 Thanks.
•  » » 22 months 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
•  » » » 22 months ago, # ^ |   0 Thanks for the explanation.
•  » » 22 months ago, # ^ |   0 (fast-two)%mod can be negative if (fast-two) is negativecorrect : (fast-two+mod) %modI think this would do
•  » » » 22 months ago, # ^ |   0 Can you please prove why adding mod will give correct result?
•  » » » » 22 months ago, # ^ |   0 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.
•  » » » » » 22 months ago, # ^ |   0 Got it! Thanks
•  » » 22 months ago, # ^ |   0 Same mistake :(
 » 22 months ago, # |   +1 the video editorials are very nice and easy to understand
 » 22 months ago, # |   -9 Question C can be googled....Though I couldn't solve it...
 » 22 months ago, # |   0 Great round and short problem statement and thanks for speedy tutorial!
 » 22 months ago, # | ← Rev. 2 →   -117 loved the contest
•  » » 22 months ago, # ^ | ← Rev. 2 →   -124 angelina karel
•  » » 22 months 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
•  » » » 22 months ago, # ^ | ← Rev. 2 →   -123 .
•  » » » » 22 months 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?
•  » » » » 22 months ago, # ^ |   +9 Dude he literally said someone posted it during the round
•  » » » » » 22 months ago, # ^ |   +30 Guess after ponies round, he has refused to understand anything in english lol
•  » » » » 22 months ago, # ^ |   +13 if you solve this 2 days ago then why you unable to solve this during contest
•  » » » » » 22 months ago, # ^ |   0 He said he couldn't attend the contest...
•  » » » » 22 months ago, # ^ |   +19 I think you only copied that question there. Xd
•  » » 22 months ago, # ^ |   +11 Why don't you provide the link to the problem, which you did 2 days ago? That would be helpful.
•  » » 22 months ago, # ^ |   +1 It is done during the contest. Why people are doing this nonsense?
•  » » 22 months ago, # ^ |   0 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
•  » » » 22 months ago, # ^ |   0 true
•  » » 22 months ago, # ^ |   0 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.
 » 22 months ago, # |   +38 Great round, fast editorial. Thank you!For D you can also bruteforce the first column and then greedy the rest.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +3 can you please explain the brute force approach?skittles1412
•  » » » 22 months ago, # ^ |   +4 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
•  » » » » 22 months ago, # ^ | ← Rev. 5 →   0 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?
•  » » » » » 22 months ago, # ^ |   +6 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 010In 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.
•  » » » » » » 22 months ago, # ^ |   0 Thanks!
•  » » » » » » » 22 months ago, # ^ |   +3 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.
•  » » » » » » » » 22 months ago, # ^ |   0 Are you sure about that?
•  » » » » » » » » » 22 months ago, # ^ |   +3 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.
•  » » » » » » » » » 22 months ago, # ^ |   0 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.
•  » » » » » » » » » 22 months ago, # ^ |   0 Correct! And for n = 2 we only need to greedy twice, not toggling and toggling the first/second row.
•  » » » » » » » » » 22 months ago, # ^ |   0 Yepp. That too
•  » » » 22 months ago, # ^ | ← Rev. 8 →   +3 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
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   0 Great explanation!!!!...............................if(m
•  » » » » » 22 months ago, # ^ | ← Rev. 2 →   0 Actually, I didn't read n<=m constraint in the Problem, before I submitted my code.So, for the case, (m
•  » » » » » » 22 months ago, # ^ |   0 okay okay got it ..thanks
•  » » » » 22 months ago, # ^ |   0 hey! cant we generate all possible permutations(O(2^(mn))),and then find minimum of all.
•  » » » » » 22 months ago, # ^ |   0 No, we can't.Check the constraint of n*m,
•  » » » » » » 22 months ago, # ^ |   0 yeah,but neither of them can be greater than 3, right??
•  » » » » » » » 22 months ago, # ^ |   +3 If one is less than 4 other can go upto 10^6
 » 22 months ago, # |   +2 Such beautiful explanations in the 3b1b video editorials :)
 » 22 months ago, # |   +1 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?
•  » » 22 months ago, # ^ |   +1 In my case, I derived the formula. Maybe not fast enough though :)
•  » » 22 months 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.
•  » » 22 months ago, # ^ |   0 I was wondering why so many people were using while(next_permutation(all(a)); And now I got to know why.
•  » » 8 months ago, # ^ |   0 I can't understand the question nor the editorial. Can you please explain me ?
 » 22 months ago, # | ← Rev. 2 →   +16 Problem D: Brute submission. (Time: O(n * m))
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 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!
 » 22 months ago, # |   +1 My C got wrong because I forgot to take (+ mod) while subtracting 2 quantities :(
 » 22 months ago, # |   0 I can change tags in problems. Is it okay?
 » 22 months ago, # |   +3 Concise descriptions, decent problems (at least for me), fast system testing, and fast editorial.
 » 22 months ago, # |   0 Problem C is just too cool and good! Enjoyed the contest and thanks for the tutorial
 » 22 months 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).
•  » » 22 months ago, # ^ |   +27 ORZ
 » 22 months ago, # | ← Rev. 4 →   0 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
•  » » 22 months ago, # ^ |   +3 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.
 » 22 months ago, # | ← Rev. 2 →   0 Thanks for the good round and superfast editorial!
 » 22 months ago, # | ← Rev. 2 →   0 This is really a good round but still I was not able to clear B
•  » » 22 months ago, # ^ |   0 I thought dp solution for B, my bad luck.
•  » » » 22 months ago, # ^ |   0 same here but realize that I have change in the last column or last row at 50 secs before ending
•  » » » » 22 months ago, # ^ |   0 Very sad...
 » 22 months ago, # |   +13 Nice problems. Better than some previous contests. Any suggestions on approach to general C and D problems are welcome.
 » 22 months ago, # |   0 The round and its editorial are very nicely designed.
 » 22 months ago, # |   0 Thank You for the super fast editorial :)))
 » 22 months ago, # |   0 I have thought the solution in problems C but I don't believe that solution is true T___T . Too bad
 » 22 months ago, # |   0 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
•  » » 22 months ago, # ^ |   0 Plz help
•  » » 22 months ago, # ^ |   0 rep(i, 0, c) in the loop with c == 1 is wrong, it should be rep(i, 0, r)
•  » » » 22 months ago, # ^ |   0 Thnx
 » 22 months ago, # |   0 Problem C can be solved using the recurrence : f(n) = n! — 2*(n-1)! + 2*f(n-1) Submission : 89440460
 » 22 months ago, # |   +6 I loved your round SleepyShashwat. Its short, straight-forward statements saved me from unnecessary thought processes. You killed it, man.
 » 22 months ago, # |   0 I still didn't get why are we using 2^(n-1) in problem C
•  » » 22 months ago, # ^ | ← Rev. 3 →   +5 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)
•  » » » 22 months ago, # ^ |   0 Thank you so much I understand now
•  » » 22 months ago, # ^ |   0 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.12341 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?
•  » » 22 months ago, # ^ |   0 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)
•  » » 22 months ago, # ^ | ← Rev. 4 →   0 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) 
•  » » » 22 months ago, # ^ |   +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}.
•  » » » » 22 months ago, # ^ |   0 n refers to the length of the permutation, not the length of the cycle.
•  » » » 22 months ago, # ^ |   0 1 , 4 , 2 , 3 and 4 , 2 , 3 , 1 are both cyclic you actually missed : 1 , 3 , 4 , 2 3 , 4 , 2 , 1
•  » » » » 22 months ago, # ^ |   0 yea ,sorry my bad!!
 » 22 months ago, # | ← Rev. 2 →   0 .
•  » » 22 months ago, # ^ |   +3 Inputting the array takes O(nm) lol
•  » » » 22 months ago, # ^ |   0 lol I forgot.
 » 22 months ago, # | ← Rev. 2 →   0 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??
•  » » 22 months ago, # ^ | ← Rev. 2 →   +1 if n is bigger them 64 ,(1<
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 Replace this cout << (ans — (1ll << (n — 1))%mod + mod ) % mod << endl; As the (1<<(n-1)) will cross 32-bit integers
•  » » 22 months ago, # ^ |   +8 n can be very large (about 1e6) so it will get overflow with long long type
•  » » 22 months ago, # ^ |   0 100 > 50 but 100%27<50%27
•  » » 22 months ago, # ^ |   0 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.
 » 22 months ago, # |   0 HaPpY to see the official video editorials, great, thanks
 » 22 months ago, # | ← Rev. 2 →   +7 Is there anyone who printed something different from $[1, 2, \dots, n]$ in 1391A - Suborrays?
•  » » 22 months ago, # ^ |   +27 Yes I printed n, n-1... 2, 1
•  » » 22 months ago, # ^ |   0 Printed them in reverse, just to make the OR large very quickly just to be safe.
 » 22 months ago, # |   0 Has anyone got wrong answer on testcase 25 in question B
 » 22 months ago, # | ← Rev. 2 →   0 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
 » 22 months 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$
•  » » 22 months ago, # ^ |   0 Can you explain this please?
•  » » » 22 months ago, # ^ |   +6 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)$.
 » 22 months ago, # |   0 My D semi-bruteforce submission: https://codeforces.com/contest/1391/submission/89444411just 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.
 » 22 months 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.
•  » » 22 months ago, # ^ |   0 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.
 » 22 months ago, # | ← Rev. 3 →   -7 /*Deleted*/
•  » » 22 months ago, # ^ |   +1 But you didn't even participate.
•  » » » 22 months ago, # ^ | ← Rev. 3 →   0 /* Deleted */
•  » » 22 months ago, # ^ |   +4 (Almost) Copied comment ✓
 » 22 months ago, # |   +18 Why the problem D named 505?
•  » » 22 months ago, # ^ |   +40 Maybe because this matrix is good 101 000 101 
•  » » » 22 months ago, # ^ |   +8 horizontally and vertically...both ways read the binary representation of 505...cool
•  » » » 22 months ago, # ^ |   0 Woah.. cool!
•  » » 22 months ago, # ^ |   0 Can you please provide an intuition for problem D
 » 22 months ago, # |   +4 Tag C as a combinatorics problem
 » 22 months ago, # |   0 Adding implementations to the editorial looks better understanding.
 » 22 months ago, # |   0 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??
 » 22 months ago, # | ← Rev. 4 →   -7 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.for n=4 maxima =4 , remaining element =[1,2,3]Sub-sequences =2^(n-1)=8123122313123{}We will place these on the left and remaining elements on the right in decreasing order so overall distribution will look like1 4 322 4 313 4 2112 4 323 4 113 4 2123 4{} 4321
•  » » 22 months ago, # ^ |   0 basically number of bitonic permutations ,right!!
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 Yes , that's a nice way to put it, I didnt knew the terminology tbh.Thanks
 » 22 months ago, # |   0 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?
•  » » 22 months ago, # ^ |   0 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...
 » 22 months ago, # |   +2 With all the respect to the aesthetics of writing problem statements, I am now convinced that short formal statements are the best.
•  » » 22 months ago, # ^ |   0 exactly, long problem statements frustates me.
 » 22 months ago, # |   +3 First 2 problems felt more like Div. 3 problems
 » 22 months ago, # |   0 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!
•  » » 22 months ago, # ^ |   +1 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.
•  » » » 22 months ago, # ^ |   +6 You really worked hard on your photo there, didn't you? XD
•  » » » » 22 months ago, # ^ |   0 haha, yes.
 » 22 months ago, # | ← Rev. 3 →   +8 Nice problemset, here's my video solutions for all problems + very funny moment at the end :)https://youtu.be/c3mjIQR902k
 » 22 months ago, # | ← Rev. 5 →   +7 what is answer for 4 11111for question D
•  » » 22 months ago, # ^ |   0 Announcement during contest — Note that if there are no even-length square submatrixes, matrix is good by definition.So answer should be 0.
•  » » » 22 months ago, # ^ |   0 so why this solution https://codeforces.com/contest/1391/submission/89424055 accepted instead it failing on above test case
•  » » » » 22 months ago, # ^ |   0 Your testcase is invalid. n<=m in constraints.
•  » » » » » 22 months ago, # ^ |   0 thanks
•  » » 22 months ago, # ^ |   0 0 (zero) if n = 4 and m = 1
 » 22 months ago, # |   0 Thanks for the video editorials, I think sometimes it is more useful than the normal editorials.
 » 22 months 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)
•  » » 22 months ago, # ^ |   +8 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.
•  » » 22 months ago, # ^ |   +2 Hello, I just realized that I did something very dumb. This is the part of the random generator which sets $n$ and $m$. Spoilerint n = opt(1); int m = opt(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.
•  » » 22 months ago, # ^ |   0 I came up with the n>=4 observation but could not figure out how to approach for n<4 :D
 » 22 months ago, # |   0 Shouldn't the time complexity of B be O(n + m) instead of O(n * m)?
•  » » 22 months ago, # ^ |   +3 To take input of the grid O(n*m) is triggered
 » 22 months ago, # |   0 Why we need to add MOD with (l-r)
•  » » 22 months ago, # ^ | ← Rev. 2 →   +3 Because (l-r) might be less than 0 and if you take modulo, it would still be negative.
•  » » » 22 months ago, # ^ |   0 What is the problem if l-r < 0
•  » » » » 22 months ago, # ^ |   0 try to extract mod from negative numbers and you'll see the difference.
•  » » 22 months ago, # ^ |   0 Because (l-r) can be negative and modulo of negative would be negative. but the answer would instead be positive.
 » 22 months ago, # |   +3 Very good work of the problem setters, C and D were very interesting. Thank you for the contest!
 » 22 months ago, # | ← Rev. 2 →   0 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
 » 22 months ago, # |   0 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
 » 22 months ago, # | ← Rev. 2 →   +3 The constraint in problem 4 is pow( 10, 6) but editorial is using bit masking... I am unable to understand >> Need help!!
•  » » 22 months ago, # ^ |   0 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.
•  » » » 22 months ago, # ^ |   0 Yes, I got it when I read it again That's a nice problem. And thank YOu also for replying
 » 22 months ago, # |   +3 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.
•  » » 22 months ago, # ^ |   0 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"
•  » » » 22 months ago, # ^ |   0 thanks a lot brother for explaining.. I totally got it.
•  » » » 22 months ago, # ^ |   0 cool explaination!!
 » 22 months ago, # |   +9 BRCode Comment or post smth so that we can give you a contribution for your amazing work
•  » » 22 months ago, # ^ | ← Rev. 2 →   +19 Upvote SleepyShashwat instead :pProblemsetting is a lot harder than making video editorials
 » 22 months ago, # |   +74 Memes time.A — Suborrays C — Cyclic Permutations ExplanationSeems to be hard to get for some so: Relate the height of the prisoners with the permutations. The small prisoner leads to a cycle. ExplanationMainly because the graph in the stonks meme itself has too many troughs.The editorial E — Pairs of Pairs
•  » » 22 months ago, # ^ |   0 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 ):.
 » 22 months ago, # |   0 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!
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 any cycle, be it 3 or n (and anything in between obv.). They wrote any simple cycle would work.
 » 22 months ago, # |   0 Can anyone explain why my C solution failed pretest 6 when I used unsigned long long instead of long long ?
 » 22 months ago, # | ← Rev. 2 →   0 ok. Got it video is little helpful
 » 22 months ago, # | ← Rev. 2 →   +3 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
•  » » 22 months ago, # ^ |   0 n<=m is always true, so you can make it even shorter
•  » » » 22 months ago, # ^ |   0 Ah thx, I didn't notice that. I updated the code.
•  » » 22 months ago, # ^ |   0 Please explain.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +3 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 columnsThen, 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
•  » » » 22 months ago, # ^ |   0 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.
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » 22 months ago, # ^ |   0 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.
 » 22 months ago, # |   0 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.
•  » » 22 months ago, # ^ |   +3 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.
 » 22 months ago, # |   0 Please also add solution code
•  » » 22 months ago, # ^ |   +2 Added.
•  » » » 22 months ago, # ^ |   0 It doesn't work, shows "You are not allowed to view the requested page", please fix it...
•  » » » » 22 months ago, # ^ |   +3 Oops. I think it's fine now :)
 » 22 months ago, # |   0 When do problems receive a rating tag?
 » 22 months ago, # |   +4 I wonder why I can't read the code for learning and it said "You are not allowed to read the page!"
•  » » 22 months ago, # ^ |   0 Me neither:(
 » 22 months ago, # |   +7 It says "you are not allowed to view the requested page" when I click on the solution code.
 » 22 months ago, # |   0 Can someone give the solution code of E to me? Thanks
 » 22 months ago, # |   +4 Unable to view the solution codes. It says "you are not allowed to view the requested page".
 » 22 months ago, # |   0 PROBLEM C. Why is it giving WA. can anyone help me? [submission:89473526][My Submission code](https://codeforces.com/contest/1391/submission/89473526)
•  » » 22 months ago, # ^ |   0 nf can be negative
 » 22 months ago, # |   +1 I love Indian round because their tutorials are fucking fast. Love U.
 » 22 months ago, # |   0 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
 » 22 months ago, # |   0 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$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. Transition Snippet when n = 3for (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); } } } } 
•  » » 22 months ago, # ^ |   0 What are pmask and cmask?? what do those variables represent??
•  » » » 22 months ago, # ^ |   0 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.
 » 22 months ago, # | ← Rev. 3 →   0 UNDERSTOOD.
•  » » 22 months ago, # ^ |   0 can u please explain why?
•  » » » 22 months ago, # ^ |   +1 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.
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +1 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 welli can prove by code https://ideone.com/oaaysPthis prints all 4*4s such that all 2*2s inside of it have odd number of 1s in italso, none of the 4*4s i printed have an odd number of ones
•  » » » » » 22 months ago, # ^ |   0 Nice Thanks for code.
 » 22 months ago, # | ← Rev. 2 →   +8 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
 » 22 months ago, # |   0 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.
•  » » 22 months ago, # ^ |   0 write a code to calculate all permutations... and find the graph and check for cycles in each graph...
•  » » » 22 months ago, # ^ |   0 can u please tell me just 1 more permutation of length 4 other than above 4
•  » » » » 22 months ago, # ^ |   0 4123, 4132, 4231, 4213 And reverse of them.
•  » » » » » 22 months ago, # ^ |   0 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
•  » » » » » » 22 months ago, # ^ |   0 What is the definition of k? Why can't k be 3?
 » 22 months ago, # |   0 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.
•  » » 22 months ago, # ^ |   +3 Before calculate the answer you have to read the whole matrix, it takes n*m (it's size)
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 Hey please help me with this doubt-> why not dp solution for B?
•  » » » » 22 months ago, # ^ |   0 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.
•  » » » » » 22 months ago, # ^ |   0 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
•  » » » » » » 22 months ago, # ^ |   0 You have to change the two R's of the last column. What R do you would change?
•  » » » » » » » 22 months ago, # ^ | ← Rev. 2 →   0 Ohk, I got it
•  » » » » » » » » 22 months ago, # ^ |   0 Don't worry. Suposse you put a luggage in position (2,8)
•  » » » 22 months ago, # ^ |   0 oh sorry, you are right!!
 » 22 months ago, # |   0 anyone please explain the solution of problrm D
•  » » 22 months ago, # ^ |   0 Bro, help me with B, why not dp solution?
•  » » » 22 months ago, # ^ |   0 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
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 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 columnsThen, 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
 » 22 months ago, # |   0 Solved D in O(m*n3). 89479757
•  » » 22 months ago, # ^ |   0 Can you explain your approach?
•  » » » 22 months ago, # ^ |   0 I solved it Greedily in O(n*m).Check this, for clear and more brief understanding: Comment
 » 22 months ago, # | ← Rev. 2 →   +5 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 :)
 » 22 months ago, # |   +6 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
•  » » 17 months ago, # ^ |   0 I have a question of what does this term (n-2)*(n-1)! present?
 » 22 months ago, # |   0 Test cases for task $E$ were pretty weak, several test cases that had potential to give TLE verdict were missing
 » 22 months 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 :)
 » 22 months ago, # |   0 Video editorials were really nice. Thank you!
 » 22 months ago, # |   0 Not unimodal,but arc permutations. In C.
 » 22 months ago, # |   0 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 3101111000001Here 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?
•  » » 22 months ago, # ^ |   +8 Ohh my bad. Didn't saw that n<=m.
 » 22 months ago, # |   0 "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.
•  » » 22 months ago, # ^ |   0 Check difference between bitwise XOR operator and bitwise OR operator.
•  » » » 22 months ago, # ^ |   0 oh.. I guess I really didn't understand both tbh.Thanks so much for the response...
 » 22 months ago, # | ← Rev. 2 →   0 Codeforces editorials are getting better day by day...This time with video explanation. Hope to see more contest like this.. :)
 » 22 months ago, # |   0 Hope to get video editorials like these for every contest !! Would be really helpful for beginners to understand D,E problems easily !!
 » 22 months ago, # | ← Rev. 2 →   0 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..
 » 21 month(s) ago, # | ← Rev. 2 →   0 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.
•  » » 21 month(s) ago, # ^ |   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.
•  » » » 21 month(s) ago, # ^ |   0 oh i see, looks like i didnt read the problem carefully. thanks
 » 21 month(s) ago, # |   0 My solution for Problem Chttps://www.youtube.com/watch?v=iGF1XfxtA74
 » 21 month(s) ago, # |   0 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?
•  » » 21 month(s) ago, # ^ |   0 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.
 » 21 month(s) ago, # |   0 Problem D is soo hard