### awoo's blog

By awoo, history, 5 months ago, translation, 1620A - Equal or Not Equal

Idea: BledDest

Tutorial
Solution (Neon)

1620B - Triangles on a Rectangle

Idea: BledDest

Tutorial
Solution (awoo)

1620C - BA-String

Idea: BledDest

Tutorial
Solution (awoo)

1620D - Exact Change

Tutorial

1620E - Replace the Numbers

Idea: Neon

Tutorial
Solution 1 (Neon)
Solution 2 (Neon)

1620F - Bipartite Array

Idea: BledDest and Neon

Tutorial
Solution 1 (Neon)
Solution 2 (Neon)

1620G - Subsequences Galore

Idea: BledDest

Tutorial
Solution (BledDest)  Comments (75)
 » In my opinion, I think that the positions of E and D should have been swapped.
 » In the problem E-Replace the Number, alternate solution mentions the small to large method. Can anyone explain how it has complexity of O(n log n)? Any resource added would also be helpful.
•  » » With small to large method you want to take the smaller set and add it the larger one. When you do this if you had an element in the smaller set, now it is, for sure, in a set with size at least twice the one beforehand. So you can move each element at most log(n) times since the set can't become more than the number of elements.Here in the task you can keep them in vectors and if needed just swap the vectors after adding the smaller one to the larger.Hope that explains it.
•  » » When you merge a smaller set into a larger set, the size of the generated set is at least twice of the smaller one. So the set-size will exceed N in no more than log(N) merges.
•  » » 5 months ago, # ^ | ← Rev. 2 →   So the worst came comes when both x and y have same number of occurrences which comes at 2, 4, 8, 16... . This means at each power of 2 indexes we will merge and total merge complexity will be O(n) So at each log(n) we do O(n) operation which makes it O(nlog(n)).
•  » » You can have a look at this blog: http://codingwithrajarshi.blogspot.com/2018/06/small-to-large.html
•  » » it is a concept of optimization of disjoint set union
•  » » your performance graph is pretty good, You will obviously make it to Red soon even if there are cheaters.
•  » » » Thanks for saying I might be red one day, I don't really care much about cheaters. I am just hoping I get +1 rating point to get CM for the first time and that can happen only when someone above me is removed.
•  » » » » Congrats dude on making it to CM
•  » » » » » Thank you :)
 » I upsolved E using map of list as merging list is O(1) operation.
•  » » I did the same, and then also tried map of list of vectors. With the idea to combine the advantages of lists and vectors, concatenating lists and push_backing in vectors. But it was a bit slower. If testdata contain many unique values, each value must be pushed once into vector and vector once in a list.
 » Can someone please explain why this DSU based solution for E is failing TC 4? I am using a hashmap and a pointer array to map the representatives to the values and vice-versa; and everything seems to be working fine. My Submission.
•  » »
•  » » » Omg, thank you so much. I was not able to find this bug when testing with smaller sets of numbers because after "merging" indices of a number to itself, I was not performing any more operations on the set...
•  » » » Can you check why am I getting MLE on my solution Problem E
•  » » mine worked https://pastebin.com/VFVg0qB1
 » In case you are interested in video solutions, Here they are(for A-E)
•  » » Amazing content sir as always
 » For problem E, we can have map of number vs linked list of indexes. Then for type 2 query, we just need to append linked list for x behind linked list for y which can be done in o(1). and for type 1 also be handled in o(1). overall o(n).
 » 5 months ago, # | ← Rev. 3 →   Can somebody please help me figure out what is wrong with my submission for EEdit: Silly mistake... I reversed the digits in my answer
 » someone, please explain to me the solution of Problem C in easy language
•  » » 5 months ago, # ^ | ← Rev. 2 →   See this https://www.youtube.com/watch?v=0wtOyCcdUWo and after that read the editorial.Learn how decimal to other base; other base to decimal works : Number system conversion: https://www.tutorialspoint.com/computer_logical_organization/number_system_conversion.htm
 » In C , are there any constraints on the total number of strings possible ? Will it be always in the INT range ?
