### awoo's blog

By awoo, history, 4 weeks ago, translation, 1783A - Make it Beautiful

Idea: BledDest

Tutorial
Solution (BledDest)

1783B - Matrix of Differences

Idea: BledDest

Tutorial
Solution (Neon)

1783C - Yet Another Tournament

Idea: BledDest

Tutorial
Solution (Neon)

1783D - Different Arrays

Idea: BledDest

Tutorial
Solution (BledDest)

1783E - Game of the Year

Idea: BledDest

Tutorial
Solution (BledDest)

1783F - Double Sort II

Idea: BledDest

Tutorial
Solution (BledDest)

Idea: BledDest

Tutorial  Comments (48)
 » Thanks for the lightning fast editorial ✪ω✪ When will systesting start?
•  » » There's some bug of hacking system. Waiting for admins to fix it.
•  » » » I really enjoyed this Educational Codeforces Round 141 (Rated for Div. 2) and its quite fun giving this contest. I am anxiously waiting for next Educational round.So please make it quick.Thankyou!!
 » Is it possible to use "centroid decomposition tree" to solve problem G?
•  » » You can use it, but it's a bit difficult and annoying to implement. The main idea of solution is similar to the one described in the official editorial.Basically, you need to be able to process the following query: for a vertex $v$, find a vertex $u$ such that $a_u + d_v(u)$ is the maximum possible. You can iterate on their common centroid $c$, and, for that centroid, query the vertex with maximum possible value of $a_u + d_c(u)$ in the subtree of that centroid. The difficult thing is that our query should exclude the vertices which have some deeper common centroid with $v$ than $c$, because for those vertices, $c$ may not be on the path from $u$ to $v$, and $d_v(u) \ne d_c(v) + d_c(u)$. To handle that, in each centroid, let's sort the vertices according to the first vertex on the path from the centroid to them; when we query the centroid $c$ from vertex $v$, we exclude the segment containing "bad" vertices from our query, so it is a combination of prefix maximum query + suffix maximum query. So, a maximum segment tree in each centroid does the trick.
•  » » I managed to write a centroid decomposition solution after the contest which I think is different to BledDest's solution. It uses the diameter idea from the editorial, but not the offline DCP trick. My implementation is offline but it could easily be converted to an online algorithm at the expense of some memory.For each centroid tree, and for each subtree of the root of that centroid tree, keep a multiset of $a_u + d_v(u)$ (where $v$ is the centroid). For each the centroid tree, keep a multiset of the maximums of the per-subtree multisets. That lets you find a potential diameter (but only considering the paths that pass through the centroid), by taking the two largest elements from that multiset. Each update requires $O(\log^2 n)$ time (each vertex belongs to $O(\log n)$ trees in the decomposition, and updating multisets requires an extra factor of $O(\log n)$).
 »
 » n^1.5 solution also works for E, https://codeforces.com/contest/1783/submission/188632405 Here is my solution, it is similar to the solution mentioned in the tutorial. (PS systesting hasn't started so not sure if n root(n) solution will work for system test case but it should theoretically)
 » 4 weeks ago, # | ← Rev. 4 →   So to solve E, first we come to the conclusion just like mentioned in the editorial that if k is a valid solution then $\forall \ i$, such that $a_i>b_i$ and there shouldn't exist any multiple of k in the range $[b_i,a_i)$ (or $[b_i,a_i-1]$ ), more formally $\forall \ x,\ b_i\leq x < a_i$ , $x\ \% \ k\ !=0$.Note that for i's such that $a_i\leq b_i$ any $k$ could be valid number to kill the i'th boss, so they are not our point of interests.Thus the question is now simplified to the following problem, we are given certain forbidden ranges, where k's any multiple if lies, then it can't be the valid solution. And to track these ranges we use range updates using difference array concept. We can build an array (suppose called pre) initialised with 0, and do $pre[b_i]$+=1 and $pre[(a_i-1)+1]$+=-1 and then do the prefix sum on this array. After this $pre[i]$ would store the count of forbidden ranges in which i lies. Thus now we can check $\forall \ k$, $1 \leq k \leq n$ , whether k is a valid solution or not in a sieve manner. Time complexity : $O(n\log{}n)$ Implementation
