Good Day Codeforces!
Me and Tsovak are happy to invite you to take part in Codeforces Round 972 (Div. 2), which starts on Sep/14/2024 17:35 (Moscow time). You will be given 5 problems and 2 hours to solve them. Two problems are divided into two subtasks.
The round will be rated for all participants with a rating lower than 2100.
The problems were authored by me with Tsovak's help to solve and alter them.
We would like to thank:
TheScrasse, Kaey for wonderful double coordination and chess skills.
Alexdat2000 for Russian translation.
turmax, BurnedChicken for nutella testing.
physics0523, Andreasyan, Arayi, zidder for red testing.
FelixArg, _LeMur_, _RedWine_, Error_Yuan for orange testing.
c2zi6, GaGeV, alex_2008, CyberCow, kHarsh3715 for purple testing.
chromate00, Kalashyan, dilanyan, WorldBias, JuicyGrape, vikram108, China001, Doctor_Strange_ for blue testing.
syegoryan, Arpi2007, Matsak, Gurgen_Melikyan for cyan testing.
ishaandas1, _supersonic_ for green testing.
gvardanyan062, Binary_Thinker for grey testing.
tibinyte2006 for colorblind testing.
MikeMirzayanov for the great platforms.
Vinton Cerf, and Robert Kahn for inventing the internet.
You for participating!
Score Distribution: 750 — (500 — 500) — 1500 — 2250 — (1500 — 2000)
UPD1: The Editorial is out.
UPD2: Congrats to the winners!
Div.2:
Div.1 + Div.2:
On the left, you see Tsovak with TheScrasse at IOI 2024.
On the right, you see me with Tsovak at IOI 2024 (I Owe Ice Cream 2024).
As a tester, I
codeforcessniper
As a colorblind tester, what color is your Accepted?
As a tester tested long before, I should recall the problems to my memory.
As a tester, I toasted the round.
orz kHarsh3715
orz kHarsh3715
As his junior, I can confirm
Does this mean C will be super harder compared to B2 ? C ~ E1 ???
or maybe E1 will be much easier than usual
Both of you are correct XD.
Finally a contest after a long time .
11 days!
after ages...
As a tester, I tried to get accepted with some shitty solutions.
nutella testing is crazy!
Why don't it also be Kinder testing :)
As a tester,I recommend you to read all problems
orz
As a contestant, BiNARyBeastt and Tsovak orz.
This is the first and last div 2 round in September... Looking for more!
Hoping for a Div3 or Div4 round soon after this contest
After a long time...
This one will be cool :D
Who is Tourist tester?????
That's a vacancy filling no time soon. :')
BTW I saw tourist appearing on the list of ICPC 2024WF judges.
"for wonderful double coordination and chess skills" back story?
I wish I had something cool and interesting to say, like we fixed a problem using our chess skills, but I don't, lol. Scrasse was just playing in a chess tournament during testing, and I used to be a professional chess player, so I found it interesting and asked him to play some games with me.
As an IOIer, it's sad that I didn't know TheScrasse was in IOI
Oh, subtask in problem B! It must be interesting!
For tourist: You for participating!!
Score Distribution: qinmingze-(jiayiGood-applepear)-asy_01-Alexey-(Yulianleaf-Yummisonflorita)
Yile_Wang's rating went down
fixed
I was stalking the writer of this round, BiNARyBeastt. I found out that he has skipped submissions in two of the past two contests.
Does he cheated in these rounds $$$??$$$
Yeah, it seems like he did
So allowing a cheater to be a problem setter $$$??$$$
It is safe $$$??$$$
Idk, I wouldn't have done it personally
Well, it was a long time ago. Not that it makes it better, but still I've participated in many rounds after that without being skipped. After checking, they are for using an alt account.
the "You" written in Legendary Grandmaster Style. When it will be true...
Remove or ban this person who posts adult photos because school Children less than 18 years of age are also practicing on this site.
I was in the middle of a class when I scrolled through the comments...
I think problem A will be harder then B1 and B2
You never know...
technoblade never dies
crazy speedforces it is
Great to see no more sex images!
As a tester, I can guarantee that you'll enjoy this round, ceteris paribus.
orz kHarsh3715
First time for me. I just started CP does it make sense to participate?
of course. div 3 and div 4 rounds would be best for you, but I'd still recommend participating
As a tester, I have many questions (perhaps about how to deal with the AI situation). Probably too many.
A contest after so00 long but clashing with leetcode biweekly
codeforces >>>>>>>>>>>>>>>>>>>>>>>> leetcode
Yess I know but still giving both the contest will always be better then participating in one
The score distribution of this contest is really unique!
Just like the authors lol
That's cool!
can anybody explain what is sub task?
It's essentially the same problem presented twice, with differences in constraints or maybe some other special conditions. All of these differences are mentioned at the beginning of the problem. Check Codeforces Round 961 (Div. 2) as a reference.
this round going to be wild, new version of GPT available for first time in rated round in CF
Where are these rankings from?
Is it rated????
No .
Why am I unable to register as unrated participant?
wish to cross 1800 rating today
"I Owe Ice Cream 2024", It's cute.
Link
Sharabi Lal is cheating alongside 100 live cheaters
Username: kya_b120
Please take action
Bhai pr as per this link eska to a bhi solve nhi hua:)
Why is B so confusing? If a teacher is at cell 1 and David is at cell 2, then the teacher moves to cell 2 and David moves to cell 1, does that count as getting caught?
That cant happen because then the teacher would catch david
I mean intuitively if we picture a teacher catching students irl sure but the question still needs to be more specific.
I can see where the confusion is coming from; they probably should've clarified that David being on a teacher's cell after either half of the procedure would lead to him getting caught just to remove all ambiguity from the question (David moves -> check catch condition -> teachers move -> check catch condition -> David moves ->...)
first moves David, then teacher. David moves first and he ends up on the same square with the teacher and the game ends
The teacher has an option to not move at all. So if David is going to move to cell 1 then the teacher will not move, whereas if David is going to not move, the teacher will move to cell 2
Yup just thinking about some parts of C and E1 solutions without any close full idea. just gonna eat popcorn and watch my rank go down.
cout.tie(NULL);????????????????My thought exactly
I'm not going to use ceil() function in my life ever again.
dp forces
exactly and some dp time limit for C xD
that good hoping for more FST so maybe i be CM this round :o
one of the Worst A in cf history.. could be the worst(est)
It worths 750 points, so it is expected to be harder than normal
what is the solution for A?
First, notice that you can avoid making palindromes by greedily making the string as "aeiou" repeating (Which is "aeiouaeiouaeiou...").
But in this problem, a palindrome can be formed by a subsequence, so there are also palindromes that can be formed by characters that are in between 2 similar characters, like "aea", "aia", "aoa".
So the second thing to notice is you can move all letters 'a' next to each other, then all letters 'e' next to each other, and so on. Now just print the string in this order and it is the correct answer. (Obviously you can't avoid the palindromes that are of the form "aa", "ee", "ii" so this is the optimal answer).
first observe that if we place similar letters apart then, we would be increasing the number of palindromic sub-sequences. Hence, we should present similar characters together, also observe that we should have many different characters as possible with lower frequency. So, at first distribute the powers using n/5 to each, then remaining would be n%5 which would be given only to the characters with i<(n%5).
got 5 WA for me it still 400
is C standard problem? how to be good at problem like C, I've been staring problem C for 90mins and still have 0 clue 😥
You can begin to understand this problem by observing what the answer for the case with N-1 strings means for the case with N strings. Problems like such generally are solved using DP. Try to understand what concatenating a new string to the end means for the final answer.
Problem C is dp, right?
yep
B ruins my mood for other problems (I sorted the teachers' position BEFORE accepting the input)
cooked
This was LITERALLY THE MISTAKE I DID. To top it off, after printing the answer I was returning the function instead of using continue, query question disaster :(
At one point I thought if 2 teacher move at the same time, it will add 2 instead of 1 for the final answer :)
Oh my god C took 100% of my brainpower, just logged off after solving it
why did u steal David's homework-?! sobs
genuine question and why are they chasing David instead of searching for his homework?
Again this happend
True,dude
Anybody got tips or good problems to help train for math questions like B?
B1, B2 are simple Binary search, to find the lower bound, thereby finding in which part david is 1. start-first teacher 2. in between two teachers or 3. teacher — end
:joy: problem C was a lot of fun
ruh roh
So many people getting fisted on C now, holy
Yep, should've just attended the Leetcode round today.
Can someone tell me what is wrong with my C submission?
The idea is that each string has "type", which is the ending it can be completed to. So na = type 1, naaare = type 4 etc.
Then I use DP[i][j] = the best composite string you can get of type j, using the first i strings.
In each DP[i][j], I store the string itself. But because those strings can get quite long, I remove the "used up" characters, and keep track of the "total score" of that string, and the "hidden score" of that string.
https://mirror.codeforces.com/contest/2005/submission/281250930
I really feel like this should make sense, but for some reason my code get WA on testcase 2.
If the final answer is of type 4 for example you need to substract 4 (because of the last 4 letters cannot be counted)
try
expected 1, your code output 2
can you tell me why my solution is wrong https://mirror.codeforces.com/contest/2005/submission/281211695
E1 is easier than C
For problem B, Am I the only idiot who took that b1<=bi<=bn would satisfy throughout. Apparently it doesn't satisfy this condition. I solved b1 in 13 minutes, but due to this dumb error, I made 6 wrong submissions before finally figuring it out
same bro same I though array will be sorted always due to which I made 4 wrong submissions
DP in C was harder than the DP in E1 for me
what to do in A and C . Plz expalin senior coders
in a , i guess u needed to eliminate this kind of palindrome "aea" etc .. as aeiouaeiou will have this palindromic subsequence but aaeeiioouu wont have , so just repeat this vowels sequence till < then sort the string in the end
i think for n==6 both "aaeiou" and "aeiouu" should work
similarly for n==9 both "aaeeiioou" and "aeeiioouu"
Am i wrong?
yes
then why did i get WA on this submission 281241976 i know the approach is not very good , but it does the exact same thing .
can u tell me some test case it fails
this string at the end in if(n%5) is not sorted
Why they need to be in sorted order ?
read my first cmnt all same character should be together
refer this https://mirror.codeforces.com/blog/entry/133206?#comment-1198302
(sorry my English is poor.) I have a question: if I submit once before, and past the pretests, and I submit a new code later, as the rule says, I will get -50 scores, but when I viewed the standing during the contest, my score of E1 changed from 944->802, and my rank fell nearly 100rks. Is this normal?
But you also resubmitted the problem 14 minutes later which means you got a lower score for the problem in the first place in addition to 50 pts penalty.
when you submitted second code.it will -50 during that time score.like your first code get 944.bt when you submit 2nd code that time the score was 852.That's why you got 802
Beautiful problems! I expecially loved C and E1. As and OI-style enthusiast I loved the subtasks :)
Even with this reminder in the statement of problem C, I still forgot to handle this case ;)
(Maybe)Worked out E2 after contest 3 minutes, and lost 900 pts.=(
What wrong in my recursive dp solution for C 281249632
AryanDLuffy likely cheated using GPT for this contest, look at his submissions and compare to previous contests. His template and coding style completely changed. Also he solved E1 in 8 minutes while writing like 50 lines of comments that a human would never do and somehow failed B2 at the same time.
Kinda funny how in the very first contest that applies the strict rules of using AI tools, he is using it so blatantly lol.
misunderstanding of problem C makes my contest to be interrupted, feeling sad.
Crazy contest. I solved A, B1, B2 and somehow still got expert performance.
Why u can't go beyond cm
because i have skill issue
Can someone please help me understand why I got TLE on B2 on this submission?
https://mirror.codeforces.com/contest/2005/submission/281216208
Since your
vis aset, you must usev.upper_bound(Notupper_bound(v.begin()...)) to achieve logarithmic time complexityFor why
upper_bound(v.begin()...)isn't logarithmic in this case, you can refer to this link (On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.)Why did my E2 solution get TLE on TC24? My solution complexity is O(n * (m + l) * log(n * m)). Is std::map too slow or do constraints of the test cases and statement contradict?
My submission: 281237867
I would be delighted if somebody helped with my problem.
I'm not sure, but what if $$$\sum n = 3\times10^6$$$ and $$$m$$$ is very small among all testcases? Looks its time complexity will hit $$$1500\times 3\times 10^6$$$. I believe
if (n > m) swap(n, m)will resolve this issue.But the sum of array lengths across all test cases is bounded with 1e3.
Yep, but there's no constraint on $$$n$$$ and $$$m$$$, only $$$l$$$ and $$$n\cdot m$$$.
from the problem statement
No,in the statementsays that n and m is bounded by 1500 for each testcase.
Yeah but I believe there could be more than one testcase?
According to the statement sum of L is at most 1500 so it is impossible that my code executes 1e6 operation in each testcase.
Yep $$$\sum l$$$ is small. But according to the statement, $$$\sum n$$$ is at most $$$3\times 10^6$$$, not $$$1500$$$, as $$$m$$$ can be $$$1$$$. It's true the math expression of constraints in the statement is a bit confusing tho.
I couldnt got your point. So you say that my solution gets tle when T = 1e3 and for each testcase N=1e3,M=1,L=1. Still my code executes total number of 3e6 * log(3e6) operations and it shouldnt get TLE. You can also check my submission history.
it's super interesting to see it failed on $$$n,m,l=1500$$$..If so, I guess it may indeed be a
map's issue and the TL is too tight. I constructed the data and found your code takes ~2300ms at that case on my local computer. That's really close! :(Oh no :(( Did I get TLE only because of the 300 ms extra? It is pretty sad to hear. Btw, I changed the array of maps with only a single map and it has got AC now. I could get many more plus delta :( Anyway, thank you so much for your help :blobheart:
You are correct. Swapping solves the issue of time limit.
There are 3 constraints in the E2 statement. Constraint 1: N,M,L <= 1500 for each testcase. Constraint 2: Sum of N*M over all testcases is at most 3 × 1e6. Constraint 3: Sum of L over all testcases is at most 1500.
I think you should check the testcases of E2.
In problem B I thought teachers and David moves at the same time, and was solving this version of problem), and it was quite annoying version of the problem)
but they do move at the same time right? if n = 5 and teachers are at 1 and 2 and david in 3 then david will move to 4 and teacher at 2 will move to 3 at the same time making the ans 5 -2 = 3 right?
No, Statement says David moves first, and only after David moved Teachers will move.
Yeah but does that make any difference? I mean they are at distinct cells in the first place..so whether david makes the first move or they make the move together the scenrio is same cuz at one point teacher and david will take position side by side and david cant move and the teacher will make a move and catch him
it makes very big difference.
consider the case:
teachers positions = [2, 100000]
David's position = 1
and if teachers and David moves at the same time:
so we will have to wait for second teacher in position 100000, to help us. So it's very important to know for teacher if either David moved or stayed, and u can't know that if they move at the same time.
David will move first, and upon that move, the teachers will move optimally to catch him
so, with your test case, if David moved (to the only cell he can move to, the cell 2), the teacher in the cell 2 will stay in that cell and catch David
and if David didn't move, then the teacher in the cell 2 will move to cell 1 and catch him
and as mentioned in the problem: Everyone sees others' moves, so they all act optimally.
Yes, I know it. I just explained other version of problem, and why it makes difference.
If they move the way you interpreted tbe question i.e. moving at the same time then they can never catch him cuz if they land on david cell david will move to their cell and if they dont move david will also not move so it will be impossible to catch him in that scenerio but yeah i get your point
it's pretty possible in all cases where we have at least 2 teachers, and we really do have at least 2 teachers in this problem.
the tactic is simple, u just will make 2 teachers adjacent pos = [i, i + 1], and will move towards David with this two.
I think that this time the problems are so hard
Don't worry, One day you will find them Easy.
If you need any help, I am happy to help you upto my level.
I sincerely hope to enhance CF pretest.(like C)
I hate dp very much
Why does this exceed the time limit for C https://mirror.codeforces.com/contest/2005/submission/281250159
Any loop with N^2 could possibly go over time limit, since N^2 isn't bounded.
dp contest(C,D,E1)
D was not really dp at first. All testers solved without dp except 2 of them. However, AI was also able to solve it. We literally changed the problem minutes before the start with Scrasse barely finishing the solution to the new version in time. The new hard version was already solved by dp.
in contest time i had dp idea but didn't implement it because i thought it would give tle.after the contest i find it accepted.But good problemset
What was the first version, and if you can, could you publish?
it was simply not asking for the amount of ways to get the gcd. You had to output only the max gcd.
Many solution of D was hacked after the system testing..Will you consider it?
new version of GPT now capable of solving div2E, it's over, seriously.
https://mirror.codeforces.com/blog/entry/133949
This was a really fun contest!
Thanks for the contest!
Problem A was fun as a first problem. Great job!
Such a nice contest!
HUGE thanks to everyone who made this contest possible! This is the best contest in my life.
After a long wait a specific country is back with all it's telegram channels..
I'm not allowed to see the Editorial !?
Now it's fixed (at least for me).
Reading wrong constraints in problem C and wasting 45 minutes thinking how to solve 🥲
A bit low-quality
I finally got CM!
did you consider whom submission was hacked after the system test?
Noone tourist-tested it?
congratulations aryanc403
Thank you!
Why does a submission of dp memoization gives TLE on C ? but when i simply tabulated it, it got accepted. as far as i could interpret, the TC for memoized solution would be O(10^3 * 10^3 * 5) + O(2 * 10^3). am i wrong here? MY SUBMISSION : 281229405 it contains both memoized rec function and tabulated solution.
You initialized dp array with -1. And it is possible for some state the optimal answer is -1. So here it is recalculating its value again. Initialize your dp array with something else like INT_MIN, it will work.
ohh! thanx. It got accepted. i have got a habit of initializing the dp array to -1. It was such a silly mistake, costed me 100 points and reaching expert in the contest.
Can anyone please help me understand why my Java 21 code is getting TLE for problem B? (I tried storing teachers' position in a TreeSet, as storing them in ArrayList and then sorting it was still giving TLE):
Looks fine to me... is Java too slow? Try Java 8 instead?
Sorry for the late reply. It worked with Java 8 as you had suggested! Does this mean we should avoid using latest JDK for competitions, and stick to Java 8? Why is Java 21 slower than Java 8? Thanks again for your help!
I wasn't sure. Your algorithm looked fine, and I guessed java 8 maybe faster or slower than java 21, so maybe worth a try.
newer versions maybe faster because it includes more optimizations, or it maybe slower because it has more features. so it was really just guessing from my side.
Question on B2:
I was expecting a Runtime Error for 281319760 because b[-1] and b[m] are called in some instances but it went through as AC.
However, this 281170767 got a RTE that I was not expecting.
Also, I thought 281319760 and 281318600 have the same time complexity but I got a TLE for the latter.
Could someone please explain, thanks.
For problem C, my python submission aligned with the given constraints, but failed because of TLE on test 17. By the way, after the contest, I submitted the exact similar code in C++, and it got accepted.
After the contest, I noticed that every python submission for problem C failed because of TLE on test 17 or test 19.
I personally believe given time constraints aren't enough for Python, and that there's no solution in Python that could get accepted. Isn't it the organizers' responsibility to make sure that this situation doesn't arise?
Can anyone please explain me why is my code giving TLE on problem C. Lazy Narek. It is O(N*M) implementation only. Link: https://mirror.codeforces.com/contest/2005/submission/281438234 Thank You!
Resolved, The DP array is typically initialized with -1 out of habit :(
MikeMirzayanov In this round, I got a message that my solution for C coincides with Tashrif2001 which is THIS and with that of puneet_73 which is THIS.
For the coincidence with Tashrif, I do think the solution idea might be similar but the implementations of me and him are radically different. The only thing that might have confused the algorithm here is using similar variable names which are pretty standard variable names. Even if I assume we were connected in some way and changed our code structures then it doesn't really seem plausible to keep the same variable names. So in this case, having similar variable names suggest more of originality than cheating because a cheater who would change the implementation structure wouldn't keep the variable names same.
For the case of Puneet, I do see a similarity on both the idea and implementation. I do want to bring it to your notice that my submission was done before him and if he copied my solution it might be the case that he could have gotten access to it via someone who hacked mine. Here is a screenshot of my conversation with him regarding this matter. So either it is a coincidence or it got leaked to him somehow via hacks because it is hard for me to accept that some so old on this platform doesnt know about hacks. That might as well be a coincidence though.
I also have the same issue, I don't know how even your template is so same both for @Tashrif2001 and @naivedyam. Probably in my room someone had leaked solution could be the case, I am not exactly sure how it is so similar. Regarding the chat and thing u mentioned 'I don't know about hacks...' I just don't want to do pointless discussions with you since you already have some 4-5 contests already skipped which tells the real deal.
I don't think I have 4-5 contests skipped check my profile once again. You are the one with 3 skipped. Last div 4 was unrated that's why it's grey. That's not skipped. One old div 2 did get skipped because of a similar issue (and one isnt equal to 4).Your baltant open lie further strengthens my claim. Moreover looking at the submission timings you were the one to submit after me!
I don't want to run into comment fighting here . This has happened many times tho, someone from room takes code and sends, most of time issues got resolved atleast for me when coordinators looks into deep properly to find who did copying.
If it gets resolved then why 3 skips still? And how come your submission happened after me? It's not possible to get codes that aren't locked from your room and codes can only be locked after you get AC. Which you clearly got after me seeing from your submission time.
2 are div4 skips which weren't even rated so I don't see any point of discussion.
The point of discussion is how is your code leaked from your room when it was submitted after mine?