•  » » We can fill at most K b's, so total number will be K^cnt, where cnt is the number of asterisks. It will easily overflow 9e18
•  » » » 5 months ago, # ^ | ← Rev. 2 →   Yes ,I totally I understand this , but have a look at this code once https://codeforces.com/contest/1620/submission/139857428
 » Can anyone check my E solution. I have stored the values and a vector of pointers along with it and and when changing value i just move the pointers from one to another https://codeforces.com/contest/1620/submission/139817827
 » Getting TLE in Problem E, with this solution. Can somebody tells why because it seems more efficient than one in the solution 2 of tutorials.https://codeforces.com/contest/1620/submission/139879128
•  » » TLE because of how you are processing your 2nd type of querry.consider 10^5 querries of 2nd type like 2 1 22 2 32 3 4....that is in the end converting all 1 to some large numberif the vector containing index of 1 has 10^5 elementsDo you see where you are going wrong?10^5 x 10^5 operations there is your TLE
 » https://codeforces.com/contest/1620/submission/139877833 Can someone explain why this submission gives TL on E? It should be O(n) since double-linked list concatenation is O(1) operation... Thanks.
•  » » It is due to this line val_map[y] = val_map[x];If y has no entry till now you are copying x's list to y which might be O(n).You can instead do val_map[y] = move(val_map[x]);https://codeforces.com/contest/1620/submission/139901581
•  » » » Thanks a lot!
 » 5 months ago, # | ← Rev. 3 →   While going through the solutions of other participants for problem E I noticed everyone is using a large vector to store the indices for each value. So I am wondering, is there anything wrong with using a map? I used an unordered_map> and it did work fine for this problem. Is there something I have to worry about when using maps for such problems (other than the hashtable overshooting the memory limit)?
 » In problem E why my solution is wrong this one.any suggestion or testcase
•  » » I think you should handle the case when 2 x y and x = y
•  » » » I am not able to understand why this case when 2 x y and x = y has to be specially handled?what is wrong with updating x with parent[x]?
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   it depends on your solution, in my case, it was because : colorInd[oldColor] = -1; so I'm deleting the old color although I should keep it. you can check my solutions and compare.
 » 5 months ago, # | ← Rev. 3 →   https://codeforces.com/contest/1620/submission/139826532 I have a question about E. in my opinion i have O(n) solution, but it takes TL at 5th test, can someone tell me what's wrong? Is it solution or it's just Python can't make it
 » Can somebody explain how we are converting x-1 to the mixed base?
•  » » Converting 0, we get 1st string. So converting x-1, we get xth string.
•  » » Here is a similar, but simpler problem to better help understand converting to other bases. C — One Quadrillion and One Dalmatians
•  » » » Thanku so much
 » 5 months ago, # | ← Rev. 2 →   Can someone tell me some similiar problem as E, or some algorithm tag?
 » In the editorial of D, no need to take more than $3$ coins $1$ and more than $3$ coins $2$ I think you meant, no need to take more than $2$ coins $1$ and more than $2$ coins $2$ Because, in the given solution code, you are iterating from $i = 0$ to $i \lt 3$. And, I have also done the same :)
 » cur = (j — i + 1) * k + 1 what is the use of plus 1 in the (j-i+1)
 » C problem is really amazing. And the solution is lot more amazing.
 » 5 months ago, # | ← Rev. 3 →   I have a different solution to F following the editorial, there can't exist $i a_{j} > a_{k}$. if an array satisfies this condition then the array can be decomposed entirely into two or less increasing subsequences.Proof: consider doing a pass through the array and greedily picking out an increasing subsequence. Do two such greedy passes through the array let $S$ be the sequence chosen by the first pass and $T$ the sequence chosen by second pass. Assume there exist an index $k$ that isn't chosen by either sequences pick such smallest $k$, indexes $1$ to $k-1$ can't be all in $S$ otherwise $k$ would be in $T$, this implies there exist an index $i$ with $i+1$ < $k$ such that $i$ is in $S$ and $i+1$ is in $T$. Pick $j$ such that all indexes from $i$ to $j$ are in $T$ but $j+1$ is not. then $a_{i} > a_{j}$ otherwise some index between $i+1$ and $j$ would had been chosen by $S$ and $a_{k} > a_{j}$ otherwise $k$ would have been chosen by $T$ so we get $a_{i} > a_{j} > a_{k}$ which is impossible. For the other direction if there exist a length 3 decreasing subsequence then all three must be in different increasing subsequences. Great!now we can construct a dp that tries to builds two or less increasing subsequences. Let $dp_{0 / 1,i}$ be the minimum possible value of the end of the increasing subsequence that $i$ is not part of(consider the end of the subsequence to be $-\infty$ if its empty) , $0/1$ denotes whether we choose to flip the sign of $p_{i}$, the transitions are deciding whether or not to stick $p_{i}$ into the same subsequence as $p_{i-1}$ ,the answer is yes if either $dp_{0,n}$ or $dp_{1,n}$ $\neq\infty$my submission :140109080 (in hindsight the dp I described should be equivalent to the editorial dp, but I think this interpretation is cleaner and easier to understand)
