Alexdat2000's blog

By Alexdat2000, 19 months ago, translation, In English

Hello, everyone at Codeforces.com!

In this round, I (Alexdat2000) and two of my friends — FairyWinx and sevlll777 — prepared 6 problems for you (one of which is divided into two subtasks), and you will have 2 hours to solve them. Everyone is welcome to follow the link: Codeforces Round 862 (Div. 2) at Apr/02/2023 17:35 (Moscow time). This round will be rated for all participants with a rating of strictly less than 2100.

And now a few acknowledgements:

Scoring distribution: 500 — 750 — 1250 — 1750 — 2250 — (1750 + 1750).

UPD: Editorial

UPD-2: Congratulations to the winners of the round!

Top 5 official participants:

Place Participant Problems solved =
1 China b6e3 6 6987
2 Taiwan Darren0724 6 6683
3 cpbeginner 6 6520
4 China suckthembi 6 6269
5 GOD_0F_DEATH 6 5915

Top 5 of all participants:

Place Participant Problems solved =
1 China jqdai0815 7 8214
2 China SSerxhs 7 7786
3 China Sugar_fan 7 7750
4 Japan maspy 6 7623
5 Japan noimi 6 7255

Participants who sent the first correct solution to the problems:

Task Participant Penalty
A A_G 0:00
B USA Geothermal 0:02
C USA BucketPotato 0:08
D Hungary peti1234 0:11
E China b6e3 0:11
F1 BeyondHeaven 0:26
F2 China SSerxhs 1:37

  • Vote: I like it
  • +362
  • Vote: I do not like it

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

Very important poll!

1.8 PvP or 1.19 PvP?
»
19 months ago, # |
  Vote: I like it +47 Vote: I do not like it

As a setter, I want to thank 9kin for what you are

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

Testers from every colors

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

pls not maduka again :)

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

As a future participant,I am excited

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

Hope to solve problem C this time.

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

Not a tester but I'm asking you in unmysterious language to give me contribution

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

As a taster, I recommend participants eat a steak before the round

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

As a tester, I very regret my current rating is 2400-3...

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

Contest and Ramadan , it is fantastic :)

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

Question, when a problem has an easy and hard version with scores of (1500 + 2000), does that mean the easy version of the problem is about as hard as a problem worth 1500 points and the hard version is about as hard as a problem worth 3500 points? Or is there no correlation?

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

as a tester, best of luck!!!

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

After Chinese cp round, hope this cf round can comfort me.

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

Hope to be a candidate master

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

As an author, I am not red

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

Good luck?

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

Seems to blue contest for cyans

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

As a tester I can say that I am a tester :-)

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

Good luck!)

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

Wasted so much time on F1, could have easily done D during that time.

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

Fun fact: problem F2 was initially proposed as Div2D 💀

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

