Alexdat2000's blog

By Alexdat2000, 19 months ago, translation, In English

Thank you for participating! We hope you enjoyed the problems!

1805A - We Need the Zero
Idea and preparation: Alexdat2000

Hint 1
Hint 2
Editorial
Solution
Rate the problem

1805B - The String Has a Target
Idea and preparation: Alexdat2000

Hint 1
Hint 2
Editorial
Solution
Rate the problem

1805C - Place for a Selfie
Idea and preparation: Alexdat2000

Hint 1
Hint 2
Hint 3
Editorial
Solution
Rate the problem

1805D - A Wide, Wide Graph
Idea: FairyWinx, preparation: Alexdat2000

Hint 1
Hint 2
Editorial
Solution
Rate the problem

1805E - There Should Be a Lot of Maximums
Idea and preparation: Alexdat2000

Hint 1
Hint 2
Hint 3
Editorial
Solution
Rate the problem

1805F2 - Survival of the Weakest (hard version)
Idea and preparation: sevlll777

Hints for the simple version:

Hint 1
Hint 1.1
Hint 2
Hint 2.2

Hints for the hard version:

Hint 3
Hint 4
Hint 5
Editorial
Solution
Rate the problem
  • Vote: I like it
  • +186
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The title says "Разбор" which is not translated ig

»
19 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Where can I read more about the XOR property mentioned in problem A?

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

    The property is simply that XOR of two same numbers is zero and XOR of a number with zero is the number itself.

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Yes, but I was asking about the property in the editorial sections, where it says about the case when n is even and when n is odd. Where can I read about that?

      • »
        »
        »
        »
        19 months ago, # ^ |
        Rev. 2   Vote: I like it -21 Vote: I do not like it

        its literally the same thing...

        $$$A ⊕ A = 0$$$, so if there is even number of $$$A$$$'s then the result is zero

        otherwise, its $$$A$$$.

        stupid

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
»
19 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Alternative solution for D: we can compute maximum distance of some node for each node in a tree, now if k>maximum distance between any two nodes , number of connected components is n. let number of nodes with maximum distance be x. then for k=x, answer is n-x+1. Now iterate from x to 1 , answer for k=y is n-(freq[y]+freq[y+1]+freq[y+2]......+freq[x])+1,where freq[x] denotes number of nodes with maximum distance equal to x. link to submission

  • »
    »
    19 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Clean ac submission with this idea : https://codeforces.me/contest/1805/submission/200446467

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

    Do we need to do rerooting for finding the maximum distance for each node ?

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

      not really, I managed to do it in two dfs calls, you can see it in this submission, for example

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

      No. General idea is for any node in a tree the farthest node from it will be an endpoint of the diameter of that tree. We can use this idea to get max distance from every node to every other node in 2 dfs / bfs calls.

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

        oh wow, I overcomplicated my stuff so much then

        my idea was that there can be two options of the longest path from a vertex: 1. it is one of its children (if we root the tree arbitrarily, say in 1). so, it's the depth of the tree from this vertex 2. it's to a child of one of its parents. to calculate this one, the a dfs call also saves the largest value of (depth of tree of a node — its depth from root), and this value is passed on as max(this value in current iteration, what was passed on already), but the value of in this iteration is the maximum depth of any tree of a son of this vertex, except the one we are going into

        so, the path can be calculated for each of the vertices in a dfs call, where we pass on the value from (2), and the parent of the vertex

        the 2 max depths of a tree of a son of each vertex and the depth of each vertex from root can be calculated in the first dfs call

        weird stuff, really. idk how I came up with that instead of the diameter idea

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

    Absolutely, I had also applied the same concept, finding the farthest distance for each node, and took their frequency, and solved using same concept,

    Submission Link . All can view my alternative implementation for Problem D, if you want.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yep, this is a well known problem that can be found in CSES

»
19 months ago, # |
  Vote: I like it +12 Vote: I do not like it

keep them parabolas to yourself

»
19 months ago, # |
Rev. 3   Vote: I like it +24 Vote: I do not like it

There is an easier and more beautiful (imo) observation in C:

