### rivalq's blog

By rivalq, 6 weeks ago,

Hint
Tutorial
Solution

Hints
Tutorial
Solution

Hint
Tutorial
Solution

Hints
Tutorial
Solution

Tutorial
Solution

# 1682F — MCMF?

Tutorial
Solution

• +147

 » 6 weeks ago, # |   -37 :holyfrick: That was lightining fast .. Thnx for the hinted editorial !! helps a lot in upsolving :)
 » 6 weeks ago, # |   -10 great problems, fast editorial, quick rating changes, and becoming specialist. thanks alot :D
•  » » 6 weeks ago, # ^ |   0 Congratulations! I have become specialist too... again)))
•  » » » 6 weeks ago, # ^ |   +1 Thanks, Congrats on that :)
 » 6 weeks ago, # | ← Rev. 2 →   +1 Missed C by just "+1", took single/2 instead of (single+1)/2. :(
•  » » 6 weeks ago, # ^ |   0 Same happended with me
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Please can you help me understand why is there a need of +1?
•  » » » » 6 weeks ago, # ^ |   0 A case like1 3 1 2 1Should output 2 not 1 because the middle element counts in the LIS of the array and the LIS of the reverse of the array too (this always happen when the number of good elements is odd)
•  » » » » » 5 weeks ago, # ^ |   0 Thank you!
•  » » 6 weeks ago, # ^ |   0 For Q2 I wrote the same logic as editorial but dry run the logic with testcase which i created wrong and thought logic was wrong and jumped to Q3 For Q3 I did mistake with the common element case. I thought a single frequency element can be sharable to both LIS(a) and LIS(a') only if it is the maximum of array. Bad Day :-)
 » 6 weeks ago, # |   +14 I wish authors who put an anti-hash test in C a very pleasant evening.
•  » » 6 weeks ago, # ^ |   0 Did authors include anti-hash test, or is it somebody's hack?
•  » » » 6 weeks ago, # ^ |   -43 authors did
•  » » » » 6 weeks ago, # ^ |   +26 How can you be so confident? lol
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +65 No, we are not that cruel (At some point, I was also an expert).
•  » » » » » 6 weeks ago, # ^ |   0 oh, sorry, than it must have been a very lucky coincidence for me lol
•  » » » » 6 weeks ago, # ^ |   +3
 » 6 weeks ago, # | ← Rev. 2 →   +23 Rating change is faster than editorial :D thanks
 » 6 weeks ago, # |   0 For C instead of using map an easier implementation will be to sort the array and count the occurrences.
 » 6 weeks ago, # |   +1 Is E related to something like toposort(finding indegree = 0)?Can someone give hint please
•  » » 6 weeks ago, # ^ | ← Rev. 4 →   0 hintmake the swaps in permutation into trees, slove the problem in it, and then using toposort.
•  » » » 6 weeks ago, # ^ |   +12 Can you elloborate on the idea ? I can't get how to construct a tree form permutation Thanks!
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +22 If we connect $i$ and $p_i$ in a graph, you will see that the graph is some loops. So for one loop with length $k$, the minimal number of swap must be $k-1$ and the swap must connect all node in the loop. So you will see that if you connet all swap $(a_i,b_i)$, it will look like a forest.
•  » » » » » 6 weeks ago, # ^ |   0 Yes, but I have no idea how to solve it on the tree
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 3 →   +15 OK. For an element in position $i$, we need to move it to position $p_i$. We will see that we can only use a series of swaps to move $p_i$, and two node have only one path in a tree. So if the edges in the path from $i$ to $p_i$ is represented as $x_1,x_2,\dots$, they must be used in such an order in the final. So we can make a new graph to describe the order for the swaps, and then use a topo sort can slove it.
•  » » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 But it seems that the number of edges is $O(n^2)$..?
•  » » » » » » » » 6 weeks ago, # ^ | ← Rev. 4 →   +15 Oh, I forgot it. A good observation in this problem is that one edge may appear at most twice in all paths. Because A swap edge can only change two position, so it can be proved that if three or more paths through an edge, there must have no solution. So there are at most $2n$ visit for all the edges. Finally, the time will be $O(n)$.
•  » » » » » » » » » 6 weeks ago, # ^ |   0 got it, thx
•  » » » » » » » » » 6 weeks ago, # ^ |   0 It is unbelievable that I send all the solution in the discussion.
•  » » » » » » » » » 6 weeks ago, # ^ |   0 lol
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I only have an $O(n^2)$ algorithm. For each loop, choose one node as the starting point, then judge whether the dfs order on the tree is same as the loop's order.
•  » » » » » » 6 weeks ago, # ^ |   0 You can see my explanation in the front.
•  » » » » » » » 6 weeks ago, # ^ |   0 Awesome! Thank you very much
 » 6 weeks ago, # |   +12 Awesome round. Fast Editorial. Quick Rating Changes. rivalq, CoderAnshu supremacy.
 » 6 weeks ago, # |   0 Can anyone tell me what is wrong with my code idea for B https://codeforces.com/contest/1682/my
