### awoo's blog

By awoo, history, 7 weeks ago, translation,

1494A - ABC String

Idea: BledDest

Tutorial
Solution (Neon)

1494B - Berland Crossword

Idea: Neon

Tutorial
Solution (awoo)

1494C - 1D Sokoban

Tutorial
Solution (awoo)

1494D - Dogeforces

Idea: Neon

Tutorial
Solution (Neon)

1494E - A-Z Graph

Tutorial

1494F - Delete The Edges

Idea: BledDest

Tutorial
Solution (BledDest)

• +78

 » 7 weeks ago, # | ← Rev. 2 →   +13 Good contest and editorial!
 » 7 weeks ago, # |   +8 First time I will reach Pupil
•  » » 7 weeks ago, # ^ |   0 How are you so sure ?
•  » » » 7 weeks ago, # ^ |   0 Confidence. As you can see Now i am in pupil
•  » » » » 5 weeks ago, # ^ |   0 are you sure?
•  » » » » » 5 weeks ago, # ^ |   0 Now I am newbie because of negative rating . You can see my rating graph .
 » 7 weeks ago, # |   +17 Thanks for EaRly editorials.
•  » » 7 weeks ago, # ^ |   0 It was a very fast Editorial Indeed. Anyhow, I loved the round. Thanks to authors !
 » 7 weeks ago, # |   0 Thanks for the editorial and codes!
 » 7 weeks ago, # |   0 Finally the editorial :)
 » 7 weeks ago, # |   +6 Can anyone please help me understand why my approach to B is wrong? I have basically done a recursive backtrack since the possibilities are very small. 108948906
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Your approach paints black twice on the same cell for this case 2 0 0 1 2. 0 0 1 1 0 0 0 1 At some point, Your array will become this. And It falsely identified it as correct solution.Modified code
•  » » » 7 weeks ago, # ^ |   0 Thank you so much!
•  » » 7 weeks ago, # ^ |   +4 In this case , your code may first fill the top row just as the green line (n-1 case), then fill the rightmost column just as the blue line (n-1 case). However, the top-rightmost cell (in red circle) is covered twice , which is incorrect .when L=0,U=n-1,R=n,D=0 ,your code will output "YES" but the correct answer is "NO" .(Sorry for my poor English :P)
•  » » » 7 weeks ago, # ^ |   0 Thank you so much! I got it now!
 » 7 weeks ago, # |   0 Thank for the (early?) editorials. I love the contest , especially problem D & E .
 » 7 weeks ago, # | ← Rev. 2 →   0 Problem BThe easiest solution And I Get AC108991755
•  » » 7 weeks ago, # ^ |   0 I also did it this way: My submission
 » 7 weeks ago, # |   0 I tried C using binary search but I am getting a TLE, I iterated through all the special positions and calculated the total number of boxes at special positions if we stacked all the boxes before the ith position and the last stacked box is at the ith position and added the untouched boxes at special position which are to the right of the ith position My submission. Could someone help with this please.