E can be easily solved with Mo on subtrees

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

    I tried it with mos but got TLE ? Can you explain why ?

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

      Idk. How did you calculate maximum? If you used smth like set, it might give TL

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

        How do you avoid using set? I tried DSU on tree and got TEL as well.

        edit: I forgot to initialize the size of subtrees :( DSU should work without any optimization.

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

          There is a trick how to calculate maximum of numbers in $$$O(sqrt)$$$ and update numbers in $$$O(1)$$$. Just maintain blocks and number of numbers in each block. For query you need to check $$$O(sqrt)$$$ blocks, and then $$$O(sqrt)$$$ elements of the block

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

        You are right! There was this problem once in a codechef contest : https://www.codechef.com/problems/PASSTHRU and I had used dsu on trees and segment tree during the contest and got TLE. After the contest the editorialist explained that it gets TLE. Looks like I haven't learnt from my mistakes.

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

    I got TLE doing this ;-;.
    I think its because of my map spam :skull:

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

    Can you please explain this?

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

      We will maintain for each subtree all numbers in that subtree in the way that we can calculate maximum very fast. Now, if we delete an edge u->v, the tree decomposes into the subtree of v and all nodes minus the subtree of v. The answer of subtree of v can be calculated with Mo, and answer for all nodes except subtree of v can be calculated the same way. You just need to first include all nodes in the answer, and then exclude the subtree.

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

Had to reread elementary school lesson to solve C lol

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

What is the solution for D?

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

    For every node, calculate maximum distance to any other node.

    For each $$$k$$$, each node with maximum distance to some other node $$$< k$$$ will be in its own component, and all nodes with maximum distance to some other node $$$\ge k$$$ will be in the same component.

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

    For each vertex find the maximum distance from all other nodes. Store these values in an array. Sort this array, then apply binary search for each value of k from 1 to n. The index at which k is supposed to appear is the answer for that k.

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

How to solve c as i got the equation as if (b-k)^2 — 4ac is less than 0 then there is no intersection when k = some value other wise there exist atleast one point where intersection exist. Is this correct approach?

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

    This is the correct approach. You need to come up with a fast way to check for each parabola if there exists some good $$$k$$$.

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

      Yes i check with binary search but still got wrong ans. Can you please check why is it getting WA? link to submission

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

        Um...Your binary search does not work at all. Consider this:

        Input:
        1
        5 1
        2 10 10 10 10
        4 3 1
        
        Correct Output:
        YES
        2
        
        Your Output:
        NO
        

        Can you see why this happens?

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

    Yes it is the correct appraoch. But checking this way will take O(n2) time if you try to brute force the solution. Use binary search for b and it will be solved in O(nlogn).

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

    Binary Search

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

      upperbound to b then while binary search?

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

        lower_bound worked for me. But also make sure to check the neighbouring two numbers as well.

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

        You can show $$$(b-k)^2-4ac<0$$$ implies $$$b-2\sqrt{ac} < k < b+2\sqrt{ac}$$$. From here you can use upper_bound with $$$\lfloor{b-2\sqrt{ac}}\rfloor$$$ ($$$k$$$ is an integer, so this works). Then you need to check if the $$$k$$$ you found satisfies the second condition ($$$k < b+2\sqrt{ac}$$$); you can use $$$\lceil b+2\sqrt{ac}\rceil$$$ as well.

        Also observe that if $$$4ac \leq 0$$$, no $$$k$$$ solves the problem.

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

          How did you got that equation b — 2sqrt(ac) < k < b + 2sqrt(ac)? can you elaborate.

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

            We can safely assume $$$ac > 0$$$; there is no solution otherwise.

            $$$ (b-k)^2 - 4ac < 0 \iff (b-k)^2 < 4ac $$$

            So we have:

            $$$ (b-k)^2 < 4ac \iff |b-k| < 2\sqrt{ac} $$$

            Now we can expand with $$$|x| < \alpha \iff -\alpha < x < \alpha$$$:

            $$$ -2\sqrt{ac} < b-k < 2\sqrt{ac} $$$

            Finally, we have:

            $$$ b-2\sqrt{ac} < k < b+2\sqrt{ac}$$$
          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            $$$(b-k)^2 - 4ac < 0$$$

            $$$(b-k)^2 < 4ac$$$

            $$$\sqrt{(b-k)^2} < \sqrt{4ac}$$$

            $$$|b-k| < \sqrt{4ac}$$$

            $$$\sqrt{4ac}$$$ is constant; Let $$$x = k$$$: if you look at the graph of $$$|b-k|$$$ where $$$b$$$ is constant, it will look something like this (red is $$$y = |b-x|$$$, blue is $$$y = \sqrt{4ac}$$$):

            You can see that the inequality is satisfied when

            $$$-\sqrt{4ac} < b-k < \sqrt{4ac}$$$

            i.e. $$$-\sqrt{4ac} < b-k$$$

            $$$-\sqrt{4ac} - b < -k$$$

            $$$b + \sqrt{4ac} > k$$$

            $$$k < b + \sqrt{4ac}$$$

            and

            $$$b-k < \sqrt{4ac}$$$

            $$$-k < \sqrt{4ac} - b$$$

            $$$k > b - \sqrt{4ac}$$$

            $$$b - \sqrt{4ac} < k$$$

            combined:

            $$$b - \sqrt{4ac} < k < b + \sqrt{4ac}$$$

            $$$b - 2\sqrt{ac} < k < b + 2\sqrt{ac}$$$

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

              Ohh ok now I got it. Thx a lot for the help! By the way which graph plotter you are using?

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

                GeoGebra Classic. I use it because we use it at school. There are other popular ones, for example Desmos, but I don't have experience with anything else.

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

      Actually i used binary search for ans but still got an wrong ans. Link to submission

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

        Let say $$$b = 5$$$ and array have elements $$$[....3, 11....]$$$. It is likely value 3 is getting ignored due to your implementation considering upper_bound only. Thats why we should be finding atleast $$$2$$$ numbers closest to $$$b$$$.

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

          Yes thank you so much. Found my mistake.

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

I think E can be solved using the small to large merging technique.

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

wasted so much time on problem C to learn about parabolas and their tangents

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

    It wasn't a very good problem imo

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

      agree i was watching videos till i realised i ran out of time! :(

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

      I really liked it NGL

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

        Yes . i Liked it too. How b*b — 4ac should be negative. ez take the closest value to b.

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

    but no needs of it. you just need to solve condition on roots.

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

    Do you need to know anything about their tangents? I thought you just need to know how to solve quadratic equations.

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

      Yes you do. There can only be two tangents to a parabola from a point.

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

        No, you don't need to know anything about that. Here is a simple solution.

        For a parabola $$$y = ax^2 + bx + c$$$, we want to choose some $$$k$$$ (from the set of given k) such that the given parabola and the line $$$y = kx$$$ have no intersections, i.e. $$$ax^2 + bx + c \neq kx$$$ is satisfied for all real $$$x$$$.

        $$$ax^2 + bx + c \neq kx$$$

        $$$ax^2 + bx + c - kx \neq 0$$$

        $$$ax^2 + bx - kx + c \neq 0$$$

        $$$ax^2 + (b - k)x + c \neq 0$$$

        This is a quadratic — there are no real solutions iff the discriminant is negative i.e. $$$(b - k)^2 - 4ac < 0$$$.

        You can see that the value of $$$k$$$ only affects the term $$$(b - k)^2$$$. Since we want to minimize the total value, we want to minimize this term. The minimum value will be found when we find the closest $$$k$$$ to the given $$$b$$$. This can be done using binary search or std::set::lower_bound().

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

          applied it but it is failing in pretest 3. with n=100000 m=100000 tests

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

            Bruh. First of all (assuming that this is the solution you're talking about), don't use floating point numbers. You don't need them.

            Second, you didn't even apply my solution. You just tried to brute force all lines against all parabolas which is $$$O(nm)$$$ and clearly too slow. Did you even understand my solution? You need to use binary search or std::set::lower_bound() to find the closest $$$k$$$ to the given $$$b$$$ in order to solve each parabola in $$$O(\log n)$$$ to not get TLE.

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

I know a lot of you wont agree with me but... please make this round unrated (or better fix my resubmission problem) :(

I got huge penalty because of resubmission after getting a lot of WA tc1 in problem C because of the strict checker thing. I know I am not the only one facing this problem so no hate but please reconsider

EDIT:it seems like my previous submission was marked as skipped now, thank you!!

Edit2: NOPE... it just shows "skipped" but still got +4 (lose 200 point). L

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

Imagine praying that there will be no graph problems or at least it will be F or smth and then D and E are both graphs. At least D was meth and binary lifts. Also C was really fun.

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

    no binary lifting is needed to solve D

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

    I usually pray for graph and tree problems (since they're fun) and hope for no geometry/hard math lol. Was quite surprised when I saw a geo problem as C.

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

      I have now officially decided that the contest was trash because C was bad I changed my mind (system test 15)

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

Good contest! Liked idea of D. C was also alright, but it caused a lot of troubleshooting in my code.

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

Solved A-D. Tried Mo's algorithm for E but got TLE.

A: Let A be the xor-sum of a[i], then the xor-sum of b[i] is A (n is even) or A^x (n is odd).

B: Find the minimum char in the string, find the last occurence of it, and move it to the head of string.

C: By the discriminant of quadratic equation we can find that k is valid is equivalent to delta=(b-k)^2-4*a*c<0, which is, abs(k-b)<2*sqrt(a*c). We can find the valid k by binary search.

D: Let eccentricity of node u: ecc[u] = the distance from u to v where v is the furthest node from u. Then we can guess by examples: for certain k, all nodes u with ecc[u]>=k can reach each other in G_k, and nodes with ecc[u]<k are isolated. We can calculate ecc[u] by dfs and maintaining distances from current node using segment tree. (I wasted much time for thinking how to solve D by dsu)

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

    got E accepted with Mo. If you calculated maximum of numbers with set, that's slow

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

    You can solve E without Mo's.

    Bucket nodes based on their values. Iterate over those buckets in decreasing order of value. Then, only buckets of size 2 matter:

    • If the bucket has size 1, then it is impossible to be a "value"
    • If the bucket has size 3, then every edge cut would result in a subtree having $$$\geq$$$ 2 nodes with that value. In this case, we can assign every un-assigned edge that value and stop here.

    Consider the first time we encounter a bucket of size 2. Call the nodes $$$a$$$ and $$$b$$$, and their value $$$k$$$. If an edge is not on the path from $$$a$$$ to $$$b$$$, then it must have the value $$$k$$$. We can assign them by iterating over every node on the path from $$$a$$$ to $$$b$$$, and then doing a DFS from each of these nodes, avoiding moving on edges on the path from $$$a$$$ to $$$b$$$ (since we still don't know their value yet).

    After this, our graph has been reduced to a path, making things easier. The next bucket of size 2 (say $$$u$$$ and $$$v$$$), we can set all the edges that aren't on the intersection of $$$Path(a, b)$$$ and $$$Path(u,v)$$$. You can do this by only doing the above DFS from two nodes (think about how you would implement this). The remaining edges are once again a path, so we can keep repeating this step.

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

Can E be solved by HLD?
If so, then I know I should have finished that part few days ago.

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

Very hard D

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

Can someone tell how to solve C, i used (b-k)^2-4ac, but got TLE on test 3

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

    you can search for the nearest k from b by sorting the k's and then use binary search

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

    yes, the parabola does not touch any line if (b-k)^2 < 4ac . so you need to find a value of k which satisfies that inequality from the given values of k, which can be done using binary search to avoid TLE

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

    You checked whether a parabola can have a suitable line individually for each line which requires O(N * M) total Time, hence the TLE. In the quadratic formula, you know that D = (b — k) ^ 2 — 4 * a * c, here the only value that is not constant when the slopes vary is (b-k), now as you may know for a line to not touch(D == 0) / intersect(D > 0) the parabola, the equation D have to be has to be a negative value i.e D < 0. Since the only varying quantity in the equation is (b-k), you can try to reduce the absolute difference between b & k. A fast way to do this is by sorting all the given slopes and then binary searching on the nearest value to the selected b. This would reduce the Time Complexity to O(M * log(N)). To know about finding the closest value from a given set of integers to a certain value N in (O(log N)), you can refer to this article: https://www.geeksforgeeks.org/find-closest-number-array/

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

I will be NEWBIE (❁´◡`❁)

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

Due to CF lag in last several minutes I was unable to send E to AK the contest(((

UPD: solution got AC :/

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

can someone hack https://mirror.codeforces.com/contest/1805/submission/200452160 pls?I had been debug for 1 hour but still got wrong on pretest two.

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

Is E solvable by rerooting technique?

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

Bruh my B FST'ed

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

    At first i thought that the contest was good but then my C FSTed so I think it was complete garbage (this is a joke i absolutely enjoyed it)

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

Can someone tell me why this code for D is wrong? 200453419

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

My math brain trick me to calculate the equation of 2 tangents instead of going for the obvious approach. Specialist here we go.

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

    Specialist community welcome you with open heart :)

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

F1>>>>D,but both have same score.

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

Beautiful contest. Absolutely loved the problems! Couldn't solve C (cheers to negative delta :P), but grateful for the learning.

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

Finally did my first ever TREE question in contest. Solutions:

A. If n is even with xor of all not equal to 0 then ans is NO, else answer is always xor of all elements of array.

B. Find the smallest char in string and put it at first, well sorry for poor english. I printed that char, then string till that char and string after that char.

C. In parabola, if 4ac is negative that means it'll definitely touch x axis and other than that, we had to find such k which makes (b-k)^2 < 4ac . after sorting vector of k, for every parabola we had to binary search the closest k to b and check whether it holds (b-k)^2 < 4ac or not.

D. We had to find the maximum distance that each node can go to ( 2 DFS ), and for every i in k we find all nodes with maximum distance less than i and print min(1+count,n).

It would be great if someone could explain me E.

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

    Can you explain D in more detail?

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

      In simpler words, the task was to remove vertex/node from tree (edge still exists hypothetically) which have farthest distance less than current i in Gi and calculate number of disconnected graphs after that.

      For i as 1, all nodes has distance one at least so there's only 1 tree present. Same for i=2,....

      Now for i as 4, if we have a node that can have farthest node at distance 3 but as the problem says only those will be considered with distance at least i present, so that nodes form another single node tree and hence number of different trees increases by 1.

      my Intuition was to calculate the maximum distance any node can visit and then considering ans as 1 in beginning remove the nodes with values less than i and add the count to the ans.

      FARTHEST DISTANCE, this is where they tell how we use 2 dfs to calculate the farthest distance any node can go, one DFS to calculate heights of particular nodes and other to find the maximum distance of a Node from all its ancestors.

      I Hope you get what I did. :)

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

        I don’t understand how you could use the farthest distance of each node to get the answer. I think to do that, we have to assume that all connected components except the biggest component have a size of 1. But I don’t know how to prove it. Could you help me with this?

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

          Consider the ends x,y of the diameter of the tree (if there are multiple diameters you can choose any one of them). You can prove that the farthest node from any vertex v will be either x or y. So, any v will either be in a connected component of size 1 or it will be in the same connected component as either x or y, but x and y are in the same component whenever k <= diameter. Therefore all vertices that are not in a component of size 1 will be in the same connected component.

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

    I solved E with small to large, but by using the observation that if the same number appears at least three times it can be a minimum, you can have a way simpler solution

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

      Can you explain that with an example, I get what you are saying, but still example would make it more clear.

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

        About small to large: this technique allows you to do queries based on subtrees (which is technically what you want here), and so for every subtree you can easily count which numbers appear at least twice, and with that you can also get the answer for the "other side" of the tree at the same time, which is exactly what the question wants.

        About the other thing I said: it's easy to see that if a number appears at least thrice, then when you remove an edge, it'll appear at least twice in either side of the tree. If a number appears only twice, then the answer for every edge can be that number except those on the path between. Then for that you can do HLD or some other technique.

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

          Okk, gotcha, I will try to implement that, seems quite new to me. Thnk you for the technique.

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

I think there should be some edge cases for C, where sqrt(a * c) is not accurate.

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

    why use sqrt, when $$$(b - k) ^ 2 < 4ac$$$ is perfectly fine as it is

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

guys, I can do binary search, greedy, and dp just fine because there are a lot of good easy-medium problem for those categories. But for graph, it seems like the good problem is >1900 rated. Any advice for me to start practicing graph?

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

    While I'm not really a proponent of following a topic-specific practice routine. Since you asked -

    You could refer to CSES' graph section. Alternatively, you could also filter problems on Codeforces by the tag — "graphs", solving them in descending order of solves.

    An issue that might come up on Codeforces is that you might encounter problems that can be solved even without applying graph algorithms tagged as "graphs", this happens when the problem also has some solution/intuition related to graphs. It's not really a bad thing either, maybe a welcome exposure to additional variations on graphs.

    As for improving, identify the challenges. Are you lacking in identifying the solution or are you unable to implement your ideas? If it's the former, take more time before jumping to implement, and maybe try out a few test cases yourself. If it's the latter, stop, and don't hurry. Implementation improves with practice, but you need to streamline the process. Read others' codes. How do the top competitors implement the solution? Learn from them. More often than not, you'll find that their solution is much more clear and concise as compared to yours, and after adopting those patterns/practices, with time, you should find your implementation skills improving as well.

    Edit: Fixed language

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

      Yeah, I agree that studying specific category isn't the best idea. But I think my knowledge in graph is kind of far behind from the other categories.

      As you mention before, it seems like I am lacking in identifying the solution. So it is like when I see graph problem, it is either I can get the idea fast or I don't have any non-TLE idea at all.

      Thank you for your suggestion by the way. I've tried that but when it is to easy, it's like I don't have to solve it using graph at all. But when it comes to harder problem.... I got stuck ☺. I will give CSES a try btw.

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

Guys I don't know why my submission to C wrong, I use binary search to check the largest k that make delta less than 0 but it got me wrong on tc4. I appreciate if someone would check me out: https://mirror.codeforces.com/contest/1805/submission/200427173

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

    If you do a linear traverse on the array line and print the value of check(a, b, c, line[i]) you will see something like: (0 is false and 1 is true)

    0 0 ... 0 0 1 1 ... 1 1 0 0 ... 0 0

    So check() is not a monotonic function and cannot be used to search the best k.

    Instead, and observing the previous array and the check() function, we should search for the value that is the nearest to b. This is done by using std::lower_bound() on line and checking the previous, current and next value in the array, if exists.

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

Problem D was a variant of Tree Distance 1.

Did anyone solve E with square root decomposition? (I think for 2sec it would have passed).

PS: Finally solved E with (eular tour + ST + MO + CC) (couldn't make in contest >_< due to multiset)

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

Task C is so boring and stupid. Not because it is geometry, but because it combines trivial geometry with a well-known task.

Task D is very interesting, exited to read an editorial.

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

Solutions of Question C should be rejudged. Or it should be done unrated. There is no mistake in my solution 200416961.

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

i just want to know why it will be WA? i use the same code but got AC????200421371

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

    I think you are missing lower bound that is "t1" in your case may not exist.

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

      but why i got AC for the same code in C++ 17(64)??

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

        Instead of using inbuilt power function ,you should always use iteration to calculate value.In this case you can just multiply 2 times.I think this will resolve problem.Inbuilt power function is susceptible to errors. I think this will help.

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

    what if t1 is equal to n+1, that is undefined behavior and differs from compiler, also maybe is a floating point error, using pow maybe gives rounding error, but I bet on the first.

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

Good contest. Solved A-D and F1(but only after contest, cause i forgot to sort numbers in the beginning:))

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

    I think F1 can be solved easier submission If {a_i} is sorted, we must only check "small" pairs,

    $$$(a_i,b_j)$$$

    . We must check

    $$$(a_0,a_j) \;\;\;(0<j<n)$$$

    and

    $$$(a_i,a_j)\;\;\; (0<i<j<2*sqrt(n))$$$

    .

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

Got RTE in the system test of problem C because of the following code: vector<ll> a(n), b(n), c(n); for (int i = 0; i < m; i++) { cin >> a[i] >> b[i] >> c[i]; } Want to punch the me who wrote this during the contest LOL.

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

    Bro the same exact thing happened to me. How did they not have a single sample where m > n?

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

Can someone tell me why this code for C is TLE? 200448401

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

    I think while loop inside func2 may be taking more iterations.Otherthan that nothing seems like TLE.

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

      I also have submitted with sqrtl function even then it is giving TLE.

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

        Share link of that submission.

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

            Just changing input datatype double to int.It is getting AC.I am not able to find reason.here is submission 200471590

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

              Thanks bro

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

                I think dealing with doulbe takes more time.No,issue with sqrtl,binary seach also giving TLE if using double.If you find any valid reason.Please share.

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

                  I think the problem is not passing double in sqrtl as this function primarily converts any argument to double, the problem is how I am taking input if I just used this line
                  ios_base::sync_with_stdio(false); then the code is got accepted. see 200474428.

                  reference : cincout vs scanfprintf

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

                  Problem is not with sqrtl.Even binary seach implementation also giving TLE.Submisson 200476282.It is little bit clear after gfg reference btw.

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

                  You are getting TLE while using double as double numbers can be infinitely close to each other. In about 70-80 iterations we can reach max accuracy of double. But in your code the condition is L<=R which can have huge iterations.

                  The same is discussed here in edu section: Binary Search On Real Numbers

                  I have taken 100 iterations in your code with double and it passes. Submission

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

                  Bro but i am using long long int as our left right pointer so finally l,r,mid are long long,so l-r will always be integer there should not be huge iterations.I still in confusion how is my code taking more iterations.Above kpsingh_20 used — ios_base::sync_with_stdio(false); then it is passing.

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

When will the ratings be updated?

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

Awesome problems, really really enjoyed! So lovely. And problem D was a really really a good modification of dp on the tree, wasn't it Elcanmustafayev?)))

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

My solution 200419006 for problem c passed all pretest cases but failed on test case 9. please help me to find the mistake.

Week pretest case

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

    I don't know how it is wrong. I just change 2*(a*c)^1/2 to (4*a*c)^1/2
    200467745 and it got accepted. please help me to understand where I am getting wrong.

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

I got FST in problem C. Here is the submission. Used my own b_search to calculate sqrt instead of builtin functions. Still FSTed lol.Any idea?

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

    Take a look at Ticket 16800 from CF Stress for a counter example.

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

      Thanks bro,the error was in the part where I was making sqrt(ac) using b_search function and then multiplying by 2.Instead I should have done sqrt(4*a*c) because the former one resulted in loss of some decimal values which could have been important.

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

Why was this submission TLE? 200462889

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

can someone find out at which case my code for C failed 200465252

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

A really nice contest . Great Job Problem Setters I loved the problems . Just a little thing if any one could help me out with this , 200438416 , how to avoid such errors in actual contest , i do get the logics to the lot of problems but fail at implementation , any way to avoid this . Thanks

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

    How does that clock hack that you used in F2 work?

»
19 months ago, # |
  Vote: I like it +1 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 tutorial

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

I might become a specialist today for the first time. I wonder why CF is taking so much time to update the ratings :/

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

    congrats and all the best :)

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

    Why it takes so much time? Is it change to unrated

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

      Let's hope that It is kept as rated. There was just a small issue with whitespace checks in Problem C

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

        Today I might be become expert, that's why worried:(

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

          is today's contest becomes unrated..?

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

            no, it's rated. but I dont know when ratings will be updated

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

The code in editorial of problem E seems to be wrong!

For the input:
7
1 2
2 3
3 4
4 6
4 7
1 5
100 1 1 100 10 10 10

It should output:
10
10
10
100
100
100

But it is outputting:
1
0
1
100
100
100

But the code of editorial seems to pass all the cases! Which implies that the test cases are weak. But also the hack is giving the unexpected verdict, see hack #899337.

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

    Why this happened? Will it result in unrated? Sadly I guess it will be... But how did the author make this error? I think E's difficulty is implementation,not the idea...

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

      I commented this because of issues and facts. I have little impugnment to the authors,just regret for the errors.okay,from now on i learn to shut up

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

    Thanks, fixed

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

When will I see my new color?

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

Thanks for the amazing round and the great problems!

I got rank 2 in this round and become International Master now.

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

Which problem you liked most?I liked problem D.Thanks for doing contest!