Hello! Codeforces Round 938 (Div. 3) will start at Apr/08/2024 17:35 (Moscow time). You will be offered 6-8 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 **6-8 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.**

Problems have been created and written by our team: mainyutin, vmanosin7, ssor96 and ZergTricky.

We would like to thank:

Vladosiya for help with ideas and great coordination of the round;

ace5, Nickir, senjougaharin, vladmart for yellow testing;

natalina for blue testing;

bitthal04 for cyan testing;

Alequisk, Mohamed_Hesham for green testing;

MikeMirzayanov for Polygon and Codeforces platforms.

Good luck!

**UPD**: There was an issue with the validation of hacks for problem G, but it has now been resolved. All successful hacks will be rejudged. Pretests were not affected by the issue and remain unchanged.

**UPD2**: Editorial is out.

yay div 3!!!

Spoilerhopefully i get to 1500

do just rating++)

spoiler hopefully i get 1200

i am new here , i participated in this round and my current rating is around 800 , but now this contest is showing as unrated on my profile . i dont get it , it clearly says -"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."

It will take some time for ratings to change

Don't worry! The rating calculation hasn't been completed yet. And there seem to be some issues with Problem G, so the rating update for this round may be further delayed.

ok, thanks

authors pic??

mainyutin orz

No pics with pizza.

Experts be like: I'm out of competition (つ▀¯▀ )つ

I appreciate the creators' effort on this div.

Is that a gan cube :o

Yes, it is GAN 356 M

PB?

Best ~17 sec, average ~26 sec

ooh nice... my best-9s avg-14s ... i think my cube's the predecessor of your cube ... gan 356x

Let this be the round where i shall become Pupil under the Heavens .

It's divine Conviction that i shall fulfil.

In the name of all mighty Behelet behold my Pupil Rank

Thou shall fulfill thy prophecy.

Good luck to everyone! I'll sadly have school but I'll find a way to participate since cf >>>>>>>> school

Contest > School

i think it's time to give it a try to change my color

Very Saaaaaaaaad