•  » » 7 weeks ago, # ^ |   0 I did the same thing. Maybe looking at my solution would help.
•  » » » 7 weeks ago, # ^ |   0 I wanted to know the reasoning behind the TLE.
•  » » » » 7 weeks ago, # ^ |   +4 I think std::find causing the TLE since it's linear.
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +5 Hey tyagsa .I replaced find to the map.I have gone AC 109024868. I'm think find works in O (N)
•  » » » 7 weeks ago, # ^ |   0 Can you briefly explain the naive algorithm mentioned in q? I am not even able to understand that :((
•  » » » » 7 weeks ago, # ^ |   0 We cannot move boxes that are in negative positions to positive ones because we cannot pull boxes on ourselves.So. we will solve for positive and similarly for negative, we add the results and print it! We can iterate to which position we will pull the boxes (the boxes to this position will be sequential). Is this position always a special position because it makes no sense to pull after a special position ?. binsearch will find how many boxes will stand consequtevely and again, binsearch will find how many consequtevely boxes are on superpositions and add suf [i + 1] to the answer, which is equal to the number of boxes that we have not moved but they are on special positions.P.S. Sorry for bad English 109027439
•  » » » » » 7 weeks ago, # ^ |   0 thanks a lot :)
•  » » » » » 7 weeks ago, # ^ | ← Rev. 4 →   0 i did the same thing as you at first got WA Here.After reading your code i did a little change of lowerbound(checking if the value at the position we found with lowerbound is strictly greater than the value at out current special index and then decrease if strictly greater) to upperbound in the first binary search and got AC Here.Can u help me in finding my mistake[UPD: found mistake (accessing the end of array in some cases)]
•  » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +1 Hey, your mistake in 2 point.1)after first lower_bound -> (if(p[j] > sp[i]) j--;) i replaced it by if(p[j] == sp[i]) j++; think why?2) and in second lower bound instead sp[i]-j i do sp[i]-j + 1. because we have j boxes, not j + 1109054593 check it
•  » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Thank you. For highlighting these points, especially point 2 but in point 1 i think i was accessing the nth element in somecases. which was giving some garbage.(did this and got AC)Appreciate your time and effor in correcting me. Thank You.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Thank you very much! never looked at the find function while debugging, will keep this in mind next time.
 » 7 weeks ago, # |   0 Thanks for the blazing fast editorial !
 » 7 weeks ago, # |   +1 Complexity calculation of problem D did not seem so trivial to me. Can anyone explain the complexity of the model solution?
