Hello Codeforces!
mesanu, flamestorm and I are very excited to invite you to Codeforces Round 886 (Div. 4)! It starts on Jul/21/2023 17:35 (Moscow time).
The format of the event will be identical to Div. 3 rounds:
- 5-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 (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).
We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.
Only trusted participants of the fourth 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 fourth 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 1400 or higher in the rating.
Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.
Many thanks to all testers: MikeMirzayanov, erekle, Bakry, Dominater069, Gheal, andrei_boaca, zwezdinv, sam571128, Sho, Wibo, Phantom_Performer, moonpie24, mafailure, Kalashnikov, SashaT9, Qualified, haochenkang, ZiadEl-Gafy, MADE_IN_HEAVEN, AdOjis485, qwexd, mkisic, Killever, sabbir-hasan-anik, peshkoff, donghoony!
And thanks to Vladosiya for translating the statements!
We suggest reading all of the problems and hope you will find them interesting!
Good Luck to everyone!
UPD: Editorial is out!
hope to have a problem like this :*(.
Yes Sir. Been There will try for top 50 this time.
Same Bro!
Congratulations on becoming a SDE.
Thank you Sir.
i am so excited it is my first *out of competition contest :)
I Think i have seen this before.
Always Copied. Can't you people be creative with your memes.
Finally, first unrated contest:)
Typical newbie comment btw xD
As a Newbie participant, I hope not to be Newbie again after this contest
As a participant, I hope to be Specialist after this contest
+1
As a tester, I would say this is a great Div. 4 Round.
Thank you and your team!
Best, Jelal
As a tester, there will be a lot of wisdom bestowed upon you.
As a Newbie participant, I hope to be Pupil after this contest
Good luck:D
*** ** hbphuc lam quyen
My first unrated round! :)
As a gray participiant, I hope to be a LGM after this contest)
Just reply
GL & HF
Right, I feel like this has a good chance of coming true.
By the way, what is the difficulty of this game
Division 4 is the easiest division. It's aimed at people with a rating below 1400.
I only solved 3 of them what that means?, btw this is the first time I join a contest.
Excited! I hope i will do well in this round.
As a tester, please stop posting cringe unfunny memes
Also the problems are pretty good
official participant with highest rating
I am official participant with Second Highest rating.
Looking forward to my first out of competition round!
Will it not be better if you use specialist instead of pupil.
no the newbie is refering that pupil is the highest rated color for Div.4
Dattebayo
First unrated contest
As a participant , I will test my speed through this contest
This is my first round as a TESTER. Wish you all the best & hope you will enjoy this round.
I wanna be tester too! Vai!
Inshaallah, you will be someday soon
As a participant, I hope to be Specialist after this contest
Me too!!!
I would choose oppenheimer.
Hoping to reach specialist after this contest!
Well, it's practically not possible. But I get what you want to convey. Same here. Skill issue
After so many fuck ups DIV-4 is the only hope for me.
Thanks for creating these! Fridays are a bit complicated for me in schedule but it's still fun to participate and continue to learn. Look forward to this contest!
Excited to become Newbie for the first time !
Contests for all div 1,2,3,4 in the next 5 days...balanced, as all things should be
As a tester, it tasted like mother's cooking.
why only 120 minutes why note 135 minutes
Good luck to everyone
Hello everybody!
I wish you all good luck! I would like to become a student (
green
). I hope that the competition will be interesting.Best, Jelal
Hoping to solve all problems!
hopefully i reach spec again after this
Hope it be my last rated div 4 contest
Alright, iron contest!!!
wait so Div. 4 is easier than Div. 3 (or Div. 2 (or Div. 1))? I thought the reverse, but seeing that this competition is rated for participants with rating $$$<1400$$$, and the previous one (with Vika) is for rating $$$<2000$$$ or something, I now think this round is gonna be easier..?
Yes, that is correct. Div. 4 is easier than Div. 3 which is easier than Div. 2 which is easier than Div. 1.
It's been 3 minutes without Div4, I can't stop shaking and I'm having serious mental breakdowns. I woke up today trying to log into Div4 but the site was down, I had a big panic attack but I managed to calm down after a few hours. I couldn't go to school today, I'm so worried that I even took my father's gun from the shed, thinking about killing myself. I am nothing without Div4, it's my life, it's my destiny, without Div4 I wouldn't be able to do anything. Div4 is the best thing ever made and I can't shake the addiction, it's the best oj out there. I can't stop shaking and crying, I'm so worried. I spent all my time on Div4, got rating and contribution.
If Div4 has a million fans, then I am one of them. If Div4 has ten fans, then I am one of them. If Div4 has only one fan then that is me. If Div4 has no fans, then that means I am no longer on earth. If the world is against Div4, then I am against the world.
I hope i become a specilast again
Bruh, my browser is always being checked. What's wrong?
div5
Problem set is good. The statements are short and easy to understand. A good div4 round...
My first *out of competition :)
My first rated competition.
i spent like 35 minutes on problem H, just to realize that i misread the question. literacy issue ngl. very good problemset btw :D
I did the same on problem E, thinking c was just the sum of the borders and not the cardboard "behind" the image.
the first contest that I aked !!!
what was the upper bound for binary search of problem E?
l = 0, r = 1e18.
No, the bound is around 1e9.
given w>=1 how can l be 0
it is actually doesn't matter, answer won't be 0 anyway
Why the upperbound cannot be 1e18 ?
let's say n = 1 then c = (2 * w + a[0]) * (2 * w + a[0])
since c up to 1e18, w can't be greater than ~5e8
for example if we will take w = 6e8, it will be
(2 * 6e8 + a[0]) * (2 * 6e8 + a[0]) = (1.2e9 + a[0]) * (1.2e9 + a[0]) > 1e18
I too couldn't figure it out at first. Then I started upper bound from 1 and kept on doubling it till it was less than my required value. After that used binary search
Div 4.5
I really enjoyed this round. Hope not getting hacked :/
What's wrong here. I am pretty sure it's a graph problem(Last problem.)
You're treating it as an directed graph.It is an undirected graph,add both the edges.
Thank you Sir for the testcase!!.
can anyone help me out in the "F" problem , i got stuck in the 6th testcase, like shouldn't the answer be 6 when the trap is placed at position "24" Help me out!
this is my approach
You can only place traps at positions up to $$$n$$$.
otherwise lcm was ans.
big bren time
you can't place a trap in $$$position > n$$$
Yo can someone pls help me out I dont get whats wrong with this code on problem 5. https://mirror.codeforces.com/contest/1850/submission/214926782
I tried to find the multiple that appeared the most, since that would catch the most frogs.
Explanation: You can place a trap at position $$$6$$$ to catch all frogs.
Hey, I am new to Code forces, can you explain these 2 points in little bit more detail please?
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
After the contest, the participants have 12 hours to "hack" any target solution, this means they can submit a test case where they think the target solution will fail (of course still within the problem bounds). If successful the hack is added to a pool of tests that will later be applied to all solutions (all successful hacks are applied to all solutions), so in the end you have accepted solutions that have passed every valid test.
Edit:Div3, Div4 don't give points for hacking.
Successful hack gives +100 points, unsuccessful hack gives -50 points.
In Div. 3 and Div. 4 rounds hacks don't give any additional points.
Is it so dumb to take too much time for the E (divide first would be the more suitable name for the problem)?
No it's not dumb. Dumb is that i was using quadratic formula to solve for 'w' and in the end couldn't submit because for some reason it wasn't working for very large inputs
I used the same approach. You took int for some variables. change that —
long double x=4*n , y=0, z=0;
And typecast your output-
cout << (long long) ans << endl;
I couldn't solve E what's wrong here?
void solve(){ ll n; long long c; cin >> n >> c; vector arr(n, 0); ff(i, 0, n) cin >> arr[i];
}
I think it fails because of sqrtl, I had the same issue as well, find the square root by binary search. Also, if you are solving it by the quadratic formula, shouldn't it be $$$w=\frac{-4\cdot sum+\sqrt{16\cdot sum^{2} - 16\cdot n\cdot \left ( ss - c \right )}}{8\cdot n}$$$ ?
this is what i did lmao and i really struggled with big numbers, ended up using double
It will overflow long long.
Suppose n=1e5, c=1e18 and all inputs are 1. then n*(ss-c) will be approx. 1e5 *(1e18-1e5) almost equal to 1e24.
We want div-4 contest more often as beginer
best div 4 contest ever
Wow. That was nice contest. Overall, good problemset.
Good Problem Set. It seems that the difficulty difference between Div3 and Div4 is much higher than Div3 and Div2.
Thanx Man i Really enjoy this Round
good round, was too scared to implement dfs for H and ended up staring at it for 1 hour :(
Bruh dfs is like 6-7 strings
What was the solution for G? My solution was to project all the points onto {1,0}{1,1}... all the directions. Group them into bins based on if they landed at the same point (after correcting for length of points), and then adding n choose 2 from each of those bins to ans. However, I got some error that I couldn't figure out if was due floating point inaccuracies or because my solution was wrong / nonsense.
x , y , x-y , x + y If one is the same, it's a pair
You don't need floats here
Find points count on each existing line
Then iterate over all of them and add C(n, 2) to the result (where n is count of points on current line)
Why do you add $$$\binom{n}{2}$$$?
Because he had studied combinatorics in school. (It's just a joke..)
Because it's a count of all different pairs on that line.
Also forgot to mention that you need to multiply the result by 2 (to count reverse too)
Hi Coders, I have done the problem E, with a linear approach, which was very slow and then i thought about binary search but some test cases passed and some not. Please can someone advice on what is wrong with this code below ?
there might be overflow in your mathematical expressions
there is an overflow
Yes, it is definitely an overflow issue. It passed with
long double
instead oflong long
.yeah it passed because of long double has 80 bits.
but better to use __int128 instead, because there can be some unexpected values while dealing with doubles
another way u could write something like
use __int128 instead
use the Quadratic equation :> ps: don't use long long but double instead TvT
I don't think using double is a good idea
why double accepted, but long long overflow, in statements said w is integer, i tried long long cause thought roots = (-b-+sqrt(D))/2*a too should be integer but its rounded.
I don't think double will get AC, he probably mean long double
it AC because long double has 80 bits, meanwhile long long has 64 bits
upd: I was wrong, double got AC, may be double can hold more than long long, but sometimes it cost accuracy.I believe in this problem better to use __int128
also (x1+2w)^2 + ... + (xn+2w)^2 = c
c = x1^2 + 4x1w+(4w)^2 ...
c-=(x1^2 + x2^2 + ... )
new_c = 4x1w+4x2w+..+4w^2+...(n times)
c = 4w(x1+x2+...+wn)
godamn i got it now i did c/=4
then nw^2 + w(x1+x2+x3...) — c = 0
and its exceeded in long long but accepted double
but i can make c/=(n*4) cause 4x1+4x2+4x3... (n times) and (4w^2+..) n times
and it's accepted long long
https://mirror.codeforces.com/contest/1850/submission/214943996
upd: seems like (w(x1+x2+x3...+xn))%n doesnt have to be 0 but it's accepted
Can someone explain why it's have to be 0
this should be accepted cause gcd should return at least n
https://mirror.codeforces.com/contest/1850/submission/214927321
Amazing contest!. Problems were clear and easy to understand. Difficulty was a bit easier than normal Div4, but great problems nonetheless. Thanks a lot SlavicG mesanu flamestorm and all testers.
Worst experience , either you make your platform better or just don't rate the contest, total time waste
use m1.codeforces.com if something go wrong during contest
Is Carrot working for anyone?
I've never seen a predictor working for a contest with a hacking phase
can someone explain the problem E like how the answer of 1st test case is 1
thanks....
Problem E is to find $$$w$$$ such $$$\sum (s_i + 2w)^2 = c$$$
editorial?
https://mirror.codeforces.com/blog/entry/118466
why this is an invalid input for F?: https://mirror.codeforces.com/contest/1850/hacks/931609/test I think because the output is bigger than 256 kb, but what to do if I want to test the limits?
one cannot see others hacking test cases, and if you are talking about the test case you wanted to try is large then you can write a code to generate that test case and submit that code.
My G got hacked (TL). Is it because of Python defaultdict? https://mirror.codeforces.com/contest/1850/submission/214881069
def solve():
Yes.
Do you an idea how to fix this? I tried use dict, but it also very slow
Refer to this article.
https://mirror.codeforces.com/contest/1850/submission/214941507 Can anybody explain why am I getting TLE for problem F, isn't harmonic series nlogn?
Your approach is not harmonic. The countertest is n = 2*1e5 and all array elements are 1.
What should I ideally do?
keep frequency map. and increase it by count of each number in array. rather than doing it for every element individually.
Seems the only codeforces contest with highest participation and with highest problem a solver
Sadly, many people see problem A, if it's difficult, they don't submit ,and hence don't participate. In this contest, A was too easy, thus almost everyone submitted, and participation flooded.
Can someone hack my G or H?
G, I don't think so. Many Gs were hacked which used unordered_map. Since you used regular map, it won't be hacked, acc to me.
no I didn't use regular map , I used unordered_map
scroll up and you will find :
but I think it still won't be hacked because I have hash struct passed
"#define map unordered_map" ohh didn't see this. "but I think it still won't be hacked because I have hash struct passed", then it would be safe ig. GG
Can you tell me why map works but unordered map doesn't?
Unordered map takes O(n) avg time complexity to insert n items. But for certain inputs, it can take O(n^2). Thus, solutions using Unordered_map can be hacked by putting in those specific inputs.
Refer to this blog bro, for more details- https://mirror.codeforces.com/blog/entry/62393
My first AK contest on Codeforces!
I used binary search for problem-E but it has some error which I am unable to figure out. Can anyone please help me find error in my binary search logic for my submission 214950555. ? edit : when i set
r = 1e10
the sample test-cases passed but on submission it fails again on some test case.You need to handle overflow for both multiplication and summation. Better to calculate the sum like this: sum+=(a[i]+2*w)^2 and check if sum > c.
Thanks for the reply.
But it should not overflow as I have taken unsigned long long. also on codeforces custom invocation it did not show any overflow errors. also the code works when i set
r = 1e10
.4*n*m*m would definitely overflow. It’s roughly around 10^23. Put some debug print and check how your binary search behaves for larger n.
Me trying to solve problem E be like:![photo-2023-07-21-19-46-30](/predownloaded/42/74/4274962d5140e3f738baece7708a146c4e684987.jpg)
gimme smileys
Can anyone tell me where did i wrong in this code
I think this code gets RE because the maximum recursion depth has been exceeded in some testcases. Python's maximum recursion depth is 1000, and you can extend the number using
however, I got memory limit exceeded this time... https://mirror.codeforces.com/contest/1850/submission/214955478
if I haven't solved 5 problems in 5 contests am I unrated for this contest ?
If you have $$$< 1400$$$ rating, you are always rated in Div. 4.
If you want to appear on the official leaderboard (i.e. standings, when "show unofficial" is off), you need to do what you stated. This does not affect if the contest is rated or not.
Can someone please tell me why am I getting wrong answers for large test-cases Solution
Fixed Solution
Use double instead of long long.
Can someone explain how this $$$\mathcal{O}(n)$$$ solution gets TL? I mean, the constant must be big because of using unordered_maps but still... Is it the case?
https://mirror.codeforces.com/contest/1850/submission/214910960
It's not about the constant, single unordered_map operation takes $$$\mathcal{O}(n)$$$ in worst case. See this
Didn't know this lol... Thanks for the source!
Why my rating didn't change after this contest?
mesanu flamestorm
It'll take time, it'll reflect in about 5-6 hours from now
Okay, Thank you!
Hope to reach pupil after this contest
Download some rating prediction extensions. You'll know your rating change during and after contest, before the official release.
Became pupil according to rating predictor
GG
I saw in some people's code of 5th problem, they have used __int128, i am seeing it first time, i want to know how this works!
__int128
is a type with 128 bits, ranging from $$$[-2^{127}, 2^{127}-1]$$$;while
int
is a type with 32 bits, ranging from $$$[-2^{31}, 2^{31}-1]$$$.You need use a special way to read and write
__int128
which you can see in their code.In most cases, You can use it like
int
orlong long
. But in some STL function, it can't work.I found there is a article that may help you.
For problem F, can anyone explain why my solution gives a TLE on test 9 when it has the same time complexity as the editorial O(log(n)) and almost the same code.
This issue with this kind of a naive approach was explained here before, in the worst case if all frogs have a hop length of at most $$$1$$$ the time complexity of this code isn't harmonic series $$$O(nlogn)$$$, but rather $$$O(n^2)$$$, because you are going to iterate $$$n$$$ times over all elements of an array of length $$$n$$$.
can you explain why in the second loop we increment the counter by the value of i , I still don't understand how that works
If by the second loop you mean this nested loop:
this basically simulates leaps of a frog, all frogs start at an integer point 0 on a coordinate line, after the first jump frog i will be at a position a[i], then after a second jump at a position 2 * a[i] and so on.
where did j=a[i] and j+=a[i] , in the second loop come from
We start at a position of a frog i after its first jump (j = a[i]) and then the frog keeps hopping with its hop length a[i], increasing its position after each jump (j+=a[i]), as mentioned before.
Sorry,may I ask a stupid problem? Why is it different between the rank I see in "common standing"and "friend standing". I am sure that its both "only show official". Thx
In common standings, all the participant's world rank will be visible. Whereas, in friends standings, you can see your rank in your friend list, and ranks of your other friends in your friend list, and their world rank in bracket().
This was my first contest ever. I solved three of them but didn't get any rating. Can someone please explain?
Well, nobody got the rating changes now, but we're waiting for them to be updated. So, you need to wait(i don't know how much)till you get your rating.
In this contest can my E be WA, G be TL?
My submission in E in contest: 214829184. I don't know how it's passed pretests. In code wrongly I did: x = s[i] + 2 * md + 1 and printed l but x should be s[i] + 2 * md and printed l — 1. Like this code: 214997775 which I submitted after contest. Please let me know if it's hackable.
My submission in G in contest: 214869824. Can it be TL or ML? It passed pretests with 1668 ms 76900 KB(Time limit is 2s). After contest I optimized it (removed set) and passed pretests with 904 ms 39300 KB(214997753). Please let me know it's hackable.
Why this contest showing unrated?
It will show rated, but we have to wait until we get the new ratings.
me waiting for system test and rating changes
for problem E, to use quadratic equation, it's not necessary to use int128. It's ok to use long double to store, and convert it back to long long at last. Submission. Note that I defined ll as long double
Can somebody please explain why this contest wasn't ranked for me?
you need to wait, usually 2-3 days after contest for the rating changes
study time
dayum, i got hacked on F and G because i using unordered_map, lesson learned haha
use hash when using unordered_map
It's all fun and games unless you are <1400
Does anyone have an idea why would my submission get WA2 on C even though it previously got AC in the contest 214793463 ?
I don't have any undefined behavior nor do I see any other error.
Thanks.
UPD: I found the bug, turned out I had an j instead of an i somewhere but it's weird it somehow passed the pretests during the contest.
(sighed) i got T again on an easy greedy preblem due to using the Arrays.sort()214808599...Sometimes i really cant tell the difference between using Arrays.sort() or Collections.sort()215048831 ,let alone passing the pretest -_-|
Sometimes problems are good in their own sense but often we make it more beautiful the way we approach problems. This is for G, I was thinking about the rotation of the axis by 45 degrees and then come to the conclusion that the coordinates after rotation of (x, y) are ((x + y)/sqrt(2), (-x + y)/sqrt(2)). So, I just have to store x+y and -x+y values in a map. We can also think of it as a straight line which is a more direct way but I felt this good (:
why I use "map<int,int>"could pass G, but use "unordered_map<int, int>" couldn't pass it ?
I hacked too and I found this blog https://mirror.codeforces.com/blog/entry/62393
Can anyone explaine how Wrapper function works? This is my hacked submission: https://mirror.codeforces.com/contest/1850/submission/214906792. And then i fixed it by Wrapper function which make my submisson accept https://mirror.codeforces.com/contest/1850/submission/214984466 *sorry for bad english
it allows for you to define a custom hashing function, which makes it less likely to be hacked by anti hashing tests
thanks to this contest i got to specialist :D
Regarding Maths solution for E problem
Why I get compilation error for this solution: https://mirror.codeforces.com/contest/1850/submission/215091151
but this other solution works: https://mirror.codeforces.com/contest/1850/submission/214911845
im going crazy, literally same thing
Pleasse help someone
you are trying to take input into sides, while your array name is side
Although I participated in my first-ever contest and I did solve 3 questions in quick time, why is there no change in my rating?
Could anyone please let me know about this??
You just upsolved three problems. Upsolved meaning, you have solved those three problems after the contest has ended. if u had solved those three problems during the allocated contest period, then you definitely would have got some positive delta.
You need to register on codeforces.com/contests.
For E, "You can also use the quadratic formula, but be careful about implementation of square root and precision issues."" so how can I be careful about the square root and precision??
use long double (if you are using C++)
Hello can anyone tell me problem F topic (I know it will be number theory but witch concept in number theory should I learn to solve it)
1/1 + 1/2 + ... + 1/n = O(ln n). That's why standart colution is O(n log n) but NOT O(n^2)
Hey I am a newbie, why this contest as unrated for me? According to this statement "take part in at least five rated rounds (and solve at least one problem in each of them)" they marked as unrated for me
The ratings are rolled back. The system is filtering out the cheaters. It will give the ratings back after checking in a few hours.
Nice contest.
In G I get TLE when using unordered_map but Accepted when changing it to map. I thought the access time was faster when using unordered_map, then how come the program is slower with unordered_map?
https://mirror.codeforces.com/contest/1850/submission/239099614