Привет всем на Codeforces.com!
В этом раунде я (Alexdat2000) и двое моих друзей — FairyWinx и sevlll777 — подготовили для вас 6 задач (одна из которых разбита на две подзадачи), а у вас будет 2 часа на их решение. Приглашаем всех перейдите по ссылке: Codeforces Round 862 (Div. 2) в 02.04.2023 17:35 (Московское время). Этот раунд будет рейтинговым для всех участников с рейтингом строго меньше 2100.
А теперь несколько благодарностей:
Спасибо [Coordinator] pashka за координацию и помощь в поиске тестеров
Особое спасибо [G.O.A.T.] Mangooste за обсуждение задач и тестирование
Спасибо всем тестерам: [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, competitive__programmer, playerr17 и KodomoTachi
Спасибо MikeMirzayanov за платформы Codeforces и Polygon
Спасибо Artyom123 за первоначальное ревью задач
Разбалловка: 500 — 750 — 1250 — 1750 — 2250 — (1750 + 1750).
UPD: Разбор
UPD-2: Поздравляем победителей раунда!
Топ 5 официальных участников:
| Место | Участник | Задач решено | = |
|---|---|---|---|
| 1 |  b6e3 | 6 | 6987 |
| 2 |  Darren0724 | 6 | 6683 |
| 3 | cpbeginner | 6 | 6520 |
| 4 | suckthembi | 6 | 6269 |
| 5 | GOD_0F_DEATH | 6 | 5915 |
Топ 5 всех участников:
| Место | Участник | Задач решено | = |
|---|---|---|---|
| 1 | EvenImage | 7 | 8214 |
| 2 | SSerxhs | 7 | 7786 |
| 3 | Sugar_fan | 7 | 7750 |
| 4 |  maspy | 6 | 7623 |
| 5 | noimi | 6 | 7255 |
Участники, пославшие первое правильное решение по задачам:
| Задача | Участник | Штраф |
|---|---|---|
| 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!
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 :(
:/
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.
ewwwwwwwww
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
Hope to be a candidate master
As an author, I am not red
Good luck?
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://mirror.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
Contest was good, but problem C took a lot of time due the fact that you had to deal with decimals which caused a lot of troubleshooting.
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 $$$ \lt 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
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?
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
In 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.
You can show $$$(b-k)^2-4ac \lt 0$$$ implies $$$b-2\sqrt{ac} \lt k \lt b+2\sqrt{ac}$$$. From here you can use
upper_boundwith $$$\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 \lt 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 \gt 0$$$; there is no solution otherwise.
So we have:
Now we can expand with $$$|x| \lt \alpha \iff -\alpha \lt x \lt \alpha$$$:
Finally, we have:
$$$(b-k)^2 - 4ac \lt 0$$$
$$$(b-k)^2 \lt 4ac$$$
$$$\sqrt{(b-k)^2} \lt \sqrt{4ac}$$$
$$$|b-k| \lt \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} \lt b-k \lt \sqrt{4ac}$$$
i.e. $$$-\sqrt{4ac} \lt b-k$$$
$$$-\sqrt{4ac} - b \lt -k$$$
$$$b + \sqrt{4ac} \gt k$$$
$$$k \lt b + \sqrt{4ac}$$$
and
$$$b-k \lt \sqrt{4ac}$$$
$$$-k \lt \sqrt{4ac} - b$$$
$$$k \gt b - \sqrt{4ac}$$$
$$$b - \sqrt{4ac} \lt k$$$
combined:
$$$b - \sqrt{4ac} \lt k \lt b + \sqrt{4ac}$$$
$$$b - 2\sqrt{ac} \lt k \lt 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.
What does pretests passed mean?
In Div 2 and Div 1 contests any test is either a system test either a pretest. When you submit a solution during the contest, it is only tested on the pretests. But it doesnt mean that your solution is correct , though. Because after the contest every solution is also tested on the system tests, and there it is decided, whether it is AC or not.
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 \lt 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.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://mirror.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 Stress for 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
My math brain trick me to calculate the equation of 2 tangents instead of going for the obvious approach. Specialist here we go.
Specialist community welcome you with open heart :)
F1>>>>D,but both have same score.
F2 ~ D, lol
guys, I can do binary search, greedy, dp just fine because there are many good easy-medium problem for those categories. But for graph, it seems like the good problem is rated >1900. How should I practice graph?
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 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.
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?
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.
why use sqrt, when $$$(b - k) ^ 2 \lt 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.
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
If you do a linear traverse on the array
lineand print the value ofcheck(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 usingstd::lower_bound()onlineand 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.
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?
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
1
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 Stress for 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 find out where is my code for C failing 200465252
can someone find out at which case my code for C failed 200465252
Take a look at Ticket 16804 from CF Stress for 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
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...
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!
Update the problem ratings
Question b is not handling the testcase well ig.
'aabcb' for this string the output should be 'aabbc' as it is the lexographically smaller array. but the editorial saying 'aabcb' as output. also the testcase doesn't handle this one.