•  » » 7 weeks ago, # ^ |   +3 The time complexity is $O(n^{3})$ First of all let's find an upper bound on the number of vertices in the graph, that is, an upper bound on $k$, in terms of $n$.I claim that the maximum number of vertices is $2n$. We can prove it by induction on depth (maximum distance from root to a leaf) of the tree. (Its really easy induction, you can try it yourself or lemme know in reply if you run into some trouble).Now for each node which is not a leaf, let's observe what happens in the recursive function $calc()$ in the editorial code. The $O(n^{2})$ for loop is executed exactly once. Then a linear number of recursive calls for its children. So, if we sum up for all non-leaf nodes, ee have $nO(n^{2}+n)$ operations over all non-leaf nodes. Which gives us a time complexity of $O(n^{3})$.
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Great explanation!Another way to visualise the maximum possible number of vertices is this: Start with the root. For the current list of leaf-nodes, what would be the worst possible split? If there are $X$ leaves, it would be a two-way split of $X-1$ and $1$. The right list cannot be split further, and we assume a similar split for the left one. This would lead to $N$ leaves and $N - 1$ non-leaves (supervisors), giving us an upper bound of ~$2N$.Why does this splitting yield maximum nodes? For each split you make, you gain a supervisor. For $N$ leaves, you can make a maximum of $N-1$ splits, and hence you can gain a maximum of $N-1$ supervisors.
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Edit: ignore this comment.
•  » » » » 7 weeks ago, # ^ |   +6 Actually you are wrong in saying that each pair of nodes can be compared no more than $O(\log_2 n)$ times, for here you assume that the maximum number of levels is $O(\log_2 n)$, which is false, because if you look at the example provided by svince in the comment above, you will see that his tree has $n$ levels, so the bottom two leaves will be compared $n$ times here.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Edit: nvm made a mistake assuming the number of levels.The time complexity is actually $O(n^{2}\log_2{n})$. Given a level in the tree, let the number of nodes in that level be $m$ and the number of leaf descendants for each node be $l_{j}$ where $1 \leq j \leq m$. Notice $\sum_{j=1}^{m} l_{j} = n$ and that the time complexity for processing the entire level is $O(\sum_{j=1}^{m} l_{j}^{2})$. This implies that the time complexity for the level is $O(n^{2})$ and the overall time complexity is $O(n^{2}\log_2{n})$ because the maximum levels in the tree is $\log_2{n}$.
•  » » » » 7 weeks ago, # ^ |   0 if you see the above comment, I provided an example where the level of the tree is not $\log n$
•  » » » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 I don't think that example justifies that for loops would run $\mathcal O(n^2)$ in the worst case. Since, that example claims that at each $n$ level you would split $x - 1$ and $1$ but the inner for loop would run only once for all $x - 1$ nodes due to the break statement and $x - 1$ times for the last node in the worst case. Summing up, the runtime of that example would be $\mathcal O(n^2)$.
•  » » » » » » 7 weeks ago, # ^ |   0 I never said that the example justifies that the loop runs for $O(n^{2})$ in the worst case. I said that it is a counter-example to the assumption that there are atmost $\log n$ levels. So unless you have a proof that the complexity is indeed $O(n^{2} \log n)$, your comment below means nothing to me.
•  » » » » » » » 7 weeks ago, # ^ |   -11 I never said that the example justifies that the loop runs for $O(n^2)$ in the worst case. Yes. You never said that. But your claim on algorithm's runtime $\mathcal O(n^3)$ implies that the loop would run $n^2$ times in the worst case. Unbeknownst to you, you made two people to feel wrong about the time complexity which is right.In summary, the algorithm's runtime is not $O(n^3)$. So unless you have a proof that the complexity is indeed O(n2logn), your comment below means nothing to me The proof would be writing a paragraph for me. But I already proved it can't be $O(n^3)$. Then a linear number of recursive calls for its children. So, if we sum up for all non-leaf nodes, ee have $nO(n^2+n)$ operations over all non-leaf nodes. You're mistaken the depth would be $n$ but it's the number of nodes at the last level or leaf nodes. Since you mentioned it's trivial to see the number of nodes of the tree is $2n$ which implies it's a binary tree. And depth should be $log_2n$. Thus, it's $log_2nO(n^2 + n)$.
•  » » » » » » » » 7 weeks ago, # ^ |   0 Ok, you are so wrong here in the last paragraph that I won't even bother correcting you. Have a nice day, and don't reply.
•  » » » » » » » » » 7 weeks ago, # ^ |   -11 Nope. I wasn't wrong. If you meant to split $\frac x 2, 1, 1, 1, 1... 1$ at each level it would be $log_2n$ recursive calls to the child nodes with $O(n^2log_2n)$ runtime else you meant to split $x - 1, 1$ at each level. Yeah it would be linear number of recursive calls to the child nodes as you said. But I disproved the runtime of for loop wouldn't be $O(n^2)$ in that case. I still don't see why you're claiming the runtime is $O(n^3)$ in the worst case.
•  » » » » 7 weeks ago, # ^ |   0 You're right. It is $\mathcal O(n^2logn)$.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +11 Actually, it's $\Theta(n^2)$ overall. Here's a precise estimation: It's easy to prove by induction that every subtree contains strictly more leaf nodes than interior nodes. Thus there are at most $n-1$ interior nodes. Everything outside of calc is obviously $\Theta(n^2)$, and dominated by reading the input. The function calc is called exactly once for each subtree, and hence at most $2n - 1$ times. In that call, ls contains each leaf in that subtree exactly once, and ch grows up to a size equal to the number of children of that subtree's root. The only action in calc which isn't $O(n)$ per call to calc (and hence $O(n^2)$ overall) is the nested for loops. Totaled over every call to calc, the inner for-loop is run at most once for each pair $(L, C)$ where $L$ is a leaf node and $C$ is a child of some ancestor of $L$. Thus, this inner loop runs at most $n \times (2n - 2)$ times, which is also $O(n^2)$ overall.
 » 7 weeks ago, # |   +17 Alternative solution for problem D (109027989)Process pairs of nodes $(a, b)$ in increasing order of weight $w$. Consider the highest ancestors of $a$ and $b$. If they are equal, skip that pair. If one of them has weight $w$, connect it to the other ancestor. Otherwise, create a new node with weight $w$ and connect it to both the ancestors.
 » 7 weeks ago, # |   0 In problem B, I tried choosing the biggest number out of the 4, reduced its value to 0 and then correspondingly decreased the adjacent numbers by 1 if required (decreased both adjacent numbers by 1 if the chosen number is n or decreased the maximum of the adjacent numbers by 1 if it is n-1). Then, I checked if any number is negative (answer is NO) or all numbers are equal to 0 (answer is YES).Keep repeating all the above steps until you get an answer. I got a wrong answer for this approach. Can anyone explain why this is incorrect?
 » 7 weeks ago, # |   0 Regarding dynamic connectivity for problem F with larger constraints: All of the necessary information to answer the relevant connectivity queries in $O(1)$ is easy to calculate while building a DFS tree. (For each back-edge leading to $c$, which DFS-child of $c$ is its other side a descendant of? For each DFS-child of $c$, is there a back-edge to some ancestor of $c$ in that subtree? Is $c$ the root?) The reasoning is basically the same as for the famous classical algorithms for finding bridges and articulation points.
 » 7 weeks ago, # |   0 How to solve the problem F with n,m <= 2 * 10^5
 » 7 weeks ago, # |   0 @awoo in your editorial in problem C, both of these vectors are not used at all correct? would you mind removing this line if so?  vector c(n), res; 