When we know that we need to find such a $$$k$$$ that $$$(b-k)^2<4ac$$$, we could rewrite this inequality as $$$k^2-2kb<4ac-b^2$$$. $$$4ac-b^2$$$ is fixed for one parabola, so for each parabola we need to minimize $$$k^2-2kb$$$. But this is also a parabola (but there is $$$k$$$ instead of $$$x$$$), so its minimum is in $$$k = \frac{2b}{2} = b$$$. Now we can just binary search for $$$b$$$ in the sorted array of $$$k$$$ and check the closest values to $$$b$$$ to the left and to the right of found value in the $$$k$$$ array to satisfy the $$$(b-k)^2<4ac$$$.

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

    Couldn't implement it so I looked at your code, could you explain why you used two additional conditions(ind<=n and ind>1) after BS? Thanks.

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

      Because sometimes we don't have the closest element to $$$b$$$ to the left (when $$$ind = 1$$$) or to the right (when $$$ind > n$$$)

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

    How can the minimum be $$$k = \frac{2b}{2} = b$$$? What approach did you use? Did you differentiate? How can the equation($$$k^2-2kb$$$) be a form of the equation of a parabola? Can you please explain it?

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

      Math equation for the parabola is $$$y(x) = ax^2+bx+c$$$. It's also a known fact that vertex of the parabola $$$(x_0, y_0)$$$ has $$$x_0 = -\frac{b}{2a}$$$. If parabola has $$$a>0$$$ then $$$(x_0, y_0)$$$ is also a minimum of the parabola.

      In our case we have $$$y(k)=k^2-2kb$$$. So x-coordinate of the minimum point is just $$$x_0=-\frac{b}{2a}=-\frac{-2b}{2}=b$$$. (Note that there are different $$$b$$$ variables in this equations — from $$$y(x)$$$ and $$$y(k)$$$)

»
19 months ago, # |
  Vote: I like it +4 Vote: I do not like it

no need to think, a brute-force solution works for problem 1805A - We Need the Zero

My solution link: 200395467

My solution
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain Hint 2.2 of problem F1?

  • »
    »
    19 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If you subtract same integer from all numbers in array, they sorted order will not change, and same with sorted order of all pairs of elements. Basically it means that arrays $$$F([a_1, a_2, \ldots, a_n])$$$ and $$$F([a_1 - x, a_2 - x, \ldots, a_n - x])$$$ are formed by the same pairs of indexes.

    I.e: $$$F([a_1, a_2, \ldots, a_n])_i - 2x = F([a_1 - x, a_2 - x, \ldots, a_n - x])_i$$$ for all $$$i$$$.

    So we can prove Hint 2.2 by simple induction on $$$n$$$. Base case $$$n = 1$$$ is obvious. What I wrote above is basically a transition from $$$n$$$ to $$$n - 1$$$ case

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In hint3 of solution of F:

How to solve the problem if ai≤1?≤2?

There's an extra '?' character

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    That's not an error, that was intended to be 2 questions

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A, hint 1: $$$A \oplus 0 = 0$$$ should be $$$A \oplus 0 = A$$$

»
19 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Problems were nice. And to make this comment less nonsence

In D every vertex that was chosen on i-th step has at most 1 neighbour which wasn't chosen yet and it will be chosen on (i-1)-th step (also it can't be leaf). So you can search only for leaves with distance i from diameter ends, and with those neighbours they will be all i-th chosen vertexes

Actually, it's big overthinking, but anyway

»
19 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem C is a good example for ternary search. Solution.

»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Great contest! if you people feel stuck on Problem A, Problem B, Problem C, Problem D then you can refer to my video editorial here-video editorial

»
19 months ago, # |
  Vote: I like it +37 Vote: I do not like it

There is a simple solution to problem E, which works even if MAD operation is defined as max value appearing at least k times.

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

    Can you please expand the approach a bit. When the tree is collapsed to seg tree by Euler tour. How is finding $$$k^{th}$$$ number of the same value equivalent to our query. I get that somehow you will maintain for each query the valid answers, can you please just let me know how exactly that gets maintained with updates.

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Go from left to right in the array formed after Euler tour, if you are at index $$$i$$$ then find $$$k$$$$$$th$$$ number to the left of same value as $$$a$$$$$$i$$$. Now any active range whose left boundary is or before that $$$k$$$$$$th$$$ number's index then that particular number will contribute to the answer for that range. After updating, query for maximum element in the range.

      Note : We have sorted the queries on the basis of right boundary, hence we are going from left to right. Iterate and add numbers till your i is less than current right index of the query.
      You can check my submission and ask whatever part is unclear in it.

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

        And what about the prefix and suffix?

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

          copy the sequence and append to itself, then the prefix and suffix can turn into a subsegment, too.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I overcomplicated my approach to C https://codeforces.me/contest/1805/submission/200453634 it gives Wa test 5 could anyone help?

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Dont use decimal calculations here, it has precision error. A simple approach is to find the largest k smaller than b and smallest k larger than b and check for the condition (b-k)^2 <4ac.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is Task C somehow related to task A of the first day of the regional stage of the VSOSH 2023?)

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

    Я придумал свою задачу где-то год назад так что вряд ли есть связь

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, at last we need to find a k which satisfies the equation $$$b - \sqrt{4ac} < k < b + \sqrt{4ac}$$$.

