awoo's blog

Educational Codeforces Round 141 Editorial
By awoo, history, 23 months ago, translation, In English

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)

1783G - Weighed Tree Radius

Idea: BledDest

Tutorial
Solution 1 (adedalic)
Solution 2 (adedalic)
  • Vote: I like it
  • +82
  • Vote: I do not like it

Comments Comments (49)
| Write comment?
»
23 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Thanks for the lightning fast editorial ✪ω✪ When will systesting start?

→ Reply
»
23 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Is it possible to use "centroid decomposition tree" to solve problem G?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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)$$$).

    → Reply
»
23 months ago, # |
  Vote: I like it +19 Vote: I do not like it

G can be solved using Shame Cube Algorithm

G
G but with simplified problem statement
G but with simplified solution

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

n^1.5 solution also works for E, https://codeforces.net/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)

→ Reply
»
22 months ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      Segment tree can also solve E. Although it's more complicated but time complexity is same O(n*log(n))

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I used segment tree too, but I failed. Can you help me reviewing?my submission...

        → Reply
        • »
          »
          »
          »
          »
          22 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks! I have found my mistake through your inspiration.

            → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oops my bad, I wrongly calculated sieve's complexity, when only primes factors are traversed then it is nloglogn. Thanks for pointing it out

      → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +18 Vote: I do not like it

A-F video editorial for Chinese:

BiliBili

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest but I only solved A :V

→ Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

E can be solved without using any brain with static range max :) 188486103

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did roughly the same thing, except I didn't know how to implement sparse table so I just used segment tree :)

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain further?

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is problem A still solvable if a[i] can be negative?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Video Solution for Problem C and Problem D.

→ Reply
»
22 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I used unordered_map in D during contest and I feel so lucky to Accepted with 1996ms time. 188483495

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Neon Thanks for solution to problem B, Very nice implementation, Learnt a lot.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the solution of the problem F? I don't understand the editorial

→ Reply
»
22 months ago, # |
← Rev. 9   Vote: I like it 0 Vote: I do not like it

why does my page shows that i am unrated for this round??????????????

→ Reply
»
22 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Is this contest is unrated? Because contest is showing unrated now.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this contest unrated now? If so, why does this happen?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Rating changes are rolled back temporarily sometimes, but they always come back after being updated.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why is rating still not updated. In morning it showed rating but after few hours it is again removed

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C If i use this test case,the ans should be 1?

test case

Win 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

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    last index will have 4 wins here as (number of i<j=4)

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Why 4 not 3?

      Last index(index 4) win only against index 0,1,2

      We beat index 0,3,4 so last index lose against us

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ahh i see i misunderstood the condition i thought win condition is ai<aj not i<j. Thx bro

          → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

problem c

this 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 ??

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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 + 1

    No, player has score strictly greater than you.

    Hence, rank = 0+1 = 1

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes I mis read the statement I thought player can win over another if his points are higher, but thanks any way

      → Reply