Hello, Codeforces! We're glad to invite you to take part in Codeforces Round 953 (Div. 2), which will start on 16.06.2024 12:05 (Московское время). Note the unusual start time of the round. You will be given 6 problems and 2 hours to solve them.
This round will be rated for participants whose rating is below 2100. Participants with higher rating can participate unofficially.
The problems were authored and prepared by Artyom123, IzhtskiyTimofey, bashkort, TheEvilBird, 127.0.0.1, Tikhon228 and me.
The round is based on All-Russian olympiad in the name of Keldysh.
We would like to thank
- Artyom123 for his high-speed coordination;
- A_G, culver0412, AlexRex0, harsh__h, CSQ31, PMiguelez, dazlersan1, htetgm, oaoaoa_mmm, FynjyBath, Mikhango, Ormlis for testing;
- MikeMirzayanov for creating Codeforces and Polygon.
Score distribution: $$$500 - 750 - 1250 - 1500 - 2000 - 2500$$$
UPD: Editorial
interesting score distribution
culver0412 orz
UPD:Sorry for misunderstood.
did you even read the announcement?
The contest time is unusual. But, I hope, the 'Dashboard' will be usual insha-Allah.
As a tester, I tested the round yesterday
As a participant, I will test the round today.
Thank you, and I wish everyone success!
Please notice the unusual time!
Comeback Round
aged well TT
i also had a terrible contest bro
Expert in next Contest
As a tester, do try all the problems.
Score Distribution is really good. Excited for tomorrow.
Hopefully I solve a,b and c .
nice dp
If FynjyBath = tester, round = good
❤️
Hoping to reach pupil ;)
You are now a Specialist bro
scoring distribution is asking me to solve abcd. I hope I can full fill its question
Clashing with Shanghai CPC, skipping this one
If I solve a,b,c in first hour I give my team eidia else Mohamed Hassan daeeeeef
Eid Mubarak bro.
good luck, hoping for +delta
alr nvmd not doing this comp. I dont wake up till 8:00 AM EST.
Hopping for +delta
OMG Mikhango!!!!
Potential SpeedForces on the way!
sounds like CodeForces Round 879 Div. 2
https://codeforces.me/contest/1834
bashkort orz . Just wanted to tell you that your pfp is my favourite pfp I have seen on codeforces. It looks cool af.
Thank you! That's ooes, my favourite singer :)
Woowww score distribution so interesting
my rating is below 1000. should i participate in this?
absoluty yeah
I am on the verge of becoming a specialist. Lets hope for the best !!!!
Let's do it..
Good start time for Chinese.And I hope I can become Expert in this contest!!!
excited for this ,lets goooooo
The round is based on All-Russian olympiad in the name of Keldysh.
Pre-Eid Day Contest , Participating
Eid mubarak!
GLHF, hope I become expert today
Getting good vibes for this round
Meow.
Lol, we thought too hard, the problems were pretty good and balanced in my opinion
WOW, this time the problems are more interesting but easier (I think) than normal div.2. This is my first time to AK in div.2 haha.
That's because it's based on Junior Russian Olympiad in Informatics, which is for lower grade students. So the problems shouldn't require any special knowledge. GG! :)
good logic used today
C would be enjoyable if we didn't have to print the permutation.
Got an edge case where my permutation wasn't working..
C would be A if we didn't have to print the permutation
your solution to C is awesome !! I can't believe I overcomplicated it so much. Thank you.
Then C would have been a piece of cake :D Btw, I figured the logic easily but spent about 2 hours to print the correct permutation. Still I am happy since this is the first time I solved 2 div 2 questions in under 30 mins.
mathforces strikes again
darn I was an hour late! still fun contest tho
It was super gang bang
bro A ques soln?
A and B yeah
div 2.5?
Why did you not let the much harder segment tree solution pass in E? I mean TLE
submitted D with just 2 min left
Can someone explain why my code for D fails?
D felt little easier than C.
Huh? Really?
I only came up with an idea for D at like the 115th minute, and I had solutions for all the remaining (and prepassed them all, except E) o.O
The idea of D is not that hard to come with, only separate when u analyze a candidate with maximum number of votants and the other case is very easy since u have to remove all candidates with index smaller always (and chose or not to remove a candidate with maximum number of votants).
I'm still in the blank honestly. Can you clarify further? (I don't even believe the idea I was about to submit for D would be correct either)
i mean, if the candidate that u r analyzing don,t have the maximum number of votants at the beggining, u have to remove all previous candidates, and if after that u don't have the maximum in that candidate u have to remove one of the candidates that in the beggining had the maximum number of votants so in the first case u print (index-1) and in the other (index).
The other case is that u r analyzing a candidate that have the maximum number of votants since the beggining, in that case if the index of that candidate is the smaller between all the others that have the maximum number of votants u print 0, either case u print (index-1) cause u have to remove all previous candidates.
Ah, got it eventually. Thank you. Now I feel doubly silly...
So I went with the idea of prefix sum and maxElement on the right of index i.
1) If the number fans of ith candidates are alone enough to win him the election then 0 candidates have to be removed.
2) If the number of fans of ith candidate are not able to win him the elections then we need to take help of the undecided voters and they will always vote the lowest index candidate that means all the candidates with index < i must be removed. If the sum of fans of index < i + a[i] + undecided voters given is >= max element on the right of the index i then the answer would be i-1. Else we also have to remove the candidate with the maximum fans on the right side of i along with all the the candidate on the left that means (i-1) + 1.
prefix sum and max element on the right side of ith index can be computed before the start of iteration.
3) one edge case that needs to be considered is if a[0] + undecided is already >= the max of the whole array then we have no choice but to remove the prefix of the ith index in every iteration
Link : https://codeforces.me/contest/1978/submission/266038667
sorry for the bad English. Also can someone please tell me how to add code / message in spoiler dropdown ?
I think that's not very clear, D is easier to implement but requires more clear-cut idea than C, C feels closer to implementation problem (and a bit harder to implement).
&& i give 1 hour+ on C... After the contest , i realized i should try D
Agreed I felt the same... I came up with the solution much faster than C. But still got WA in D due to silly mistake :(
5 seconds away from submitting D... I was too drowned on E+F and that wasted my time... :(
UPD: That D actually AC'd. I have myself to blame, I guess.
For E, I resolved the problem into the following Given a list of segments, for each query l, r find number of segments that fall into [l,r]. I'm not sure how to build a segtree for this (the merging part). Any hints?
Your reduction is correct. You can solve the queries offline with a simple point-add range-query segment tree.
Precalculate A array. Notice for each query only numbers on edges(a[l], a[l + 1], a[r — 1], a[r]) change. Calculate them manually.
As r-l+1<=5, you can actually use 5(in fact 4) partial sum arrays to solve the problem.
Imho E was quite easy, easier than D and probably even C, I am surprised there are not that many AC.
how you solved e?
I didn't solve it (my code got buggy), but it seems like E is a standard sqrt-decomposition problem.
You probably over complicated it, u can see my code:)
Just shuffled my mind again, silly me I guess. Thank you...
E is a prefix sum problem.
you can answer l+2----r-2 by precalculation. by doing some calculation, you can merge the answer.
Suppose we have a whole string. Then the algorithm is first:
and then
Save the new
s
andt
intos_aug
andt_aug
This is quite obvious, we always improve answer. You can check that after running those 2 steps neither of steps repeated would change anything.
We can precalculate prefix sums on final t and use it to get number of ones in the segment.
Now, actually we have substrings. The key is to notice that only 2 first and 2 last elements could be different from what we calculated initially, so we need to handle those elements manually, it would be O(4).
Answer would be
result for manual cases
+sum_inclusive(t_aug, l+2, r-2)
Cases with len of segment < 4 are easier to hardcode separately.
P.S I made stupid off-by-one error initially so had to write stress test, it wasn't complicated but still wasted a bunch of time :(
The main part of code:
I think E is easier than C.
D and E are both easier than C.
I think E is the easiest problem in CDE and D is the hardest
I overcomplicated D for myself (I see segtrees everywhere these days), but actually it's not as bad as it may seem, you can solve it with just a multiset alone.
That being said I myself got lost figuring out what do I want to do with segtrees.
D is prefix sum: https://codeforces.me/contest/1978/submission/266037233
Indeed. I think the hardest part in C is how to prove the correctness of the solution.
What did you find hard to prove in C ?
I quickly came up with a guess that I just need to use the elements from two ends of the array. However, I couldn’t prove that it’s the optimal way and after 30 minutes of thinking I submitted the code and found it accepted.
why it's not working 266036235 problem D
I know this will TL anyway but, quite shock that even brute force solution got WA on pretest 2 am I understand something wrong completely?
does someone know why I got idleness limit exceeded on C. I'm so sad right now :(
https://codeforces.me/contest/1978/submission/266042353
Notice that 0 <= k <= 10^12, but you use "int". So k may fail to read. Then in the next test, n may fail to read. At that time, you creat a vector with size n(n may be a large interger). So you will get "MLE". (Forgive my poor English
but I have
#define int long long
"mx += abs(2 * i — n + 1);" should be "abs(i — (n — i + 1)) = abs(2 * i — n — 1);" Because of this mistake, "while" will not stop But I don't know why it get "MLE". Perhaps "swap" does lots of copy.
its not mle. its idleness limit exceeded
Your loop is wrong:
This does not sum to $$$(n*n)/2$$$. Example testcase:
2 4
. Expected outputNo
, the output on my machine isSegmentation fault (core dumped)
.How to solve F?
Extend the original array into $$$a_2, a_3, \dots, a_{n-1}, a_n, a_1, \dots, a_n$$$, then use DSU to connect the elements of that new 1D array.
Corner case: if $$$a_i = 1$$$, all appearances of it in the matrix must be counted separately.
Whats in test 2 of F? Any counterexamples? (My solution is kind of scanline on dividers).
got the edgecase with a_i = 1?
Wait, when we have 1s on diagonal, we can't collapse them into one component... Okay, guess my code only works when a_i=1 is the last element... Thanks for the hint!
Thanks for a great round! I hope my C won't FST... I don't understand what is wrong with my solution for F, btw, like no idea. So sad couldn't find mistake during the round.
Okay, i was never connecting $$$a_i = 1$$$, sad. My solution still will get TL, but, if i saw that during the round, i would probably come up with better complexity.
long long
forcesI guess many people, including me, got confused that the word "number" was used instead of index.
Exactly, how difficult was it to use "index".
Just Found out that B can be done without Binary search.. Maybe I think too much LOL. 265999363
I did it with Arithmetic series
I used ternary search, I thought that it's the most straightforward way to do it lol
Lol now I see poeple have done it in O(1), feel ashamed hahaha
how to proof C that we have to take the two pointer and if 2*diff<=k then we reduce it else either p1++ or p2--. Anyone?
First, if you swap all pos(1,n, 2,n-1 , 3,n-2.....), the ans is max ans you can get. Then ,when you p2--, the new ans -= 2, since answer exist only when k % 2 == 0,so it can reach all legal k .
Thanks, got it! I started thinking in terms of set bits in k therefore got confused although D was easy than C.
Can you explain how to prove that we get max with that configuration?
Such a fool contest! For prob. A to prob E, there's nothing harder than suffix sum! How can this Contest be Div.2 ???????
why does the idea of swapping $$$i th$$$ and $$$i+k/2$$$ th elements not work for task C?
if k > 2*n ,you wasted.
can you please elaborate?
I had a post check after swapping elements that answer is possible iff after all swappings, $$$k>0$$$
My bad, I gave up in the contest, but, it was a ridiculous mistake.
Here is the AC submission, it uses the same idea as above: 266053962.
The only difference is that $$$cnt$$$ starts from $$$1$$$
would have been great for me if i had not wasted time in B
oops!
It was not possible to make a better contest !! Hats Off to vaaven
Can someone please share a typical case for D?
This case helped me in debugging
5 3
2 4 6 11 12
Can someone tell me the TC where this code gets runtime error[submission:266046159]. Approach:We can always create any K greedily if its even and is less than the max value achievable.Then we know that if we swap two values,then twice of their difference contributes to K,so i have halved the value of K to x.Then using binary search on set to get maximum possible value which we can attain to decrease x, we swap both of them and decrease x.We repeat until x is 0.
Nice overall round with +ve delta forces. I think this round was a great opportunity to gain some positive delta bcz the problems were a bit easier than a normal div 2 round. Kudos to the tester who gave us the hint to read all the problems bcz I think there was a good chance an average newbie coder could have also solved D if he was a bit sincere on the clock(unlike me).
why its not working???? PROBLEM D
System test when?
testing please we wanna submit unsolved
I don't know if I should be happy or sad if my compiled error submission gets accepted after I fix it
yeah i fixed silly bug after 1 min contest ended and now it got accepted(
I am so ded rn,i forgot that iterator doesn't copy it points to original location,which returned ruined my C solution.
Can anyone give the test case for problem C where this submission is giving wrong answer 266027942
UPD: Nvm got it
solved my first div 2 problem in contest (just A but still happy about it)
Ayyo... Why am I getting Idlesness error in C??? 266040778
Does it lead to negative points??
on problem A and D why don't you just say index instead of number ... what a problem statement
Will this solution work for E?
https://www.ideone.com/PApbrg
I was very slow in contest, I assumed that E would be harder and started it very late.
LOL it turned out to be easier
I solved B using calculus first derivation. I know this is not intended solution. But I would love to share here because it was interesting.
Noticed that the answer should be
$$$a(n - k) + bk - \frac{k(k + 1)}{2} + k$$$
you can use gaussian for this computation.
You can modify this to make $$$f(k) = -\frac{1}{2}k^{2} + (b - a + \frac{1}{2}) k + an$$$
You can look for the maximum $$$f(k)$$$ using first derivation, $$$k = b - a + \frac{1}{2}$$$. Don't forget to check the answer with $$$k = 0$$$ and $$$k = min(n, b)$$$ as the boundaries.
Statements were a bit unlcear, in my opinion.
A: The statement says "highest number", but I can't find where 'number' is defined. There are many other places where 'number' is used, but some of them are referring to 'number of pages'. There is no place where it says 'number' actually means $$$i$$$. It is not obvious that '$$$1$$$-st book' means that the 'number' of the book is $$$1$$$. It could be more clearly stated, or could just be replaced with another word.
B: The story of the legend is misleading. Like, Bob organized the promotion to "attract customers", but he's trying to sell them even more expensive than they currently are? Why would customers be attracted to such promotion?
To add to that, in problem B it felt like the variable $$$b$$$ was introduced in the statement with too little explanation. Like, the first explanation of what $$$b$$$ actually represents only comes up in the input section so until that point you're just kinda left to assume that it's probably just an input parameter.
100% agreed I was very confused that what is b. The only way I got it by looking at the test case explanations.
LOL yeah I agree
I just realized my solution for F had a very terrible sieve, that it didn't really puncture composite numbers — so instead of listing all prime divisors for integers in range $$$[1, 10^6]$$$, it lists all divisors instead (this will affect the DSU process later on since the number of edges are increased drastically).
Solution: 266020666
Can it be uphacked? Thanks in advance.
I am doing the same , with primes , getting TLE on 3rd test case , any idea the weak areas in the code . https://codeforces.me/contest/1978/submission/266151360
Your map loop was unnecessary: you can just go through all pointers of the map instead of looping from 1 to
maxi
, also index-accessing a map is dangerous as it will create memory block on keys not yet initialized.Should a test like this appears $$$10^5$$$ times:
it would be pretty likely that you'd TLE/MLE due to that, as that loop will certainly create $$$10^{11}$$$ blocks in total.
My fix: 266154363
The fix still has a RTE though, but it seems easier to patch that (it also has CF's diagnosis log), so I'll hand it back to ya.
oh , thanks , maxi i was intially trying but i removed that , forgot to remove from the area (you are pointing) . Me idiot
Also that RTE is because of spf vector is of N= 1e6 length but the numbers can be upto 2e6
Finally, after so many attempts I made it :)
Providing the same numbers with most number of divisors didn't really work (they took only around 3.6s), so I tried a bit of things to slowdown other aspects, mostly to cause cache misses. Still I must not have lowered the number of divisors of the numbers too much, so I tried to find some integers that:
Then it was about trying with different $$$x$$$'s and the number of integers (which I mostly went with 10, to repeat exactly $$$t=10^5$$$ times). It also took me some tries to shuffle with different seeds to make it actually exceed 4s, as in average it was still around 3.7~3.9s.
Freaking hell, so even this uphack was gacha-based. Thank you for your effort though, it was fun witnessing and reading your approach on it!
Great Contest. Absolutely Loved it. This was my first time solving Div2 B & C
why does this solution to E give wrong answer? Can you suggest a countercase?
The wording threw me off so bad for A and D that it took more time to solve A than it took to solve D. v_v
Can anybody point out the error in my code of c or give me a test case where my submission is failing?
Submission id is 266045808
Accepted
Best contest for me.
Can someone suggest me how to plan to solve the correct questions?? Since many of you are saying that D and E were both easier than C. But I solve in order and presume that E>>D>>C in difficulty so no point in reading it. I solver A and B under 30 mins, figured the logic of C easily but it took me 2 hours to implement it and AC'd after the contest was over. I am still a newbie (hopefully will become Pupil now) so can you guys please suggest me how to plan to solve the right questions??
i was doing Binary seach on the problem B for optimal k which gives me the max profit but getting wromg answer i dont know which case is not being handled pair<ll,ll> possible(ll n,ll a,ll b,ll mid,ll initial) {
}
void solve() { ll n,a,b; cin>>n>>a>>b;
ll low=0; ll high=n; ll initial=n*a;
while(low<=high) { ll mid=(low+(high-low)/2); pair<ll,ll>temp =possible(n,a,b,mid,initial);
} ll val=n*b; // cout<<mid<<endl;
cout<<initial<<endl; return; can check my code..
You should use ternary search. Cause if you keep increasing k the answer will keep increasing and at some point it may start to decrease. So there is a peak.
You can also differentiate the equation to find the maxima, which is actually the desired value of k.
thanks
Bro... 2 rating points away from pupil...
I know how you feel bro)
1 rating point away from specialist
round is relatively div2
I can't believe how 6000 coders solved C.I would like account verification to be more difficult. Because it's unreal to watch how many guys who write for the first time pass ABC.
Yeah I was able to solve C started contest half hour late immediately got the idea but implementation omg 266044140 took me around 5 attempts good thing was you can debug C easily if something went wrong its amazing how people were able to implement on first go .. also if anyone wants to hack my solution feel free because I am still not sure about some edge cases
CDE should've been in reverse order, C took too much of my time and couldn't solve D due to a small implementation error. Upsolved E pretty quickly.
Editorial is not published in contest materials
why did my rating drop down by 4 even after solving 3 problems(ABC) today?Can someone explain how does this rating change works? Is it coz I got ranked lower than my rank in previous div 2 round?
It is not directly how many problems you solve which determine the rating change, but rather how you perform compare to others. see https://codeforces.me/blog/entry/102
Before Eid-day, I am back to CYAN!!!
d1mk orz
d1mk strahi09 orz
266080165 Can anyone tell me what's wrong with my problem D solution, it fails in the second test.
Can someone please explain how problem E can be solved?
Could someone address the 'Unexpected verdict' issue on my hack? It's just a simple $$$t=10000$$$ test where 9999 of them are
1 10^12
and the last one is190001 18050190000
to hack an $$$\mathcal{O}(n^2)$$$ solution with slow I/O. I don't think any intended solution is supposed to get hacked on this test.UPD: resolved.
Though I couldn't solve it in the contest, D is such a nice problem
I can't delete my comment so I'm editing it
B can be solved using ternary search i think it should be added as a tag https://codeforces.me/contest/1978/submission/266093452
overkills shouldn't be added as tag I think
Please release the tutorial
https://codeforces.me/blog/entry/130527
hey everyone, this is my submission for problem c in div 2 contest, may someone tell me what is wrong with my code? even though my manhatten distance is correct? https://codeforces.me/contest/1978/submission/266099707
its true
C appeared before in last year's ECPC, likely giving some participants an advantage since C > ABDE. This is probably a coincidence, but it suggests that the selection of testers should maybe consider representation from all regions, or at least the major ones.
why binary search on k won't work in porblem B ?
Because the Bob's profit expressed as a function of k is not monotonic but rather unimodal. So one can use ternary search to find
k
which delivers the maximum, though this is not the unique approach to solve this problem.For me after upsolving F is much easier than C xd
Abnormal round. B with quadratic function, E,F with simple ideas which are easier than normal.
I suspect that the top1 cheated. Maybe more than 1 people use that account to submit.
Why did i get a plag on que E , it was a standard one the check the segments in a range only change being the inserting of l and r
no response , anyways im uploading my notes(from a CP course) from which i copied the code(ig its not against the rules) Notes
I request vaaven to please have a look at these and kindly remove my plag
As a chinese participant, it is a very usual time in the afternoon.
E < D < C
My cf id is not opening and handle is kxhitz I had given last contest on 16th June 2024. Please check it out and resolve this issue as soon as possible.
PLEASE GIVE ME A SOLUTION FOR THIS
Thanks you for good contest! I enjoyed it!
I am agree with you!
what is the penalty for wrong submission for div2 ? time or points or nothing ?
You are welcome
Thank you to all the problem setters and testers for an engaging and challenging contest! I found problems B and C particularly interesting due to their unique approaches. Looking forward to the next round and hoping to see more creative problems like these!
I got a Wrong Answer on test 2 in problem E. Can any one help me? Many thanks.
Code