I am not participating :(

Hope to be pupil after this contest

Good Luck!!!!!

i am new here , i participated in this round and my current rating is around 800 , but now this contest is showing as unrated on my profile . i dont get it , it clearly says -"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." , can you please explain what am i missing.

Hope to be specialist after this contest

Good luck to everyone!

Authors' photos again!

Hope I can get back to my real rank of pupil

orz sir

hi everyone, mwah. i love yall. happy contest day! wish you good luck. mwah. (please downvote me)

should i participate or nah?

yes bro participate believe in yourself

OMG! Another mainyutin round ...

OMG! Another mainyutin round...

The cat is so

cool!cute cat-meme owo

Back to ExpertBro did a manifestation

lmao

Bhai it's IQ 69. If you have a bad performance in div2 and you are becoming a specialist from Expert and the next contest is div3. Let the rating fall. At least div 3 will be rated.

Why ppl are lately participating comparitively less in contests? I remember seeing 40k

registered_participantsand 30kactually_participants! (not a long ago) But nowadays it's hardly 20k pplWell I bet some people had spring break last week, this week they're back to school.

Queue is too big.

queuedforces :noo:

long queue

The site is unusable for today's round,i have been waiting for 10 min to submit,it keeps loading.

I am sorry but The queue is too annoying today.

then just switch to another problem

That doesn't affect the fact that the queue was still too long

Also being able to get feedback that your answer is correct/wrong in a short amount of time is important in a format where speed is necessary, since it overpenalizes answers that fail the tests since you could be working on a different problem only to return to see that you WA'd on the problem you left

well then check the solution yourself before going to another problem

hope rated

this comment is in queue

For once, I won't believe that my poorly optimized G could survive, so guys, please hack my G submissions till TLE XD

Nice contest overall. I was infuriated by H at first since I skipped a crucial line in the statement, yet after that the problem was really nice, huge kudos to its setter.

My inexperienced self tried pretty hard, but sadly could not even get close. :(

Actually, isn't the worst case a highly composite number like $$$720720$$$ or $$$360360$$$? Then how did it get so close to TL (your solution passed my worst case test in about 1.5 seconds)?

Honestly I couldn't think of anything better than what you just stated. This is weird.

Maybe since a lot of numbers are the same in my testcase, the compiler magically optimizes stuff away? Or another reason might be that the server is slower during contests as opposed to during the hacking phase (I'm probably wrong about this one, if anyone knows about what difference there is, please enlighten me)?

Your first theory actually made sense, since caching, in regular cases, could be considered a CPU trait, and that would help speeding up if your testcases are identical.

Nice idea, I believe most of the time is wasted on (re-)allocation of

`visited`

, if you make it static I believe it would be a massive speed up.Just duct taped my code again and it actually worked: 255770022

Thank you, another thing to remember for future implementations.

Not as massive as I expected. This is more like it should be :)

`Is there an explain for this solution?`

Edit : Got it 255813710

Just got the time to have carefully reworked my codes. Putting stuff to global static, queueless the BFS, etc.

This should be good now, and the runtime is already covering some hacks.

255814613

how come there is such a big gap between this two implementation? (reallocation and looping reset

`visited`

) Isn't both operations`O(n^2)`

?nice problems

Ahh! I just figured out how to optimize my solution for E.

same man just did D, uploaded the file and submitted with 40 secs left,the submit didnt even register somehow!

can you explain your solution please

Given the constraints of the problem statement, it suffices to code a solution that works in

O(N^2)per test case. So, we can brute force over allnto find the largest possiblekthat can change the characters to 1's.How do we find out whether this can be done for some

k?If

s[i]is '0', then we must flips[i...i+k-1]. Fromi=n-kton-1, we can't create anymore flipping segments. Therefore, after performing some operations, we can check whethers[n-k...n-1]is only 1's. Iff so, thenkworks.Of course, flipping each

s[i...i+k-1]isO(k), which is slow. Instead, find out how many timess[i]has been flipped. Let this beflips. This can be done using a dequeD: whenevers[i]is '0', flip everything fromi...i+k-1 (incrementflips) and pushi+ktoD. Ifiis inD, decrease the current number of flips (decrementflips).For the remaining k values, check if

s[i]= '1'. We follow a similar procedure as before. To check ifs[i]is '1', check ifflipsis even or odd. If it is even, thens[i]did not change. Otherwise, it clearly changed. Ifiis inD, then decrementflips(as this was an endpoint like other flips).I hope this explanation makes sense.

RIP python users for F

Why?

SpoilerMy python code for 201^3 dp wasn't nearly fast enough.

SpoilerTell other method pls

Hint 1Hint 2Hint 3SolutionCodeThanks broski for writing this, I appreciate it.

SpoilerYou don't need the wacky 3D DP for F. I did a different method and it got AC in Python.

Can anyone please give a test case where my D solution will fail?

How do you handle this case?

Your code answer1 [9, 9, 9]

The right answer2 [9, 9, 9] [9, 9, 1]

Why is this giving a runtime error? My code works when I test it myself

Submission: 255757485

You have an out of bounds array access on line 30

B is harder than F.

I guess not, just do what is asked, nothing tricky is there.

only need to be careful about the conditions that matrix you form should be consistent from every path you choose to build it from.

update: corrected a typo

Think out of the box and B would be really easy.

Take the minimum element of $$$b$$$ is a new $$$a_{0,0}$$$, then construct $$$a$$$. Sort $$$a$$$ and $$$b$$$, and we'll now only need to check if two sorted lists are identical.

Quick proof:$$$1 \le c, d$$$, so it's certain that in a grid, the $$$(0, 0)$$$ cell will have the minimum value, as all other values will be it adding some non-zero positive value in.

Trying to compare B and F is so weird because they're so different since B is a "just code it" problem and F is a logic problem, but I definitely agree with this opinion since F is guess forcable and one of the integers isnt even that relevant (namely 4)

If they increased the integer maximum to be 8 I'd think that would make it a reasonable F problem

I think F should come before D. He's too easy in that order!!!

how to solve F, i have some idea, but was afraid of lot of case work solution so did not went ahead with my intuition

int main() { int tc; scanf("%d", &tc); while(tc--) { int a0, a1, a2, a3; scanf("%d%d%d%d", &a0, &a1, &a2, &a3); int ans = a0/2 + a1/2 + a2/2 + a3/2 + (a0 % 2 & a1 % 2 & a2 % 2); printf("%d\n", ans); } }

Check this solution.

I just followed the instructions step by step 255749602 (Maybe I'll get hacked).

you actually did what I was afraid of during contest, hats off.

how to be confident when writing casework solution, How to let go of this fear what if i miss some condition...

Apart from the computable parts (like time complexity) the rest is up to luck, I keep missing some condition which leads me to 8 WAs in C and E.

I'm not sure if I've got the right answer. I can't prove that my solution is comprehensive anytime soon, I just pray that he is.

Confidence is something that is affected in many ways, with Codeforces Round, just code what comes to mind, short time don't allow to think too much, you should think about the comprehensiveness of the solution at the end of the round.

you can just do dp[201][201][201] for first 3 numbers and 4th number is independent so just add d/2 in answer.

Can someone explain why 255755491 gets

TLEfor problem D. It should be O(nlogn),right?Briefly reading your code, I see that you used

`multiset::count`

.However, a quick google search shows that:

That could be it. However, I submitted the same code(255759509) with C++20 and it passes now in 452 ms.

UPDATE— Read the comment belowThanks for the help.multiset .count() was indeed the problem ,i replaced it with multiset.find() and it passes now. Code- 255761397

Video Solutions for all problems:

Video for A-D: Video for E-F: Video for G-H:

what a

intresting problem H, sadely could not solve it,can someone share the hints for it?

First, lets try to solve an easier version of this problem:

Ignore "However, each $$$r$$$ can only be used for

at most onetower."SolutionNow, it isn't hard to see that we can handle each tower independently. So, for each tower, for every possible radius. we calculate how much damage the tower will contribute. Then, we just take the maximum of those value. (Since it can be easily shown that $$$r \in [0, 13]$$$, a $$$O(nmkr)$$$ solution would suffice).

Going back to the main problem:

SolutionOur issue is that the same $$$r$$$ can't be chosen for more than 1 tower. However, note that this is just a classical maximum weight matching/assignment problem, which can be easily solved using Hungarian algorithm.

I completely missed that little detail about unique radius, but wasn't in time anyway.

You can just do bitmask dp in O(nm2^13)

did not know about this hungarian algorithm, will definately learn about this

Is the intended solution for G not this: Brute for all factors of gcd(a[0][0], a[n-1][m-1])?

If it is, why is the TL so annoyingly tight?

I also tried that and got absurdly close to TL. I even thought that I might have made some idiotic implementation error to have the execution time ramping up...

Fr it was so annoying, I submitted G, confident that it passes, and started coding F. 5 mins later I go back and see, tle on 24 🤡. Then I do some changes, submit, come back and see tle 🤡 Then finally I get it too pass, but it takes close to 2900ms and will get hacked 🤡

I was doing bfs using queue and for some reason it was taking a lot of time. Changing it to simple dfs made the runtime to only 296 ms. For your case however, i think your precomputation of factors is taking a lot of time.

I think that is the intended solution — 255735337

My $$$O(nm\log^2(A))$$$ solution uses 1/10th of TL

My this solution passes in TL easily

Spoilercontest shows how many problems with greed code that i can't write XD

Is this solution to G hackable. I stored all possible values of the gcd at cell $$$(i, j)$$$. I think it should work because there are at most $$$\log A$$$ values of the gcd on a path. Code:255759157

Can H be solved using maximum weight bipartite matching? I also used the observation that no tower would have $$$r > 20$$$, was this a wrong assumption?

Update: After looking at some other comments, I think I got the issue with my solution.

r would be less than 13

Yes. Please check https://mirror.codeforces.com/blog/entry/128243?#comment-1141662

A nice competition!

I enjoy it!

https://mirror.codeforces.com/contest/1955/submission/255756584

could anyone tell a counter test case where this fails for D

Spoilerthank you!

Nice contest. Problems were good. Thanks for the round mainyutin vmanosin7 ssor96 ZergTricky and all testers.

Also, congrats Geothermal on back-to-back wins!

div 2.33

Was the statement for problem A silently modified during the contest? More specifically, was the word "exactly" added or did I just miss it.

Dude I can swear there wasn't the word "exactly" when I first read it, maybe I just missed it...

Also I was mistaken at the term "a promotion", I thought that it can only be used once, but turns out I can use it multiple times. Got 2 WA on problem A lol

Seems like we just missed it... I checked a video and it did say exactly from the beginning. The only difference was that it wasnt bold.

Using a segtree on problem E be like

What's the solution for problem E?

Basically since $$$O(N^2)$$$ passes, you can test every possible $$$K$$$ from $$$N \rightarrow 1$$$ and return the first one that works. This step runs $$$O(N)$$$ times. The question is now: how do you check if operations of size $$$K$$$ can turn a string to all 1s?

First, notice that since this is just an XOR these operations are both commutative, associative, and their own inverse. So there's no point in applying the same operation to the same substring more than once.

With that, notice that if $$$s_0 = 0$$$, there is only 1 operation we can and must perform: invert {$$$s_0 ... s_{k-1}$$$}. Inductively, it is sufficient for us to apply the operation only when the first element in the operation is zero. This step runs also in $$$O(N)$$$, bringing our current total to $$$O(N^2)$$$.

The final step is figuring out how we can apply the operation very quickly. If we prefer typing or templates to critical thinking and reasoning, we can just use a range update / point query data structure like a Segment Tree, Fenwick Tree, Sparse Table, etc. I did this in during the contest 255770625 and made sure to statically allocate my segment tree instead of using

`std::vector`

so I didn't get hacked. I also manually coded this because I enjoy a nice hand-crafted segment tree (brainrot).However, instead of that beautiful solution, we can do it intelligently by inverting in $$$O(1)$$$ on the fly by keeping track of whether or not we are inverting, and then setting a reminder $$$K$$$ indices ahead to remember to start un-inverting. I did this after the contest 255903468.

Problem G and H are enjoyable. Enjoyed how there was such a simple solution to G if you made the appropriate observation. And problem H was very interesting, I implemented a dp bitmask, but some reason still getting WA on test case 4. I think I may have small bug, but I think the approach is correct.

can someone please tell me why this 255705783 is WA test 1 when I run it locally it gives me the correct output, furthermore when I switch the compiler to c++17 it gives TLE test 3 this time, maybe it's smth abt c++20 that I don't know ?

255760248 Why does this submission exceed TL ? I think the complexity is $$$O(n\cdot(n\cdot \log n))$$$

I realise this is most probably not the intended solution. But if it helps to understand the submission, I have just tried to go over all possible $$$k$$$.

Used PBDS for calculating if a current position has been previously flipped an even or an odd number of times.

For each $$$k$$$, considering all previous operations that have modified a position, I have never flipped a position that is currently a $$$1$$$ and always flipped a position that is currently a $$$0$$$.

IMO $$$\mathcal{O}(n^2 \log n)$$$ is a very dangerous complexity for $$$n = 5000$$$, and I would not gamble on it even with 3s TL.

You could actually improve this part by using a queue instead of a PBDS.

My $$$\mathcal{O}(n^2 \log n)$$$ solution got AC and ran in under a second with Fenwick Tree. 255763784

Thanks for answering. I was also guessing that PBDS is going to cause TLE even if $$$O(n^2 \log n)$$$ could have squeezed past the TL. Thanks for the queue insight too. I realised I know nothing about queues :)

The only thing I could suspect is that PBDS is already a high-coefficient $$$\mathcal{O}(\log n)$$$.

For the queue stuff, just imagine this assuming we're trying length $$$k$$$: store the starting points of all flipping segments in the queue, then when investigating index $$$i$$$, any starting indices up to $$$i-k$$$ has no value. Why a queue? We're iterating indices in ascending order, and added index would later be invalidated in that same order as well, which fits the FIFO nature of a queue.

Yeah, makes much more sense now. Thanks a lot and welcome back to CF contests.

I used PBDS for calculating if the current position has been previously flipped an even or odd number of times. Here's my submission.

I later realized we insert indices in a monotonically increasing fashion in the data structure we maintain. So we can also use vector/queue. With vectors we can use lower_bound and with queue we can pop the indices that are at a distance k of far than current k.

Vector solution: here Queue solution: here

All submissions you've linked are in queue at the moment lol.

But, yeah lesson learnt.

Don't be lazy and use sets everytime you want a sorted list.Now that you have put it this way. Its baffling how obvious this was and yet I missed it.

Want a sorted list. Want integer-positions. PBDS. TLE. Die.

Yeah it was pretty obvious but even I wasn't able to come up during contest so I did it using ordered set. It was only after contest when I realized it can be accomplished using vector.

And as AkiLotus mentioned, queue can be used to eliminate the logarithmic factor and achieve a linear solution.

can anyone explain the idea to solving D?

Sliding window. Just check for every segment of length m if there are atleast k elements in that segment that are present in b. Count can be maintained using a map.

I failed to see the key observation that GCD must be a divisor of both top-left and bottom-right corners, so I ended up solving a more general version of the problem which finds maximum gcd for each path from top-left corner to cell (i,j). Tbh it was a good problem to practice some prime optimizations although it was not intended.

bro my computer crashed during the contest and my coding software was deleted (dunno why) and any custom invocation would take more than 7min (dunno why) so i just had to randomly code on the submission site ToT

I usually use the one from AtCoder, it runs the code and gives the result faster than Codeforces most of the time.

use online compiler like online GDB or other there are many options and they are fast

what's wrong with my c ? pls check[submission:255762443]

F should be in place of B didn't read it during contest

Extremely easy problem F!!!!! -_^

## include

int main() { int tc; scanf("%d", &tc); while(tc--) { int a0, a1, a2, a3; scanf("%d%d%d%d", &a0, &a1, &a2, &a3); int ans = a0/2 + a1/2 + a2/2 + a3/2 + (a0 % 2 & a1 % 2 & a2 % 2); printf("%d\n", ans); } }

Spent half contest time to implement the simulation for problem C, couldn't make it but still a great experience.

Thank you guys for a nice contest!

same , you're not alone

I just realised problem G is but a simple BFS ToT

I have an ask for harder version of $$$G$$$ , same constraints , just your starting cell can be any cell inside the first row and finishing cell can be any of the last row , then how to solve it?

How is that any different? Just run dfs from every cell in first row instead of first and check if any cell is visited in last row instead of only bottom right.

Problem G is the same as https://community.topcoder.com/stat?c=problem_statement&pm=16140&rd=18085. Of course, it's not as big of an issue as Div 3s are supposed to be educational anyway, but just putting this out here :D

Can binary search be applied in E to make TC roughly NlogN

No, because function is not monotonic. For example, s=000 k=3 is possible, while 2 is not.

I don't think the function is monotonic

Why using qsort (C/C++) in B can be easily caused by Quicksort hack halyavin.cpp to cause TLE (e.g. 255659588) ?

It's the nature of quicksort algorithm itself to have $$$\mathcal{O}(n^2)$$$ worst case time complexity, thus as long as you know the sorting was a pure quicksort and you know how the pivot was chosen by the library, you could always counter it.

How to E

bruteforce + greedy

How to check if k is valid

well you have to choose some subarrays of size $$$K$$$ to invert and subarrays do have a unique starting index and so you put inversion on an subarray starting from a

particularidex at most $$$once$$$ so you start from the beginning , on your current index the value of the character in string is fixed so you can choose that index as starting point of a subarray or not(which is a certain choice), so if you do inversion the cost of that ends $$$K$$$ indexes later and if it's valid it will be at $$$\le n +1 $$$ and if valid you move on to the next index to check validity again otherwise invalid provedCan anyone suggest a tc where this fails for problem D :(255769513

1 4 3 2 1 1 2 2 2 2 2

Output should be 1

SpoilerOhh great! Thanks!

can anyone explain this solution to problem E? i fail to understand how we are checking if integer k is valid or not.

submission1 submission2 Why they are giving different answer? The only difference is in the solve() function only. Is this a CPP Bug or I missed anything? mainyutin

It may not be a reason actually, but most likely it is because you are not clearing your

dpafter/at the start of the next testcaseCan anyone tell me why my code of problem C 255769305 is giving TLE on testcase 3. I thought deletion in deque is O(1).

The time complexity of your code is O(min(s,k)), s = sum of durability of the ships. As s and k might be too large (k <= 10^15, for example), it would give TLE.

your solution time complexity is min(sum of all the element, k) which in worst case can go upto 2e14 like your are just simulating the process which is not optimal

required optimisation — in the while loop of q.size() and k

take the min of q.front() and q.back() if 2*mn <=k do this {

then reduce mn from front as well as back of deque then if q.front==0 do pop_front() and if q,back()==0 do pop_back()

} else break;

now if d.size() is greater than 0 check can we remove the first element (value should be <= (k+1)/2 if yes pop_front() do same for last element if it exist (<=(k/2))

I spent really a lot of time during the contest trying to make my

Esolution faster, even though it should haveO($$${n^2}logn$$$)complexity, which is withn <= 5000should pass the3second limit. The only thing that helped me was changinglong longtoint, but even so, it's still very slow. Does anyone have any idea why myEsolution is so slow (below is the final one)? And a similar question is aboutDas well, because I can't see any clear reasons why it is so slow:E:255741981D:255675779Edit:Sorry about how code inElooks like, I don't know why it shifted, because for me it was totally normal when I was sending it..

I too felt the cheating happened in this contest a lot, my rank was around 160ish before 1 hour end of contest, and i could not solve anything further was only able to solve 5(A-D and G) but somehow so many other peoples solved problems that my rank went to 700+, i was thinking maximum i can slide is around 300-400 but 700+ did not feel organic... I might be wrong but this is what i feel.

I feel like especially in the last 8-10 minutes, the spike of "AC'd" submissions shot up.

Bro this is common if you cant solve good problems , you solve the easy questions fast it doesnt mean that the people below you cant solve the tough one faster than you that happens everytime , the people who have much more knowledge will eventually occupy the rank

pray for me to reach pupil ^_^

Great Contest!!! Very nicely framed

does unsuccessfull hack have panalty in this round,

I tried to hack some solution, but failed will my score be affected by this?

No

Similarly,do successful hack doesn't affect your socre.

Was the cpp's hash function mechanics of unordered_map changed recently ?

cause i can't seem to hack solutions using the default unordered_map like before .

Can someone tell How can we solve G using bfs I was first storing the factors of the last number and then I was doing dfs and each time i find a new pair of gcd between two colunms then I am checking it to be divisible by a factor of last number . Help needed !!!

`gcd(matrix[1][1], matrix[n][m])`

Getting a tle by applying this on 35th testcase

Maybe you made a mistake caused this.

This is a sample 255813710

This is another one but with a lot of resets that slow the process 255812987

problem D first I used map for frequency and I got TLE I removed the map and I used a simple global frequency array but with t 1e4 and the frequency array being 1e6 it is not possible so what should I use here in this case?

you can use same frequency array but you zero it at the end of a testcase using only values in a and b . or you can use an map with custom hash

thanks the first one worked, I actually used a multiset for array m and used count() many time so maybe that's why I got TLE the problem is not in using map here because many people used map and it passed

Toooo many hacks for G.

you may want to rejudge G with a higher time limit, except you had a better intended solution

No I believe intended solution was O(d(maxA)*n*m) ,where d(n) is number of divisors of n , which easily passes the time constraints .

I've seen multiple solutions with the same complexity hacked, you can check the hacks for yourself.

Like this? 255813710

Many people were hacked on G.

Poor pretest.

My 320 hacks on G were about trying to achieve maximum number of possible GCDs for as many cells as possible, so that solutions that hold all GCDs using a slow data structure such as

`std::set`

will insert a lot of elements. My test made it more than a million elements per test case, and since we can have 20 of 100*100 tests in a single file, these solutions tried to insert more than 20M elements in total, leading to TLE.But it seems like there are far more intense cases, as even my possibly more optimized solution couldn't pass, as well as several LGMs' solutions, and now with all the

`Unexpected Verdict`

s we can assume even testers' solutions are hacked...Thank you for the explanation! I just woke up to a wall of hacks and was about to ask how so many seemingly reasonable solutions got hacked.

`std::vector`

+`std::sort`

+`std::unique`

was also hacked.Now just C-array+

`std::sort`

+`std::unique`

works good. https://mirror.codeforces.com/contest/1955/submission/255802770https://mirror.codeforces.com/contest/1955/submission/255802770 Hacked.

Just heard a news that the validator isn't checking the constraints on the sum of $$$nm$$$ properly, so it's allowing cases like $$$n=100, m=100, t=100$$$

https://mirror.codeforces.com/contest/1955/hacks/1012724 This hack basically just repeated my original hack 5 times and it didn't get

`invalid input`

. Writers, please check.I think this is kind of an emergency so I'll just poke them: mainyutin vmanosin7 ssor96 ZergTricky Vladosiya

MikeMirzayanov please take a look at this

Average div3 moment

Yes the test that hacked me uses t=999, n=100,m=100 which is not allowed under problem constraints.

Thanks a lot, working on it.

Now it fixed and all hacks are rejudged. I'm terribly sorry for such bug that I didn't notice.

Greatest hacker ever.

It seems that E is more difficult than F.

Can someone hack my solution in E? 255743941

it's O(n³) with an optimization

G is so humorous!!!

G-question is hacked to fly

what a sight. seeing Geothermal losing and regaining his high ranking after the contest

It seems that the validator for problem G is wrong. The problem said that the sum of n * m cannot exceed 2 * 10^5, but it can be hacked with such data.

can you give a submission for a reference?

Try mine, it will RTE#2226 in cases of violation.

hey, also look at mine, it's gonna FST https://mirror.codeforces.com/contest/1955/submission/255724529

The authors should change 2e5 to 1e5, and almost everyone with a logn factor passes

FST for sure, see this comment for countertest ideas. There are better solutions than that.

idk, why the testors had to make the problem so tight, and if yes, then they should have added this in pretests, i had a better solution in mind, but as this one passed, I wasn't bothered to submit another

I don't know either, strict TL isn't a first-time thing. I also got TLE on another "better solution" as well, and that was because of suboptimal alloc. Though, on hindsight, 2e5 usually is a vanilla constraints, so I do feel like them brushing it off is a normal instinct.

By the way, your earlier one won't pass, I just resubmitted to check and make sure — it still fails a test within limit.

yeah, as i said, it's because of the log factor, if the constraints are relaxed, mine might pass.

btw, yours is working?

Yeah, kinda — see the link I left on the first comment of this chain.

(I won't count tests from 36 and beyond as they breached the $$$2 \cdot 10^5$$$ limit for sum of all $$$nm$$$.)

Validate is wrong.

`cpp #include <bits/extc++.h> using namespace std; int main(void) { ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr); size_t constexpr T=30; cout<<T<<"\n"; for (size_t t=0;t<T;++t){ cout<<"100 100\n"; for (size_t i=0;i<100;++i){for (size_t j=0;j<100;++j) cout<<114514<<" \n"[j==99];} } return 0; }`

This passed the check.What is this ? I precalculated divisors for all elements upto 1e6 ( in MlogM time where M = 1e6 ) and solved the overall problem in (approx) cuberoot(1e6) * 1e5 time , still hacked ? solution

max number of divisors for numbers up to 1e6 is 240.

but it is still should be okay to pass

Ohho yeah right , my bad

The time complexity for the Python judge is not being properly set.

I got TLE at test 3 for my submission in python (submission no — 255718411) I got accepted for same code in Pypy 3.6 (submission no — 255806654)

Due to this , I have made additional 2 negatives. It's NOT FAIR If you want you can check in my recent submissions

Your Python submission and PyPy3 submission have different code. What are you complaining about? The Python one uses

`list.insert`

that is $$$O(n)$$$, and it's $$$O(n^3)$$$ in total, so I think TLE is the correct verdict.Just go to my profile and click on submissions and just click on show unofficial submissions and then check last two submissions (255848468 and 255848184)

So

`qsort`

is a poor way to solve cf problem? Since it can be hacked easily. I did not even imagine that qsort in stdlib have a O(n^2) situation, I thought it should have some method to prevent it from happening because it is in Standard Library! Forcing me turn to a cpp programmer? My rating is gonna drop for this ridiculous reason. ahhhhhhhhhh X(But I think write C in C++ is not a big deal.

You can implement your own sort and copy it if you're committed to using C .

It's not stdlib's fault. It's the algorithm's fault itself, as it has slow worst cases, but average cases being so fast that it is commonly used; yet in an environment where hack is allowed like Codeforces, worst cases actually matter.

Perhaps making your own sort next time? IMO implementing something like merge sort isn't even much more difficult.

Can anyone explain G? I thought this is a simple standard Dijkstra algo to keep track the GCD for each path with PriorityQueue?

Any path must start at (1,1) and end at (n,m) , therefore the gcd of the path must be a divisor of both. Simply check for each divisor if it could be the gcd using dijkstra or bfs.

Your approach is wrong though. A greater GCD on a node won't guarantee greater GCD at the end, in case that GCD was a large but obscure number, which would quickly get diminished later on, while the smaller GCD prevailed.

An example:

If you take $$$19$$$ as the GCD to go for cell $$$(2, 2)$$$, two $$$6$$$ on both possible ways onward from it will delete them all and result in a GCD of $$$1$$$ at the end.

Sorry I still not get it. https://mirror.codeforces.com/contest/1955/submission/255758743 is mine.

I did give a bad test to straight-up testing honestly.

Found your counter test though, and it looks even weirder.

How come it outputted $$$4$$$? (supposed answer is $$$16$$$).

I have a feeling that your code overwrote GCDs in a weird manner, leading to only one GCD being chosen and it's hard to tell when it's optimal or not.

When 684 342 19 6 684 then the tracked GCD becomes 1 and stay in the bottom of PQ. And other higher GCS in the other path can be considered in the next run.

Firstly I would like to acknowledge the contest author's effort and thank them. Now I can began my issue with the contest.

I think the statements for problems could have been more clear considering this is a Div 3. Also the explanations for the samples wasn't there or was not even helpful at all. I know that the author is not duty bound to explain the samples but with poor statement explanation I think this should have been done.

I did quite bad in the contest and to check whether I was feeling these issues because I did bad, I slept this off. Now even in the morning I feel the statements could have been better with better sample explanations.

It is so surprising to see so many G solutions are hacked. Given that my rather standard DP solution https://mirror.codeforces.com/contest/1955/submission/255745682 is accepted just fine, now I wonder whether I have missed something important, like a more advanced approach that usually works better.

The moment bro drew attention to himself...

Lmao

this can also be hacked sadly, I wrote similar solution and many more similar solution is hacked already.

Now it makes more sense. It appears that the hack used 200 tests of 100x100 matrix, with the sum of n*m being 2000000 which is 10 times of the limit as specified in the problem statement. So it is likely an invalid hack.

Hacked :)

There are tests added by hack, like Test #50, contains 800 sub-tests each with 100x100 input, with a total sum of n x m 8000000, which is 80 times of the upper limit as promised in the problem. Now the whole thing become less interesting due to these invalid hacks.

SpoilerVery good topic, each level is easy to difficult. Thank you

Can Someone Please Try to hack this: https://mirror.codeforces.com/contest/1955/submission/255768412

The problemset was good no cap. but it's really sad to see so many solutions being hacked. There's a lot to improve in testing.

so，is it rated？

fvck G

Wow... with what happening in G, I feel quite disappointed.

I could accept my code TLE'ing due to bad implementation caught in stresstesting, but allowing hacks to let loose because of validators going nuts?

Please, problemsetters, be extremely keen in validator writings. Crosstest and add various validator tests if possible. This is not even the first time in a long while this happened, and this problem even has pretty standard constraints that one shouldn't excuse of difficulty in writing conditional checks, so why letting the issue prevail?

I don't really want to disrespect the authors, the problems themselves are fine, but this time the underneath preparation has an absurdly critical hole that I feel like I need to raise my voice.

Proof that hacks go out of problem statements' defined boundaries, solution RTE with exit code 2226 is my personal indicator when that happens.

The bad thing for me in the contest is, that I solved G directly after D, a similar solution like Geothermal, yet got hacked. The good thing is I participated in VC :)

still I think the contest should be unrated as people who solved G directly after D would be paying prices otherwise :(

I think this will depend on what actually had happened underneath. The best cases would be that only hacks having those breaches, thus those tests could be removed, relevant hacks reverted, and contest rated as usual.

If even the original testset had limit breaches, then nope, unrated for sure (though as I quicktested the original testset was fine).

If we can remove those hacks and solutions can be rejudged then why not, that would be better

Wow I just resubmitted your best Rust solution, just to see it AC with 10x execution time.

Breaching hacks are insane.

unrated

How come this test case passed for Hack

This is 1000*100*100 well beyond limits

The same happened to me. Check this mainyutin.

Any idea why this code gets TLE on problem D ?

the time complexity of

`multiset::count`

is $$$O(n)$$$, not $$$O(\log n)$$$To elaborate on the above comment, it is $$$\mathcal{O(k + \log n)}$$$ where $$$k$$$ is the number of occurences of the sought number in the multiset. So if the frequencies of your numbers are small enough, you can use

`multiset::count`

. But, in general if you want to only check whether a certain number exists in the multiset,`multiset::find`

is strictly better, because it's exactly $$$\mathcal{O(\log n)}$$$, which is always better than $$$\mathcal{O(k + \log n)}$$$.Yes, this is more accurate.

How to write that equation or the formula O(K+logn) sir? If you dont mind can you explain a little bit with an example.

`$$$\mathcal{O(k + \log n)$$$`

(not actually three dollar signs, only one, but it's like this because if I don't put the backticks on either side, it just renders as $$$\mathcal{O(k + \log n)}$$$).$$$( O(K + \log n)) $$$ Thanks master. But how can I properly write this equation- $$$( O(nk^2/w$$$ + $$$k^3/w))$$$ can you tell me please.

`$$$\mathcal{O}(\frac{nk^2}{w} + \frac{k^3}{w})$$$`

This gives you $$$\mathcal{O}(\frac{nk^2}{w} + \frac{k^3}{w})$$$ (actually, I think your way ($$$\mathcal{O}(nk^2/w + k^3/w)$$$) looks better than this one, but you can use whichever one you think looks better). By the way, if you're interested in learning about LaTeX, this is a good place to start: https://artofproblemsolving.com/wiki/index.php/LaTeX:LaTeX_on_AoPS.

Thank you Master. I was going to asking you about LaTeX . Thanks!

thank you!

How was problem C guys? I was struggling to solve to solve it? But Finally I solved it.

A-find if 2*a<=b if so you can buy all ns with a, else buy (n/2)*2 with b and if n is odd add 1 B-sort the matrix and find the first number and then insert it in a vector, add d n times and find the value and insert them all in vector, then add c to the initial value of the matrix row and do this n times too C-Kraken attack (k+1)/2 shots from the start and k/2 shots from the end, just iterate over the array from the start and from the end and decrease the value as much as possible, if it becomes 0 add it to the answer D-store the values of b in map, and the values of first m elements in map, while doing that check if the values is second map were smaller than the value count in first map , if so do matched++, now iterate over the other values of a buy keeping an l(left) remove the left and add the right, simultaneously updating the map ,and updating the matched values as explained. E-Just iterate over all values of length to be the ans, then just reverse the length k segment whenever you find 0 in the string, at last if all are 1s this k is possible, hence find the maximum of such k F-first of all ans is a/+b/2+c/2+d/2 because their xor will be zero as the same value repeats twice, secondly is one of the a,b,c is absent then no further action is required as they wont add to the ans because of the placements of 1's in their binary representation, but is a,b,c are odd that means 1 ans can be extracted out of these 3 values hence ans++

rest ask from a higher rated coder,thanks :-)Why so many Hacks on G? Even mine is hacked. Whats ideal expected TC for G? Is it better than O(n*m*100). Rating of G has gone from 1900+ (yesterday) to 2500+ (now) on clist :(

The validator is incorrect, so tests which are above the limits can pass as hacks. But a fraction of the solutions are TLE even with a correct validator.

ohhh right thanks, then maybe I will wait till system testing :)

The test validator is wrong.

Can someone explain to me how to approach problem F. I can only think when count of all 1,2,3 and 4 is even and when cnt(4) is even and count 1,2,3 is odd. These could be the 2 cases when bob can win. Unable to code the solution. thanks in advance.

$$$cnt(4)$$$ is independent from the rest, so calculate it separately.

For $$$cnt(1)$$$, $$$cnt(2)$$$ and $$$cnt(3)$$$, I prefer splitting into two cases:

Pick the better case out of the two, then add $$$\lfloor \frac{cnt(4)}{2} \rfloor$$$ in for the final answer.

4 has independent bit compare others(1, 2, 3).

So you can try O(N^3) DP on one, two, and threes.

just calculate dp(one, two, three) + four / 2

255713576 Hey this is my first contest ever and only one of my submission got accepted. The thing is on running the same code for B , C and D I'm getting the required output but here on site it displayed otherwise. I understand that writing in python would slightly impact the time execution but probably shouldn't be the case up until i reach a way higher rating. So it would be great if someone could point out the logical errors if any or if there's way i should be submitting my code, thus providing me with pointers for the same. Thanks

Also in regards to my rating, given the rules i should be eligible to participate and this should be treated as rated for me but it is still shown as unrated.

I like your clean code, but you should optimise it a bit: 255745156

It's normal to perform poorly in first contests, with practice it will get better

i think it's time to give it a try to change my color

The time limit and constraints for G are so stupid

I am curios to know why I got TLE on test 35 in G: 255703960

It is simple, try all divisors of $$$a_{1, 1}$$$ with $$$O(nm)$$$ dp.

We will have maximum 240 divisors (from 720720).

So maximum $$$<5 \cdot 10^7$$$ operation.

`std::vector`

construction can be strange but time limit is 3 seconds, it allows use nearly $$$10^9$$$ operation I think.So how could I gotten TLE?

Some people with the exact same idea still pass for some reason. Very weird constraints and time limit.

I almost have the exact solution too and it TLE'd in test 35. Then, I changed vectors to global regular arrays and it passed.

This is not making sense, this is not testing the coder's ability to code

Yes, I see. But I think it is foolish, 20 times slower than expectation.

As I said,

`std::vector`

construction shouldn't affect very much.Even Jiangly wrote same solution as yours and got TLE,

this solution is so obvious, I did similar, but what I did I precomputed the the divisors till 1e6 in log2(1e6)*1e6 time.

still I have no clue how the hell my solution got TLE.

Take my words with a grain of salt, but my suspect is that the alternating testcases here was not for show, but a deliberate attempt to cause cache misses and thus slowing down any time a "true" test begins, making it work with a worst-case speed every time.

That's why I don't love after-contest hacking phase.

I also encountered this situation, and later I changed vis from a local vector to a global variable and it passed. I guess the 2D vector initialization in C++is very slow

`std::vector`

construction involves dynamic allocation (allocating from the heap). It is not a cheap operation. When $$$t = 10^4$$$ and $$$a_{1,1} = 720720$$$, you are doing it $$$240\times 10^4\times n$$$ times (times $$$n$$$ because you allocate for each of the rows). Which is significantly slower than just constructing once.Also, the nested

`std::vector<std::vector<...>>`

is not fully contiguous in memory, so you also get potential cache misses when you access the next row.Same code works fine locally though.

By locally do you mean your own computer or codeforces custom invocation?

Anyway, my point is that the difference between using a nested vector and constructing it many times, vs using a global array, is not subtle. And this could be a determining factor when the time limit is tight.

can you please tell why

vector::assignworks faster than just creating it everytime withconstructor?with

constructor: 255927707, TLEwith

vector::assign: 255927628, 734ms