But how do we find any such k if $$$4ac < 0$$$? i.e. how do we find a real number between two imaginary numbers?

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved E using (segtree + euler tour + mo algorithm + coordinates compression + frequency array).

Submission: 200485345

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Segtree + Mo's algorithm? Is that $$$O(n \sqrt{n} \log(n))$$$ or I missed something?

    • »
      »
      »
      19 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Yes, I actually used a multiset but got TLE so I moved to a fast segtree implementation which doesn't have all the overhead of the STL containers. At the end the worst case is still $$$O(n\sqrt n \log(n))$$$, but this is the worst case which is unlikely to happen (I think). Because we don't always update the segtree, it is updated when some condition is satisfied.

      To be honest I didn't notice the time limit during the contest and took too long time thinking about the solution till the contest ended. If I had the time and noticed the time limit I wouldn't submit it.

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

        You can use square decomposition to update in $$$O(1)$$$ and find the maximum value in $$$O(\sqrt{n})$$$. Therefore, the complexity is $$$O(n * \sqrt{n})$$$, which is much more comfortable than using Segment Tree, which takes $$$O(\log {n})$$$ for each update.

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

    Where can I learn about techniques like coordinate compression and mos algorithm?

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    check out my similar solution, I didn't have to use a segment tree just like how steveonalex explained. This is a really important trick so if you don't know it, I would recommend that you have a look at it.

»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Has anyone solved E using rerooting technique?

»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone explain Question D in more detail?

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have different solution for problem D. Let's calculate farthest leaf from node i (this can be done by rerooting) and keep this value in fd[i] (short for farthest-distance). Now, for specific k, we check if node fd[i] is greater or equal to k. If this statement is false, then this node is isolated from every other node completely. Otherwise every node which satisfy this statement will be connected into one whole component. Thus we can calculate number of isolated components by prefix sum and add one as a "main" component. Consider fact that you can get answer n + 1 so you have to print min(n, answer).

Here's code for better understanding 200435906

P.S. If you liked this explanation or it helped you solve this problem, please add me as a friend. Reply if you need proof for this type of solution.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, can someone point out my mistake? 200462857

»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Finally became specialist! :)

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E's idea is pretty straight forward yet somehow I failed to notice the simplest implementation...
I noticed that the biggest value appears more than 2 times will be the answer for all edge and all values that appear 2 times will update all the edges that are not on their path, yet to update and maintain maximum value on a tree in O(1) or O(logn) is beyond me(in the worst scenario n/2 updates)(and yes, I thought about HLD which I only know about the general idea).
The lesson here(at least for me) is: practice your tools until you are perfectly familiar with it, so you know exactly what it can do, what can be done with it and what can't.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission 200473816 for F1 has passed but I believe it should fail. I have represented every number in the form a.m + b where m = 1000000007 and b < m. Since the number can reach $$$2^{3000}$$$, it should still be insufficient to store such numbers. Can someone please look into this?

  • »
    »
    19 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I had this same approach when i was trying this problem during the contest. But since the numbers can grow very fast, i eventually discarded it. I think subtracting the smallest $$$a$$$ at every iteration from every term will make much sense similar to editorial, using this approach we can just directly output the remainder stored as $$$b$$$

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

      Yeah. My code should WA for the given constraints, right?

      • »
        »
        »
        »
        19 months ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        Not sure about WA or not, but overflow is definitely possible. So to avoid it, i would be subtracting smallest $$$a$$$ at every iteration to avoid any overflows.

        As in the constraints $$$1 <= array_i <= 10^9$$$, the initial values of quotient $$$a$$$ will be 0, it is likely that pairs of $$$a = 0$$$ or pairs with smaller $$$a$$$ are affecting the result more than any other pair.

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

          It is indeed overflowing like I expected. The value of $$$a$$$ (first element of the array in priority queue) becomes negative after a few iterations. What's blowing my mind is that my code is still giving the correct answer for every large input I generated. The output matches with that of the editorial code. I would really appreciate if someone could take a look and explain why this is happening.

          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            I stress-tested your solution with 4 generators, for $$$~10$$$ minutes for each generator. Countertest was not found. And I don't how can I generate countertest myself.. I believe countertest should exists, but it seems literally impossible to generate it in any way (at least for me)

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

              That is really surprising because if all the array elements are non-zero, it is guaranteed to overflow after less than 100 iterations since $$$2^{100} »» 10^{18+9}$$$. Therefore, every such test case should be vulnerable to failure in theory if $$$n > 100$$$. Correct me if I am wrong. In practical, it is working properly even for very large arrays.

              • »
                »
                »
                »
                »
                »
                »
                »
                19 months ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                Overflow is happening $$$mod 2^{64}$$$, so if two number overflow at the same time they sorted order is the same despite of overflow. So to break it we need to build test where of 2 important numbers at some step one of them overflow, when other not. And if you read F2 tutorial, you know that in fact only 50 smallest numbers of array affect the answer. And also we cant give any array to test overflow, because first 30 runs of your function F will be correct. And after applying F 30 times all arrays are kind specific. This is why its Hard to create a test where overflow actually matters.

