### awoo's blog

By awoo, history, 15 months 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
• +82

| Write comment?
 » 15 months ago, # |   +37 Thanks for the lightning fast editorial ✪ω✪ When will systesting start?
•  » » 15 months ago, # ^ |   +11 There's some bug of hacking system. Waiting for admins to fix it.
•  » » » 15 months ago, # ^ |   0 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!!
 » 15 months ago, # |   +9 Is it possible to use "centroid decomposition tree" to solve problem G?
•  » » 15 months ago, # ^ |   +9 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.
•  » » 15 months ago, # ^ |   +26 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)$).
 » 15 months ago, # |   +19
 » 15 months ago, # |   0 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)
 » 15 months ago, # | ← Rev. 4 →   +3 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
•  » » 15 months ago, # ^ |   +12 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.
•  » » » 15 months ago, # ^ | ← Rev. 3 →   +5 Segment tree can also solve E. Although it's more complicated but time complexity is same O(n*log(n))
•  » » » » 15 months ago, # ^ |   0 I used segment tree too, but I failed. Can you help me reviewing?my submission...
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 15 months ago, # ^ |   0 Thanks! I have found my mistake through your inspiration.
•  » » » 15 months ago, # ^ |   0 Oops my bad, I wrongly calculated sieve's complexity, when only primes factors are traversed then it is nloglogn. Thanks for pointing it out
 » 15 months ago, # | ← Rev. 2 →   0 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
 » 15 months ago, # | ← Rev. 3 →   0 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
 » 15 months ago, # |   +18 A-F video editorial for Chinese:BiliBili
 » 15 months ago, # |   0 Nice contest but I only solved A :V
 » 15 months ago, # | ← Rev. 3 →   0 E can be solved without using any brain with static range max :) 188486103
•  » » 15 months ago, # ^ |   0 Did roughly the same thing, except I didn't know how to implement sparse table so I just used segment tree :)
•  » » 15 months ago, # ^ |   0 Can you explain further?
 » 15 months ago, # |   0 Is problem A still solvable if a[i] can be negative?
•  » » 15 months ago, # ^ |   0 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.
 » 15 months ago, # |   +3 Video Solution for Problem C and Problem D.
 » 15 months ago, # |   +11 I used unordered_map in D during contest and I feel so lucky to Accepted with 1996ms time. 188483495
 » 15 months ago, # |   +1 Neon Thanks for solution to problem B, Very nice implementation, Learnt a lot.
 » 15 months ago, # |   0 Can anyone explain the solution of the problem F? I don't understand the editorial
 » 15 months ago, # | ← Rev. 9 →   0 why does my page shows that i am unrated for this round??????????????
 » 15 months ago, # |   +11 Is this contest is unrated? Because contest is showing unrated now.
 » 15 months ago, # |   0 Is this contest unrated now? If so, why does this happen?
•  » » 15 months ago, # ^ |   0 Rating changes are rolled back temporarily sometimes, but they always come back after being updated.
 » 15 months ago, # |   0 why is rating still not updated. In morning it showed rating but after few hours it is again removed
 » 15 months ago, # | ← Rev. 2 →   0 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
•  » » 15 months ago, # ^ |   0 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
 » 15 months ago, # |   0 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
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 last index will have 4 wins here as (number of i
•  » » » 15 months ago, # ^ | ← Rev. 4 →   0 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
•  » » » » 15 months ago, # ^ |   0 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.
•  » » » » » 15 months ago, # ^ |   0 Ahh i see i misunderstood the condition i thought win condition is ai
 » 15 months ago, # |   0 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?
 » 12 months ago, # | ← Rev. 2 →   0 1 3 0 1 1 0 If this is the test case for problem C what will be the answer? The editorial answer output is 3, but isn't it should be 2? BledDest
•  » » 12 months ago, # ^ |   0 We can only win against the opponent $3$. So, we have $1$ win, but both the opponent $3$ and the opponent $2$ have $2$ wins each ($3$ wins against $2$ and $1$, $2$ wins against $1$ and us). So, two players are above us, and our place is the $3$-rd.
 » 11 months ago, # |   0 In tutorial for G, at the first bullet point, please change the wording to There is a vertex v on diameter path (x,y)...Thank you.
 » 7 weeks ago, # | ← Rev. 2 →   0 problem cthis test case is saying that it should be 1 can someone tell me how 2 0 1 0 if I win against the 0 then the 1 will win on me and will win on the zero so he is 2 and i'm one so he is the first place and i'm the second so what is going on here ??
•  » » 6 weeks ago, # ^ | ← Rev. 4 →   0 Note — I am assuming 1 indexing. Player 1 is at index 1 and player 2 is at index 2.Since, you have 0 energy, you can only win against player 2. So, player 1 will beat you. Since player 2 is at higher index (index 2) than player 1 (index 1), he will beat player 1.Thus total wins of each player are — You — 1 (You beat player 2) Player1 — 1 (He beats you) Player2 — 1 (He beats player 1) Now, rank = No of players whose score is strictly greater than your score + 1No, player has score strictly greater than you.Hence, rank = 0+1 = 1
•  » » » 6 weeks ago, # ^ |   0 yes I mis read the statement I thought player can win over another if his points are higher, but thanks any way