•  » » Your solution sounds exactly the same as the editorial. I don't see where you get $O(n\log \log n)$ from; it look like $O(n\log n)$ to me.
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   Segment tree can also solve E. Although it's more complicated but time complexity is same O(n*log(n))
•  » » » » I used segment tree too, but I failed. Can you help me reviewing?my submission...
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   The code need to be rewritten. I even cannot understand how it passed first 10 tests.In fact, you just need to update range [b[i], a[i]-1] where a[i]>b[i]. And for each k, if any multiple of k is in any such range, k is bad.
•  » » » » » » Thanks! I have found my mistake through your inspiration.
•  » » » Oops my bad, I wrongly calculated sieve's complexity, when only primes factors are traversed then it is nloglogn. Thanks for pointing it out
 » 4 weeks ago, # | ← Rev. 2 →   Can someone help me figure out why this submission for problem E TLE's? I'm pretty sure that the time complexity is O(nlogn)188635530
 » 4 weeks ago, # | ← Rev. 3 →   There is another sol for E. At first delete all pairs, where ai <= bi(now we need check is it true that ai / k == bi / k for all k). After that we will iterate over all k and for ki iterate over all x, that n / ki <= x. And count the number of pairs, that ai / ki = x and bi / ki = x(its not hard to calculate with scanline and fenwik). Its easy to see, that ki can be answer if and only if the sum of all x will be cnt of pairs. Now we check this parameter and calculate answer Time complexity will be O(nlog(2)nlog(f)n) Submission
 » A-F video editorial for Chinese:BiliBili
 » Nice contest but I only solved A :V
 » 4 weeks ago, # | ← Rev. 3 →   E can be solved without using any brain with static range max :) 188486103
•  » » Did roughly the same thing, except I didn't know how to implement sparse table so I just used segment tree :)
•  » » Can you explain further?
 » Thanks [user:Bledest]for the editorial. Nice Explanation for problem D.
 » Is problem A still solvable if a[i] can be negative?
•  » » I think it is, but we need lots of disscusion after sorting.Or random_shuffle can be a way, it's impossible to hack random_shuffle solutions I think, but pay attention to 0.
 » Video Solution for Problem C and Problem D.
 » I used unordered_map in D during contest and I feel so lucky to Accepted with 1996ms time. 188483495
 » Neon Thanks for solution to problem B, Very nice implementation, Learnt a lot.
 » Can anyone explain the solution of the problem F? I don't understand the editorial
 » Why does this contest has too less submissions
 » 4 weeks ago, # | ← Rev. 9 →   why does my page shows that i am unrated for this round??????????????
 » Is this contest is unrated? Because contest is showing unrated now.
 » Is this contest unrated now? If so, why does this happen?
•  » » Rating changes are rolled back temporarily sometimes, but they always come back after being updated.
 » why is rating still not updated. In morning it showed rating but after few hours it is again removed
 » 4 weeks ago, # | ← Rev. 2 →   Can we solve E by delete potential answer?Like, for every a[i] > b[i], delete all k that a[i] <= k < b[i], count how many element had been deleted, and printf all those remains?Still , I can't figure out what's wrong with my idea or my code , can anybody help me? 188823323
•  » » Not sure what's the mistake here, this solution should give the correct answer.However, it will most likely TLE as it's $O(n^2)$ complexity
 » In F:My code got the wrong answer at test point 10, but I checked it many times and still didn't find anything wrong. Can any kind person point out the mistake? Thank you. My submission
•  » » OK. Maybe I know where my mistake is. Now I needn't help.
 » For problem C If i use this test case,the ans should be 1? test case15 102 2 3 4 4Win against 2 4 4 = 3 win 2 have 0 win 2 have 1 win 3 have 3 win 4 have 3 win 4 have 3 win Editorial code output is 2
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   last index will have 4 wins here as (number of i
•  » » » 4 weeks ago, # ^ | ← Rev. 4 →   Why 4 not 3? Last index(index 4) win only against index 0,1,2We beat index 0,3,4 so last index lose against us
•  » » » » As in your case we won against indexes {0,3,4} so will have 3 wins. 1. index 0 = (indexes<0) + 0(lost against us) = 0 wins. 2. index 1 = (indexes<1) + 1(win against us) = 2 wins. 3. index 2 = (indexes<2) + 1(win against us) = 3 wins. 4. index 3 = (indexes<3) + 0(lost against us) = 3 wins. 5. index 4 = (indexes<4) + 0(lost against us) = 4 wins. index 4 will have 4 wins but we only have 3 wins so ans is 2.
•  » » » » » Ahh i see i misunderstood the condition i thought win condition is ai
•  » » » » » » okay
 » I really like to know how to solve problems like G in contests. I spent almost half an hour trying to grasp the concept of "wp(x,y)" and doing all the provement myself and yet still unable to understand why to construct such variate at the first place. In my opinion, there can be many different variates to construct and each with so many properties that might contribute to solving the problem. For me, even if I managed to construct this "wp(x,y)", I can't bring myself to actually exam all its features and not to mention figuring out which one among them is the cruial one. So anyone who solved this problem by themselves willing to share some insights?
 » I feel it is very difficult to deal with problem B. Is there any good practice method?
 » Problem E was a very nice problem.