### oursaco's blog

By oursaco, history, 6 months ago,

Sorry for the weak pretests on A :(. We hope you enjoyed the round nonetheless.

1904A - Forked!

Idea: Apple_Method
Preparation: Apple_Method/oursaco
Analysis: lunchbox

Solution
Code

1904B - Collecting Game

Idea: oursaco
Preparation: oursaco
Analysis: lunchbox

Solution
Code

1904C - Array Game

Idea: lunchbox
Preparation: lunchbox
Analysis: lunchbox

Solution
Code

Idea: oursaco
Preparation: oursaco
Analysis: oursaco

Hint 1
Hint 2
Solution
Code

1904E - Tree Queries

Idea: Apple_Method
Preparation: oursaco

Editorial 1:
Analysis: oursaco

Thanks to errorgorn for the solution!

Hint 1
Hint 2
Solution
Code

Editorial 2:
Analysis: willy108

Hint 1
Hint 2
Hint 3
Solution
Code

1904F - Beautiful Tree

Idea: Apple_Method
Preparation: oursaco
Analysis: Apple_Method

Hint
Solution
Code
• +135

 » 6 months ago, # |   0 i love oursaco
•  » » 6 months ago, # ^ |   -8 i love oursaco
•  » » 6 months ago, # ^ |   0 Great Idea to express that in the username xd
 » 6 months ago, # |   0 after this contest i realised, that chess tasks are not for me)) i solved B easily, mb im stupid for A idk
•  » » 6 months ago, # ^ |   -12 Lol, I could say the same about math tasks. My suggestion would be for you to go onto chess.com and practice in your free time :)
•  » » » 6 months ago, # ^ |   -12 i don't think the problem is that you are not good at chess enough, this is really just a brain teaser, i might suggest instead to get familiar with those type of problems, a good book about this is "The art and craft of mathematical problem solving", an interesting one full of problems, although it barely talks about math, just skip the math ones since the book structure is designed for so :3
•  » » 6 months ago, # ^ |   -12 and who can explain why this 236632847 doesn`t work ?
•  » » » 6 months ago, # ^ |   +6 Try this sample: 1 4 2 5 8 1000 1006 Correct answer would be 1 instead of 2 (from your solution)The reason is that when you use upper_bound, it give you the first element that is considered greater than your number. You should get the prev of that element for calculating difference. In the case above, 1006 - 1000 give you 6 and upper_bound give you 8, but you should look for 5
•  » » » » 6 months ago, # ^ |   +1 thanks you man !
•  » » 6 months ago, # ^ |   0 can you provide and explain your B solution?
 » 6 months ago, # |   +9 Got TLE in B on system testing. Did two wrong submissions also on B. I was hoping to be blue today. But missed the chance.
•  » » 6 months ago, # ^ |   +24 Downvotes shows hate or what?
 » 6 months ago, # |   -12 What's wrong with this solution for A? 236554300
•  » » 6 months ago, # ^ |   -12 236585544 is my solution with same approach
•  » » 6 months ago, # ^ |   -12 Don't do that, if you check all cases by it makes your code so long and sometimes missing cases lead to WA. Instead of using you can make 2 vectors Move_x, Move_y then For from 0->7 (a knight can move 8 cases) from the Queen and King, If a cell can be moved by King and Queen your Ans++. You can refer to my code: 236529329
•  » » » 6 months ago, # ^ |   -6 Yes, solved it like that later but thought casework would work as well. I missed a few cases in brute force case solution which I have to check
 » 6 months ago, # |   0 Pretests were weak for problem D too.https://mirror.codeforces.com/blog/entry/123079?#comment-1092107
 » 6 months ago, # |   0 I liked D2 on how simple its implementation really was. Even though I implemented sparse table and range update segment trees, realizing it only required monotonic stack was pretty cool.
•  » » 6 months ago, # ^ |   0 so i think you'll be likely to dislike problem E and F.（hard and long code）
•  » » » 6 months ago, # ^ |   0 Not really. In general, I like problems that have harder logic and lesser implementation. However even if the implementation is long, if the question is very unique and beautiful, I love it regardless.
 » 6 months ago, # |   0 Can someone hack my O(n^2) solution?https://mirror.codeforces.com/contest/1904/submission/236581716
 » 6 months ago, # |   0 can anyone tell me why did I get TLE here ? https://mirror.codeforces.com/contest/1904/submission/236554358.I think the complexity here is O(N*N*log(N)). Am I wrong?
•  » » 6 months ago, # ^ |   0 You used set and map there. So on the worst case time complexity is O(N*N*log(N)*log(N))
•  » » » 6 months ago, # ^ |   0 I used them separately.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Quite strange that commenting out the map gets it accepted because the map itself should run in O(N*logN)
•  » » » 6 months ago, # ^ |   0 thats why I'm asking. I really didnt understand the issue in that part of the code.
•  » » » » 6 months ago, # ^ |   0 Your set h contains at most N ^ 2 elements. Then u lower_bound in that set for every i in array a, and run the pointer back to the beginning of the set, so the time complexity is O(N ^ 3 * logN)
•  » » » » » 6 months ago, # ^ |   0 Should the time complexity not be O(N^2 logN). As logN is required to find the upper/lower bound in the set for an element. Why there is an additional N factor in TC. Could you please explain?
•  » » » » » » 6 months ago, # ^ |   +6 oh my bad, i thought he runs the pointer back to the starting point after using lower_bound. Anyway, his code is correct, just need a few minor optimizations. Here the fixed code: 236638928
•  » » » » » » » 6 months ago, # ^ |   0 Thanks
 » 6 months ago, # |   0 Thanks for contest
 » 6 months ago, # |   0 Can someone try hacking this solution to D2?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 This test will TLE, courtesy of porker2008 print(1) print(200000) ans = [200000 - i for i in range(200000)] print(" ".join(map(str, ans))) ans = [min(200000, 300000 - i) for i in range(200000)] print(" ".join(map(str, ans)))
•  » » » 4 weeks ago, # ^ |   0 porker2008 be like: Your wish, my command mate!!
 » 6 months ago, # | ← Rev. 2 →   -10 nice problems
 » 6 months ago, # | ← Rev. 2 →   0 Can Someone explain where my code is wrong for Problem B https://mirror.codeforces.com/contest/1904/submission/236571395
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 #include using namespace std; #define ll long long #define int long long // clang-format on void sol( ){ int n; cin >> n; pair v [ n ]; for( int i = 0; i < n; i++ ){ cin >> v [ i ].first; v [ i ].second = i; } sort( v , v + n ); for( int i = 1; i < n; i++ ){ v [ i ].first += v [ i - 1 ].first; } int k = v [ n - 1 ].first; v [ n - 1 ].first = n - 1; for( int i = n - 2; i >= 0; i-- ){ if( k <= 2 * v [ i ].first ){ k = v [ i ].first; v [ i ].first = v [ i + 1 ].first; } else{ k = v [ i ].first; v [ i ].first = i; } } for( int i = 0; i < n; i++ ){ swap( v [ i ].first , v [ i ].second ); } sort( v , v + n ); for( auto&& i : v ){ cout << i.second << ' '; } cout << '\n'; } signed main( ){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); cout.tie( nullptr ); int t = 1; cin >> t; while( t-- ) sol( ); return 0; }
 » 6 months ago, # |   +3 Loved this competition! My solution to problem C first failed on system testing, but then suddenly the verdict changed) Also, my friend’s solution failed on the same test, but it changed the verdict after the final results! Can someone please explain how this could be, because I just don't understand how system testing works on Codeforces. Sorry for my poor language...)
•  » » 6 months ago, # ^ |   +3 Something like that happened to me as well. Not sure what happened there
 » 6 months ago, # |   0 can somebody help me with the reason of tle on d2(hard version) on test case 25 .here's my submission — https://mirror.codeforces.com/contest/1904/submission/236593367
•  » » 6 months ago, # ^ |   0 that is n^2
 » 6 months ago, # |   +2 Cool Contest!
 » 6 months ago, # |   0 For D1/D2, I had a solution I'd like to share.Firstly, if any position exists such that a[i] > b[i], then obviously there's no solution.Then, I iterated over the numbers from 1 to n, and for each i, I tried to find all the intervals centered around a position j such that a[j] = i. I then tried to extend it as much to the left and right as possible without messing any conditions up. I found that it you did this for all numbers from 1 to n in increasing order, then you'll either construct a valid solution or find that it's impossible to do so. You can optimize this a bit for D2 by binary searching how far to the left and right you'll extend your current position to and using range assignment and range query operations to check if the intervals you're using are okay (You can do that with a lazy segment tree).In essence, it's similar to the official solution except you actually construct the solution in this case instead of determining if it's possible. Here's my submission: 236596139It barely passes in time lol
•  » » 6 months ago, # ^ |   0 i solved D1/D2 in this way, but my code is shorter than yours
 » 6 months ago, # |   +12 It will be better if F offers stronger samples.I finished coding and passed samples in 15 min but got WA on #3, and failed to debug in remaining 30 min.Anyway, A~D are enjoyable.
 » 6 months ago, # | ← Rev. 2 →   0 Nice problems. D2 systests were pretty weak though.
 » 6 months ago, # |   0 In problem E, how are we handling the case when path is outside of current subtree?
•  » » 6 months ago, # ^ |   +3 If you reroot the tree to $x$ correctly, then each leaf in the segment tree will store the distance of a node to $x$ and this isn't limited to just $x$'s subtree. Doing a max query on all the non blocked intervals will then find the maximum distance to all reachable nodes.
 » 6 months ago, # |   +23 Was the TL and ML for problem F a little tight in this contest? I see a lot of submissions here which have taken > 3 seconds.I have roughly the same solution as the editorial, except that my graph is built with edges denoting >= relationships (instead of > relationships), then I find the SCCs of the graph, and the remainder of the construction is roughly the same. Or is there something else extremely slow about my code? I could get it to pass very narrowly with pragmas though.
•  » » 6 months ago, # ^ |   0 Maybe to solve the memmory problem,you should use tree chain dissection.
•  » » 6 months ago, # ^ |   0 But the time complexity is O(log^2n) However
•  » » 6 months ago, # ^ |   +16 I ran into a similar problem. I tried implementing the editorial's idea and got TLE (later cloned the contest and checked that it passed in 4788ms), then changed how i did toposort and barely got AC.What seems to have happened is that they only had 1 AC solution that passed in 2s (1793ms in my testing) and used the standard "make the TL 2x the model solution", but the way they get the nodes to draw the edges is particularly smart, so it's very easy to make something inneficient compared to it and end up with double or triple the constant factor.By the way I did some testing with your code, it passed in 5038ms and 567200KB. Changing the bound for g from MXN * MXK * 3 to MXN * MXK * 2+20 makes it pass the memory limit (482900KB) and changing its type from vector to basic_string also makes it easily pass TL (2761ms).
•  » » » 6 months ago, # ^ |   0 Thanks a lot for looking into this! I had no idea that there was such a substantial improvement possible with basic_string instead of vectors, thanks for pointing that out too!
 » 6 months ago, # |   -10 E is a great problem, thank you for such a masterpiece!
 » 6 months ago, # |   -9 https://mirror.codeforces.com/contest/1904/submission/236574245why my solution give wrong answer for B
 » 6 months ago, # |   -8 236621743 can someone please give me any idea to improve this code as iam getting time limit exceeded for test3 of B.
 » 6 months ago, # |   -8 orz
 » 6 months ago, # |   -8 Can someone help me understand the solution for D.Why does there always exist a valid sequence of operations if we can satisfy the conditions for each element independently
 » 6 months ago, # |   0 How to solve problem E if the queries given online?
•  » » 6 months ago, # ^ |   0 The solution described in "Editorial 2" is online.
 » 6 months ago, # |   0 Nice Solutions.
 » 6 months ago, # |   0 Can someone help me in C? The first test gives me MLE and WA but in my computer gives me a correct answer 236711122
•  » » 6 months ago, # ^ |   0 Maybe you can try resubmit.I tested your solution and it is working fine (there is a bug in your solution though)
 » 6 months ago, # | ← Rev. 4 →   0 In Problem F, can anyone explain how they are achieving this exactly: "Given a path and a node, add a directed edge from the node to every node in that path"? I can't understand how they can add edges to (or from) all the nodes in the path, won't that take linear time? Also, in this sentence "we can repeatedly add an edge from that node to the largest node we can" what does "largest" node mean?
•  » » 6 months ago, # ^ |   +3 Imagine creating a binary lifting on the tree. You have $bin[i][0] = par[i]$, $bin[i][1] = par[par[i]]$, etc. Here, $bin[i][0]$ is an auxiliary node that has edges to $i$ and $par[i]$. $bin[i][1]$ is an auxiliary node that has edges to $bin[i][0]$ and $bin[par[i]][0]$. Note that this is equivalent to $bin[i][1]$ having edges to $i$, $par[i]$, and $par[par[i]]$. Similar to how you always jump up the largest power of 2 that fits when you perform binary lifting, you will always add an edge to the auxiliary node with the largest power of 2 that fits. This will always require at most $log N$ edge additions.
 » 6 months ago, # |   +9 There is also a $O(nlogn)$ online sol for E (although with high constant).Take the euler tour of the tree (the version where you insert again every time you go to a new node, exactly like this image taken from https://cp-algorithms.com/graph/lca.html ): $\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Vertices:} & 1 & 2 & 5 & 2 & 6 & 2 & 1 & 3 & 1 & 4 & 7 & 4 & 1 \\ \hline \text{Heights:} & 1 & 2 & 3 & 2 & 3 & 2 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\ \hline \end{array}$Lemma: the length of the diameter of a tree is $\max(height[a] - 2\cdot height[b] + height[c])$ for $a \leq b \leq c$, being $height[i]$ the height of the $i-th$ node in the euler tour. In that case, if $v[i]$ is the $i-th$ node in the euler tour, the endpoints of the diameter will be $v[a]$ and $v[c]$ and their lca will be $v[b]$. Proof is an exercise to the reader ;)Using that lemma, we can ban segments like the solution 1 and if $x$ is the source node of our query, the answer will be $\max(height[a] - 2\cdot height[b] + height[c])$ for $a \leq b \leq c = x$ or for $x = a \leq b \leq c$, which can be done with a segtree. You just need to remember to rollback your updates after every query. Code: https://mirror.codeforces.com/contest/1904/submission/236721097
 » 6 months ago, # |   0 Hi can someone help me in figuring out why my two pointer approach for problem C is failing?
•  » » 6 months ago, # ^ |   0 Ive sorted the array and finding the sum which is closest to the ith element and then min of all their difference is the answer.. can anyone pointout the issue in my logic?
•  » » » 6 months ago, # ^ |   0 1 2 2 1000 499 You can try this case. SpoilerThe correct answer is 2.The first operation is to get 501 from 1000 - 499. The second operation is to get 2 from 501 - 499.
•  » » » » 6 months ago, # ^ |   0 Thanks!! i missed this case
 » 6 months ago, # |   0 In problem C should I pick different (i,j) each time?
•  » » 6 months ago, # ^ |   0 No there is no any condition on taking different (i,j) each time.
 » 6 months ago, # |   0 Or can someone share their two pointer approach for problem c?
•  » » 6 months ago, # ^ |   0 Your two pointer approach is mostly correct except two bugs.Check out 236828774 for references.
 » 6 months ago, # |   0 Direction of the edges in the explanation for the solution for F are backwards
 » 6 months ago, # |   0 can someone please explain what does |a| notation mean in problem C? is it the length of array?if so, why sorting array in this problem doesn't violate the condition of must pick some (i,j) such that 1≤i
•  » » 6 months ago, # ^ |   0 You are correct. |a| means the length of the array a.Essentially, in each operation, you can pick two different elements (can be equal) from the array and compute the absolute differences and put the result back to the array.So the order of the elements in the array does not matter and you are free to reorder the array (including sorting it).
•  » » » 6 months ago, # ^ |   0 got it, thank you very much for clarification!
 » 6 months ago, # |   0 Can anyone explain me how edges are created in "problem F" in simple way and why are they created in that way(thought process)?
 » 6 months ago, # |   0 why do we need to find smallest ai satisfying ai≥v and greatest ai satisfying ai≤v in C why can't we go over all combinations of dif[i]-a[j] (where dif is the difference array of a of length n-1)failed submission : https://mirror.codeforces.com/contest/1904/submission/236901057
 » 6 months ago, # |   0 Hi thanks for this contest and I hope this is not necro-posting but for $B$, don't you think it is enough to check if $p_i \geq a_{i+1}$ and then set the answer of $i$ equal to the answer of ${i + 1}$? I have an implementation which you can check out 237039030.
 » 6 months ago, # | ← Rev. 2 →   0 My submission to problem F. Getting a TLE, unable to figure out why. Its similar to others', like MridulAhi (link). Can someone help?
 » 6 months ago, # |   0 good D2 and E
 » 6 months ago, # |   0 Could someone help to find what's wrong with my code https://mirror.codeforces.com/contest/1904/submission/237279390?
 » 6 months ago, # |   0 Can someone tell me why did we multiply 4001 in this solution https://mirror.codeforces.com/contest/1904/submission/236534459
•  » » 6 months ago, # ^ |   0 It's not "multiply $4001$". As the official solution we need set>. But in fact we can use set, because every point with small $x, y$ can be "hashed" by $1000x + y$. Why it is true? Ok, let $(1000x + y)$ = $(1000z + t)$. Then $(y - t) = 0 \bmod 1000$. But if $y, t \leq 100$, then $y = t$ and so $x = z$. So in fact we just need to use $(x, y) <-> (k * x + y)$ for a big $k$.
 » 6 months ago, # | ← Rev. 2 →   0 why does this solution gives TLE on problem C 237622851
 » 6 months ago, # | ← Rev. 3 →   0 Can someone tell , in problem 3 why this code is not passing the test case 35 of test case 2 . https://mirror.codeforces.com/contest/1904/submission/237695706
•  » » 6 months ago, # ^ | ← Rev. 2 →   +5 I think it is because your num might not be initialized for some test cases and it is reading the old value from the last test case.Removing it will now TLE on test 4: 237886642This is probably because you need to sort and erase elements from vector for each iteration of b[]Slightly change your code without changing your algorithm can get it accepted: 237887308
•  » » » 6 months ago, # ^ |   0 Thanks! a lot porker2008 for solving my query .
 » 6 months ago, # |   0 Problem BCan anybody explain me why is the last sentence of tutorial is correct? If we have a [3, 8, 4, 5], then sorted it gonna be [3, 4, 5, 8] p — prefix sum [3, 7, 12, 20]. Lets calculate answer for i = 2, pi = 7 and largest aj (pi >= aj) is 5 and j = 2. But the correct answer is 3 because we can collect all 3 numbers if started with 4 -> 3, 5, 8
•  » » 6 months ago, # ^ |   0 The tutorial is correct. The answer is not j, but answer to j.If you start with 5, you can collect all other three. So if you start with 4, since prefix sum is 7, and it is greater than 5, you will have the same answer as if you start with 5, which is also three.So it is better to calculate the answer to larger j, then smaller j.
 » 6 months ago, # | ← Rev. 2 →   0 o
 » 5 months ago, # |   0 Please! Could someone explain me why this 240992164 gives a wrong answer
 » 5 months ago, # |   0 Whats' wrong with my solution for D1?https://mirror.codeforces.com/contest/1904/submission/244601635
•  » » 5 months ago, # ^ |   0 Take a look at Ticket 17327 from CF Stress for a counter example.
 » 3 months ago, # |   0 Task E is really cool!Both of the intended solutions are really cute, the continuous interval is also really cute. Thank you for this task!
 » 3 months ago, # |   0 I got stuck on problem C for a while. For case k=2, after sorting A, I looked for closest elements of D[i] = A[i + 1] - A[i] in the array to check for the second minimum absolute difference. Well.. my mistake was choosing D[i] = A[i + 1] - A[i] (same as k=1) in the first place thinking that it helps to minimize, but i and j could actually be any pair. Of course, I didn't realize it and checked the editorial to finally understand my stupidity.
 » 6 weeks ago, # | ← Rev. 2 →   0 For problem C, case when k=1 why are we checking for minimum among a[i]-a[j] and a[i]s. Shouldn't it be the minimum among the former only as that's how the operation was defined?
•  » » 6 weeks ago, # ^ |   0 consider the case: 2 5 10 here according to you the answer will be 3 but the min of the whole array will be 2 therefore we need min(a[i], a[i]-a[j]).
 » 5 weeks ago, # |   0 Can someone explain the soln to B? I didn't understand the tutorial's soln.