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:

Thanks to

**[Coordinator] pashka**for coordinating and helping with testersSpecial thanks to

**[G.O.A.T.] Mangooste**for discussing tasks and testingThanks to all the testers:

**[MVP++] Ormlis**,**[Upsolver] physics0523**,**[Upsolver] Vladithur**,**[Upsolver] vsinitsynav**, pashka, Dominater069, darkkcyan, AlperenT, rsj, NewLul, Sweezy, KiruxaLight, gmusya, aryan12, tomsangotw, jonatas57, ivn1k, vefg, putis, DDima, 9kin, Dmitry345, ak2006, playerr17 и KodomoTachiThanks to MikeMirzayanov for the Codeforces and Polygon platforms

Thanks Artyom123 for the initial task review

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 | b6e3 | 6 | 6987 |

2 | Darren0724 | 6 | 6683 |

3 | cpbeginner | 6 | 6520 |

4 | suckthembi | 6 | 6269 |

5 | GOD_0F_DEATH | 6 | 5915 |

Top 5 of all participants:

Place | Participant | Problems solved | = |
---|---|---|---|

1 | amiya | 7 | 8214 |

2 | SSerxhs | 7 | 7786 |

3 | Heltion | 7 | 7750 |

4 | maspy | 6 | 7623 |

5 | noimi | 6 | 7255 |

Participants who sent the first correct solution to the problems:

Task | Participant | Penalty |
---|---|---|

A | A_G | 0:00 |

B | Geothermal | 0:02 |

C | BucketPotato | 0:08 |

D | peti1234 | 0:11 |

E | b6e3 | 0:11 |

F1 | BeyondHeaven | 0:26 |

F2 | SSerxhs | 1:37 |

Very important poll!1.8 PvP or 1.19 PvP?CFR 8.62 PvP

Imagine voting for 1.8 pvp

wtf, why 1,8 is winning? 1.8 pvp is trash.

In fact, problem solving is the winner

1.8 going to win, there are many servers out there still running on 1.8 because of pvp

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

As his classmate, I also want to thank him

Classy contribution

As m0t9_'s classmate, I also want to thank him

9kin orz orz orz

Testers from every colors

pls not maduka again :)

What evil Madoka did for you?(

Don't say the name, we are scared :(

:/

best of luck!

Good luck ....

As a future participant,I am excited

Hope to solve problem C this time.

It's Ez. It is Binary search.

wow! Are you from future?

Still couldn't solve it in time. Just missed one condition and now thinking of my existence on this earth.

JEE_MAIN_LOOSER orz

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

your wish is granted

But you need to ask nicely...

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

and as a participant, I ask for a steak to the testers before the round starts.

and as a steak, i recommend testers eat a participant before the round.

good contest

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

Contest and Ramadan , it is fantastic :)

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?

Usually it works like that.

Looks like they changed the numbers after reading this comment :D

as a tester, best of luck!!!

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

Hope to be a candidate master

In case of light mode attracts bugs, I'll set my editors theme to dark mode and then I'll join you.:)

SpoilerAs an author, I am not red

Codeforces round comes thick and fast. I hope everyone will have a positive delta rating.

i want to be a tester** :)**

Good luck?

Bn Allah help us;

Seems to blue contest for cyans

Hopefully.

Leaving on the edge

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

Good luck!)

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

Fun fact: problem F2 was initially proposed as Div2D 💀

xd

E can be easily solved with Mo on subtrees

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

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

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.

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

Do you have any blog or any article related to this trick?

I've definitely seen it somewhere, but I can find it now.

Just for the history: https://codeforces.com/blog/entry/100910 Item 2

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.

I got TLE doing this ;-;.

I think its because of my map spam :skull:

Can you please explain this?

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.

Had to reread elementary school lesson to solve C lol

can you explain your solution to problem C please

What is the solution for D?

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.

Wait so how do you find the maximum distance from a node to any other? dfs?

https://cses.fi/problemset/task/1132

thanks a lot!

GeeksForGeeks

