Hello Codeforces!
I am glad to invite you to Codeforces Round 958 (Div. 2) which will start on Jul/15/2024 17:35 (Moscow time).
The contest will last for 2 hours with 6 tasks for you to solve. The contest will only be rated for those with a rating not higher than 2099, but high-rated competitive programmers are also more than welcome to participate out of competition.
The score distribution is: 500-1000-1000-2000-2500-3500
The contest will be impossible without the help from:
- 244mhq for wonderful coordination.
- gyh20, Dominater069, Um_nik, A_G, omeganot, tkl2006, harsh__h, oursaco, Hori, kostia244, ishaandas1, maomao90, waidenf, Stefan2417, ItsNotMeItsYou for testing.
- MikeMirzayanov for Codeforces and Polygon.
Good luck and have fun!
Update: editorial
Update: video editorial
wtf a div2 with 3500 problem? Why not add more problems and extend it to a 1+2?
That's the score, not the problem rating.
I know, but very often they are almost the same.
I was also surprised but it appears to be more common than I thought: three of the last 10 div2 rounds had a problem valued at 3500 points, including Codeforces Round 949 (Div. 2) and Codeforces Round 940 (Div. 2) and CodeCraft-23. Additionally, I'd say that a good 1+2 needs at least 3 problems of this level (judging by Codeforces Round 942 (Div. 2) and Codeforces Round 942 (Div. 1)), so it's not as easy to extend as it may appear.
I think you are right.Maybe it is hard to add more problem.Or it will have too many div1 and div1+2 if every div.2 like this add more problem to div1+2.
A huge difficulty gap b/w C and D O_o!!
Unrated only for Legendary Grandmasters:-O
Wow feecIe6418 round! I missed you a lot!
speedforces!!
Maybe, they call speedforces because the difficulty level in between two consecutive problem is too high. The person having more skills/practice got beaten by the speed of some other participants just because he was unlucky in starting problems in some of the contests. And anyway both candidates won't be able to solve the next problem because it's too difficult that results in negative rating change. <- My perspective :)
this. in some contest solving first 3 problem FAST is sufficient to be expert of even CM but solving first 3 problem SLOW can result in gray performance < 10000 rank.
this high variance of distribution of problem difficulty scares many div3 people including me.
Right. Solving first 3 problem FAST (in 15 minutes total) is much much better than solving first 3 problem SLOW (in 2 hours). What's your point?
yes but having extra room to upsolve (problem D) may help those who failed early e.g) multiple WA on pretest, already gray but problem D is too high: (problem_rating — current_rating) > 500 -> game over. However if difficulty gap between B and C or C and D is reasonable this cannot happen.
so the fair contest should form problem rating of arithmetic sequence, imo
Nothing is 100% fair, just solve faster. I don't see your point.
lets make contest with 1 gray *800 problem with 4 *3500 impossible problem.
just solve faster.. okay.
You know I didn't mean it like that, but ok enjoy your upvotes.
Yeah, so, about that...
As I tester, I enjoyed the problems and encourage you to participate!
I, Tester
Goal: ABC in 30 mins, D before the 2 hour mark.
as a tester
as a contestant
as a
as
404
817
Hopefully, the problem statement will be short and precise just like the announcement!
Goal solving ABC by the end of contest
As a tester, I am sure about tolbi is Nutella.
Also participate this round, problems are very cool.
why isn't this on home page?
"I am glad to invite you to Codeforces Round (Div. 2)" . you haven't said div2's id XD
A + B + C = E.
B=C
B+C=D
A+B+C=E
A+B+D=F
A+C+D=F
etc.....
Great! I hope to reach +1750 in this round
if you want 1750 rate then solve 2000 problems
are you asking for downvotes?
maybe
hoping to solve 3 problems
Same
1000?2000!
i have a strong conviction that this will going to be BIG speedforce for div3, fast solve ABC or ff.
you were literally correct lol
OH! gyh I miss you a lot
As a participant ,i love the testers.
Let's see if I can avoid bricking this contest.
hopefully i reach 1434 rating this round
I think this round is going to be mathforces
I am good at math. (•-•)
He's from China :(
I knew it. why some codeforces rounds are so maths heavy
This is my first contest. Thanks to CodeForces.com. I will do my best for this contest.
How did it go?
I blew it, due to my poor skill, I will study harder and harder. For now, I satisfied with my codechef result with 4 stars. https://www.codechef.com/users/enthusia0209
But now, I do think that I must learn from CodeForces.com contest.
Thank you, dear.
Gl next time, everyone starts in 5 digits here XD
I ve solved A,B and D. thank you for encouraging me.
What happend to C lmao
tried for 30mins but gave up and skipped D.
You had Entire Saturday and Sunday. But no, we will host the round on Monday. wow.
There is a Div. 2 round scheduled for this Saturday :)
i hope to be expert today
this time your goal is realistic :)
enjoy in contest.
oh this is the good chance that i can improve my rate :) HOPE CONTEST IS EZ!!!
C is 1000 points. Speedforces incoming.
Hope I can be Expert in this contest!!!
GLHF
You meant to say that the contest would be impossible without the help from..., right?
Now it seems that we won't be able to solve any tasks unless we contact the creators :D
Mistake
2 accounts are forbidden, so you will be banned.
What's your idea for e?
Sorry bros
What are you doing? Rofl. You can edit your comment a thousand times but people are not blind.
And I keep falling! Am I getting more stupid or are CF contests getting more difficult?
number of people who cheat are insane now. When ABC is hard cheaters will have the advantage because honest people wont be able to solve it but they can copy paste it from somewhere doesnt matter what the difficulty is.
The first one to pass problem E~
Also my first time to be the first to pass a problem on Codeforces! Happy~
smurf account detected.
Question D Looked so innocent to me, I thought it was only about Bipartiteness of the graph, Later I understood it's way more complex than that.
++
I can't believe that more than 12k participants solved problem A all by themselves.
A is easy, am I missing something?
Personally, I didn't come up with a formula for problem A. I just used multiset to simulate without thinking too much, with an extra optimization which is to not insert all the 1's inside the set again
(My first solution got TLE because I underestimated the problem and didn't add the optimization lol)
lol
At first it looks like the most innocent-looking bipartite graph problem lol
haha
Ther is a problem in a persian contest that is really similar to problem D.
Basically this problem there is no $$$a_i$$$ but the problem gives you a tree and asks you to set a positive integer value to all vertices in such a way that no to connected vertices have the same value and the sum of the values is minimum.
It is basically problem D but with $$$a_i = 1$$$ for all $$$i$$$.
It is not so far from problem D and i know two solutions for the problem in persian contest that can be changed to AC solutions for D by changing a few lines.
This problem from 2015 Facebook Hacker Cup is also similar: https://www.facebook.com/codingcompetitions/hacker-cup/2015/round-1/problems/D
man, that was TOUGH :)
don't know why but I smell brute force in D.
bro please clean your nose you are cooking wrong
probably the hardest div2 A I have ever seen
I solved B & C but failed in A :<
Thanks for the contest. especially for task D. the first idea that comes to mind — two days is enough (painting tree in two colours) passes the sample but is wrong :(
I think it requires O(logn) rounds to kill all monsters?
I guessed that with a bit of intuition, but not sure how to approach a formal proof of it.
.
me too
A >>> (B + C)
OMFG got accepted E in the last 2 minutes. My first E in div2 for nearly 2 years.
I was thinking of using segment tree and binary searching through the upto which range our ai is the current minimum. Is this approach correct. In theory this will work in O(N log^2N). What do you think
It is still ambiguous. Can you say it more clearly?
instead of segtree + binary search, you can just use a stack...
Damn, I got too many penalties on B for concatenating to a new string instead of just using normal variables.
A is harder than C, Nice.
In what sense bro, i couldn't come up with any idea how to approach C :(
lets say we have bits in positions 4,3,2,1
what's the optimal here ? first lets take all bits then we take 4,3,2 then 4,3,1 then 4,2,1 then 3,2,1
now its just in reversed order :) that's why I said what I said
Cool!
A is easy too....just think like : Break the current number(>1) in max possible 1 you can break, leave rest for next step.
EX: S = 5, k = 2
1 4
1 1 3
1 1 1 2
1 1 1 1 1
EX: S = 6, k = 3
1 1 4
1 1 1 1 2
1 1 1 1 1 1
Both the observation and implementation of A are simpler than C
ok i swear if the submission for D that im about to send ACs im gonna be so pissed (i was 3s late)
also here's my approach for D
observation 1: you only need to delete at most 3 times
first deletion will split everything into trees of depth 0 or 1 (if it's depth 2 then the non-leaf can be deleted in the first move and it's guranteed to be better)
2nd and 3rd deletion just "cleans" the trees of depth 0,1 i let dp[a][i] = min price to delete subtree i WHILE deleting node i at t = a
then for all child v1,v2,...,vk of dp[1][i] = val[i] + min(dp[2][v1], dp[3][v1]) + min(dp[2][v2], dp3[v2]) + ... + min(dp[2][vk], dp[3][vk])
dp[2][i] = 2*val[i] + min(dp[1][v1], dp[3][v1]) + ... (you get the idea)
then the final result would be min(dp[1][0], dp[2][0], dp[3][0])
however this gets wrong answer on pretest 2 (either it's wrong or it's my implementation that's wrong)
just go with log2(n) instead of 3
Can you tell what's the intution behind log(N) rounds
i tried firstly with 3 got wrong ans then thought max it can be 100 looking at the constraint then got tle then i just felt since my logic and implementation is correct it must be logn
8 1000 1 1 1000 10000 10000 10000 10000 1 2 2 3 3 4 1 5 2 6 3 7 4 8
wow...
so turns out i threw top 80 because of that
still positive delta tho so yay..?
at least it was better than last div2 where i solved a wrong version of E and spent forever debugging it (only to realize the mistake AFTER the contest)
I tried the exact same thing ;-; , but using this logic idk why it didn't even pass the given tc , will have to upsolve later:).
so hard :( but nice problem. I think E is pretty good.
resolved
$$$k$$$ needs to be atleast $$$2$$$
oops sorry, my bad
can anyone tell Whats the logic behind problem -d
my logic — just doing dfs and marking all alternate nodes in a tree then the answer will sum of all nodes + min(sum of marked node, sum of unmarked nodes)
it fails this test case
1
4
1000 1 1 1000
1 2 2 3 3 4
oh thanks a lot bro got it
i think its because lets say u have 4 straight connecting nodes and u can imagine like an array and counter test case will be something like 100000 1 1 10000 since best option is picking 1 and 4 instead of 1 and 3 or 2 and 4
if the tree is 10 — 1 — 1 — 9 the answer is not 31, but 24. the optimal in this case is with 3 turns instead of 2 (I'm also thinking about the logic, but this was my counterexample of the dfs idea)
this shouldn't work, counter scenario: think of an array where you need to maximize the total value you pick without picking adjacent elements! this can be solved by a simple dp; and so this each path in this tree can act as an individual array if you think
is there a direct bitwise formula for C I solved it but nevertheless found the bit manipulation I did quite complicated.
You can look at my solution if it is of any help
The number of submissions for problem C is beyond my expectations and nowadays looking at no of submission always demotivates me(i feel how this fast submission crossed 1000)
Auto comment: topic has been updated by feecIe6418 (previous revision, new revision, compare).
Not able to solve B after lot of attempts can't find the case where the code goes wrong.
let me help you bro
think of this test case 00000011100000000
here in this test case in first move you will combine all prefix 0 with 1 in the second move combine all suffix 0 and in the third move apply operation on the remaining array so answer will be 1
the corrrect approach is to combine all consecutive 0 into one '0' so that no one gets into waste and then checking is count of 1 is greater than 0 or not
Can someone explain in short the idea for C ?
For each number, just unset one set bit starting from msb to lsb
Lets build $$$a$$$ from the end.
$$$a_k$$$ cant be larger than $$$n$$$ because that would mean $$$a_{k-1} | a_k \gt n$$$.
It turns out that $$$n$$$ can always be put as $$$a_k$$$. (dont know how to prove that sometimes $$$a_k$$$ smaller than $$$n$$$ can result in bigger $$$k$$$)
Now for every next number $$$a_i$$$ we construct (actually previous in $$$a$$$) we will try to decrease it as little as possible compared to $$$a_{i+1}$$$ while the $$$a_i | a_{i+1}$$$ is equal to $$$n$$$.
in C, is the len of the longest sequence equal to => (no.of set bits in n)+1, except for the cases where the no.of set bits is less than equal to 2..
Probably the best contest I ever gave on Codeforces. Got wrong answer on A then understood my mistake and then solved C with 1 minute 29 seconds remaining!!!!! Very happy rn.
Hello,
These problems were trash.
Yours faithfully.
Comment from your main.
Have you considered that it could be a skill issue?
solved a, b in 14 mins but could not solve C. Can some one throw some light. Am i missing somethng obvs?
print number in binary format
started 1hr late solved B and C only stuck at a cause A, doubt was whether there exist an easy sol in constant time but would have implement in log(n) complexity rather if no time pressure. Will try best to wakeup early next time
For problem A: imagine you have a block of length $$$N$$$, and you can cut it at $$$N-1$$$ different positions. During one move you can make $$$K-1$$$ cuts (this splits a piece into $$$K$$$ pieces). You want to make cuts at all $$$N-1$$$ positions, since this will result in $$$N$$$ pieces of size 1. This means the required moves will be $$$\lceil \frac{N-1}{K-1} \rceil$$$.
Hello everyone, this contest is good. I solved 2 questions in 13 minutes, but I'm stuck on the 3rd question. Even though the 3rd question is challenging. There was a live stream running on YouTube called "Sharabi Lal". If someone official is watching, please block this. However, even if they do, they might create another channel. What can we do? Maybe you should increase the quality of the plagiarism checker or something similar. If someone is found cheating, you could mark their ID differently or publish the name of the cheater after the contest. Or maybe not. I'm just frustrated.
Yes, you could also have a "Report Suspicious" button where someone could report if they suspect someone else of copying code.
Please edit out the channel name else more cheaters would get to know about it and follow him.
Is D dp, trees or both?
Basically Dp...try to traverse from one leaf node...
DP, the move in which you kill a subtree's root must be different from the time in which you kill its children. You can have $$$dp[i][j]$$$ = the minimum cost to kill the subtree rooted at $$$i$$$, if you kill the root during move $$$j$$$. For $$$dp[i][j]$$$, we take $$$A[i]*j$$$ damage from the root, and then we then have to pick $$$j' \ne j$$$ for all the child subtrees.
Rainboy round , I want to know which country he belongs to.
he is asian but respresents USA at IOI
How to not choke in questions like A :<<
This contest let me become purple and >1900 for the first time, i love the problems!!!(O.o)
Congratulations bro
What's the idea behind problem E?
Why was my D-question never system tested?
Haven't you finished the test yet?
Hi everyony. It's written in the description that "The contest will only be rated for those with a rating not higher than 2099". But my rating hasn't changed yet. Should I just wait for some time or there is some kind of mistake?
I saw A tutorial it's really easy I think I couldn't solve it because I restricted my self that in each operation n should be divided by number <= k
I got WA in 270731172 during the contest. I submited the same code after contest and it accepted. 270754276. Why ?
I don't think both codes are same, you must have made some changes
ur code fails here.
It checks whether the n is power of 2 or not. Also this lines present in the AC code. I think I got WA because I use local vector and when I use global vector I got AC. I don't why.
no, it got lucky AC
pow(2, bits-1)returns double, and double precision is not that good.try to use
(1 << (bits-1))instead, it will get accepted whatever vector u useProblem D got me good. Oh well, We will get 'em next time.
Auto comment: topic has been updated by feecIe6418 (previous revision, new revision, compare).
Hello
Hi
same dp and name
Finally became a CM, thanks for the contest!
Dear Codeforces Team,
I recently received a notification regarding a solution coincidence for problem 1988C with solutions Rudransh58/270724137 and 2022ucp1403/270738520. I would like to address this concern and provide some context.
First and foremost, I want to assure you that I have always adhered to the rules and guidelines of Codeforces and have achieved my rating through my own efforts. I have not engaged in any activity that would violate the rules, including sharing or copying code.
I am unaware of how this coincidence occurred, but I can provide the following points to support my position:
Independent Work: My solution was developed independently based on my own understanding and problem-solving approach. Code Sharing: I have never used public platforms like ideone.com with default settings or any other medium to share my code. I take the confidentiality of my work seriously. Common Sources: It is possible that the coincidence is due to the use of common techniques or standard algorithms widely known in competitive programming. If there are any common sources that could have led to this similarity, I am unaware of them. I am committed to maintaining the integrity of the competitive programming community and am willing to cooperate fully to resolve this issue. If further details or explanations are required, I am ready to provide them.
Thank you for your attention to this matter.
Best regards, Rudransh58
Your coding style completely changed between problems A/B and problem C. Even the indentation and formatting are different.
Problem A and Problem B, which use <bits/stdc++.h>, include macros for ll and mod, and solve everything in the main function.
Problem C, which uses different includes, no macros, uses a solve() helper function for testcases, and has different spacing/formatting.
It's because i've used diffrent moduled code which i've pre written on my vs code, so i did use diffrent includes, no macros, used a solve() function that's on my vscode!!, and changing the code writing style does'nt mean i've copied the code.
Hello. I have a question: I got 1700 this round and I did see that my rating increased about 261 or so, but after 2,3 days, this became unrated!! Is this a bug? Could somebody please tell me why this would happen, please?
I have the same question...