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, MisterReaper 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.
This is the first time I've seen a grandmaster's comment receive so many downvotes. People generally tend to upvote whatever a grandmaster says.
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
Hopefully, the problem statement will be short and precise just like the announcement!
Goal solving ABC by the end of contest
us
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.....
Thank you to all
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
problem statements are the main reason as we read a big story and makers make more confusing some good coders ignores the stories and go read testcases. some problem have confusing story and does not have testcase exxplained. took more time! good wishes ;)
@tkl2006 and @ishaandas1
I Want some tips on how to be eligible for system testing of these contests...
@feecIe6418 can also answer
1000?2000!
Every round should be unique so it's fine to have bit different score distribution
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
omeganot orz
As a participant ,i love the testers.
Let's see if I can avoid bricking this contest.
I smell a shitty round...why can't you guys make C problem moderately difficult ? (one which gives near about 1500 points on right submission )
I bet its going to be a weird guess or some shitty greedy being involved in C problem
You can make it then if it's that easy.
hopefully i reach 1434 rating this round
I hope to reach 1100 in this contest (ノ^_^)ノ
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.
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?
Dont change the topic mate you are cooked. lol.
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.
++
Fooled by score distribution! all eyes were on B and C, A surprised many.
I can't believe that more than 12k participants solved problem A all by themselves.
Less than past contests, maybe cheaters needed some rest
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
Wasted 15 minutes reading OR as XOR :(
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 :<
i solved A but failed in B idk why i missed some cases :( i need to work more
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?
Let's say our original sum is F
when A[i] is removed we calculate from 0 to i. The minimum idx which have min(idx, i) is A[i], lets say X . and maximum idx which have min(i,idx) is A[i], lets say Y. Then count the subarrays between [X,Y] in which i is included. Subtract this*A[i] from the F for this index ans
instead of segtree + binary search, you can just use a stack...
I haven't really solved problems using Stacks. And yea this is one of my weakness that my mind focus on Seg trees whenever something related to range comes. gotta work on that. And I will try to solve the problem with both approaches. Thanks for the info
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
if n would have been large this brute force would have failed, but within these constraints this solution seems okay
Both the observation and implementation of A are simpler than C
for the first time i couldn't solve A, but i was able to solve B and C.
Did A in 9 mins, but was not able to do C even after throwing my whole mind at it for 1.5 hours.
It's interesting that the problems time limit is in ascending order.
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)
so hard :( but nice problem. I think E is pretty good.
resolved
$$$k$$$ needs to be atleast $$$2$$$
oops sorry, my bad
The minimum value of K has to be 2
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)
Think of a case like this one:
1
4
100 5 5 100
1 2
2 3
3 4
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.
Can you explain your logic in brief Please ?
You can take a look at my solution here. You basically iterate over the bits from highest to lowest significance, and if the bit is on, you turn it off and print the rest of the bits as they were. Also don't print zeros and that's it.
You can look at my solution if it is of any help
take n in binary for example 23 is 10111
the answer will look like :
(the number of ones + 1)
00111 10011 10101 10110 10111
look at my submission
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
Just replace all consecutive zeros with a single single zero(make a new string) and then count c0 and c1 and apply the conditions given in the question.
If we try to observe a pattern in answers A is simply ceil(n-1/k-1)
Can someone explain in short the idea for C ?
For each number, just unset one set bit starting from msb to lsb
My solution : keep searching the bit which is 1 from the smallest bit. When it is 1 , replace it with 0 and make the bits after it to be valid for A | B = N (So we can keep finding smaller number)
(Sorry, My English is bad, I am not native speaker.)
Therefore, the answer of 14 => 4
Lets build $$$a$$$ from the end.
$$$a_k$$$ cant be larger than $$$n$$$ because that would mean $$$a_{k-1} | a_k>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..
when no of set bits > 1, the answer is just no of set bits plus 1; otherwise, just print 1
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?
take n in binary for example 23 is 10111
the answer will look like :
(the number of ones + 1)
00111 10011 10101 10110 10111
look at my submission
print number in binary format
N = 13 {1101}
unset the msb
0101 = 5
set the previous unset bit and unset the next bit
1001 = 9
do this again
1100 = 12
1101 = 13
the length of this seq will be equal to == No of set bit + 1
Special Cases(2^N)
Length = 1
sequence is 2^N only
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$$$.
i had same approach but mine was little mistake i took ⌈N/K−1⌉
i think D was too hard
I turned my head away from that problem and went to E as soon as i realise its prolly DP on trees LOL
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.
Thanks
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 :<<
What I try to do is Think simple and don't overcomplicated anything and be greedy(Although it doesn't work everytime)
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?
Wait for some time
It'll change in a few hours
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
Oh yes. I change local vector to global vector.
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 useOkay I'll try it. thanks.
Problem D got me good. Oh well, We will get 'em next time.
good contest!
Auto comment: topic has been updated by feecIe6418 (previous revision, new revision, compare).