Привет! В 23.06.2024 17:50 (Московское время) начнётся Codeforces Round 954 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 7 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи были придуманы и подготовлены 74TrAkToR. Хочу поблагодарить всех, кто оказал бесценную помощь в подготовке этого раунда:
- Координатора Vladosiya за отличное общение и блестящую координацию раунда!
- Тестеров veleboks, iNNNo, Sk0rlupka, sharkycode, Noobish_Monk, meowcneil, Matrosk1n, sumit_kk10, Sonya_2009, FelixArg, KirillKhalin, viteli, zwezdinv, EJIC_B_KEDAX, _why_not_, detective...dots, Leeda, windreaper за качественное тестирование раунда и важные советы!
- MikeMirzayanov за прекрасные системы Codeforces и Polygon!
Всем удачи!
UPD: Разбор
UPD: Видеоазбор
who is your contribution dude
OMG 74TrAkToR!!!!
orz 74TrAkToR
https://mirror.codeforces.com
Are you sure this is Codeforces?
It might be:
Mathforces
Algoforces
Codeforces
Interactiveforces
The question asks you to upvote and answer :D
Queueforces
include cheatforces too
5) speedforces
Bruteforces
Education-forces (Problem F)
Classicforces be like
Div 3 doesn't feel like Div 3 when 74TrAkToR is author
why?
As the problems change and adapt, we too must become more vigorous and evolve into more superior problem solvers
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣤⣤⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠀⠀⢀⣴⠟⠉⠀⠀⠀⠈⠻⣦⡀⠀⠀⠀⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣷⣀⢀⣾⠿⠻⢶⣄⠀⠀⣠⣶⡿⠶⣄⣠⣾⣿⠗⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⢻⣿⣿⡿⣿⠿⣿⡿⢼⣿⣿⡿⣿⣎⡟⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡟⠉⠛⢛⣛⡉⠀⠀⠙⠛⠻⠛⠑⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣧⣤⣴⠿⠿⣷⣤⡤⠴⠖⠳⣄⣀⣹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣀⣟⠻⢦⣀⡀⠀⠀⠀⠀⣀⡈⠻⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⡿⠉⡇⠀⠀⠛⠛⠛⠋⠉⠉⠀⠀⠀⠹⢧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⡟⠀⢦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠃⠀⠈⠑⠪⠷⠤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣾⣿⣿⣿⣦⣼⠛⢦⣤⣄⡀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠑⠢⡀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢀⣠⠴⠲⠖⠛⠻⣿⡿⠛⠉⠉⠻⠷⣦⣽⠿⠿⠒⠚⠋⠉⠁⡞⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢦⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⢀⣾⠛⠁⠀⠀⠀⠀⠀⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠤⠒⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢣⠀⠀⠀ ⠀⠀⠀⠀⣰⡿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣑⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡇⠀⠀ ⠀⠀⠀⣰⣿⣁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣧⣄⠀⠀⠀⠀⠀⠀⢳⡀⠀ ⠀⠀⠀⣿⡾⢿⣀⢀⣀⣦⣾⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣫⣿⡿⠟⠻⠶⠀⠀⠀⠀⠀⢳⠀ ⠀⠀⢀⣿⣧⡾⣿⣿⣿⣿⣿⡷⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⢀⡴⢿⣿⣧⠀⡀⠀⢀⣀⣀⢒⣤⣶⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇ ⠀⠀⡾⠁⠙⣿⡈⠉⠙⣿⣿⣷⣬⡛⢿⣶⣶⣴⣶⣶⣶⣤⣤⠤⠾⣿⣿⣿⡿⠿⣿⠿⢿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇ ⠀⣸⠃⠀⠀⢸⠃⠀⠀⢸⣿⣿⣿⣿⣿⣿⣷⣾⣿⣿⠟⡉⠀⠀⠀⠈⠙⠛⠻⢿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇ ⠀⣿⠀⠀⢀⡏⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⠿⠿⠛⠛⠉⠁⠀⠀⠀⠀⠀⠉⠠⠿⠟⠻⠟⠋⠉⢿⣿⣦⡀⢰⡀⠀⠀⠀⠀⠀⠀⠁ ⢀⣿⡆⢀⡾⠀⠀⠀⠀⣾⠏⢿⣿⣿⣿⣯⣙⢷⡄⠀⠀⠀⠀⠀⢸⡄⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⣿⣻⢿⣷⣀⣷⣄⠀⠀⠀⠀⢸⠀ ⢸⠃⠠⣼⠃⠀⠀⣠⣾⡟⠀⠈⢿⣿⡿⠿⣿⣿⡿⠿⠿⠿⠷⣄⠈⠿⠛⠻⠶⢶⣄⣀⣀⡠⠈⢛⡿⠃⠈⢿⣿⣿⡿⠀⠀⠀⠀⠀⡀ ⠟⠀⠀⢻⣶⣶⣾⣿⡟⠁⠀⠀⢸⣿⢅⠀⠈⣿⡇⠀⠀⠀⠀⠀⣷⠂⠀⠀⠀⠀⠐⠋⠉⠉⠀⢸⠁⠀⠀⠀⢻⣿⠛⠀⠀⠀⠀⢀⠇ ⠀⠀⠀⠀⠹⣿⣿⠋⠀⠀⠀⠀⢸⣧⠀⠰⡀⢸⣷⣤⣤⡄⠀⠀⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡆⠀⠀⠀⠀⡾⠀⠀⠀⠀⠀⠀⢼⡇ ⠀⠀⠀⠀⠀⠙⢻⠄⠀⠀⠀⠀⣿⠉⠀⠀⠈⠓⢯⡉⠉⠉⢱⣶⠏⠙⠛⠚⠁⠀⠀⠀⠀⠀⣼⠇⠀⠀⠀⢀⡇⠀⠀⠀⠀⠀⠀⠀⡇ ⠀⠀⠀⠀⠀⠀⠻⠄⠀⠀⠀⢀⣿⠀⢠⡄⠀⠀⠀⣁⠁⡀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠀⢀⣐⡟⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⢠⡇
OMG Bro 74TrAkToR!!! :Skull
letsss goooo div3
Why everyone disrespects him, everyone made mistakes before. Just enjoy round!
Because he has made more than one mistakes.
Because he made mistakes more than others
Div.3 begin, 74TrAkToR's back, enjoy the trip.
:)
OMG! Another 74TrAkToR Round ..
let's go! Hope everyone has fun.
I feel this blog will be the most downvoted blog in codeforces history.
No this blog will not be most downvoted blog.But i can't say the same to your comment so.
Can you (or anyone for that matter) explain why 74TrAkToR is getting so much hate. I am new here, so don't know much about the previous contests......
https://mirror.codeforces.com/blog/entry/124060
The most downvoted blog is 74TrAkToR's appeal
74TrAkToR has to increase his contribution. Good luck !!!
Did you mean contribution??
Looking at your contribution value, I don't want this round.
It is not for you anyway.
Sorry Guys
Competition will return
Marzipan got wronged, ngl.
rated div-3 after 255 days)
Nice progress
I hope you have a wonderful round
I believe 74TrAkToR will bring us a wonderful Div3 this time.
YES, it will be a wonderful round.
true bro
As a tester, I tested :)
What's up with div1 + div2? I can't help, but notice that for some reason low-rated users participate in these contests less eagerly than in div3/div4/even div2
As a CM, I can say that there is a notable difference in difficulty and performance between div2 and div 1+2. This would further exasperated if I could do rated Div3 and Div 4 like pupil/newbie. They just want to do the easier problemsets.
int count = div_3_every_month;
if(count>=3) { cout<<" Helpful for Newbies , Pupils and specialist "<<endl; } else { cout<<"As it is now"<<endl; }
what do you think?
bro you must have some mental disorder
Your opinion doesn't define me. Let's move on. Sometimes the best response is no response!!.Best wishes for you!!
Good Bye 2023!!
Hope to enter in blue......
This is going to be the one for the books
Oh no, Oh no no no no, 74TrAkToR is the author, shut the doors and windows, a crisis is about to begin
I think 74TrAkToR is one of the geniuses. He is very good at writing problems and very popular on this site
I think 74TrAkToR is one of the geniuses He is very good at writing problems and is very popular on this site
OMG T74TrAkToR round this will be amazing ...
I don't get it. why some people hates him.
It sounds a little interesting！I will try my best to enjoy the round！
Have the ratings of previous rounds been re-judged? I don't know how my rating got decreased by 18 suddenly.
Yes, my rating also decreased by 30. Maybe there will be roll back again to distribute the real rating!
same i also got a -18
Hope to solve A
no matter the condition I actually enjoy when A is very tricky even if I'm not able to solve it
are there any hacking points for this contest?
No, there are no points for hacking in contests with open hacks phase (usually educational, div 3, and div 4) as someone might create multiple accounts to hack themselves and gain points for this, but if you find a test case that can be used to hack a lot of solutions you can get a better place in the standings by hacking people above you.
Finally I can write this.
as a tester, I can confirm that this contest will be a div 3
on the edge of being specialist
trust in 74TrAkToR round
hope to reach candidate master
bro isnt even close
I will do it soon isa :)
isa?
it means God willing but in Arabic we say In shaa allah
I think we should let the bullets fly for a while, at least until we see the problems of this one :D
Hoping by this contest I leave newbie status
My cf id is not opening and handle is kxhitz. I had given last contest on 16th June 2024. Please check it out. Solve this issue as soon as possible so that i can continue my practice and participate in contests.
Looks like it has been banned after the recent rollback, if you can prove that the solutions were your original ones and not cheated with anyone, then you can message the Coordinator of the last round to remove the ban otherwise it is gone forever.
thanx for reply. I have messaged the coordinator of that round. Sir, how much time this would take as I have never copied anyone's code in any contest I had given till now.
Is there anything else I should do ??
Quit cf, you cheated in 6 almost consecutive rounds
But Sir I haven't received any warning mail and also didn't received any accusation message to my account regarding any case of cheating by me, Even Sir I didn't attempted cheating. Sir I have also contacted the coordinator of the last contest to solve my problem. Please suggest me what should I do for it.
as div3 enjoyer, i hope it will be a great round!
Dreaming to achieve contribution as 74TrAkToR
same, plz downvote me
With such a low rating from this questioner, I have reason to believe that this game is bad, and I believe there are a lot of people who have stepped on it, because I've seen a lot of honest people get downped, which is kind of ridiculous
Good luck everyone !
Who's going to try to OEIS G tomorrow?
Tracktor has become celebrity of codeforces
free tibet!!
Good luck everyone!
damn i thought 74 is all history
Hope pref 2000+ Although 74 round
Excited for Round 954! Big thanks to 74TrAkToR and the whole team for their hard work and dedication in organizing these rounds. Good luck to everyone!
i have high respect for low contribution authors
Best of luck everyone!
Hope today is not speedforces.
Upvote me- Div 3 A to Div 3 D easy and Div 3 E and F medium and Div 3 G Hard
Downvote me- Div 3 A easy and Div 3 B to G Super Super Hard because of 74TrAkToR
delayforce
Delayforces...
Hey，but why？
Because its div3
?
contest got postponed for 15min
deley
Bro it's delayed!
delay :(
what should we do in delayed time?
just play chess
74TrAkToR is late...
Delayed cause everyone's watching F1
CF>F1
nahh
mAXX won, orz.
Delayed
delayed :)
This is a delay in second 74TrAkToR's contest in a row
if you mean as a coordinator — third
Delayforces :(
why is there a delay?
Is there ever going to be a div 3 round without delay?
when you become a problemsetter, make an on time cf round
The TrAkToR is going slowly so we have a delay.
thanks I just finished a heavy plate of pasta and I needed that 15 minutes
Everyone will try to become a pupil or specialist. I will try to submit before the cheaters
Problem A Solution
YOU ARE THE CHEATER
I think its delayed because Codeforces is having issues...
the time has been changed?
I was thinking the same thing XD
Please, don't worry about delay, Mike asked for it to increase testing speed a little.
I think its delayed because Codeforces is having issues
I hope it's a nice round, Good luck to every one! :)
Does the delays coincidentally happen in 74TrAkToR's round.
Traktor king lets go
What happened? why so much people know about the writer?
because of Good Bye 2023.
I thought that I missed the round start by one minute. But, it turned out that I have to wait for more than 10 minutes for the round start now!
Good luck to all, compete fairly and enjoy competitive computer programming.
Hope Goodbye 2024 will be super hard for B and above problems and only A is very easy if 74TraKtor Coordinates again.
still loading ,uhhh?
good round, solved A,B,C
I don't understand the author's intention to split $$$G$$$ into two tasks and not able to think of a specific algorithm to solve $$$G_1$$$.
Lol, many people submitted G1 but not G2. Or submitted G2 much later.
I believe both $$$O(n*sqrt(n))$$$ or $$$O(nlog(n))$$$, anyway $$$O(n*log^2(n))$$$ could pass. Can anyone share the algo of $$$G_1$$$
Does D use meet-in-the-middle to solve? It seemed so easy but I couldn't solve it...
not-balanced round
Does D use meet-in-the-middle to solve? It seemed so easy but I couldn't solve it...
its just some case handling but there is an edge case that I couldn't find out yet
it's just brute force on brute force
first solve the following question: given an array of numbers, what is the minimum value of their expression?
this is easy enough: multiply ones and zeroes, sum everything else.
after solving this problem all you have to do is try it for all possible lists of numbers. notice that there are only $$$n - 1$$$ such lists
the final complexity is $$$O(n^2)$$$
I was thinking that approach, but it seems there are lots of cases to handle. For example, assume the digit is "abc0def". How do you decide whether to multiply c x 0, bc x 0, 0 x d, 0 x de, ..? We need exactly N-2 symbol. Probably 0xde leads to the most optimal one instead of 0xd.
At the end I use DP.
in this case you multiply everything by the zero, for example:
$$$ab * c * 0 * d * e * f$$$
Handle the edge case where result is 0. Which is pretty simple.
Since you always have (n-2) signs, therefore theres always a 2 digit number(including 01-09) present in your calculation.
The problem reduces to finding this 2 digit number then applying the following algorithm:
Let i be the starting position of the 2 digit number. For each character from 0..i-1 and i+2..n, add if digit is not 1 otherwise multiply it and finally add the 2 digit number.
Now to find that 2 digit number: You can iterate through all possible 2 digit numbers and add them to vector and sort it.
Then among lowest 2 digit numbers that have the same digit in 1's place, pick the one that gives you the lowest result.
You need to do this because sometimes picking the minimal number is not optimal, like 22 gives better result than 21 in one of the test cases.
I couldn't come up with a better method to pick the minimum number so I kinda brute forced it. The time complexity is O(nlogn). (Picking optimal 2 digit number through sorting)
Sorry if my description is kinda convoluted I am still learning
Actually, you can brute force the element that will be combined with the right one and then try this: When there is 1 you multiply it, otherwise you sum it and write corner cases with zero, because you can multiply everything and make ans 0, but not in 101 and etc.
Solved 4 problems, I'm very happy and satisfied :D
Really nice problems!
I found a bug in my bridges code due to problem F, thanks to problem authors!
You must think you're humorous by choosing these questions. :D
bye bye rating 💩
problem b were bit hard for it's position (second div3 problem), waste 30min to implement without ChagGPT, rating completely ruined
I loved G, cool round! (maybe F was a bit too obvious tho)
Thanks for the amazing contest 74TrAkToR !!! Finally a Div 3 contest that felt like a proper, balanced Div 3 contest <3
if you solve 5 tasks first time it doesn't mean that contest is balanced (((
Ofc not, it might mean that the contest was easier than usual because I was able to solve more problems. But I did feel like this was a proper Div 3 for those whom it was meant for — people rated below 1600. The tasks weren't too random (like traktor's previous contest) and almost 1.5k to 2k people below 1600 rating solved till E in the contest, so I think it is fair to judge it was balanced. Not too much DSA, not too much math, etc.
Also, this was meant as an appreciation comment for traktor for organizing this good contest after what has happened in the past.
Shit man!, wasted almost an hour because of overflow in D, could have done some more if that didn't happen, Only me to blame! thanks for the round..
G2 43no case: what is the case that getting mle
What was intended for G2? I used (almost) the same $$$O(n\sqrt{n}\log(n))$$$ code for G2 as G1 which doesn't seem like it should pass G2.
I solved it in $$$O(nlogn + n*maxdivs(A))$$$ which $$$maxdivs(A)$$$ about $$$300$$$ i guess. The problem becomes for 2 simplified fractions, count the number of pairs of fractions $$$(x1/y1), (x2/y2)$$$ multiplied together to produce an integer. When fixing the denominator of the first fraction ($$$y1$$$) => the numerator of the second fraction must be divisible by the fixed denominator ($$$x2$$$ divisible by $$$y1$$$). => count the number of fractions with numerators $$$x2$$$ and $$$x1$$$ divisible by $$$y2$$$. Just brute all $$$y2$$$, processing $$$x1$$$ can be done before.
D and E are too much implementation heavy...
what is the correct idea of E? I thought of try pairing every two elements from A so every element we can write it as follow : a[i]=x*k + a[j] for j != i
but I didn't implement it
is it correct?
.
Let $$$x + kn = y$$$ ($$$n$$$ operations on $$$x$$$). This implies $$$y - x = kn$$$. This difference is divisible by $$$k$$$. Thus, two elements can only be made equal if they give the same remainder when divided by $$$k$$$ (if they don't, their difference is not a multiple of $$$k$$$).
So we group elements with the same remainder modulo $$$k$$$.
If there are $$$\geq 2$$$ groups with odd number of elements, it is impossible to construct a palindromic array.
So, we move on to the case where you can apply operations.
For each group, let its sorted list of elements be $$$a_1, a_2, \cdots, a_n$$$.
For an even-sized group, $$$(\lvert a_2 - a_1 \rvert + \lvert a_4 - a_3 \rvert + \cdots + \lvert a_n - a_{n-1} \rvert )/k$$$ is the minimum score needed for that group.
For an odd-sized group it's similar but a little bit more complicated. You will pair $$$2k_1$$$ elements in the front and add their score using the even group method. Then, an element will be left out to be the middle element of the palindrome. After that, the score for the remaining $$$2k_2$$$ elements will be added. The optimal left out element can be calculated using prefix sums.
So you have the total score for each group, and you sum it over all the groups to get the final answer
How can the optimal left-out element be calculated using prefix sums? What's the implementation idea
You can look at my code if it is of any help
This problem from AtCoder is the same, you can read the editorial on there
First time get MLE in div3 round
I knew I shouldn't have given this round. Guess people never change.
For E, I wasted a lot of time on prefix/suffix sums to find the optimal element in the odd length array to put in the middle. Then, I realized I could use DP to do it without much thinking.
same bro realised it later and wasted a lot of time on prefix sums, also I did another blunder, by asking this from gpt-4 and claude 3.5 sonnet. they weren't able to code correctly this simple task of prefix sum.
Solution which uses prefix/suffix sums.
https://mirror.codeforces.com/contest/1986/submission/267058869
you could also do it using prefix and suffix sum. see
Lol me too,but int the end i just ended up doing it with single variable :) or ig :(
Interesting. I found Greedy with prefix sum easier.
How does the DP work in detail? I don't really understand the transitional relationship.
Nice approach . I was not able to think about this and solves using prefix and suffix sum of two pairs. It was very heavy implementation for me
Why do we even need DP? Can't we just solve it in O(1) memory? (267066755)
(recent) parameter in your dp function is not necessary.
No need of 3d DP, recent state can be avoided, 2d is also accepted
remind me to never give a traktor round again!
solved F 3 minutes after contest finished...... :(
I would die rather than to attempts traktors mathy and implementation heavy rounds
implementation forces!
L round
wrote recursive function to verify my observations in D and I found out that I can memoise my recursion function and convert it into dp.
It is just a lot of bruteforce
yep
You can do D with (heavy amount of) casework and greedy ig
Skipping traktor's rounds from now on.
who let him cook a template bridge problem???
lol
For this kind of a standard problem there are not that many solves tho
Although it does scream bridges the moment you look at it
what is template bridge problem? easy to solve with concept from classical/standard problem?
Take a look at this
Additionally in today's problem you also have to come up with a way to calculate sizes of components after you remove a bridge (which is not too difficult)
I copied the bridge search algorithm from an Internet site (the algorithm was published long before the start of the round) without rewriting it by hand and made some changes. I read the competition rules on the codeforces platform and still didn't understand if I could do this. I hope this question will be clarified to me.
I pasted the statement into GPT4 and it gave a slow python DFS solution, then with one prompt I managed to get it to provide a correct solution (only had to fix an overflow bug).
use c++, and do it in O(n) by storing subtree sizes and a bridge finding methodwas the prompt that allowed it to solve the problem!I thought what could possibly change by just increasing the constraint by a mere 5 times in problem G, but it effectively thwarted my square root decomposition solution from G1, and I ended up having many MLE/TLEs :( .
div 2.74 (74 from 74TrAkToR)
div 2.74 (74 from 74TrAkToR)
why carrot giving error?
as it is stuck in traktor
nice
good round, thanks for the problems.
It is so hard ! How can I improve myself quickly ? I vp many recent contests and make the topic I missed after the contest.
Task F can be said to be a learning task for finding bridges in a graph. I copied the bridge search algorithm from an Internet site (the algorithm was published long before the start of the round) without rewriting it by hand and made some changes. I read the competition rules on the codeforces platform and still didn't understand if I could do this. I hope this question will be clarified to me.
You could.
According to third-party code rules you should be fine, although I don't know if a copy pasted solution from a public source can get flagged for plagiarism
Why u would put a copy past bridge template in F
I'm not able to guess the complexity for my solution of G2, someone hack it. 267078205
Decent round tbh. Better than previous round by 74TrAkToR. Skill issued on implementing, but so did everyone else, I guess.
I was worried for this round (delay+ goodbye 2023 trauma) but hopefully it was good, good job 74TrAkToR !!
I was worried for this round (delay + goodbye 2023 trauma), but hopefully it was good, Good job 74TrAkToR
Here is my DP solution for D.
267043778
You can check my video editorials of D, E and F if you have any doubts
How to hack B?
can anyone hack my solution?
Silly mistake cost me E :(
267089006 testcase where it fails ?? someone
got it .....
what could be the rating of c?
Okay I'm fairly new to Codeforces, so I have no idea what hacking is. I had successfully solved A and B. But now sometime later after the round has ended, I open up the round page, B is highlighted in red, and after checking submissions I see that the verdict for B has changed to "Hacked"..... what.... why.......
It means that your submitted solution isn't fully correct
How not correct, like to what extent?
It means that someone has found a testcase in which your solution is giving wrong answer. So he basically hacked your code....
.....wow okay
In this particular case your solution can't fit in given time constraints, so it fails. You need to find a more optimized one.
I have a new version of c can anyone help me in that.
Update in 1986C - Update Queries, what if t was not allowed to sort the string c then how will approach. any suggestions.
Here's what i thought about this:
First lets store the distinct occurences of indices in increasing order along with its count. Now for an index $$$i$$$ in this array, we will try to place the smallest available character in $$$ith$$$ pos of $$$s$$$. The position of the chosen character in string $$$c$$$ should be such that we can place all other occurences of $$$i$$$ before it (since it only matter what we place last for an index $$$i$$$). For each character the best chance to be able to choose it would be if we choose the last available occurence of that character.
So now what remains is how do we choose which characters would correspond to the leftover occurences ? It would be best to strike off the maximum characters to the left of the last occurance of the chosen character. We can simulate that using a segment tree.
I was thinking of the same approach but the main difficulty I faced was like suppose for index 1 we have count of 4 and for index 2 we have count of 3.
So, we have sorted t array something like this: 1 1 1 1 2 2 2 .........
Now have to assign best character to last 1 such that there are at least 3 characters before it so that we can assign them to preceding 1. Now for 2 we need to remove max 3 characters that were assigned to 1 and the smallest characters then again go with 2.
Can you tell how you will tackle this, if possible, provide the pseudo code and expected Time complexity.
For each character we will store a set of its occurances in string c. Now suppose we want to assign the last index of 1 a character, we begin by checking if it is possible to assign a, b, c.. z . Checking if its possible simply implies if there are enough positions to the left of the last occurance of a char. For this we will use a segment tree to find range sum of available positions. Now once we find a valid index, we will start assigning the rest of the occurances of 1 characters. Suppose the valid index was $$$i$$$. Now we need to assign all previous occurances of 1 to some available characters that werent already assigned from $$$[1,i-1]$$$, and it is best to assign the max characters which are available one by one. To find out a max character we will query the max in range $$$[1,i-1]$$$ which will return the index of the max available character in $$$c$$$ in that range. Now we set this value as 0 since we already used it and remove it from the set of occurances of that character and proceed further.
So for each index we will be querying once,updating the segment tree once, updating occurance set and checking all characters validity worst case. So expected TC should be $$$O(26n + nlogn)$$$.
I don't know why some people complains so much about this Round, it doesn't matter if it's all implementation or math, after all is a problem u need to solve, there are no excuses in real life problems, good Round admins!
Could anyone please explain how to solve D? I understood that the main task is to find the two digit number, and then multiply a number if it is 1, otherwise add it. But I just cannot figure out how to implement that.
Here is my submission https://mirror.codeforces.com/contest/1986/submission/267070013 What I did was I first handle the cases when there is a 0. I then generate all possible combinations of two digit numbers, and for each combination calculate the answer, and then took the minimum of all the answers. Calculating the answer is a separate function, I did it recursively:
That's almost how I did it. Great contest.
Contest was great,but cloudfare spoil it for me
D was such a pain, I missed one simple if for a super basic case I thought I added, but realised I forgot a little after the contest whilst laying in bed sad after not solving D.
Any reason we are using memory limit 128M instead of the default 256M for G?
I didn't see any reasons to reject solutions on the memory constant factor.
MLEFORCES
Can anyone explain why unordered_map solution is giving TLE, while map is working fine?
unordered map
map
You should read this: https://mirror.codeforces.com/blog/entry/62393
It is interesting that the post was made 6 years ago, yet lots of people (me including) dont know. Shouldnt they patch and prevent people using bugged version? Even though perfect implementation is crucial in CP, one shouldnt penalized due to buga from the compiler.
This isn't a bug of the library or the compiler. C++ specification clearly states that
unordered_map<K,V>::insert()'s time complexity is worst case O(N) (cppreference).If you are curious about how this happens, study the data structure of hash tables.
can someone explain why this fail for problem B https://mirror.codeforces.com/contest/1986/submission/267043411
Your code fails if n=1 or m=1:
You look at positions (i,j+1) and (i+1,j) without checking if they exist. I don't recomend to write so many if-statements, because then it's very easy to make small mistakes like this. Example of my code without so many if-statements: 266984242.
i am kinda new to codeforces , how is ranking decided ?? does it depend on number of problems solved ?? (or) do each problem has different weightage ?? like problem D. has more weightage than problem C . if anyone knows this please enlighten me :) .
If a point distribution is mentioned in the announcement blog, the problems will carry weight accordingly. If no distribution is mentioned, then the problems have no specific weightage. Generally, Div3 and Div4 contests do not have specific problem weightage, while most Div2 contests do.
Thanks for the clarification
Turns out test 43 is the first test where $$$n = 500000$$$, which is odd.
Stress tests should be among the initial tests. Otherwise, it takes too long to get the verdict during a contest.
Can someone please explain that in E — Beautiful Array, for the input
13 3 2 3 9 14 17 10 22 20 18 30 1 4 28
How is the output 14? I re -checked multiple times and found it to be 15.
Please reply ASAP
for your remainder equal to 1 the sequence is {1,4,10,22,28} in this you should remove 10 and pair 1 with 4 and 22 with 28.
sorry for bad English.
Does anyone feel E was of rating 1400+?
It should be :/
Is there going to be a system testing after the hacking?
Is there going to be a system testing after hacking?
Can someone explain why this solution failed as TLE?267007171 .I expected the Time complexity as O(nlogn+mlogm).
I'm pretty sure that you are making it O(n^2) through string concatenation (basically, appending a char to a string of length n has time complexity of O(n) because strings in python are fixed-sized unlike C++ where they are almost a glorified vector)
Thanks for your reply and pointing out the mistake, i think it would be a lot helpful to me in the future. Really appreciate it But still i got a question — why does this same code passes with Python3- 267178416 whereas the same code gets a TLE with PyPy3- 267007171
I am not Python expert, I mostly do C++ and some Rust but my guess is that Python3 interpreter recognizes that you are building a string char by char and does some clever optimization on this code which allows it to avoid the O(n^2) pitfall somehow
I have sacrificed 'D' to score 'E'! It was a little heavy implementation (E).
unrated
what?
who announced??
Unlikely, It's just that tests took quite a lot of time because there were a lot of hacks and that's the reason the whole thing kinda got shifted to later
unrated???
It is not unrated. It seems like rating has not been updated yet.
Is the round going to be unrated??? The ratings aren't updated after system testing
It's not unrated. Ratings are yet to be updated, they will be updated soon.
Are you sure
click on show all on your rating graph..it will show you that its unrated
It's not the first time that ratings have not been updated even after 24 hours to the start of the contest. Besides, there is no reason for the contest to be unrated.
but its showing unrated in the graph and in contests section. does anyone know anything official?
It is showing unrated brother..
so is that final or should we expect something lol
It will move to the list of rated contests after rating change. It's just temporarily listed as an unrated contest.
haha..wait till infinite time
it always shows unrated before ratings are in
see the contribution of the author now..
why did this happen though
That's because of Good Bye 2023, nothing to with this round
the author replied. the round is rated guys, just wait
where did he reply ?
i texted personally, he replied "rating round". that means it's rated if I know english
Can you send a screenshot of your chat with 74TrAkToR?
don't know how to share image here, it just asks to enter a url
You can just upload an image to some cloud service (like google drive) and then put a link.
https://drive.google.com/file/d/1D4LXvsF7kiMMFbxIXGw9bTSNcJNLSHKT/view?usp=drivesdk
this means the round is rated right
unrated :(
why unrated
unrated for me too
Until a contest is rated it will be displayed as unrated. Sometimes it can take more than 24hours to roll out ratings and sometimes they rerate contests too. Nothing to worry ratings will be out maximum by tomorrow. (P.S Don't mind if there are any spelling or grammatical errors)
yes..it's been updated for me
Changing map to a sorted vector of elements + binary search works in G2, the time complexity is the same but i can't figure out why it removes the MLE i get with map, since intuitively, i am storing count in map and elements in vector, the storage in map is more sparse, is this happening because in testcase 43 the array values are such that, it leads to lower count values in map and thus, reducing the advantage of sparseness?
Map submission
Vector submission
267268308 I made this code for C and this is giving compilation error in CF but it is working fine in vs code. Can someone tell what is wrong with this code.
So why does this code: link return a result of Runtime error? I was able to compile the sample locally.
So why does this code: link return a result of Runtime error? I was able to compile the sample locally.
I had given this contest on time using my laptop. This post is to show that there was no violation. Kindly look into it @codeforces The 1st ques was the X Axis in which the soln was that to find the median and find distance of rest 2 points from the median. The median would be the center point after sorting the array
The 2nd ques was Matrix Stabilization. I had created a priority queue and inserted all the cells into it. then changed the value to the maximum around it if it was greater and again pushed in pq else skipped
The 3rd ques Update Queries. In this ques, I created a set for the indices array and sorted it. also sorted the string c and mapped each ele to each index. and finally applied the transformation on s and found the ans.
The 4th ques was Mathematical Problem. If zero is first or last ele-> ans is 0. if len ==2 , ans is the number. Now, if len > 3 and zero is found, ans is 0. If len == 3 and zero is found in middle, return max of a+c and a*c. If 0 is not there is the string. I have to take pair of each 2 ele and combine and check for the mini. If 1 is found, skip it
The 5th ques was Beautiful Array. I used a map to track remainders % k and their corresponding values, ensuring each remainder set has even size by inserting and removing elements. Finally, I calculated the minimum operations needed to make the array satisfy the required conditions and return the result
Dear Codeforces Team,
I have received a notice about my solution (ID: 267058250) for problem 1986D coinciding with other solutions. I would like to clarify that any similarity is unintentional. Here are the details:
I have always aimed to compete fairly and adhere to the rules. I hope this clarifies any misunderstandings. Please let me know if further information is required.
Thank you, Mr.Mittal
Respected Admin/System,
This is HeroicMage. This is with regards to the message for my submission Your text to link here... being similar to Your text to link here....
I am extremely sorry for this. I won't tell that I don't know the other person. In fact, he is a good friend of mine. But I haven't copied from him or from any other participant on the website. I just used the concept of prefix sums and suffix sums to exclude one element to find out the maximum among all possible contributions to answer if the size of numbers with same remainder is odd.
I could see the similarity in the use of data structures and the concept of prefix and suffix sums in both the submissions. But the data structure similarity could be also for people who might have used map <int,vector> or unordered_map instead of map<int,multiset>. But I can tell with utmost honesty and sincerity that I haven't copied from anybody else. It is my own solution and my own idea.
Hello sir i just wanted to say that i haven't leaked any solution the claim that is being made on me is wrong. ashok_0/267077276 he has copied my solution i dont know how my solution got leak. I was giving contest in cafe where all others are also doing the contest. Might possible that he has cheated or all the pcs are connected with the main server so he has access to the main server. Sir my all solutions are in cpp and also my templates are same.His solution is in java and he has copied my solution. Please help me Sir I haven't done wrong.
Hello sir i just wanted to say that i haven't leaked any solution the claim that is being made on me is wrong. ashok_0/267077276 he has copied my solution i dont know how my solution got leak. I was giving contest in cafe where all others are also doing the contest. Might possible that he has cheated or all the pcs are connected with the main server so he has access to the main server. Sir my all solutions are in cpp and also my templates are same.His solution is in java and he has copied my solution. Please help me Sir I haven't done wrong.
I just received a message about plagiarism. The people who I can see have plagiarised with me are all my hostel mates. I don't know how they got hold of my code, but I have definitely not shared it with literally anyone.
You can see that I am the 1st person to submit E in the way I have written it, ensuring it is unique and not plagiarised. I would request you to penalize all similar submissions after mine as mine wasn't plagiarized theirs was through no fault of my own. I HAVE SOLVED ALL THE QUESTIONS ON MY OWN AND THIS IS THE BEST CONTEST I HAVE HAD TILL NOW, SO PLEASE PLEASE PLEASE DONT ROLL BACK THE RATING
This is the 1st time such a thing is happening with me and I will ensure this never happens again, please don't penalize this round
..
Respected Codeforces team,
I had received a message saying that my solution for F, E and D coincides with other people's solutions (around 200 to 500 people), I would like to clarify that my code for D and E were written by me (E's logic was easy it was looking for numbers with same remainders and grouping them, the case of having one remainder having an odd set of numbers took some implementation but I got the logic early cause I had solved some similar grouping problem earlier, though for earlier versions of D ChatGPT AI was used for writing the calculating minimum value function (helper) the final version which got excepted was written entirely by me), for F, I used chatGPT AI (which is publically available) to generate a function for finding the bridges in a graph and computing subtree sizes. Please check my solutions and look into it.
I just received a message about plagiarism. The people who I can see have plagiarised with me that i do not know anyone of them an they are not my college mates . I don't know how they got hold of my code, but I have definitely not shared it with literally anyone. Before this contest regarding this also come but there is an the solverd and the system check that my code is not in the other solutions like. as this that i use the python and my submission is very fast and i have the error also
if i have error then you think that i cheat the code if i cheat the code then why i do not take it in the first step as the both solution like a and b or the contest that i have do it with my mind as the c question. please deplag the code because i give my beast as i can and if i cheat the code then why i should give the 3 solutions only why i do not give the all solutions . please do not plag this contest . You can see that I am the 1st person to submit C in the way I have written it, ensuring it is unique and not plagiarised. I would request you to penalize all similar submissions after mine as mine wasn't plagiarized theirs was through no fault of my own. I HAVE SOLVED ALL THE QUESTIONS ON MY OWN AND THIS IS THE BEST CONTEST I HAVE HAD TILL NOW, SO PLEASE PLEASE PLEASE DONT ROLL BACK THE RATING
.
I am writing to express my concern regarding the recent cancellation of my contest submission due to the coincidental similarity of one of my four codes with another participant's code. While I understand the importance of maintaining the integrity of the contest, I would like to clarify that this similarity was purely coincidental and not a result of any form of misconduct.
It is not uncommon for similar solutions to arise independently, especially when addressing common problems or using standard approaches. I assure you that all my submissions were created independently and with the utmost integrity.
I have submitted all the code by writing them manually on VS code first then submitting it. I don't use libraries or any other stuff that must be one of the reason which might have gotten my code to be similar to others, but in honor regards I want u to consider if my only 1 out of 4 code is found similar but I made Problem D which is much harder than C myself. Which clearly shows that I have enough potential to solve C too on my own.
I kindly request a reconsideration of my disqualification, taking into account the originality and uniqueness of my other three codes. I am more than willing to provide any additional information or clarification needed to resolve this matter fairly.
Thank you for your attention to this issue. I look forward to a fair resolution.
Sincerely
i'm kinda new to contests in codeforces so i dont know if this was a hard contest or the other div 3 contests where too easy. i normally solve around 2 or 3 problems in div 3 contests but i could only solve problem A in this one.is that just a me problem ?
in the second paragraph of problem D, what does two symbols cannot be written consecutively?
Was there some changes in the rating updation?
I had gotten +39 now I have +51 in this contest.
Recently I am being accused of plag cases by many people and this is actually hurting me a lot. You can check out my linkedin GeeteshPaidi and confirm that i am a python developer and C++ is actually my new language, that one time due to time pressure i have written my code in python because i could lose my rank. For that one qn i am being accused as a cheater. So i decided I am talented enough to rise to this rank again instead of taking these claims. Thank you codeforces for teaching me another life lesson. See you again on the top board with only C++. Signing off as geeteshpaidi. This account will no longer be active!
jiangly Can you please explain your solution for G1 and G2?
Good contest
.