»
19 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is that 3 dfs in D a common trick to find all ending nodes of diameter? Can't figure out an efficient way to do so during contest.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

great round

»
19 months ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

For F2 the smallest K that works is 43

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

    Yes, this is correct. Btw, here is an equation to evaluate this number:

»
19 months ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

There is a $$$O(Nlog^2N)$$$ solution for Problem E using Sack on tree..

We can root the tree at any arbitrary node. Now every edge between a parent and child in the tree will break the tree into two components. One of the components is the subtree of the child and the other component is all the other nodes. Now if we had to find the largest value having a frequency greater than x, we can do that normally with sack. However, it won't work for the other component. To solve for the other component we can have an additional data structure. Initially, we will add all the node information to this data structure. Then we can start with our sack on the tree. Whenever we add any node to the data structure for a subtree, we delete it from the additional data structure and vice versa.

Now coming on to the data structure required. We have to support the following actions, increase or decrease the frequency of any value and find the maximum value having the frequency>=2. For performing both of these operations quickly we can use a map and set together. We can update the frequency in the map and then use the set to answer queries about the maximum value. We will have to use a frequency array instead of map for our code to work within the tl.

Implementation

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

    Can you please explain the time complexity a bit more? I understand that the $$$O(N log N)$$$ complexity comes from each node being relocated (merged into a larger vector) up to $$$log N$$$ times. However a relocation operation (your update function) in this case may need a set insertion/deletion, which is another $$$log N$$$ factor. Can you prove that in the worst case the time complexity wouldn't be $$$O(N log^2 N)$$$?

    For example, imagine a tree where every value appears in exactly two nodes. Therefore, the possible frequency of any value is limited to { 0, 1, 2 }. In this case, every relocation seems highly likely to need a set insertion/deletion.

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

      I completely overlooked that part. Really dumb on my part.

      Thanks for pointing out.

»
19 months ago, # |
Rev. 9   Vote: I like it 0 Vote: I do not like it

For D

let $$$min(f(k)+1, n)$$$ equals the solution for k

If we have x nodes that their farthest distance are less than k So, f(k) equals $$$x$$$.

I think this approach would work if this statement is true

let d(x,y) equals the distance between x and y. Then suppose d(a, b) >= k and d(c, d) >= k then one of d(a, c), d(a, d) must be >= k which means if the vertics is not indvidual, then it is connected to all other non-indvidual vertices

which means there is one or zero big connected component and all the other vertices are indviduial. So the answer of k should be the number of indvidual vertices ( + 1 if their number is not (n)).

which equals the first equation $$$min(f(k)+1, n)$$$

this is the approach I used in my solution here but it got WA 4

Could anyone please tell me where I went wrong?

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

excuse me, for question C, if there exits a solution so the max k for this open upwards parabolas is bigger than which has been input and the min k is lower than which has been input, so I tried to check : double nma = b[i] + 2 * sqrt(a[i] * c[i]); double nmi = b[i] — 2 * sqrt(a[i] * c[i]); also there are some special I did checked xd. but wrong answer on test(2,57), is that mean "double" can not fit this solution? Sorry about my poor English. Here is my code, thx if you can drop some advices. https://codeforces.me/contest/1805/submission/200577146

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

    It's a common mistake that multiply two 32bit integer and surprisingly get unexpected answer.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My O(nlog^2(n)) solution to problem E using small to large merging technique. Implementation

»
19 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Why couldn't I passed promblem E with Segtree + Mo's algorithm,or this way is wrong,can somebody help me,thanks so much! 200585844

»
19 months ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