•  » » 6 weeks ago, # ^ |   +1 I just edited one line on your code!
 » 6 weeks ago, # |   +15 Just gonna share my construction for D here (no clue whether it's the same as the editorial): SpoilerRed crosses are odd degree vertices. The black lines trace out edges between even degree vertices. Blue lines are edges between odd degree vertices. Also, imagine I drew a circle.Submission: 158082919 (the code isn't very neat)
•  » » 6 weeks ago, # ^ |   0 Thanks
•  » » 5 weeks ago, # ^ |   0 What do you do when there are two ones at the end?
•  » » » 5 weeks ago, # ^ |   +1 If the upper or lower segments of even degree vertices do not exist, it is fine to connect them to the next available point.You may be thinking that the previous 1 will have even degree, but it will be compensated by a blue edge.
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 For example, this is what I get when I try to follow the intuition from the picture to construct the tree on string 10001100 (crosses are vertices with odd degrees, circles — vertices with even degrees)If I follow the intuition from the picture, I end up with a 1 with an even degree.
•  » » » » » 5 weeks ago, # ^ |   +1 Well actually the answer is NO for this testcase since the number of 1s is odd.
•  » » » » » » 5 weeks ago, # ^ |   0 Oh, my bad. Thanks!
 » 6 weeks ago, # |   0 For question C an input like 1,2,9,8,10,11,11 should have 3 as an answer right but the code will give 4 as the answer. Can someone tell me what am i missing?
•  » » 6 weeks ago, # ^ |   0 Put 1 in the middle.
•  » » 6 weeks ago, # ^ |   0 11 10 9 1 2 8 11 , 1 is common in both lists.
•  » » » 6 weeks ago, # ^ |   0 Got it Thanks!!
 » 6 weeks ago, # |   0 the round was lucky for me; I just became specialist ;)
 » 6 weeks ago, # |   0 Another easy to see proof for A: Number of element equal to the middle element has the same parity as that of N. So decrease N by 1, the parity of the middle elements should be changed
 » 6 weeks ago, # | ← Rev. 2 →   +25 Here's a pictorial solution to D which is very similar to the one in the editorial. SpoilerAssume that the red dots are odd guys and there are lots of even guys on the boundaries. The blue curves denote the edges. The green one is a special case to handle some leftover even guys.The one in the editorial just picks a pivot adjacent to a red dot so that the green curve looks like a blue one. Observe that the parity of the degree of the pivot is correct irrespective of its choice.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 ありがとう
 » 6 weeks ago, # | ← Rev. 2 →   -43 I think C solution is not correct, as it doesn't contemplate all possible cases. The one concretely isn't ok on the pretests 2 is the input num 22:1 1 2 3 3Where it says answer is 3. If it was the 1 or the 3 the number that had a single appearance it would be right, as it could be put in the middle of the array, but when is the 2 there is no way to order it that gives result 3. I made this awful code just to test it and it seems that the max increasing substring is in fact 2 // C++ program to display all permutations // of an array using STL in C++ #include using namespace std; int maxSubsequence(int a[], int n); // Function to display the array void display(int a[], int n) { for (int i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl; cout << maxSubsequence(a, n) << "\n"; } int maxSubsequence(int a[], int n){ int rl = 1; int lr = 1; int aux = 1; for(int i = 0; i < n; i++){ aux = 1; int j = i + 1; while(j < n && a[j-1] < a[j]){ aux++; j++; } rl = max(aux, rl); } for(int i = n-1; i >= 0 ; i--){ aux = 1; int j = i; while(j > 0 && a[j-1] > a[j]){ aux++; j--; } lr = max(aux, lr); } return min(rl, lr); } // Function to find the permutations void findPermutations(int a[], int n) { // Sort the given array sort(a, a + n); // Find all possible permutations cout << "Possible permutations are:\n"; do { display(a, n); } while (next_permutation(a, a + n)); } // Driver code int main() { int a[] = { 1, 1, 2, 3, 3 }; int n = sizeof(a) / sizeof(a[0]); findPermutations(a, n); return 0; } Am I missing something?