•  » » It seems you proved Dilworth Theorem.
 » For E I think you can also use dsu.For each number $x$ in the array, all of the indices $i$ such that $a[i] = x$ will be in the same group. Maintain an array $root$ that keeps track for each number in the array what the current representative of that number's group is. It will be $0$ if the number doesn't exist in the array. Also maintain an array $val$ that tracks the leaders' value. So the number at index $i$ will be $val[Find(i)].$For the first type of query, we check if $x$ is in the array. If it is, we merge the index of the added element with the pre-existing group for $x.$ To find the correct group we just look at $root[x].$ (It will be $0$ if $x$ does not in the current array.) If $x$ is not in the array we set $root[x]$ to the last index of the array of the newly added element.For the second type of query, we again check to make sure that both $x$ and $y$ are in the array. If they are both in the array since we're doing quick union we first merge, and then set the $val$ of the root of the merged group to be $y.$ If $y$ doesn't exist in the array then it's easier, we just set $val[root[x]]$ to be $y.$ And of course if $x$ doesn't exist then there's nothing to do. Finally we update $root$ if needed, ie. set $root[x] = 0$ because $x$ no longer exists in the array.
 » please can someone tell me why is this code failing for C ?? https://codeforces.com/contest/1620/submission/140169385 I have lost my mind at debugging this for 3 hours at this point,also is there a way to see the full testcase in this website ?
•  » » arr_choice.at(curr_index)*prod can overflow right after the last non-zero digit, when, by algorithm, the loop should break.prod might be up to 10^18 (=x) and arr_choice.at(curr_index) might be up to 4*10^6 (= 2000 * 2000 = k * n). 10^18 * 4*10^6 = 4*10^24, which is larger than ~9*10^18 (~ long long max).
 » 5 months ago, # | ← Rev. 2 →   Nice problems
 » 5 months ago, # | ← Rev. 3 →   In problem C, for this test case TC: 1 8 3 18 a***a*The output of the editorial code is abbabbb i.e; (2+1) * (3+1) => 12th lexicographically smaller but I asked for 18th right. How is this correct?
•  » » 5 months ago, # ^ | ← Rev. 4 →   Your test has n=8 and the string is length 6 — something is wrong. However, that's not how you obtain the number from its digits. Consider base 10. If you have a number, consisting of digits 1, 2 and 3, then this number is 1 * 10 * 10 + 2 * 10 + 3. Same here. You have a number, consisting of digits 2 and 3 (the lengths of b segments in the answer). Thus, the number is 2 * (3 + 1) + 3 = 11. So this is the 12th string but if n was equal to 6 in your test.If the string instead was *a***a* and the answer was babbabbb, then the number would be retrieved as 1 * (3 + 3 + 3 + 1) * (3 + 1) + 2 * (3 + 1) + 3. So you have to multiply each digit by the bases of lower digits and add up the results.
•  » » » 5 months ago, # ^ | ← Rev. 6 →   The test string was "*a***a**". Thanks a lot! I understood now. First we are converting from Decimal system to this system and to convert from this system to Decimal, we are multiplying the base-i. Similar to how we convert to from Hex to Decimal by multiplying 16 powers. PS: I like your humbleness and helping nature.
 » My code for problem C gives TLE on test case 5. Can someone please help me out? Here's the link to my solution. https://codeforces.com/contest/1620/submission/140430241 Thanks!