I should've probably just copied the code from there instead of coding it on my own; I would've probably gotten like 200 more points :(

Have a look at this post: link

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.

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?

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

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

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

Can you see why this happens?

Ohh ok so here my logic is bit wrong as am assuming that larger the number more closer to the ans. So if the mid value is not giving me discriminant >= 0 am going to the right side of the array only.

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

Binary Search

HintIn order to minimize $$$(b - k)^2$$$, $$$k$$$ should as close as possible to $$$b$$$

upperbound to b then while binary search?

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

Yes using that , Try to find 2 numbers, where one number $$$<=b$$$ and another $$$>b$$$. And then see if any of them gives $$$D < 0$$$

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.

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

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

So we have:

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

Finally, we have:

Thx for the help.

$$$(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}$$$

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

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.

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

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

Yes thank you so much. Found my mistake.

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

same idea, bro! my solution

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

It wasn't a very good problem imo

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

I really liked it NGL

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

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

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

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

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()`

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

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.If you have the equation of the parabola and the equation of the line, you will check if there are a points of intersections between them by equalize these equations, so the equation of the line will just affect on coefficient b, from the equation of quadratic solution term of sqrt((b-m)^2-4*a*c) will give you an imaginary solution so there is no intersections, imaginary solutions have minus under the square root like this sqrt(-1), so you will check if there is a line with slop 'm' make these ((b-m)^2-4*a*c)<0 or imaginary solution.

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

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.

no binary lifting is needed to solve D

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.

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

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

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)

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

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:

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.

Can E be solved by HLD?

If so, then I know I should have finished that part few days ago.

if you want to overkill it like me, yes

Very hard D

i felt it was quite standard , i guess this problem was inspired from the problem -> calculate the diameter of a tree

"standard"

What's next？FFT in problem C?

solve cses

it was straightforward for me. Don't know will get FST or not..

that's what she said

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

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

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

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/

Thanks a lot to all replies!

I will be

`NEWBIE`

(❁´◡`❁)Due to CF lag in last several minutes I was unable to send E to AK the contest(((

UPD: solution got AC :/

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

Take a look at Ticket 16798 from

CF Stressfor a counter example.tkx:D

Is E solvable by rerooting technique?

Same question

Bruh my B FST'ed

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)

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

Take a look at Ticket 16799 from

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

Specialistcommunity welcome you with open heart :)F1>>>>D,but both have same score.

Couldn't get an idea for problem D at first, switched to problem F1, gave 20-25 minutes to it, the solution i was trying was getting complicated. Returned back to D, solved it using some observation and given testcases, and luckily it got AC XD .

F2 ~ D, lol

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

Finally did my first ever

TREEquestion 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.Can you explain D in more detail?

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

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?

Lets consider the first testcase only, let's consider we have already calculated the distances and it came out to be : 2 3 3 4 4 4

Now, let's work for every i

i=1 connected graphs -> 1 (6 Nodes in this).

i=2 connected graphs -> 1 (6 Nodes bcz every node u have another node v with distance at least 2 )

i=3 connected -> 2 (5 Nodes, 1 Node), first one is out bcz there's no v node for root node which can have distance at least 3.

like so for i=4 connected graphs -> 4 ( 3 nodes, 1 node, 1 node, 1 node).. these 1 nodes are basically the ones to had distance between then less than i in whole graph.

i=5 ad i=6 , connected graphs -> 6 bcz all no u and v exists with distance as 5 or 6.

I don't know where you getting stuck, but we just have to calculate how many different graphs we get for every i, that's all is there :/

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.

I got it, thanks

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

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

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.

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

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

i used sqrtl

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

Because I am using bisect.

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?

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

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.

Can anybody tell me why code fails on pretest 6

~~~~~ bool chk(ll a,ll b,ll c,ll k){ return (b-k)*(b-k)-4*a*c<0; }

ll n,m; cin>>n>>m; vectorv(n); priority_queue<ll,vector,greater>pq,pq2; multisetmst; loop(i,0,n-1){ cin>>v[i]; mst.insert(v[i]); pq.push(v[i]); } sort(all(v)); vectorind;

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://codeforces.com/contest/1805/submission/200427173

You are also making the similar mistake in problem C . Refer to this

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

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.

but C is not geometry -_~

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

what if variable it points to the the end of vector? Your code fails.

Yeah i got my mistake.

your solution is wrong

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

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

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

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.

You have added wrong submission number. I don't know why your code got passed but one should be careful for such minute mistakes.

because in 64bits and 32bits double is different

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.

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

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

. We must check

and

.

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.Bro the same exact thing happened to me. How did they not have a single sample where m > n?

I Got FST in C , wished pretests could have been stronger.I later fixed it.

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

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

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

Share link of that submission.

200464373

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

Thanks bro

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.

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

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

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

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.

When will the ratings be updated?

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

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

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.

I think because of precision error. Never use float numbers where they are not needed!

But where I am using float number?

here

sqrtl function I guess.

Take a look at Ticket 16803 from

CF Stressfor a counter example.Here is the testcase1

2 1

0

2

1 -2 1

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?

Take a look at Ticket 16800 from

CF Stressfor a counter example.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.

Why was this submission TLE? 200462889

Can someone tell me what is wrong with my solution? https://codeforces.com/contest/1805/submission/200443236

Take a look at Ticket 16801 from

CF Stressfor a counter example.Take a look at Ticket 16802 from

CF Stressfor a counter example.can someone find out at which case my code for C failed 200465252

Take a look at Ticket 16804 from

CF Stressfor a counter example.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

Screencast

What an anime lover... xd

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

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

Helpful video….

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

congrats and all the best :)

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

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

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

is today's contest becomes unrated..?

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

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.

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

Cuz human is a human, not a robot. It is fine. There was a little problem. No need o change the round to unrated.

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

Thanks, fixed

Will this round be unrated or rated? Please reply.

Rated

When will I see my new color?

Thanks for the amazing round and the great problems!

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

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

Dear Judge! Please consider my case... Literally 3 hours ago, a warning came about plagiarism of the code from the user Anton_Wars... In fact, it was my second account that was open in different browser tabs on the desktop. I accidentally attempted to do task "C", having no idea that I was not doing it from the main account. Please consider this comment and forgive me for such an act. I swear on the word of the programmer that this will not happen again... I didn't do it on purpose, only with my mind and experience I'm trying to conquer the rating system on such a wonderful platform as Codeforces... Please take this comment seriously and give me a second chance... Sincerely, the participant of the contest.