•  » » 6 weeks ago, # ^ |   +16 The answer is 1 3 2 3 1. Your testing code is just not corrected in finding LIS.
•  » » » 6 weeks ago, # ^ |   -8 Oh I see, for some reason I thought the sequence had to be consecutive. Thank you!
 » 6 weeks ago, # |   0 Can someone please refer to me sources to understand what supermask is? (for problem B)
 » 6 weeks ago, # |   +19 I liked problem F, but I feel like it would've been better to not add the artificial complexity from the bipartite flow graph stuff.I'd prefer something like "there is a wall of stacked 1 by 1 blocks along the number line. for most of the infinite number line the height is average, but unfortunately there are some positions where there are more or fewer than average blocks in a single column. can you figure out how many steps to the left and right in total the boxes need to be moved? The non-average heights are given in this format with queries..."
•  » » 6 weeks ago, # ^ |   +5 I second that, it'd be better this way
 » 6 weeks ago, # |   +24 A shameful round for me only solved A-C ): :(
 » 6 weeks ago, # |   +3 Great Round, enjoyed it a lot!!!
 » 6 weeks ago, # |   0 in problem B, with the input:180 1 2 7 4 5 3 6it seems like the answer is not correct, if im wrong, pls point out my mistakes.
•  » » 6 weeks ago, # ^ |   +2 what is your ans?
 » 6 weeks ago, # |   0 Man the solution for D blew my mind :D Great Round!
 » 6 weeks ago, # |   0 Good tutorial for C
 » 6 weeks ago, # |   +2 please add the problem rating in the tags of the problems.
 » 6 weeks ago, # |   0 Unordered_Map users...in problem C : We are faster then map users..... (*Le) Author : test Case 28....; (after getting rank 4500+) Yeh Anti-Hashing Ky hoti hei ----- " Does Unordered_Map become Shower than Map " > lol <
 » 6 weeks ago, # |   +5 It was not intuitive or provable in the contest that maximum X would be the AND of all misplaced elements of the array. Bad day for me:)
 » 6 weeks ago, # |   +5 Changing just one line in my problem C code gave AC after the contest :(
 » 6 weeks ago, # |   +5 For problem B, why the upper bound of the answer is the bitwise AND of all elements which are not at their correct positions.
•  » » 6 weeks ago, # ^ |   +6 Because X must be a submask of all such elements and bitwise AND is maximum of those X.
•  » » » 6 weeks ago, # ^ |   0 Thanks:)
 » 6 weeks ago, # |   -8 In question C , on using unordered_map , I am getting TLE whereas using map accepts the solution. Can anyone please tell why it is so? My both submissions : Accepted Solution using map [problem:C][TLE submission using unordered_map](https://codeforces.com/contest/1682/submission/158110821)
•  » » 6 weeks ago, # ^ |   0
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +5 unordered map answers its queries(add, get) in amortized O(1) time. The key word is amortized, which means that there are cases when it's not that fast. The worst case is O(n) in time for these operations, which you've probably dealt with in tc 28.
 » 6 weeks ago, # |   0 I have a different solution to problem D, firstly we left rotate the array until the suffix segment with $s[i]=0$ has been moved to the front, i.e the last element now has $s[i]=1$. Now I maintain a stack initially empty, with node index and parity of node starting from left end of the string, and make an edge between stack top and ith index element, then pop the stack top. Now, based on the parity of the top element and the ith element, I push new elements into the stack.Why and how it works is a bit difficult for me to explain but these observations might help understand the reasoning-1) A contiguous segment of even elements can be replaced with 2 odd elements. We connect the vertices in a line with the odd elements being both ends of the line.2) When an edge is constructed between an odd element and an even element, the even element can now be treated as an odd element and the odd element can be forgotten.Here is my submission
 » 6 weeks ago, # |   0 speedforces
 » 6 weeks ago, # |   0 can anyone please elaborate editorial B
