Hello! Codeforces Round 954 (Div. 3) will start at Jun/23/2024 17:50 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of **open hacks**.

You will be given **7 problems** and **2 hours and 15 minutes** to solve them.

Note that the **penalty** for the wrong submission in this round is **10 minutes**.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participant of the third division*, you must:

- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

The tasks were created and prepared by 74TrAkToR. I would like to thank everyone who helped me a lot with round preparation.

- Coordinator Vladosiya for excellent communication and brilliant coordination of the round!
- Testers 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 for high-quality testing and valuable advices!
- MikeMirzayanov for amazing Codeforces and Polygon platforms!

Good luck!

**UPD**: Editorial

**UPD**: Video Editorial

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

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣤⣤⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠀⠀⢀⣴⠟⠉⠀⠀⠀⠈⠻⣦⡀⠀⠀⠀⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣷⣀⢀⣾⠿⠻⢶⣄⠀⠀⣠⣶⡿⠶⣄⣠⣾⣿⠗⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⢻⣿⣿⡿⣿⠿⣿⡿⢼⣿⣿⡿⣿⣎⡟⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡟⠉⠛⢛⣛⡉⠀⠀⠙⠛⠻⠛⠑⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣧⣤⣴⠿⠿⣷⣤⡤⠴⠖⠳⣄⣀⣹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣀⣟⠻⢦⣀⡀⠀⠀⠀⠀⣀⡈⠻⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⡿⠉⡇⠀⠀⠛⠛⠛⠋⠉⠉⠀⠀⠀⠹⢧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⡟⠀⢦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠃⠀⠈⠑⠪⠷⠤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣾⣿⣿⣿⣦⣼⠛⢦⣤⣄⡀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠑⠢⡀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢀⣠⠴⠲⠖⠛⠻⣿⡿⠛⠉⠉⠻⠷⣦⣽⠿⠿⠒⠚⠋⠉⠁⡞⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢦⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⢀⣾⠛⠁⠀⠀⠀⠀⠀⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠤⠒⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢣⠀⠀⠀ ⠀⠀⠀⠀⣰⡿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣑⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡇⠀⠀ ⠀⠀⠀⣰⣿⣁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣧⣄⠀⠀⠀⠀⠀⠀⢳⡀⠀ ⠀⠀⠀⣿⡾⢿⣀⢀⣀⣦⣾⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣫⣿⡿⠟⠻⠶⠀⠀⠀⠀⠀⢳⠀ ⠀⠀⢀⣿⣧⡾⣿⣿⣿⣿⣿⡷⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⢀⡴⢿⣿⣧⠀⡀⠀⢀⣀⣀⢒⣤⣶⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇ ⠀⠀⡾⠁⠙⣿⡈⠉⠙⣿⣿⣷⣬⡛⢿⣶⣶⣴⣶⣶⣶⣤⣤⠤⠾⣿⣿⣿⡿⠿⣿⠿⢿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇ ⠀⣸⠃⠀⠀⢸⠃⠀⠀⢸⣿⣿⣿⣿⣿⣿⣷⣾⣿⣿⠟⡉⠀⠀⠀⠈⠙⠛⠻⢿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇ ⠀⣿⠀⠀⢀⡏⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⠿⠿⠛⠛⠉⠁⠀⠀⠀⠀⠀⠉⠠⠿⠟⠻⠟⠋⠉⢿⣿⣦⡀⢰⡀⠀⠀⠀⠀⠀⠀⠁ ⢀⣿⡆⢀⡾⠀⠀⠀⠀⣾⠏⢿⣿⣿⣿⣯⣙⢷⡄⠀⠀⠀⠀⠀⢸⡄⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⣿⣻⢿⣷⣀⣷⣄⠀⠀⠀⠀⢸⠀ ⢸⠃⠠⣼⠃⠀⠀⣠⣾⡟⠀⠈⢿⣿⡿⠿⣿⣿⡿⠿⠿⠿⠷⣄⠈⠿⠛⠻⠶⢶⣄⣀⣀⡠⠈⢛⡿⠃⠈⢿⣿⣿⡿⠀⠀⠀⠀⠀⡀ ⠟⠀⠀⢻⣶⣶⣾⣿⡟⠁⠀⠀⢸⣿⢅⠀⠈⣿⡇⠀⠀⠀⠀⠀⣷⠂⠀⠀⠀⠀⠐⠋⠉⠉⠀⢸⠁⠀⠀⠀⢻⣿⠛⠀⠀⠀⠀⢀⠇ ⠀⠀⠀⠀⠹⣿⣿⠋⠀⠀⠀⠀⢸⣧⠀⠰⡀⢸⣷⣤⣤⡄⠀⠀⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡆⠀⠀⠀⠀⡾⠀⠀⠀⠀⠀⠀⢼⡇ ⠀⠀⠀⠀⠀⠙⢻⠄⠀⠀⠀⠀⣿⠉⠀⠀⠈⠓⢯⡉⠉⠉⢱⣶⠏⠙⠛⠚⠁⠀⠀⠀⠀⠀⣼⠇⠀⠀⠀⢀⡇⠀⠀⠀⠀⠀⠀⠀⡇ ⠀⠀⠀⠀⠀⠀⠻⠄⠀⠀⠀⢀⣿⠀⢠⡄⠀⠀⠀⣁⠁⡀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠀⢀⣐⡟⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⢠⡇

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

memeI 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

I think 74TrAkToR is one of the geniuses He is very good at writing problems and is very popular on this site

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.

this round is brought to you by...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

Who's going to try to OEIS G tomorrow?

Tracktor has become celebrity of codeforces

damn i thought 74 is all history

Hope pref 2000+

Although 74 roundExcited 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

Delayforces...

Hey，but why？

Because its div3

?

Bro it's delayed!

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

Spoiler## YOU ARE THE CHEATER

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! :)

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$$$

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

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..

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

sortedlist 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.

Codesame 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 method`

was 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)

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

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

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 .....

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 - Запросы обновления, 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 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

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.

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 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

.