•  » » long p = 1; for(;p<=list.get(i)+1;++p) { if(p*productt[i+1]>=x) { // ... return i; } } This loop might have up to 4*10^6 iteration. You can rewrite this logic without a loop using integer division. Be careful with not overflowing long, including in intermediate results.
 » I really dont understand the problem D. Why there is no need to take more than 3 coins 1 and more than 3 coins 2? In my opinion, there is no need to take more than one coin 1 (i.e. one coin 1 at most) because if any ai required two coins 1, two coin 1 could be replaced by one coin 2; and ,similarly, there is no need to take more than two coins 2. This really confuses me. Could anyone explain it? Thanks in advance!
•  » » Your approach is correct. My solution works similar to your idea. Submission
•  » » » Thank you so much!
 » in problem A if the string is (NNNE) in this case the answer should be NO but the editorial says something different..... can anyone make me understand how it is possible pls????
•  » » Consider the array with entries 1,2,3,1. Here 1 != 2 != 3 != 1 == 1. Hope this helps
 » I can't understand why my code is wrong. It can't pass the example. #include #include #include #define ll long long #define rint register int #define INF 0x7fffffff using namespace std; int t,n,a,m; int maxElem(){ int maxn=0; for(int i=1;i<=n;i++){ maxn=max(maxn,a[i]); } return maxn; } bool single_judge(int val, int c1, int c2, int c3) { for(int cur1=0;cur1<=c1;cur1++){ for(int cur2=0;cur2<=c2;cur2++){ if(cur1+2*cur2>val){ continue; } if((val-cur1-2*cur2)%3!=0){ continue; } if((val-cur1-2*cur2)/3<=c3){ return true; } } } return false; } bool judge(int c1,int c2,int c3){ for(int i=1;i<=n;i++){ if(!single_judge(a[i],c1,c2,c3)){ return 0; } } return 1; } void solve(){ int ans=INF; for(rint c1=0;c1<3;c1++){ for(rint c2=0;c2<3;c2++){ if(m-c1-c2-c2<0){ continue; } int c3=max(0,m-c1-c2-c2); if(judge(c1,c2,c3)){ ans=min(ans,c1+c2+c3); } } } cout<>t; while(t--){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } m=maxElem(); solve(); } return 0; } 
 » Could not understand the solution for A. Can anyone explain in a simpler way ?
 » https://codeforces.com/contest/1620/submission/140748031My subission for C is giving wrong ans at tc 1 in codeforces compiler , while it works properly in my system, can any one check
•  » » Sorry my bad . I noticed an error now.
 » 5 months ago, # | ← Rev. 2 →   Counterexample to B. "Since there are points on all sides, the points on the opposite side are the furthest" https://ibb.co/G3FnRmW
•  » » 5 months ago, # ^ | ← Rev. 3 →   i got it now. i was calculating the height of triangle wrong but cant delete this now can i?
 » 4 months ago, # | ← Rev. 2 →   I solved E using Linked list in O(n) https://codeforces.com/contest/1620/submission/141979731
 » Here is the casework solution for D https://codeforces.com/contest/1620/submission/142005976
 » Does anyone know why this solution to E is getting an MLE on testcase 4? 143353188
•  » » same happening with me 143433175
 » 4 months ago, # | ← Rev. 2 →   Edit: I see why because of this link: https://codeforces.com/blog/entry/64625 check it. Problem G: Some contestant solved this problem using inclusion-exclusion, let cnt be the number of strings that are subsequence of the strings given by the mask, they do +cnt when the amount of bits is odd and -cnt when is even. Then, they do dp[mask] = cnt and apply SOS DP at the end. SOS Dp is clear, but what is the argument of that inclusion-exclusion when adding and decreasing depending on the bits?Sorry for my engish, thanks in advance.