•  » » 3 weeks ago, # ^ |   0 From the given sequence of numbers, there is subsequence of numbers from the original sequence that are not in order and can be sorted by swapping among themselves with the help of a fixed value, X in this case, which is also part of the original sequence, when when we take bitwise and of all the numbers from the non-sorted subsequence we make sure the final answer(bitwise AND) is the value made out of all set bits of numbers part of the subsequence hence we can reorder this subsequence with this largest fixed number X. I hope this helps.
 » 6 weeks ago, # |   0 In 'C', the solution to 1 1 2 in test case 2 is 2. Shouldn't it be 1? min(1,2)=1
•  » » 6 weeks ago, # ^ |   0 You can place them as 1 2 1.
•  » » » 6 weeks ago, # ^ |   0 Oh snap.Thanks for the tip. I missed the part where we can rearrange the array arbitrarily :(
•  » » » 4 weeks ago, # ^ |   0 Sorry for this stupid question, but how can we change the order? Isn't the order of the characters important?
•  » » » » 4 weeks ago, # ^ |   0 problem allows you to place elements in any order you want so that you would get min(lis,reverselis) maximized. Read the problem once again, it has to be clear
•  » » » » » 4 weeks ago, # ^ |   0 oh didn't notice, Thanks a lot!
 » 6 weeks ago, # |   +6 Video: A very interesting Multiset Hashing Solution to Problem EPosting this because the Editorial to problem E is not posted yet (and I talked to the problemsetters and their solution is different from mine)
•  » » 6 weeks ago, # ^ |   +10 This was the soln I implemented during testing. 158094993
 » 6 weeks ago, # |   +5 For A, don't you mean $s_i = s_{n - i + 1}$ instead of $s_i = {n - i + 1}$?
 » 6 weeks ago, # |   0 In second problem ,AND SORTING i am confuse in why it is taking 'and(&)' of all elements present at not correct position, please help
•  » » 6 weeks ago, # ^ |   0 We don't need to move the elements at the right places. Hence only the elements at wrong places should be eligible for swapping. Thus X should be & of all those values.
•  » » » 6 weeks ago, # ^ |   0 thanks buddy
 » 6 weeks ago, # |   0 In part C https://codeforces.com/contest/1682/submission/158147851 if I don't write i
 » 6 weeks ago, # |   +5 I'm afraid that I didn't catch the point of problem C.Why don't we just make the subsequence in a monotonically increasing order?Like this:[2 2 4 4 5 5].By this way,LIS(a')=0.
•  » » 6 weeks ago, # ^ |   +5 Oh, I made such a stupid mistake. :( Neglect it.
 » 6 weeks ago, # |   +10 Good Problem E!Maybe Better for having a sooner editorial XD
 » 6 weeks ago, # |   0 Why not use Hash to solve the 1682A?And why do you Hack unordered_map in 1682C?
•  » » 6 weeks ago, # ^ |   0 Why not use Hash to solve the 1682A? Because its an overkill. Simpler easy to implement solns exist. And why do you Hack unordered_map in 1682C? Because it's hackable.
 » 6 weeks ago, # |   +14 I have added editorial of problem E. It's really long and detailed. Hope you would like it.
•  » » 5 weeks ago, # ^ |   0 For problem E, how to understand the phrase "because we have to sort the permutation in a minimum number of moves which isn't possible if two cycles are merged at any instant".
•  » » » 5 weeks ago, # ^ |   +1 I have understood, thanks.
 » 5 weeks ago, # | ← Rev. 2 →   0 In problem 1682C — LIS or Reverse LIS?, how do we have the answer 3 for this input: 1 1 2 3 3?
