Henlo Codeforces!
We are very glad to invite you to the Codeforces Round 754 (Div. 2), which will be held on 12.11.2021 17:35 (Московское время). This round will be rated for participants with a rating less than $$$2100$$$. For higher rated participants, we challenge you to solve problem F ;)
All the problems were authored and prepared by Ashishgup, the_hyp0cr1t3, ExplodingFreeze and me. We have tried our best to create an interesting problemset with clear statements. Hope you enjoy the round :D
You will be given $$$6$$$ problems and $$$2$$$ hours to solve them.
We would like to thank:
antontrygubO_o for his amazing coordination and help in improving our problems.
Our army of testers: Um_nik, 244mhq, Monogon, _runtimeTerror_, Jeel_Vaishnav, AmShZ, errorgorn, ijxjdjd, Utkarsh.25dec, Dragnoid99, yash_daga, Vivek1998299, taran_1407, MagentaCobra, Retired_cherry, sinus_070, AC_007, talibmohd, KahanHai, Dragonado, Submit_Galactic_Algo, KeyurJain, tvcv901, ekanshi, Jellyman102, jimmy18, inferno14 for testing the round and providing valuable feedback.
MikeMirzayanov for the Codeforces and Polygon platforms.
Here's the scoring distribution of the round:
$$$500 - 1000 - 1500 - 2000 - 2500 - 3500$$$
UPD: Editorial is out
Also, congratulations to the winners.
Div 1 + 2:
Div 2:
Fuck off!
INDIA WALE MAA CHOD DENGE ISS ROUND MEIN CKMKB
CKMKB PKMB
PKMKB
Damn an Indian Round, super excited for this :)
A round by Ashishgup to break the drought, I am excited!!
As a tester, I can confirm that problems are simply amazing.
Is it going to be tough ?
They still have us in the second half
Codeforces round after a long time, sadly I can't participate due to my exam. :"(
All the best for your Exam
True,these exams are really giving us hard time!
skip your exam
SSC Exam Bro. :((
If they have added a newbie tester then testers army would have testers from every rating range
Then, if you could choose, who would be the newbie to also participate in testing?
worse
"Brace yourselves for WA on pretest 2"
At least we can expect strong pretests
Probably, all the problems have only two pretests...
or maybe, we have several pretests but the second one goes hunununununununu….
As a tester, the statements are short and the problems are great.
Finally...
Problems prepared by ashishgup, this round gonna be interesting
Incoming game theory problems!
Now I dont care about rating. Let me see WA on pretest 2
"WA on pretest 2" no doubt problems are prepared by Ashishgup.
Has this round the strongest second pretests:)
After a long time finally a div 2 contest .
With Ashishgup as problem setter, we may expect some problem on turn-by-turn game (Source: 5 out of 7 of his contest has such problem).
Prediction successful ,Orz
Ashishgup as an author, me ready to brick whole my contest on div 2A :P
Contest after a long time, Looking forward for it!
rainboy be like : challenge accepted! i'm gonna solve F first.
Hope i'll solve the problems in this round :(
well Good luck to all
Game theory problems loading
Finally another Ashishgup round!
(waiting for a constructive and a game theory problem)
SergiuS2003 will win the round
hoping to be green in this round
hoping to be green in this round
join me. reject cyanity return to green.
I did my best but only managed to get -18
hoping to remain green after this round
As a tester, I can confirm that the questions are really interesting and diverse. And Ashishgup rounds are always fun! ;)
upvote for the image
"Brace yourselves for WA on pretest 2", nothing new for me), haha
Lets see which Game are we gonna Play in this Round !!
I haven't had a positive delta in any Ashishgup round. Let's hope for a change in this one.
I hope you reach master in Ashishgup's round :)
The legacy continues...
Lol
In this round also, Ashish : 1 Priyansh : 0 hehehehe..........
Oh jesus, I am nervous. I'm only 27 points away from expert, I hope I can get them tomorrow.
1 upvote = 1 less WA on pretest 2
Hope that I won't choke again in an Indian round
Game Theory Problem for sure!
So many shitty memes in the comments of this announcement. Or it has always been like this and I didn't notice?
too many wrong answer on pretest 2 ngl
speedforces
Participants whose Problem's solution got accepted in 1st attempt..( passing pretest 2)
Jury verdict after everytime I submitted solution C
i can see an avengers infinity war fan.
also an anime fan… XD
Damn True,....
Just one pretest of problem C was difficult, not difficult but out of context of our thoughts.... :_)
I believe everyone missed that Testcase for which the answer was 7.Sad
yes, that was a little distant from other
btw , u have an amazing username bro, XD
F**k Div 2 Problems A
A is a bingo problem (a+b+c)%3
"For higher rated participants, we challenge you to solve problem F ;)"
5 minutes left in round completion. No one solved F. Where is rainboy when we need him :')
Is F O(N^5) dp? I feel like i moreless got the idea, however it's impossible to implement. Maybe I'm completely wrong.
Thanks for the round and F is really challenging, Waiting for the editorial!
I am sorry but problem E requires no thinking at all. I wonder how this got accepted...
Also, should Problem F be in a Div2 contest? Even LGMs can't solve it, while 2Fs should have at-least 20-30 solves.
I think problem F was there only to satisfy their ego.
yeah E can be solved by looking at the pattern only, which feels wrong for div2-E.
How to solve problem C in O(n)?
The length of the substring is bounded by 8.
Can you explain how you made this observation?
First, lets understand that if there is aa, so answer will be 2. Then if this up statement does not work in our string, then we its obvious that i, that s[i] == 'a' are at least at distance > 1, because first statement doesnt work. Then lets see what we can get from here. We can see that if there is s[i] == s[i + 2] and s[i] == 'a', either way it will be our answer. Then lets find another case when there is something like that abca, acba answer will be 4 there. If these all cases doesnt work, then i that are equal to 'a' are at least at distance >= 2, and if we think little bit we can see that we have abbacca, accabba. Thats all. Sorry, for my bad english and may be bad explanation
How is an len=8 substring possible? For me its bounded at 7.
Same. Can the answer be anything other than 2,3,4,7,-1 ?
I kind of just searched these substrings.
Link to my submission
By bounded by 8, I meant < 8.
There are only 4 cases: 1. aa 2. aba 3. abca 4. abbacca
And you can prove that if the gaps between the 'a's are greater than 3, then it is impossible to get a good substring.
you can observe that you need only 1 operation, or none at all if it's already sorted, let's call X the number of 1's in the string, it's a binary string so you can tell if it's sorted by looking at the last X bits if they are all 1's then it's already sorted, if it has zeros then we choose those zeros with the ones that are not in this group. 0001111 (it's sorted because the last 4 digits have 4 ones(all of them)) 00110101 (here we can say the last 4 digits has 2 zeros in them, so we take those with the ones that are not included)
*if it's not clear 0 0 1 1 0 1 0 1 the last 2 ones are already in place (no need to do anything), the last 2 zeros need to be replaced by ones, the first 2 ones are the ones(all that is left) to be replaced it will always be non-increasing because the ones that we choose are always in the front
I dont like very much that style of problem statements, where there are a lot of details explained, and then in the last third of the text some more or less related question is asked.
Better give a first sentence to understand the idea of the problem, then come up with the details.
I rather prefer this type
I think they could just highlight the most important words
For problem D, was the idea based on placing numbers according to their most significant bit (using the fact that a tree is bipartite)?
For D, the final idea that came in my mind was that we will try to end the game at every node itself. Which summed up that there cannot be neighbours with their MSB equal. But no clue how to solve this construction. Any hints?
Yes, the idea is correct. We can try to end the game at every node. For every node, try to make sure that all neighbors have an unequal MSB.
Color the graph white and black (such no two nodes are the same color).
Notice, number of numbers with MSB at Position 0 = 1, number of numbers with MSB at Position 1 = 2, number of numbers Position 2 = 4, and so on.
Let number of white nodes be w and black nodes b. Consider min(w, b). Consider the binary representation of min(w, b) For now, assume w<b. Let's say w=5. In Binary it is 101. So take numbers with MSB at position 1 and 3, and use those to color the white nodes. Use the remaining numbers for black nodes.
How to solve problem B ?
I thought of a O(n) solution but couldn't solve it.
Then I later saw that that n<=1000. By that time 1hr had already passed so I gave up :(
find the
1s that are in the wrong place.This was my idea of D —
First, the condition u^v<=min(u,v) meant we can only go from u to such v that their MSB is in same position. Eg 4 to 5 ,6 ,7 etc. Then we need even path lengths (length = no of edges) to make those nodes optimal. After this I was kinda stuck. Is this approach correct?
P.S I liked C. Nice observation required.
rip rating -122
spammed 1.5h on C and wrote a BIT and a monotone stack. nothing worked so I got frustrated and started writing garbage. HA HA HA HA HA HA!
I tried to submit some curse words but the contest ended :(
good problems though. My bad. D was pretty okay, but I didn't solve it on contest :(
I abandoned my ape instincts and spammed submissions.
Loved problem D !
what a problemset. take a bow lord Ashishgup
Question F is so strange that I thought of three false algorithms!
And now i have delta -108 instead of -3 :(
sad :<
orz
When will the explanation be available?
Can we use binary search in problem C?
int l=1,r=n; int mid = l + (r-l)/2;
Iterate over string to find if there is a valid substring having length mid. If this condition is true, then right = mid-1 else left = mid+1;
Will this approach work?
No binary searching won't work. You can consider S = "aabbaa" for example. Substrings with length 2, 3 or 5 that satisfy the problem conditions exist, but there is no valid substring with length 4. The key to this problem is observation: The smallest possible lengths are only one of [2, 3, 4, 7] or -1 if there is no valid substring.
I didn't take that meme serious, and then...
Really nice D.
Congrats on CM!
lol
Sums up my today's contest.
...
Problem C Editorial :- https://www.youtube.com/watch?v=EWhmvHCB19k
Problem C was a mess
if you couldn't solve problem C it doesn't mean it is a mess
Problem A should be rated at least 1200. Even though it's a one liner it takes a lot of effort for beginners to deduct the answer. Especially with weak mathematical background. Some of the 1200 problems are easier to solve just by working through the problem. The problem is very good but it should be rated properly. It's definitely not 800 and 900.
I had the correct solution of problem C when I saw it last night. However, due to some mistakes on coding, it took me one extra hour to work it out, which made my rank only 3000+, I should have been in the top 1500 :(
Thank you so much for making this round, really enjoyed competing.
WA on pretest 2 was my close friend in this contest. I don't know why it didn't leave my side.
I want to know what the difference is between these two WA and AC
please help me
Thanks for such a competing contest :D
Problem D was nice I really enjoyed it while upsolving but it doesn't seems to be a 2100 rated problem