Haiii Codeforces ^_^
Note the unusual starting time. This round starts 30 minutes before the standard starting time.
vgoofficial and I are extremely excited to invite you to Codeforces Round 979 (Div. 2) on 19.10.2024 17:05 (Московское время). You will be given 7 problems and 2 hours and 15 minutes to solve them. One problem will be split into two subtasks. This round will be rated for all participants with rating below 2100.
This round is based on... absolutely nothing.
We would like to mention the following individuals for making the contest possible:
Our coordinatorz satyam343 for his active and insightful coordination once again. ORZ!!!!
Our testuwuwuwuers for their efforts in improving this gramazing contest: nifeshe (VIP tester), Thienu, Anonymous_Noob, Dominater069, A_G, Everule, LipArcanjo, omeganot, MridulAhi, 18o3, Edeeva, IceKnight1093, andrewtam, JagguBandar, LMeyling, Intellegent, valeriu, aryanc403, awesomeguy856, kingmessi, amoeba3, golions, unalive, alexlikemath007, fishy15, Vladosiya, NovusStellachan, CutSandstone, chromate00, ntarsis30, Non-origination, redpanda, Lilypad, kevlu8, MatthewC3297, mathtsai, jcai972, and our honorary newbie tester tibinyte.
Alexdat2000 for translating the statements to Russian.
The most jacked user on this list, MikeMirzayanov, for developing Codeforces and Polygon.
Score Distribution: $$$250 - 500 - 1000 - 1500 - 2000 - 2500 - (3000 + 1500)$$$
As an author, I hope you like orangutans.
yes... I do...
As a tester, I can confirm that the coordinator satyam343 coordinated.
As a tester, I can confirm that problems have non-negative no of test cases.
Zero test cases??
As a tester, I can confirm that all problems have atleast zero test cases.
As a tester, everything can be negative.
just like my contribution
Or my Delta post-contest.
As a contestant, I can confirm that being a newbie and giving contests is sooooo damn hard but i solved a problem on my first contest, hail yeah!I feel like flying man.
Rating distribution?
Thanks for the perfect contest.
This round also follows the trend. Unusual starting time without specific reason and follow-up score distribution. It's consistent.
unusual starting time so people have time to eat lunch before meta hacker cup
We code on a full stomach — we code with full force!
and score distrib out now
Great way to practice my regional ICPC round, which starts only 7 hours after this round. Good luck everyone :)
There's meta hacker cup too just 1 hour after it ends
Oh wow, love it but I'll have to stay awake till 3AM in my time zone and compete in ICPC at 7AM. Not so sure what to do...
Maybe try sleeping extra previous day :D
Factually speaking, it's not "regional" but "provincial". At any rate, good luck.
Man, I miss the good old days...
Yeah living the days now, thanks for the correction!
satyam round.i am cooked :)
as a participant, good luck to all :)
I bet this round is based on Honkai: Star Rail :D
Lose the bet and I lose rating :(
aventurine reference?!?
Let's hope my rating won't decrease this time
If I don't reach expert level in this round m gay
If I reach expert in this round m gay
If you don't reach expert in this round r gay
Everyone except Champaklal is gay.
Haha
...
M getting +30 delta so its fine
Sa7a wa7ch
That was a close one, congrats bro.
after getting destroyed by educational round hoping to get good +ve in this round gonna grind hard in VCs and problemset
I was getting to green which I'm actually dying for and then the system tests on B destroyed me
nt bro u will reach green in next div2
thanks good luck for you too, this time if I managed to to solve a b c I will not look at any thing else and I will just check all my submissions because I need to reach pupil for my well-being
As a tester, i think orangutans are very beautiful.
As a tester, that is concerning. Seek help.
what?
uwu owo round
Are you impressed?
As a first-time tester, I learned a lot from testing this round!
How to become a tester $$$??$$$
The best part of a cry round being announced is the emoji :) (and of course the round, cry rounds are the best :D)
I think I will solve 3-4 problems..
In problem B, why cant we take the first x biggest numbers, subtract the minimum, then add it to the answer?
Try this testcase: 4 1 2 3 5
Vote me down, if you think I will return to the specialist after this round.
Wow, 250 score problem.
as a participant, i am monke.
As a participant, I confirm that all the problems have inputs and outputs.
How can you be sure?
hope that I could become expert :-D
So many IM's, M's and GM's are testing this round :)
as a participant, good luck to all :)
yup
good luck to all:)
Another cry round!
What does "ORZ" mean?
A person kneeling on the ground
U can use this word like "sto somebody orz",it looks like two persons are worshipping somebody.Isn't it fun?
genuine question — how are scores for problems chosen? does the score indicate difficulty of problems with respect to each other?
shameless plug
Finally, a cry contest!
How to become a tester?
Pookie Gorila... xd
Is it rated? I AK IOI.
I'am JCed?
If I don't reach pupil after this contest, I will eat shit.
Did you eat? :)
:(
I can feel the pain bro...
seems kind of unfair that orangutans can't participate in the contest due to being too high rated
As a monkey tester, I have made sure no orangutan attacks you during the contest.
I'm so happy I can take the test on my birthday! It would be better if I pass as many as possible...
This is going to be a great Saturday!
First ABC contest on AtCoder, then Codeforces round in 25 minutes, then Meta Hacker Cup Round 2 in 40 minutes.
In total it's almost 7 hours of coding. Good luck to everyone!
This comment literally gave me goosebumps. Let's go....
testuwuwuwuers
If I can't reach Expert in this round, I'll play Distorted Fate AT16 until my accuracy reach 99%
Wish you have fun :)
lol I'm so unfortunate. But I've just reached 99.67% for the new AT16 instead, hope the both challenges are equivalent on difficulty
I have never solved E before, and I hope to solve E this time :D
Vladosiya fan = me
I have registered for tomorrow's div1, what if I lose rating points in this one and become expert, will I be able to give both div1 and div2 simultaneously tomorrow?
1 WA is 20% of problem A. is this not just bad scoring? why not multiply everything by 2?
Maybe becase problem A is easier than usual div2 problem A's.
$$$1$$$ WA is $$$20\%$$$, and most people will resubmit it (As it's the easiest problem). That's another $$$20\%$$$.
As a participant. I'm going to drink and drive if I don't reach 1000 in this contest.
So this is a div3 contest! Did everyone feel the same?
well it was the worst contest for me.
it's not it's how lucky you are today
no
OMG i don't know what is wrong with my C
us
you start from the end to the beginning and the edge case was when the first number is 1, so if alice reaches the last 2 numbers you check if the first one is 1 too, because 1|0 is the same as 0|1
same, wasted 1.5 hours figuring out what was wrong
think greedy , just 2 cases 1. if 2 consecutive ones then Alice will put an OR between them 2. else if any of first or last is a 1 then Alice will put an OR next and before it respectively.
OMG i thought we had to put or's and and's sequentially!! i did not read the test cases's explaination.
for me it's B cost me ~ 90 min to figure what's wrong in my solution... and a tons of WA (painful as hell)
Bruh Does D need that much coding? I got the idea of the solution more than 1 hour ago, but still didn't finish implementing it.
segment tree to get min max range queries. every R that has L on left and right is where a new loop starts. check if minimum of a loop is lower than the maximum of the loop before it and it is then it's not possible to make non decreasing, but I didn't know how to store the results easily.
I had to create sets to min and max of each loop and update them with each query, but I was slow in doing this. was there an easier way? or am I just wrong about my idea
Same idea
p does not change so precalculate d[i] = max(p[1],..,p[i]).
if S[i]=='L' and S[i+1]='R' then it is only possible to sort if d[i]<=i.
On the permutation, only the intervals $$$[L,R]$$$ such that $$$\min(p_L,p_{L+1},\cdots,p_R)=L$$$ and $$$\max(p_L,p_{L+1},\cdots,p_R)=R$$$ matter.
Meanwhile, on the string, only the intervals $$$[L,R]$$$ such that $$$s_L s_{L+1} \cdots s_R = \mathtt{"RRR}\cdots\mathtt{RRLL}\cdots\mathtt{LLL"}$$$ matter.
I hope you can figure out the rest yourself.
I had pretty much the same idea: Get the positions of 'LR' and find the minimum/maximum between such positions (using segment tree) and check if minimum = 'L' index and maximum = next 'L' index. This was indeed an implementation-heavy problem and required storing/deleting information into sets.
same, I was searching for another idea because I knew I couldnt implement this one (also you have to use binary search to find which segment you are changing and there are also some cases)
We should have the similar idea, and I spent a lot of time implementing it. But after that I realized there exists a much easier way, we just need to keep track of the min/max value on the left/right side of each
LR, and since the array itself won't change, it can be done quite easily with some precalc...damn that would have made it much easier
i dont use sets or segment tree, its can be simplified alot
Animated Video Editorial for the Contest! The video editorial has problems [A-F].
Link: https://youtu.be/CpSIK4YPi00
I've spent almost all of my free time for the past 5 days doing this and it came to like 1.5k lines of manim. I think I could have done more if I more time, but I hope i will improve for the next one.
studying.
today C is extremely familiar with this 1988B - Make Majority
How so? I believe it is quite different.
both problem can be solved by if else a few cases and edge cases. i.e. find '11' or if start and end with 1 or a few cases...
In my perspective, both problem have 1 same alternative solution: Count 1 and groups of consecutive 0, then compare them to have the final result.
I copied my own code and change the last condition and AC.
To make C exactly like 1988B, make Bob go first instead of Alice and n>=2 in both problems, here you go.
Except implementation is not the only part of solving this problem.I’m sure nobody had trouble implementing the problem as much as they had trouble seeing the relevant observations. And I have no idea what you’re talking about regarding having Bob start because that’s definitely not the same problem. Just because having 1’s at the beginning or end is relevant to both problems doesn’t make them “very similar”
ok I'm just being naive... I apologize.
can anyone share their solution for D?
Consider positions where we have LR in the string. They basically split string into two independent segments that must be good: sortable and in the correct position. Keep segments in a set for splitting\merging, check if a segment [l; r] is good by querying min and max on it, min should be equal to l, max to r.
I see. So, if I may ask, how did you handle the min max queries?
sqrt-decomposition
a string of $$$L, R$$$ is good if and only if for any pair of adjacent $$$LR$$$ to the left of $$$L$$$ every number is > than every number to the right of $$$R$$$.
if $$$s_i = L$$$ and $$$s_{i+1} = R$$$, you can't swap them which means that the subarray $$$[1,i]$$$ should be a permutation of length $$$i$$$. you can check this using XOR hashing and storing the invalid positions into a set and the answer should be YES if the set is empty
Gotcha. So, in terms of implementation, it is kinda similar to the C2 from a few contests ago, right?
IDK which problem ur talking about but this is the implementation I did
You can see my implementation too,i didnt use anything fancy.
as someone who failed to implement the C2 from a few rounds ago, and managed to implement this one, i think it's much simpler, and you can check my solution for details. You don't need sets or segment tree at all, and it actually is kinda clean if you do it properly.
This is how I did it. This is the 1st time I solved a D problem in contest :)
I am so proud of my submission 286812781. Though it gave me 4 WA's
Huge difficulty gap in C to D ? or skill issue
And huge difficulty gap in D to E.
can confirm spent whole content on E with no avail.
Hey, for today's D I keep getting TLE, my idea is slightly different from the intended but the logic is the same, could someone spot the mistake/correct me, I do not think my constant factor is THAT BIG: TLE CODE
My submission for E (286816083) does a very weird thing. When I run all samples together, it gives the right answer for the first sample and wrong answers for all subsequent samples.
BUT if I run every sample individually, it gives the right answer for each. I want to kms because I believe I have the right approach but cannot debug this bullshit runtime error.
E is a beautiful task though.
I'd be grateful if someone can point out what undefined behavior in my code causes this torturous semantic error
you initialize new variable mx in the for loop instead of updating existing one
to expand:
ll mx=min(mx, ct[i])uses uninitialized value of mx, that's why you get inconsistent output. I found this by compiling your code withclang -fsanitize=memorywhich when running the program points out uses of uninitialized valuesughhhhh I'm going to kms 😭😭😭 Thanks for finding the error. AC now 286829682
On problem B, my O(n) solution time limit exceeded when I used PyPy (https://codeforces.net/contest/2030/submission/286728378) and got accepted when I switched to Python (https://codeforces.net/contest/2030/submission/286730019). I've encountered this problem before, but never during a contest (got -50 pts because of this). Usually, PyPy is faster, so when should I use PyPy, and when should I use Python?
fix the link, I can't read your submission
that's because the contest hasn't been judged yet — I think the same is happening to other links as well
Strings are a bit weird in pypy. Never use += since it is not appending to that string but creating a new string making it O(n).
ooh, that makes sense, tysm!
thanks for helping me understand the meaning of cry once again :)
Nice contest. Loved the thrill of solving D with last 4 mins left.
great problemset.
nice problem D.
every time I enter a div 2 contest except the educational ones I regret it so much because of problems like B I couldn't solve C but at least it's not guessing problem like B why these kind of problem is only here in codeforces div 2 and not anywhere else on earth
it has a pretty simple proof tho
you need to guess the answer and then proof it I prefer 4000 rated problem in div 2 B instead of this one
yeah, i see your point. But pattern recognition/deduction is also a constructive skill no?
I thought f(t) was the number of subsequences that included exactly one zero and any number of ones I just realized it's just zeros
I don't even guess but it cost me 2WA 1TLE to complete the problem (I brute force all the way to see the 1 "1" is optimal)
But the problem B change in the middle of the contest really mess with my mind (prolly cost me ~ 15 minutes of confusing and get back to track). Also I'm late 20 min because of my own careless...
its a simple observation, not guessing at all
today I read B and C completely wrong that's why I was frustrated but it's my fault yeah you are right it's not guessing
Partial solutions:
A: Put min and max together therefore from i = 2 to i = n. Max(i) — Min(i) is max of array minus min of arrray. Answer is (max(arr) — min(arr))*size(arr) — 1).
B:
Answer: put one 1 anywhere in binary array. (I put in front).
This is because half of all subsequences contain that 1, the other half do not(including the empty subsequence). Therefore, the oneness of the array is |half of all subsequences(the ones with the 1) — (half of all subsequences w/o one — 1(because the empty subsequence is ignored). Since, the amount of subsequences that are nonempty is odd (2^size of array — 1). A oneness of one is the minimum oneness we can achieve.
C:
Alice has a winning strategy if
a) The beginning or the end are 1 in which case she inserts an OR surrounding that. This will make the final result 1 because 1 OR x/x OR 1 = 1. and all ANDs are precomputed, before any of the ORs are.
b) There exists two ones attached to each other.
Initial — 00000011000000 Alice move 1 — 0000000 OR 11000000 If Bob does 00000000 OR 1 AND 100000000 Alice responds with 00000000 OR 1 AND 1 OR 00000000. If Bob does 00000000 OR 11 AND 0000000 Alice responds with 0000000 OR 1 OR 1 AND 0000000. By turn three Alice has surrounded 1 or 1 AND 1, which evaluates to 1 with ORs, so therefore a sequence of 0s and 1 is gauranteed to OR with 1, and so the result is 1. Therefore, Alice wins.
All other scenerios Bob wins.
D:
Key Insight 1: If we see an LR we cannot push any element left to L to a position right of R.
This is because L allows swaps from (L and L — 1), while R allows swaps from (R and R + 1). All things past these two canot impact either position.
Key Insight 2: Try to divide permutations.
Take 1 3 2 5 4 , imagine it as 1 | 3 2 | 5 4. Now, considering insight 1, what must be true to allow this permutation to be sorted? Answer: The must be no LR is positions 2/3 or 4/5 LLLRR is fine as no element from the first three positions needs to move to the last two positions but LLRRR is not because now 2 and 3 cannot swap.
Computataion: Maintain a max seen for first k items in permutation, if k = max, then we have the division between new blocks. Store all divisions between blocks.
Then, create an array from 0 to n. If we see an LR, where LR does not stradle over a division of blocks, then arr[L] = 1, else arr[L]=0
Now for queries, if sum(arr) = 0, output YES else NO [Note: we can store sum as a variable as only two thing in array can change each query]. We input the query(Q), flip the bit, and check for LRs in block immediately to the left and right of Q, and update arr[Q] and arr[Q — 1]. sum -= old(arr[Q] + arr[Q — 1]). sum += new(arr[Q] + arr[Q — 1]).
thanks for the contest, really enjoyed the orangutan questions
Can someone please provide me the answer to D, during the contest i tried but couldn't solve it
D:
Key Insight 1: If we see an LR we cannot push any element left to L to a position right of R.
This is because L allows swaps from (L and L — 1), while R allows swaps from (R and R + 1). All things past these two canot impact either position.
Key Insight 2: Try to divide permutations.
Take 1 3 2 5 4 , imagine it as 1 | 3 2 | 5 4. Now, considering insight 1, what must be true to allow this permutation to be sorted? Answer: The must be no LR is positions 2/3 or 4/5 LLLRR is fine as no element from the first three positions needs to move to the last two positions but LLRRR is not because now 2 and 3 cannot swap.
Computataion: Maintain a max seen for first k items in permutation, if k = max, then we have the division between new blocks. Store all divisions between blocks.
Then, create an array from 0 to n. If we see an LR, where LR does not stradle over a division of blocks, then arr[L] = 1, else arr[L]=0
Now for queries, if sum(arr) = 0, output YES else NO [Note: we can store sum as a variable as only two thing in array can change each query]. We input the query(Q), flip the bit, and check for LRs in block immediately to the left and right of Q, and update arr[Q] and arr[Q — 1]. sum -= old(arr[Q] + arr[Q — 1]). sum += new(arr[Q] + arr[Q — 1]).
Was the server also unavailable to you for the last 15 minutes before the end and for 15 minutes after the end of the contest? I was only able to connect to m1.codeforces.com but not to the main website. Something needs to be done with stability of the service.
Nope, worked fine except the usual cloudflare human check in the beginning.
Maybe I'll become pupil today
Difficulty guess
A:800
B: 900
C: 1400
D: 1800
E: 2400
I did not attempt F/G1/G2
damn D was really hard still 2k+ submission I think I have skill issue
i think C is 1200 at best, its a stupid observation that anyone can make. D is also 1800 only because implementation, but i think the idea itself is 1600 at most
I put C higher because it is easy to miss the observation or take more than one try (as I did).
I still didn't got the idea of D can u help me out in that. While C's idea was stupid but was definitely tough to make so I think it can be 1300-1400
I think E is *2200 and F may is *2300.
UPD: I think G1 is about *2600.
https://codeforces.net/contest/2030/submission/286828473
I thought a little different for problem D but idk where it's going wrong. The basic intuition is the string should be of type R*L* (RRR...LLL). So, I stored the indices of L and R in two separate sets. If highest(SetR)<lowest(SetL) is true, answer to that query will be True. And if the array starts in correct order (1,2,3..) I neglect those indices, same as for ending (..n-2,n-1,n). I'm unable to understand why this approach isn't working?
Anybody solved F with Merge Sort Tree?
Yes
I'm not able to find the case where this code will fail. can anybody help here?
https://codeforces.net/contest/2030/submission/286836896
used prefix and suffix arr instead of segmented tree it passed :D
Thanks for the problems!
I think the difficulty from C to D was huge. From a few lines to a heavy implementation
Edit: well it seems it's much easier to implement than I thought .
Hello,Mike.
I'm using my friend's account,and w2y51c318 is my account.
In this contest,I used WrongAnswer_90 as my secondary account to take part in,and my two accounts:2w51y318c and WrongAnswer_90 was both banned.
I feel regreted to break the rules,and register a new account w2y51c318.I used it to participate in this contest and got rank 1.
I thought everything was in the past,but when I was enjoying today's contest,I got banned again.
I do not use any other account,and w2y51c318 is my only account now.I feel confused about being treated like this.I just wonder if you just mistakenly banned my account.
https://codeforces.net/contest/2030/submission/286859205 i really need some help with my code,i cant find where is wrong.problem D
Good start time!I don't need to stay up late!
This was yesterday bro.
Once again,I become the joker :(
wrong post
I received a notification about my solution for[problem:2030A][submission:286757203] being flagged for similarity to other users' solutions. I would like to clarify that the similarity might have occurred because a friend and I are part of the same training group and often practice together. While we did not copy each other's code, we may have developed a similar coding style due to our training sessions. I understand this could have caused the solutions to appear more similar than usual.
Please note that my submission was written independently, and I did not engage in any form of plagiarism or code sharing during the contest. I am happy to provide further details if necessary.
Thank you for your understanding, and I look forward to resolving this matter.
Best regards,
Hello,
I am writing to express concern and to appeal the recent decision on my submission (plvzfq-rit/286815457) for Problem 2030C, "A TRUE Battle," and sravani_k29/286809003. A system message was sent and notified me that my submission was flagged for being similar to sravani_k29's. While I do understand that this is being done in an effort to keep the competition fair and honest, I would like to humbly ask for your kind reconsideration in this matter.
Upon taking a closer look, it seems to me that my submission is similar to sravani_k29's since the problem seemed to be quite simple, and that we shared a common simple approach to solving it (considering the editorial for this problem). It does not also help that Python (the language we both used) lends itself to creating simple scripts. It is also unlikely that I have copied from sravani_k29 since I do not know them. In an attempt to add further proof to my claim, attached are screenshots of the digital scratch work (with date) I have made during the competition for this problem:
To explain my scratch work and thought process, after failing my first submission wherein I had falsely thought that there was a property based on the number of 1's and 0's, I decided to create a binary tree showing possible outcomes if one were to add a 0 or a 1 to the end of the parent string. From there, I had evaluated each possible case up to cases with length 4. Seeing that starting with 1 was conducive to Alice's success, I decided that it was a sufficient condition and went on to investigate other successes when the string started with 0. Lining them up in a column and evaluating them again, after some time, I saw that if the string were to end in a 1 or if it were to have a 11 inside it, then either would also be conducive to Alice's success. This then led me to my solution.
Hoping for your kind reconsideration,
Sincerely,
plvzfq-rit
Embarrassingly removed my old blog post since I found this was the way to go
Dear MikeMirzayanov, please investigate this matter. Thanks.
Regarding the issue of my leaking code on a public platform, please take a look at this. https://codeforces.net/blog/entry/135438