•  » » 5 weeks ago, # ^ |   +3 1 3 2 3 1
 » 5 weeks ago, # |   0 Can anyone explan the problem F?
 » 5 weeks ago, # |   0 Really good problem D and E! But why the editorial of problem F is really late......
•  » » 5 weeks ago, # ^ |   +9 We both are extremely busy in office, sorry for the delay. Will post it very soon.
•  » » » 5 weeks ago, # ^ |   0 Thanks really much!
•  » » » 5 weeks ago, # ^ |   0 Understand! Thanks very much!
 » 5 weeks ago, # |   0 Hi , in c is there any way to get one common index in even number for (a) and (a)prime ??
 » 5 weeks ago, # |   0 I have been trying to solve the problem 'B". Why and how displaced a&b&c... = max(X) ? Why '&' of some elements is '&' of all the pairs between these elements? Why 'X' must be a submask of all elements which are not at their correct positions. Can you please suggest some articles based on supermask and submask? I really appreciate any help you can provide.
 » 5 weeks ago, # | ← Rev. 3 →   0 Correct me if I am wrong but another interesting property in Question E is that if you have a correct order say [(a,b),(b,c),(j,k)....(f,g)] and you inserted them in a stack (the 0th index inserted first) then the solution obtained by popping the stack (essentially reversed) is correct given that you switch the places of numbers of that pair (instead of the indices).Here is an example: 4 3 2 3 4 1 1 4 2 1 1 3 The optimal solution here was [2,3,1]. Using my way, we say it's [1,3,2]. Solving:- First we perform the (1,4) swap (recall, (1,4) are elements this time and not indices). We get 2 3 1 4- Time for (1,3) swap; 2 1 3 4- Finally (1,2) swap; 1 2 3 4 I tested it for all of the solutions for the second test and it worked too!
 » 5 weeks ago, # |   0 Can you please tell me why I'm getting time limit exceeded. Here is my code
•  » » 5 weeks ago, # ^ |   0 Yeah, I got it now.
 » 5 weeks ago, # |   0 Hey guys I have a question regarding C :Consider the test case : 1 3 1 2 2 Now, there are three arrangements of $[1, 2, 2]$ : $[1, 2, 2]$ : here, $LIS(a) = 2$ and $LIS(a') = 1$ so beauty is $1$. $[2, 1, 2]$ : here, $LIS(a) = 1$ and $LIS(a') = 1$ so beauty is $1$. $[2, 2, 1]$ : here, $LIS(a) = 1$ and $LIS(a') = 2$ so beauty is $1$. So beauty in every case is $1$. My code outputs $1$ as well. However, the output and the formula from the editorial suggest the answer should be $2$. Can anybody point out where the flaw in my reasoning is?
•  » » 5 weeks ago, # ^ |   +10 Nevermind I made a mistake in case $[2, 1, 2]$ got it
 » 4 weeks ago, # | ← Rev. 2 →   0 I'm getting TLE at testcase #28 in Problem C. Here's my submission. Can anyone help me why I'm getting TLE.
•  » » 4 weeks ago, # ^ |   0 Unordered maps can be blown up easily. You can refer comments above for the same.
•  » » » 4 weeks ago, # ^ |   0 LOL what made hash function slow here ? I'm new to this could you plz explain it.
•  » » » » 4 weeks ago, # ^ |   0
•  » » » » » 4 weeks ago, # ^ |   0 thanks
 » 4 weeks ago, # |   0 hey, I am trying to understand why in problem C the solution is said to be NlogN? We simply add to the map and then traverse it, isn't it just N? what am I missing here?
•  » » 4 weeks ago, # ^ |   0 Adding elements to std:map in C++ is log(size).
•  » » » 4 weeks ago, # ^ |   0 Thank you!
 » 3 weeks ago, # |   0 Hi, I don't understand the logic for Problem B, can someone please help me out?
•  » » 4 days ago, # ^ | ← Rev. 3 →   0 If the array is in sorted order than index and element at that index will be same as each of them occurs exactly at once in array; So the elements which you will have to swap will be at different indexes. Thus you will end up ANDing all those elements which are not same as their indexes i.e. if (i!=array[i]) ans &= array[i] My submission
 » 9 days ago, # |   0 why was int ans = (1 << 30) — 1 used in task 1682B;