awoo's blog

By awoo, history, 4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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)$$$).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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))

      • »
        »
        »
        »
        4 weeks 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...

        • »
          »
          »
          »
          »
          4 weeks 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.

    • »
      »
      »
      4 weeks 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

»
4 weeks 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

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

A-F video editorial for Chinese:

BiliBili

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest but I only solved A :V

»
4 weeks 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

  • »
    »
    4 weeks 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 :)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain further?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks [user:Bledest]for the editorial. Nice Explanation for problem D.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Video Solution for Problem C and Problem D.

»
4 weeks 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

»
4 weeks 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.

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this contest has too less submissions

»
4 weeks 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??????????????

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks 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.

»
4 weeks 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

»
4 weeks 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

  • »
    »
    3 weeks 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

»
4 weeks 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

»
4 weeks 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

  • »
    »
    4 weeks 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)

    • »
      »
      »
      4 weeks 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

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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

»
4 weeks 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?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I feel it is very difficult to deal with problem B. Is there any good practice method?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E was a very nice problem.