•  » » 7 weeks ago, # ^ |   0 Whoops, sure, they were used for a slow solution and I forgot to remove them.
 » 7 weeks ago, # |   0 Problem F was beautiful.
 » 7 weeks ago, # |   0 solution of ABC String using python(easy to understand)--> https://codeforces.com/contest/1494/submission/109052454
 » 7 weeks ago, # |   0 can someone please help me find why i'm getting wrong ans on B . My approach is i try to fill the corners firsthttps://codeforces.com/contest/1494/submission/109065708
 » 7 weeks ago, # |   0 Can anyone tell me what is wrong in my code? https://codeforces.com/contest/1494/submission/109073464
•  » » 7 weeks ago, # ^ |   0 You also need to check if c or c1 becomes negative at any point while iterating.
•  » » » 7 weeks ago, # ^ |   0 how it will help?
•  » » » » 7 weeks ago, # ^ |   0 ))((C is zero even though the bracket sequence is not regular.
•  » » » » » 6 weeks ago, # ^ |   0 okk, thanks a lot.
 » 7 weeks ago, # |   0 Can someone elaborate editorial for F? I can't quite understand meaning behind solution.
 » 7 weeks ago, # |   0 how bit-masking working here and why are we taking & upto 8 only
•  » » 7 weeks ago, # ^ |   0 Well, we used bit masking here for generating all possible combination of 3 variables( considering you are referring to Problem A). 2^3 = 8. So A can be replaced with ( or ). similarly B and C. Now we just need to check with a current choice, we are able to make a valid string or not. It is a clear brute force. I have used a similar approach to Problem B also submission.
 » 7 weeks ago, # |   0 Is there a DP solution for C? The tags mention Dp as well. I up-solved it using Binary Search. If anyone solved using dp, please do share it. Would love to know the dp approach.
•  » » 7 weeks ago, # ^ |   0 Yeah suffix sum is DP
 » 7 weeks ago, # | ← Rev. 2 →   0 Can anyone tell me why (problem B) for test cases 2 1 1 2 2 answer is YES? should it not be NO? nevermind got it :)
 » 7 weeks ago, # |   0 Can D solved with heaps , I tried to solve it with heaps but it fails ans the checker comment doesn't make any sense to me ! can anyone help me figure it out . 108993423
 » 6 weeks ago, # |   0 can someone explain solution of question B?
•  » » 6 weeks ago, # ^ |   0 The code may seem complicated because it uses bit-wise operations and bit masking But it's pretty simple, it tries every single combination of colors that can occur on the edges (there are only 16 possibilities), and checks if they can satisfy the requirements. If none do it just outputs "NO".If the code is what confused you, don't worry about it. You can just write it with simple if else statements, he just wrote it more practically.If you want to understand what his code does just research bit-wise operations and bit masking on google, they're not complicated at all. Cheers.
 » 6 weeks ago, # | ← Rev. 2 →   0 I can't seem to find what's wrong with my implementation for question C, it's basically the same as the editorial, but I'm getting WA on test 2 on the 78th case.
•  » » 5 weeks ago, # ^ |   0 I am also facing the same verdict. My code : 110020481I am unable to find any corner case against my submission
 » 5 weeks ago, # | ← Rev. 2 →   0 Problem-> 1494C - 1D Sokoban Submission-> 110472885Basically, as written in the tutorial, I used binary search(upper_bound) to find the next upper limit.Can someone find the mistake in the code ;_;