Hello Codeforces!
We are pleased to invite you all to participate in Codeforces Round 891 (Div. 3), which will start on Aug/07/2023 17:35 (Moscow time).
The format of the event will be like any Div. 3 rounds:
6-8 tasks;
ICPC rules with a penalty of 10 minutes for an incorrect submission;
12-hour phase of open hacks after the end of the round (hacks do not give additional points)
after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
by default, only "trusted" participants are shown in the results table.
We encourage participants with a rating of 1600+ not to create new accounts but to participate unofficially.
Only trusted participants of the third division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 (or you are a newcomer/unrated), then the round will be rated for you.
Problems have been created and written by our team: FBI, Skillful_Wanderer, SashaT9 and Pa_sha.
We would like to thank
MikeMirzayanov for creating Codeforces and Polygon.
Vladosiya for coordination.
nigus, YocyCraft, lis05, Nazar, welleyth, pavlekn, senjougaharin, Vladithur, DJeniUp, volochai, eggag32, moonpie24, shell_wataru, Kalashnikov, Bogdan1110, ksu_, zamong_juice, myav, sonyalytv for testing the round and making it better.
Good luck!
UPD: There was an error on problem F. We fixed the tests and rejudged solutions . We apologize for that. It only affected a few people whose solutions passes all tests now. Also some hacks were already added to the tests and broke some of solutions.
UPD2: Editorial
As a developer who happened to be the leader of the team, I would say you just these two words. Good luck!
I am glad to say that I have received luck from the one and only FBI :)
FBI please catch cheaters
I hope the contest will be good, in advance I congratulate you on becoming the authors of the contest on cf
Thanks! Hope you will like our contest
Keep Calm & Create Interesting Competitions For All
As a coordinator the guys have prepared an interesting competition for you!
As a tester, I hope div3 users will enjoy this contest from well-prepared problems.
As a first-time tester, this is the best contest I’ve tested :) I hope you’ll like the problems!!
And also the worst :)
If you don't solve some easy tasks, it doesn't mean that contest is bad!
Nice!
rename it to Div.2
No bro div2 D is never easy,
what about B?
made video explaining A&B&C&D:
https://youtu.be/elQ4jmUfYqM
thought would be usefull for community
We know hacks do not give additional points, they just take away points .,.
Hoping it will be a great round of
Div.3. Best of luck to all contestants!As a coach of these guys, I am delighted to see their first performance as problem setters at Codeforces, as well as to see positive feedback from the testers. I do believe that problems are well-prepared and fascinating. Also, I hope that everyone (including Grothendieck, the mathematician after whom we called our team) will enjoy the contest.
As a tester, I can assure you that the problems are of high quality, and you will definitely enjoy solving them. Please, read all the statements. Even if you find yourself stuck on a problem — try to solve the next one.
Good luck! May the skill be with you.
As a first-time tester, all the problems are fun and well-prepared. I hope you will enjoy the contest and earn a positive delta! Good luck!
KEKW
First Unrated Div3 :)
Congrats!,But even though Div3 is unrated for everybody 1599+, everyone is welcome to participate)
:) Thankyou Buddy
SashaT9 orz
Tomorrow : Problem A : dp on a tree ):
Ukranian Contest!
Hoping to become cyan in this round.
Me too!!! GL & HF to all <3
Good Luck everyone!!!
Wish everyone can enjoy the Div.3 round, let's gooooooooo!
Ukrain rocks!!!
You mean: UK rains rocks ?
High IQ brother!!!
I will solve at least five problems.
All the best
hope a good round, although i will be unrated.
Hope that I can get back to expert.
Good luck!
I wish good luck to the participants and no problems during the round to the developers! I am also very glad that now more and more different teams are preparing div-3 rounds! ✨
hope everyone rating increse after div 3 , good luck everyone !
You know this can't happen right?
may be , but i hope this happend
Currently, There's a variety in teams who prepare DIV 3. Interesting UwU
Hope to become expert
Hope to be Specialist this round.
All the best
I really like it when I see the problem setters of the contest have solved thousands of problems, when their rating graphs has lots of ups and down, because they know the struggles of people who have practiced a lot and lot but still face problems during contest. And they set problem keeping these things in mind.
Hope to become expert!
A div 3 prepared by Ukrainian and Russian, I love this.
Congrats!!!
Thank you very much!!!
안녕, i am a (beta) tester
Hopefully i will be pupil again. Good Luck guys!
Hope to become Specialist :)
Wow, so the writers are all from Ukraine!
!!!! NO CYAN TESTERS in this round !!!
My last rated div.3
Character++
Good Luck!
Hoping it will be a great round of Div.3. Best of luck to all contestants!
I hope to get close to 1600 or above.
John Cena wishes you luck
Hoping that rating will increase in this round. Best of luck to all pupil!
Hope that the statement is clear and short
So there won't be any rating awarded for participants like me?
"Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 (or you are a newcomer/unrated), then the round will be rated for you."
good luck to everyone
Thanks for this round! Good luck to everyone!
Speedforces!!
Speedcoding is a different kind of fun...
Problems B and C ruined the contest for me
idk but i feel like this contest might have been a little bit hard :)
Problem statement is very strange and difficult
very boring problems
I see a lot of negative comments, and I don't know why, as the statements were pretty clear and problems seemed fine, just like in the last 2 contests.
G is absolutely beautiful!
Didn't solve but seems pretty elegant to me as well!
Is it 2^(number of pairs u-v where dist(u,v) < S) ??? I couldn't think of a concrete solution
No, the main idea is based on Kruskal's algorithm. If you know Kruskal's then you'll recall that it adds edges in increasing order of weight, but if an edge creates a cycle, then it skips it. Now if you apply Kruskal's to the given tree (add edges in order of weight), you'll be able to deduce some of the edges that need to have larger weights than the current edge. (bad explanation, ik, but it should get the main idea across.)
I believe that if any of the edge has a weight s initially, then it's 0.
Otherwise, it's a combinatorics problem — You can try to insert every possible edge with every possible combination with every weight in range of [max weight in the given tree+1, S].
P.S: 0 if w_i==s is wrong. An edge can be added without changing the MST.
80 is a possible output as shown in testcases; so unlikely
kind of standard actually, ive seen this exact thing before (counting how many pairs of nodes each edge is maximum of)
It's div3, so perhaps standard problems are excusable.
i disagree, all rated contests should have non-standard problems. Either way, i was talking about why i dont find it beautiful or even good.
How to solve F?
Hint: for each pair of x and y, there is only one set of numbers which satisfies a + b = x and a * b = y
If ai is part of a pair then ai+(y/ai)=x, which gives a quadratic equation. Solve it and you get the values of ai and aj. The rest is simple combinatorics. Be careful of the case when the quadratic equation has zero or one solutions.
For every $$$(x,y)$$$ the is at most one unordered pair of integers $$$(a,b)$$$ such that $$$a+b = x$$$ and $$$ab = y$$$. You can find $$$a$$$ and $$$b$$$ via quadratic quation.
You can store the frequency distribution of a_i in a map and then just try to solve the quadratic. If roots are equal, answer is n choose 2 where n is frequency of the root otherwise, it is n1*n2
you just need to know how to solve a quadratic equation
Solved it 5 minutes after contest sadge. The answer is pretty simple, just notice that you can rewrite your two equations as two quadratic equations and then apply the quadratic formula.
a_i + a_j = x means that a_i = x — a_j. And if you insert this in a_i * a_j = y you get a_j*(x-a_j) = y which can be written as a_j ² — a_j x + y. And the same for a_i.
Then quadratic equation gives you two possible solutions x — sqrt(x*x — 4*y) and x + sqrt(x*x — 4*y). So you just see how many of these elements are in your array to make an answer out of and you get your answer :)
https://codeforces.com/contest/1857/submission/217739412
Bro i saw your code what is (x+thing)%2 in that can you please explain
Sorry for the non-descriptive name, but thing is just the square root of the discriminant. You can see that in the quadratic formula the answer is (-b +/- thing)/2a. Which is (x +/- thing)/2 (which you see in the code)
The reason we have (x + thing)%2 in our code, is just because we are working with integers and not floating point numbers. If (x+thing) was an odd number, then the quadratic formula would've given us a non-integer as an answer, which we know we can't have, so we exclude those cases.
Got it Bro thanks
How to solve G ?
Consider Kruskal algorithm performed on input tree. On each step we're connecting 2 components via edge with weight $$$w$$$. The other edges connecting these two components must either have higher weight or just not exist, so we multiply our answer by $$$(S-w+1)^{S_1S_2-1}$$$, where $$$S_1$$$ means size of first component and $$$S_2$$$ size of the second one.
I mean, problem G is much more than that, isn´t it?
No, it's the whole solution.
Actually my code for problem G is almost identical as yours but I mean, the reasoning to solve the problem is more than that in my opinion.
B was a little unclear for me. also hard.
Thanks for the round. I solved until problem E. Problems up to E were fine for me, except for problem B.
Missed F by 30 seconds. F
Me too
https://codeforces.com/contest/1857/submission/217739412
I solved it right after contest, only because I TLE'd because I used multiset.count instead of map.
I feel like Problem B was too hard for D3B.
It take me a lot of time :(((
Agree! Statement is foggy!
What's the test 24 on pG:(
Exit for the type of frequent
Hmm, I've no idea. Could you please explain? I guessed my modulo had some problems at first, but it seems not.
In most solutions, there is an exit for the type in exponentiation
Doing modulo on the exponent is wrong (I was doing this too and it's worked for many past problems as I guess the exponents never got that high).
oh I got it, thanks
On line 44 in submission 217723319,
int x=fpow((s-c+1)%mod,(siz[a]*siz[b]-1)%mod);should be changed toint x=fpow((s-c+1)%mod,(siz[a]*siz[b]-1)%(mod-1));because of Fermat's little theorem.I learned that before but I forgot it in the contest:< U're so genius:D btw,I think I heard ur chinese name before. :)
I'm nothing close to genius. Your friend guagua0407 is much more genius than me.
Worst Contest.
very easy with problem F, but i wasted time for B, and D, E , F is more easy than D or E.
difficulty is subjective
GOD i was so close to getting D >:(
i solved exactly 1 problem just like i do in Div 2s, and the first problem was on par with the difficulty of those with Div2 A problems. i at least expected to solve 2-3 problems in this contest, i feel down. i know it happens but i think the level of this contest is a bit higher than it should be.
yes problem B is more hard with Div3 — B, bad problem
B = C >> F for me, solved in in 7 minutes but for the next hour couldn't solve and implement B and C correctly. Feels so bad ;(
yes me too,F took me 10 minutes but B is 30 mins
Need to work more on constructive and greedy problems, literally they are of the types either you get the idea early or you can be stuck for the entire contest getting no idea
yes, i think it is so easy to me when start, but some complex case torture me.
best words to describe xD, there is always some complex case there to torture us in these problems ☠️☠️
Problem statement of B is the ultimate example of "How not to write a problem statement".
Very irrritating problem statement, could have explained some good examples properly atleast :|
upvote it as much as you can, so that it reach to mike!
I solved C using this. Can it be optimized further? 217736885
sort the input first, and you can see the result. Example n = 5, the result is B[0], B[4], B[7], B[9], B[10]
Thanks!
Sorting and jumping with decreasing step may be better... my solution : 217640944
Thanks for the solution. Well explained too.
What does "Unexpected verdict" mean in hacking?
There is wa
guys when does results will come
After hacking and final testing
about this time tomorrow
Appreciate it :) I really enjoyed the round.
I wish I could notice earlier the fact that
the description of problem B was actually describing normal round operation, but still I had lessons learned.
B was an unclear statement take me a lot of time to understand!
Same here.
I rather chose to infer from examples
I too found it challenging. Like if we traverse from back then answer was a bit different. It would have been more easily solved only if there were more suitable examples.
Good contest. Enjoyed. But F, it was just like: "Hey! do you know quadratic equations?"
rename this contest to Div.2 ):
i think it was quite easy, especially if we check the solutions stat other div. 3 contest.
What the hell was B? very bad problem statement!
Agree
solved E, F but unable to solve D :v. Wasting time for thinking about graph and reverse graph :v
I was lucky enough to consider transpose the equation
au−av ≥ bu−bvintoau−bu ≥ av−bv.Then the problem turns into finding maximum values in the new array
c = a - bWhy does this code give WA in problem G? Can you help me please to find a mistake in the code? https://codeforces.com/contest/1857/submission/217742367
Problem B take me a lot of time to understand and solve :/
Solutions for problems A, B, C, D and E were on youtube during the contest again. Can't codeforces contact Youtuble to delay codeforces related videos when there is a contest? + Why do people even cheat? Why are they getting from cheating?
Some of the videos posted during the contest: https://www.youtube.com/watch?v=JZZoBIzIHIo&ab_channel=CodeSolve https://www.youtube.com/watch?v=JZZoBIzIHIo&ab_channel=CodeSolve https://www.youtube.com/watch?v=K3rzSAD4CfY&ab_channel=CodeSolve https://www.youtube.com/watch?v=_pDafLiCTBE&ab_channel=ConTestSolution https://www.youtube.com/watch?v=DBOQraJclYQ&ab_channel=ConTestSolution https://www.youtube.com/live/jAg0kZJ7j1E?feature=share
I had this same question nearly a year ago, there will always be cheaters, no matter how hard you try to ban them, also the solution to this problem by simply banning everyone would not work because you can create new account,the trick with youtube also would not work because there are even telegram channels where solutions are leaked for some amount of money (I already tried to come up with a solution with people cheating, but I have no ideas), the only way not to get affected by them is to overcome them,most of the cheaters have a rating less than 1300,soo outperform them)
I think that we just need to calm down. In any case, cheaters will never get more than 1300 rating.
FBI Why where is no such test in F that $$$x^2 - 4y$$$ is not a full square?
that's for hacks
Does that mean we should not add any tests? Let the paricipants add test themselves during hacks!
No, that is not. I suppose all test were random.
That is just poor testers' work
more than 1 mil test cases and no such as x^2 — 4 * y is not a full square? Odds say that it was intentional.
What is not how this works, you can make 2mln random tests and you won't find correct test.
Then tell me how it works
https://codeforces.com/problemset/problem/1743/D
Solve this and you find out why random tests are bad
Majority of tests on cf are random
No, they are not.
If they were random, 90% or more uncorrect solution would become accepted
What gives you that idea?
you know,if the tests were actually random, you could have passed this problem by just randomly outputting 0 and 1 ))),
I guess, that is that your F validator does, randomly validate tests
you know, the thing is that you don`t know how tests were generated and you will never know,so i think that it would be appropriate to stop trying to insult someone from the preparation team)
Many comments says that F had several problems with tests. So, it wasn't intentional, just bad work of testers, and probably by authors themselves, because test 7 was with zeroes in it, meanwhile it is prohibited by statement $$$(1 \le |x| \le 10^9)$$$.
I simply forgot to check if
And got accepted, now I hacked my solution ofc, but this is strange that this test wasn't added
I think the problem statement in C is kind of easy to be misunderstood.
It's quite sad that I couldn't solve C despite solving (preliminarily) D E F.
E same
MathforcesThat's right
I have a question: when the manual will be released? I'm interested in the solve of the D task
sir the manual will be released tomorrow, till then you can ask for hints for D
Transpose the equation
au−av ≥ bu−bvintoau−bu ≥ av−bv. Then the problem turns into finding maximum values in the new arrayc = a - b.How can we solve problem C? what's the intuition behind and are there any similar problems?
to push all them in the array
Math.
Sort array b, then the minimum element shows up
(n-1)times, next smaller value shows up(n-2)times, ... so on and the last value(largest one) can't be determined.So we can simply choose the maximum value for the last one, which is
10^9in this problem.wow, really cute explanation by cute person
Ah thanks, i just realized b was result of all possible pairs not subarrays, should have re read the statement. -_-
I really enjoyed the contest, and in my opinion B wasn't that bad like other comments say, but the implementation was tricky
B was really easy, C was tricky
For a div3 C I think it's pretty good, if you figure out that the smallest element in array a will be present n-1 times in array b, then the rest is very easy (other than the implementation)
The problem statement was kinda wacky and the implementation is way above D3B level.
Just brute force from the "tail" of the number to the head with increasing previous number by 1 and printing original num from the head till the first possible change + zeros
Can somebody look into my solution for C: https://codeforces.com/contest/1857/submission/217718886 I am not able to find the mistake. Thanks.
if you try to restore elements of a in sorted order.Then it will be easy.
thanks for the suggestion.
Guys please give some hints to D, I's stuck there
You already got your answer.
That's for C
Nope, that's D.
Man, it was for D :)
try modifying
a[u] - a[v] >= b[u] - b[v]in different ways :)None of the CF extensions are working. Not even CF Get Rating or CF Analytics. It shows codeforces API error. I just wanted to know my predicted delta. Anybody else with the same error?
same here, javascript rabbits ate all the carrots :(
Now as i realise my F's getting hacked it doesnt matter anymore (:
I dont know what this line mean after the TC "It is guaranteed that the sum of n over all tests does not exceed 10^3"
Most of the prb I notice but not able to understand what they say I need to sum n values of every TC, or the array sum of n not exceed 10^3 or what they mean
Each test has some number of test CASES. I believe you're referring to problem C here.
There are some (unknown) number of tests, but that doesn't matter since your code is run once for each test. The time limit is also per test.
For this problem, there can be up to 200 test cases per test. Each test case can have n up to 1000, but the sum of all test cases in one test cannot exceed 1000.
So if there is a test case with n = 1000, there is only one test case. Or there could be 10 test cases with n = 100 each. Or 2 test cases with n = 700 and n = 300.
Usually, the worst-case scenario test is one TEST CASE with the maximum n and this is the important takeaway.
I my opinion hardness of Problem G sharply increased.
Consider D...
Good contest overall problems was fun! However I noticed there is a bad test case on problem F. In the constraints, it stated that x and y had to have at least an absolute value of 1 or greater. However, test case 7 had queries where x = 0, causing my code to fail. :(((((((( I've noticed a lot of other people failed this case too, so ig i have the power to make this unrated :p
Submission: https://codeforces.com/contest/1857/submission/217663720
It is only a little mistake, doesn't do any harm and they fixed it.
I thought the integer in B was upto 2*(10^5) ; but it actually had upto this many number of digits. Tried manipulating the solution for input as long long to solution for input as strings ; but to no avail & messed this up. Should have given time to C,D instead.
In div3s and these time penalty rounds particular dont get discouraged by not being able to solve easy problems, read all of them one by one, and start to solve one which feels more solvable and interesting to you
fun.contest.id would work on this advice & come back stronger! Thanks!
I am sure,you will come back stronger ^_^. Always have that heads up attitude no matter what, Focus more on solving problems and finding interest in them, you will start to see results going your way :)
problem D hadn't pretest like:
is it good?
It's
2 <= nin problem D.yeah fixed, I mean it hadn't max test for a[i] — b[i]
Yes it should have.
I think it had a test, refer to this comment: https://codeforces.com/blog/entry/118765?#comment-1056254
Not exactly this, but something on those lines.
There was a test where array $$$a$$$ was $$$10^9$$$ and array $$$b$$$ was $$$-10^9$$$ (10 test case)
it was for hacks)) Poorly, i think that -1e9 is minimum value)
Problem statement of F mentions $$$1<=|x|$$$ but testcase 7 has $$$ x = 0$$$ and $$$ y = -9$$$ as one of the queries.
This should not fail in my opinion if $$$x \neq 0$$$ was ensured.
Edit: incorrect link
F's pretests were really weak i forgot to check the most important condition whether the (-b + sqrt(D)) is divisibly by 2 or not :O. A lot of hacks incoming
I don't think it's possible for
(x + sqrt(x^2 - 4y))to be odd.4yis always even. Ifxis odd,x^2must be odd. Thenodd - evenis odd. So sqrt must be odd. So,x + Dis even.Similarly you can argue for the case where x is even.
That's such a relief. Good analysis :)
Just wanted to get some clarification, for the problem D of today's contest. I got this weird error in the following submissions (using java):
When I submitted equivalent code using long, it worked (using java): - https://codeforces.com/contest/1857/submission/217686813
Using int, cpp code worked though: - https://codeforces.com/contest/1857/submission/217741962
Anyone has any idea what might have happened? I would really appreciate the help. Thanks in advance.
The issue is caused by your compare function for pair. min(A[i] — B[i]) can be -2e9 and subtracting from another -2e9 overflows.
That is some big brains dude!!
Thanks a lot, you might have same me hours here.
One more doubt, though, does codeforces raise exception, for integer overflow also?
For C++, the answer is yes in practise and no during contest.
Task C is complete constructive shit. I liked all the other tasks very much.
Lol, it is not even constructive
Well, for this it was constructive, because it is necessary to stupidly come up with an array.
The idea behind problem C was nice actually, not stupid.
In order to become a good competetive programmer, you need to be able to solve constructive problems ;)
Please hack my solution to F, i wanna sleep peacefully now (:
Can anyone suggest me some better approach in E? MY submission https://codeforces.com/contest/1857/submission/217726880
i think, the only optimization here can be not finding lower_bound(vb.begin(), vb.end(), va[i]), but using just i instead, because anyway you get 1 from segments like [a, a] and lower_bound adds logN to your complexity. The idea seems ok.
Edit. I'm sorry for not noticing that, but this way you should use vb for iterating through the indices, not va. So, you don't actually need va except for reading the input :)
ok will try that way also! thanks
well i got RE for 7 times in D 217669362 (exit with 11:java.lang.IllegalArgumentException: Comparison method violates its general contract!) and solved in this version 217692889 ...never got exception like this before,can anyone tell me why?
Why were all problems except G math-y?
look at this guy's submission Stark663
I think he is a cheater
no,but he may be banned because he violated the rules that you are agreeing to before registering to any CF contest)
Video Editorial For problems A to F.
https://youtu.be/6s1vEnzK7vI
nice,but I don`t think that it is allowed to post this before the hacking stage is over)
And why is that so? Everybody is sharing their solutions anyway. Also there's no rule iirc that prohibits that.
maybe you are right, thanks
Now EveryOne's solutions are public So I guess That should be Allowed.
Why am I getting MLE at test case 4 in F? MY submission https://codeforces.com/contest/1857/submission/217743843 How can I optimize it?
Even if it didn't MLE, it would have probably been hacked (TLE) because you used unordered_map, see this blog for more details
ok
Not necessarily related to MLE, but I wonder what's C++ sqrt()'s behavior on negative input because x * x — 4 * y could be negative.
I guess then it might show Runtime Error
made video explaining A&B&C&D:
https://youtu.be/elQ4jmUfYqM
thought would be usefull for community
Problems are good, but they could have written the statements much better way.(B,E) :(
It was contest with the most creative (also good) problems I have ever participated.
Although B may be difficult for many people, it can be in best problems for last contests. Also E and G were pretty good. But I think F was too mathematical, perhaps you could add another problem which more greedy or more algorithmic.
Thanks for the great contest, I love it :D
how this code got hacked https://codeforces.com/contest/1857/submission/217662800
Isn't it like $$$O(len^2)$$$ for 99999..99999?
TY for the contest <3
yea it was a good contest
Please check this blog , Problem F constrains has (1 $$$\le$$$ $$$|x|$$$ $$$\le$$$ 10^9).
Meanwhile in test 7 many test cases have x = 0.
I don't know what should happen in this case, but please do something about it.
I get it nvm
open upsolving please
If I hacked someone, but it was unsuccessful. Do I lose points?
No
Ok, thx.
I don't know why my solution is failing for F: https://codeforces.com/contest/1857/submission/217724931 Can somebody help me?
you need to check again if temp*(x-temp)!=y
thanks, it got AC
Thanks, I got AC by adding this. But I'm trouble in why is it necessary? I try to check
sqrt(x * x - 4 * y) * sqrt(x * x - 4 * y) != x * x - 4 * ybut got WA too. Thanks for your patience.According to Quadratic Formula,you need to assure that ai,aj are all Integers, so sqrt(x*x -4*y) should be an Integer too, or else you may get wrong answer,so having a check is nice
After multiple tests, I have figured out the reason for WA. It's due to the precision issue of the square root function. If you change it to long long or long double and use sqrtl, it will work.
WA in long long and sqrt 217887489
AC int long long and sqrtl 217887432 AC in int128 and sqrtl 217887348. (I have define int long long so it may look kind of stange.
It will Be amazing Div i think
yesterday, i can not access codeforces by browsers in my computer (my phone can access) until 40th minute of contest. Is there anyone like me?
I think question B of this contest is very similar to this one.
It is the same except for the data range.
Great contest as allthe questions can be understood very clearly.
I managed to solve up to E during the contest and F afterward. The problems were nice, they were from various topics and I enjoyed solving them.
Very good
What was the approach for E?
I got TLE here : https://codeforces.com/contest/1857/submission/217725866
Your code is O(n^2), read the editorial for O(n log n) solution
Math tag for problems ×
Math tag for contest ✓
I'm wondering if there will be a system testing after hack phrase? :o
It looks like system testing is in progress.
The round was made unrated?
G is beautiful
Had sys test finished?
It is writtent that tis contest is rated for everyone having rating less than 1900. But my rating haven't updated current rating :-806
Rating takes time to update
It usually takes several hours to 1 day to update rating. And the hack phrase has just ended, so we still need to wait patiently.
Thansk for answering !!
My F was hacked. Can someone tell what's the issue?
My Submission : 217815371
You didn't check if the square root is an integer or not , as ai and aj must be integers.
Wasn't this sufficient??
ll t = sqrtl(x * x — 4 * y); return (t * t) == (x * x — 4 * y);
i think you still need to check if the discriminant is negative or not
Why have you taken a $$$MOD$$$ here?
As i am a beginner learner,i solved one problem first time in a contest.when will the rating add to my account?
Usually in 12 hours since the hack phrase has just ended, I think.
l dont see problem C was less then 1e9!!! it talk me 7wa
When you encounter many wrong answers without obvious reason in your code, you should read the whole problem statement carefully again and think more on corner cases in your code. This is what I do in attempt to reduce number of continuous wrong answers.
yes thanks！！！
l just have not guts that i was ac
When is the rating update MikeMirzayanov
Can anyone help me find out why this submission for F is getting tle? 217653085
unordered_map
y cant we use unordered_map?
oh bro! Ok, now I think it's time to learn new lesson
WHY did code give TLE in system testing (PROBLEM -F)
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 200000; int p=1e9+7; void solve() { int n; cin>>n; unordered_map<int,int>mp; for(int i=0;i<n;i++) { int a; cin>>a; mp[a]++; } int q; cin>>q; while(q--) { int a,b; cin>>a>>b; int val=sqrtl(a*a-4*b); int count=0; if(val*val==a*a-4*b) { if((a+val)%2==0) { int num1=(a+val)/2; int num2=a-num1; if(num1==num2 ) { count+=(mp[num1]*(mp[num1]-1))/2; } else count+=mp[num1]*mp[num2]; } else if((a-val)%2==0) { int num1=(a-val)/2; int num2=a-num1; if(num1==num2) { count+=(mp[num1]*(mp[num1]-1))/2; } else count+=mp[num1]*mp[num2]; } } cout<<count<<" "; } cout<<endl; } signed main() { int t=1; cin>>t; while(t--){ solve(); } }Try using map instead of hashing. Searching in a hashmap is O(n) worst case.
Why F using unordered_map will TLE?
In the worst case scenario unordered map can perform 1 operation in O(n)
I'll never use unordered_map again...
Presumably, because of this
what is causing TLE in problem E?
use more efficient algorithm in your code
All the writers are from Ukraine! that's cool!
I see the system testing has stopped at 100% for a while xD.
Hmm, it's 20:00 in my timezone and I haven't eaten yet T.T
Rating changes???
Nah,hot yet
Why not?
You know,I could start telling you some bs answers, but i literally have no idea, the system testing is not over yet,maybe that is the problem
Why is the contest frozen for so long MikeMirzayanov FBI
I noticed some (about 10) submissions have been "running on test 1" for hours. Though I don't know why they are like this, it might be the reason why the contest is still "system testing: 100%".
This is very weird. My submission is among one of those.
I also noticed that all those submissions are of problem B submitted between 20:28 and 20:30.
It seems like it was finally fixed 20 seconds ago
Never expected such good performance by me in such div 3 contest
By the way can someone suggest some problem around the problem G to practice
Not Bad
I finally became a pupil!
Problem C is much much easier than problem B
Honestly it depends on implementation skills, B is pretty easy to figure out but the implementation is difficult, while in C you need a bit more thinking with easier implementations
Problem B was good, but the test cases weren't exhaustive during contest, it didn't help with the fact that codeforces was down so had to use m1 lite version which didn't show my submission time and solution was accepted, although i should have written efficient code in the first place, but this kind of gave false positive until solutions were hacked :(
hh, this kind of thing often occurs, but this pretest is still passable, at least most people's C, wa7 will realize the error later, 883's pretest is the weakest
Yeah, it has happened before, it just feels bad when i could have written o(n) code switching just 2 lines in my original code. If only I saw my code runtime...
this div 3 is so marvelous. This is the first time I have accepted 6/7 problems in div 3. The latest problem is so difficult (DSU), so I cannot accept full of contest. Anyway, it made me satisfaction ~~
As I pointed out in an earlier comment, there was some problem judging 10-12 submissions of problem B (which is why I guess the rating updates was delayed). It seems to have been resolved, but my submission 217644169 now got TLE on Test 8 which I think should work fine because I tested my solution locally and on online compilers and it runs in 200ms for that particular test case (as opposed to 2000ms shown on the verdict page).
Could somebody help me out here?
If the input is 444……(199999 times '4') and the final digit is '5', the complexity of the loop that modifying digits to '0' will be O(n^2). I test it on my computer and it costs more than 10 seconds, so it turns TLE.
Oh, I didn't think of that, but I get it now. Thanks!
Statement of the problem B is disgusting
Nice!!!Through this round of Div3, I became Pupil for the first time!
217918655 Can someone please explain me why am I getting TLE for problem B in my code.
Each string concatenation works in $$$\mathcal{O}(n)$$$, where $$$n$$$ is the length of the resulting string. Therefore, your code works in $$$\mathcal{O}(n^2)$$$ which is too slow for $$$n \leq 2 \cdot 10^5$$$.
Woah gotcha dude, I thought substr() function works in log(n) time. Thankx :)
I never understand the pointing system... I mean although i just solved one question how could i lose points for that??
One of the main reason your rating is decreasing after cobtwst is that you underperformed (your performance is below your rating).
I got a TLE because of umap on F QwQ
I was so close to AK :(
Fun round for sure! Really enjoyed D, E and F, even though had to re-solve them after the round. Good tasks for a begginer, since they did indeed give me some new approaches!
Writing foggy statements and make them difficult to understand does not show any intelligence. Does it? I think the motive should be cleared at first. The main challenge should be make the problem challenging to the audience , not to make them struggle to read some foggy statements
good contest
hey i got a warning mail from codeforces that Your solution 217732009 for the problem 1857C significantly coincides with someone else...." i used ideone compiler so i dont know if due to that this happed.this happened to me in the last contest too please look into it.
For question B, why does the test case input for 60947 have a solution of 100000?