Dumb $$$O(N\sqrt{N}\log{N})$$$ solution using Mo's for problem E which runs very fast: Link

  • »
    »
    19 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    May I ask if there is a tutorial for the fastset in the code?

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

      It's just a template I copied from some grandmaster. If you any doubts about how to use it, you can ask me.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1805C - Place for a Selfie A simple solution for C 200620934

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got TLE on test 5 in problem F1,I think my progress time complexity is O(n^2 logn),can sombody help me. This is my submission,thanks so much! 200650061

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to use dsu on tree in problem E,I think its time complexity is O(nlogn),but I got TLE.can sombody help me. This is my submission,thanks so much! https://codeforces.me/contest/1805/submission/200871054

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question about F2.

Here is one a submission.

I used the same solution as F1, but instead maintained each number and its number of occurrences, in the random case the different numbers are few and far between, the code works fast, but it gets time limit exceeded on test 26.

I would like to know what kind of data can be used to maintain a large number of different numbers during the operation. Can anyone help me?

My English is bad, if there are any grammatical errors, please point them out.

»
19 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

for problem E, my approach is to flatten the tree and apply mergesort tree for queries (similar to number of unique numbers in range but here we need to find maximum value non unique number).

Im getting wrong answer in testcase 18.

my submission: https://codeforces.me/contest/1805/submission/200885370

please anyone say whether my approach was wrong or any mistake in my code. thanks in advance.

»
19 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Alternative Solution to E in $$$O(nlog^2n)$$$:

We can use small to large merging technique. We will maintain $$$3$$$ vectors of sets:

$$$\cdot$$$ $$$Current: $$$ will maintain current $$$MAD$$$ values in subtree $$$\newline$$$ $$$\cdot$$$ $$$Unusable: $$$ will maintain values that are occur less than $$$2$$$ times in the other created tree but occur more than $$$2$$$ times in the total tree $$$\newline$$$ $$$\cdot$$$ $$$Other: $$$ will maintain the largest values that occurs more than $$$2$$$ times in the total tree but less than the values is $$$Unusable$$$ $$$\newline$$$ First one is pretty easy to update, just update it when you currently have less than $$$2$$$ values in the node but will have more than $$$2$$$ when updating it with a subtree.$$$\newline$$$ Second one is updated is a similar way, if you have more than 2 values not occurring but updating it with a subtree results in less than 2 values not occurring add to this set. Also when we add to this set make sure is the value occurs in $$$Other$$$ erase it from there $$$\newline$$$ Third one is a little bit more annoying to update. Find the value right before the current value that occurs at least twice in the tree. Make sure it is not the smallest value in the tree and also that this value does not occur in $$$Unusable$$$. $$$\newline$$$ After doing the merging mentioned right above, we have to do a little casework. $$$\newline$$$ $$$1.$$$ If $$$Current$$$ is empty and number of values occurring at least twice is equal to the amount of numbers in $$$Unusable$$$ the answer is $$$0$$$ $$$\newline$$$ $$$2.$$$ Let $$$max$$$ define the largest number that occurs twice in the tree. If $$$max$$$ is not in $$$Unusable$$$, the answer is $$$max$$$ $$$\newline$$$ $$$3.$$$ Otherwise the answer is equal to the maximum of the largest number that is in $$$Current$$$ and $$$Other$$$ $$$\newline$$$

First log factor comes from the sets, other one comes from small to large merging. Be warned the constant factor is extremely tight and i had to do many things to barely fit into TL so this is not recommended.

Implementation: 201189988

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add the rating of the tasks in the archive:)

»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Actually, for problem $$$E$$$ small to large merging is an overkill.

The first thing to notice, as the editorial states, is that numbers that appear once or thrice can effectively be accounted for quite simply. Thus, we only need to consider numbers that appear twice. From here on out, assume that every number appear twice.

Of all the numbers that appear twice, one of the numbers is going to be the maximum (as in, find the maximum number that appears twice). Say this maximum number is $$$x$$$, and it appears on vertices $$$u$$$ and $$$v$$$. Then, for all edges not on the path from $$$u$$$ to $$$v$$$, the maximum number you can get is going to be $$$x$$$, since $$$u$$$ and $$$v$$$ will be on the same connected component after the split.

Therefore, we only have to deal with vertices on the path from $$$u$$$ to $$$v$$$. To do this, we can root the tree at $$$v$$$ (or I guess, by symmetry, at $$$u$$$) and naively update the connected components.

If done right, the complexity of this approach is $$$O(N)$$$. In my implementation (211295484), the complexity is actually $$$O(N \log N)$$$ because I used maps, but you can do it without maps.