Hellowo Codeforcers :3

sum and I are very delighted, ecstatic, enchanted, euphoric, excited, exultant, jubilant, overjoyed, and proud to invite you to participate in Codeforces Round 952 (Div. 4), which will start on Jun/11/2024 17:35 (Moscow time). There will be $$$8$$$ problems, with one split into two subtasks, to be solved in $$$2.5$$$ hours.

As usual, I have to copy and paste the following...

The format of the event will be identical to Div. 3 rounds:

- 5-8 tasks;
- ICPC rules with a penalty of 10 minutes for an incorrect submission;
- 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
- after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
- by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only *trusted participants of the fourth division* will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as *a trusted participant of the fourth 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 1400 or higher in the rating.

**Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.**

We want to express overwhelming gratitude to the following individuals for making the contest possible:

Vladosiya and mesanu for coordinating the contest and reviewing the problems.

Dominater069, omeganot, Phi-001, flamestorm, nskybytskyi, willy108, ScarletS, mark, yuan-shen, vgoofficial, htetgm, buffering, yash_9a3b, haochenkang, ETL, natalina, MatthewC3297, and lcsc0 for testing the round.

MikeMirzayanov for the usual.

We suggest reading **all** of the problems as we have put mucho effort into all of them. Best of luck, mis amigos!

**UPD**: Editorial

Auto comment: topic has been updated by cry (previous revision, new revision, compare).ORZ

orz

As someone who loves newbies, I hope this contest helps your rating!

Thank you, master. :)

Thank you, sensei. :)

I hope Pupil people directly reach Expert and get rid of two divisions

hey i was wondering if when will the ratings be given?

Thank you sensei !

I despite them

yes sir

My planned post-contest discussion stream

i am waiting for this

Published 2 months ago! :O

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially.Aye aye captain!

bro love regular show too?

Now i need to wait for the next Div. 4

The round feels more solid with sum and cry as problem setters! :)

uwu :3

Woah!! Another Div 4 Round again... Let's Go!And gain some ratings!

The best part of testing was the brotherly camaraderie I shared with vgoofficial.

Thanks to my friends cry and sum for setting the contest. It will be fun for any Div 2 competitors, so even if you are out of contest you should give it a try!

I am honored

Will try to solve this round in rainboy style :)

what do you mean by that?

Dear USACO Bronze Participants,

I write to offer my sincerest apologies for the unexpected challenge presented by Problems 1 and 3 in the recent USACO Bronze contest. It appears my attempt to craft engaging problems inadvertently led us down a rabbit hole more labyrinthine than anticipated.

Upon reflection, I understand how frustrating it must have been to encounter such formidable obstacles, akin to stumbling upon a hidden boss level in a seemingly straightforward game. Rest assured, it was never my intention to transform the contest into a virtual odyssey fraught with unforeseen perils.

As the architect of these challenges, I take full responsibility for their unintended complexity and any resulting vexation. Please know that I am committed to rectifying this misstep and ensuring future problems maintain a balance of accessibility and intrigue. Your feedback is invaluable in guiding this endeavor, so please continue sharing your thoughts and experiences.

In the meantime, I hope you'll accept my heartfelt apologies and know that your perseverance in the face of adversity is truly commendable. Together, let's navigate this coding journey with determination and resilience, knowing that each challenge only strengthens our skills and camaraderie.

With sincere regret and gratitude, cry

which round was that ?

2024 us open

gotchu i will do my best even though im too highly rated

Last round, Div4 has just celebrated its 4th birthday, and it looks like we'll be saying goodbye to the SlavicG flamestorm mesanu era, meeting more and more interesting questions. Thanks all of you! :D

We need Errichto to come back and set an algoforces round :)

its not codeforces, its ! codeforces

cry orz

sto orz (just two cats about to fight)

why is cry crying (crying emojis)

Ladies and gentlemen, finally I can say what I've always wanted to say at Div. 4 rounds announcements: My first unrated contest :^)

Div-4 is Mental satisfaction for Newbies

Hope this contest will be perfect div 4 contest and Codeforce website won't be down or lagg AND thanks sum****

My first unrated contest , yay!

What if those whose rating is >= 1400 are restricted from registration? As we have seen this restriction in Div-1 contests. Then the submission queue and system testing will be smooth, I think. And you know, after the contest anyone can make submissions!

Every greeting synonyms of this blog could be the problem title of the whole Dashboard to make it more interesting!!!

Hopefully, I will make a comeback to reach CYAN after this round, insha-Allah.

lol

I am gonna reach Pupil at this contest!!

Best of luck! I hope you do great

thanks you! I hope we both will reach Pupil

what if we reach pupil than what there is nothing we get after reaching out there .

create 2 new problems and make a div 3 also.

New faces at Div.4? Hehe, time to do a clean AK for appreciation's sake. Congrats on your first Div.4 round!

As an unrated contestant i hope to solve the problems

Looks like the problems will be named

A.delighted

B.ecstatic

C.enchanted

D.euphoric

E.excited

F.exultant

G.jubilant

H.overjoyed,

that will be cool

i'd be sad if it isn't that like why'd someone find exactly 8 synonyms.

Isn't proud also a synonym?

sad

can i be rated ? i want to be rated because my rated is so ....

Specialist 1407 XD

The best writer...

I registered when I was an Specialist. It still shows asterik(*) next to my name. Will this be rated for me?

I guess you can try unregistering yourself and registering again

the frequence of div4 is really low,i sincerely hope all the trusted participants good luck, hope this will help u get rating

Most casual announcement ever.

What is the penalty of resubmission in this round?

10 minutes

I hope someday division 4 won't be rated for me ...

Hey, just a request.. during such rounds the servers can not take the loads ig and that happens to the mirror websites as well sometimes. Please take a look into that

Excited for Codeforces Round 952 (Div. 4)! Best of luck to all participants—let's solve some great problems and learn together!

Hoping to perform better after 2 poor performances .

hope my rating>0

Is the Div4 the easiest competition game in CodeForce?

no its hardest game ever on CF . God of CF also afraid to solve these div 4 problems

hopefully i can participate in a div4 soon!

What kind of self-destructive wish is this!

let's go!!good luck everyone

11003 users be like:I am gonna get a better rank than you !!! (Challenge me!!!)

In recent times, cheating is significantly increased and we the Newbies are suffering a lot :) It becomes harder to Newbies to increase ratings because of these cheaters.

Div 4 is like a Major Event to Us (Newbies). We eagerly wait for this round :D

I am delighted, ecstatic, enchanted, euphoric, excited, exultant, jubilant, overjoyed, and proud to participate in this round.

Well, this won't be rated for me, Good Luck to everyone

Hopefully my last rated Div. 4. Goodluck to everyone!

By seeing your submissions ,i think you are cooked.

Yeah I fucked up big time. Solved G literally 5 seconds after contest ended and apparently F got hacked. Unlucky.

Damn if you solved G that means you will reach specialist in the very next DIV2

Hope to get positive delta

Hellowo :3

:)

SpoilerMy first unrated contest

Good luck to everyone! I'm old and slow but if I don't solve at least ABC I'm going to tilt kek.

Hope to reach pupil, also good luck to everyone!

All the best guys :))

I hope I will get some point. UwU

Vai Kalke semistar final ☹️(Bangla)

what do these lines means?"ICPC rules + 12-hour open hacking phase.**Untrusted participants are not included in the official rank list."1.ICPC rules= after every wrong submission that's on testcase 2 or more,+10 minutes in penalty.12-hour open hacking phase= people have 12 hours to generate testcases to try and make anyone's code getWA,TLE,RE, etc.Untrusted participants= people who haven't yet participated in5 ratedrounds.nothing

My submission for problem D has been in queue for quite a while(>10 mins I believe). What should I do? Should I consider resubmitting?

The problems are easy so we get lots of submissions, queue will decrease soon, just wait.

Div 5

It's called "solvable for rated participants"

ABCD, I'll take it.

geometryforces... and negativedeltaforces for me :(

where did you see geometry?

D and E. To be fair D was just a simple observation- choose the row with the most number of '#'. But I just wanted to comment geometryforces for the fun of it :)

Woah, nice stuff for D. I solved D the lazy way and take the mean value of all x-coordinates and y-coordinates of

`#`

cells. XDOh wow, my old and slow brain convoluted this one way more than needed ... I found the first row with a single #, call it r1, then the other row with a single one (if it exists), call it r2, then center row is (r1 + r2) / 2, and center column is just the column with the single #. Row with just the most number of # would indeed be MUCH simpler and quicker heh, nice!

Wow, taking mean is an interesting observation. liked it! It might come in handy for some other problems, but maybe a bit of overkill for this problem. Anyways, I observed the first row where I get a

`'#'`

, and I know that this is going to be the column of the center. For the later rows, I only checked if this column has a`'#'`

in it. The center's row is the average of last such row and the first row.Can you explain to me why this method works? Thank you!

It's easy to see that a Manhattan circle is centrally symmetric at its center — that is, if a circle is centered at $$$(h, k)$$$ and there exists a point $$$(x_1, y_1)$$$ in the circle, then there will always be another point $$$(x_2, y_2)$$$ also within the circle such as $$$\frac{x_1 + x_2}{2} = h$$$ and $$$\frac{y_1 + y_2}{2} = k$$$.

We can keep discarding those pairs of points while calculating the average (coz' if a point has positive difference at x-coordinate from the center, its symmetric point will throw back at it with the same-margin negative difference, discarding themselves — and the same goes with y-coordinate as well). Eventually, there will only be the circle left, making it by default the average value of the x/y-coordinates over all points of that circle.

What is the approach in G (definitely not digit DP with such a big k, right)?

$$$k > 9$$$ means instant $$$0$$$. For $$$k \le 9$$$, denote $$$n = (\lfloor \frac{9}{k} \rfloor + 1)$$$, $$$ans = n^r - n^l$$$.

UPD:I made a terrible drunken mistake at first revision of this comment. Fixed now.can you explain more please

Try to brute force the valid $$$n$$$ and see what does it look. It is pretty trivial after you see the pattern.

By running simple examples, you can understand that this equality is satisfied only if there are no carries during multiplication.

For example, for k = 3, only the digits 0, 1, 2, 3 (amount = 4) are suitable to appear in any number, for k = 2, only the numbers 0, 1, 2, 3, 4 are suitable, amount = 5 for k = 7, only the numbers 0, 1 are suitable, amount = 2

Well, calculate amount ** r – amount ** l (of course with using mod and fast pow)

you can actually get solution's close form. Assume N = number of valid digits (if multiplied by k <= 9)

Then, res = ((N-1) * (N^l + N^(l+1) + ... + N^(r-1))) % MOD

You can use geometric mean to compute

(N^l + N^(l+1) + ... + N^(r-1) = (1 + N + .. + N^(r-1)) — (1 + N + .. + N^(l-1)).

Then use mod inverse to handle substraction

How to solve C?

If a number in the list is the sum of all other numbers, then it is the maximal number in the whole list.

Ohh!

Got it. Thank you for sharing the insights. Appreciated.

Suppose you have an array a1, a2, ..., an. You need to choose n-1 elements in such a way so that their sum is equal to the not chosen element. But because all elements are non-negative, the only way for that to happen is if the not chosen element is maximum.

Therefore you can keep track for each prefix two things: the current prefix sum, and the maximum element in that prefix. The prefix is good if sum — maximum = maximum.

My submission: 265313130

any counter example for problem E , submission

Can anyone please help me with my solution for H1, it gives runtime error on test 5. 265363442 Thanks for your time.

From my "investigation",

`Exit code is -1073741571`

means stack overflowAnd the culprit is the dfs function with too many parameters. Maybe you should try reducing the number of parameters by using some global variables, and see if it works

how do you do G? and is H1 related to graphs or can we do it without it

H1&H2 is floodfill, a common graph algo

H1 can be solved using DSU

I dont know DSU

really ?

yeah. You can reach purple without knowing DSU.If you are really good at DFS/BFS/floodfill and common DPs on graphs.

How did you get so good by just solving around 300 problems ,or do you practice at some other platform?

I did USACO prior (got to silver)

plus many years of math competitions.

So you practiced their training problems?

why our F is hacked, please help what was wrong with the code?

i see, then i would not be able to solve it

Explain your solution lil bit please?

H1: 1. Floodfill(look it up).

Create a row and cols array

During each floodfill,track which rows and cols can be reached(rows and cols within 1 of connected component. and size of connected component. Rows[row] += size, Cols[col] +=size. For each row and col reacheable.

For each '.' add one to its row and col.

Answer is max(max(rows),max(cols))

You can notice for $$$K>=10$$$ there exist no $$$N$$$.

For $$$K < 10$$$ you can form cases as follows:

Spoilercould you explain why k >= 10 there exist no N

It's impossible to make a decimal digit 10 times larger

i see thanks!

What is delta? How does rating work with respect to previous contest ratings?

Problem E was the best.

even problem G got leaked

Is G a troll Problem???

Yeah, first I thought of using digit Dp then used math and solved problem.

spend 20 min in E because I was doing cin>>x>>y>>x>>k instade of cin>>x>>y>>z>>k :)

Todays codeforces was very slow in loading too much frustrated

at one point I had four problems in queue

Subtle Flex...

How to solve E in less than O(n^3) ?

There are only 2 degrees of freedom(3 variables — 1 constraint). Iterate over those and get the 3rd from the constraint.

Because x <= 2000 and y <= 2000 you can brute force on just those two, and see if k is a multiple of their product. If that's true, z is going to be equal to k / (x*y).

The time complexity will go from O(x*y*x) to O(x*y).

265331162

But time complexity will be O(x * y * t) it is too much

It is guaranteed the sum of all x, sum of all y, and sum of all z do not exceed 2000 over all test cases.Wow, thanks!

It was so simple task

I try to find better time complexity, but did not notice than N^2 is enough

You can fix two coordinates and find the third one using $$$K / (i * j)$$$.

Then for {i, j, k} you can have at max 3! orderings of {i, j, k}.

For each of these orderings find the max answer.

Thank you everyone for the insights!! After a bit of trial and error got the n^2 approach working :)

Fun fact: E was originally proposed to be A of 887

Div2 ?

yes

Ngl I would have choked if it was a Div2 A

how to solve G

The answer is $$$x^r - x^l$$$ where $$$x = \lfloor \frac{9}{k} \rfloor + 1$$$.

By running simple examples, you can understand that this equality is satisfied only if there are no carries during multiplication.

For example, for k = 3, only the digits 0, 1, 2, 3 (amount = 4) are suitable to appear in any number, for k = 2, only the numbers 0, 1, 2, 3, 4 are suitable, amount = 5 for k = 7, only the numbers 0, 1 are suitable, amount = 2

Well, calculate amount ** r – amount ** l (of course with using mod and fast pow)

hello @cry !

i faced a very big technical issue in todays contest of server issue and i was not able to submit many solutions , most of time it was buffering for human verification.

please help regarding this matter.

same for me

number theory forces

How 'F' has 7k+ submissions? In [newbie, pupil] range it's 4k+? Am i missing a very simple idea?

You only need to know priority queues 265323773 (or binary search)

what ? It's not binary search on answer?

binary search works too

But still 7K+ for F by newbies is odd ,i mean they can but why would someone be 1000 rated if they knows this level of binary search. However it might be a case 1400+ people abusing Div4 by their alts.

I use binary search of answer

Simple binary search works

Wow! Binary Search works? I need to upsolve this problem! Thanx Master!

Hey! can you tell my why this binary search solution got hacked

Thank you

I think because you used int. You should have used long long. Also in the problem example you can see that they told ans can be large , use 64bit integer

same to me G was easier although I did not do it during the contest but I upsolved it still not sure how to do F

F is not a simple problem for Newbies and pupils .

most of the submission were done thanks to cheaters

i reached rank 900 during the first 1h:30 but when the cheats came out i was knocked to 3000

thankfully a lot of the submissions got hacked.

wasn't it just priority queue bash?

In Problem F, what was the safe upper bound to assume on the number of turns for the binary search? (Taking into account any overflow that may occur). I saw solutions with upper bound equal to 1e12, 1e13 and 1e17.

They can be hacked, correct way is to set upper bound LLONG_MAX, which isn't possible for any hacks

The boss health is maximum 2e5 and the worst case is 1 attack with 1 damage and 2e5 cooldown, so the upper bound should be 2e5 * 2e5 = 4e10 I think.

In the worst case: n = 1, with a = 1, c = 2e5, h = 2e5, so I think something close to 2e5*2e5

yeah thinking this i kept it as 1e12. still it got hacked any reason why?

Same man :(

Me too.

i made this in contest:

but it got hacked. However, this was accepted now:

I think that just the sum explodes in some test case for me.

i guess there are no new tests while hacking phase because i reload the hacked solution and it's accepted in my hacked solution exists the row sum>=h then break

When n=2e4,

and a[i]=2e5 and c[i]=1 for all i. Then total sum is close to 2e4*mid*2e5 if we don't break. Hence when mid comes to 2e10(assuming hi=4e10+1) then LONG LONG Overlow happens and due to which Binsearch will shift low pointer to mid.

I think this is the reason why many of the solutions got hacked because they forgot to break early just like me :(.

Solution

Still hacked with break :(

Because ur hi value is too high to begin with. Even if n=1, and in first mid evaluation, mid=5e17 and when we keep a[0] = 2e5 and c[0]=1. Then sum += (5e17 * 2e5) which again gives LONG LONG OVERFLOW.

Ah, so hi should be at most $$$\big\lfloor \frac{2^{64} - 1}{2\times 10^{5}} \big\rfloor$$$ huh? (assuming a unsigned ll)

during checking the m values, if the m value is big enough and c is small, and A is again large, then it easily overflows even int64. I got hacked for the same reason and only had to add a similar early return statement for it to not hack.

4*10^10 + 1

I tested it with testcase which gives the largest answer, and the largest possible answer is 39999800001 = (2*10^5)^2 — 2*10^5 + 1 with the test case: 1 200000 1 1 200000. In most solutions 1 is added after binary search, so you can search from 1 to 39999800000, but be really careful to handle the case when right edge of search is an answer, so better just search up to 4*10^10, this wouldn't slow down a solution

Also don't forget to check case when answer is 1 before the binary search

Nice problems, congrats for such a great contest.

very nice tasks

in F task

from 21 6 1 1 1 1 1 1 5 5 8 10 7 6

how we got 21?

Won't it be 27

Can someone pls give some hint in G. I got stuck there is it some kind of dp or math problem. And also hint for H2

H2 hint: fix the row and column ($$$r$$$ and $$$c$$$). Instead of calculating the total sum of sizes of connected components that would be connected if we paint $$$r$$$ and $$$c$$$,calculate the total sum of sizes of connected components that would NOT be connected if we paint $$$r$$$ and $$$c$$$.

G: If $$$k\cdot n$$$ results in any carry, $$$D(k\cdot n)$$$ won't be equal to $$$k\cdot D(n)$$$.

Thank you

More like Div 5.

the contest that i most enjoyed in a long time.

Can someone please explain the TLE in my submission of H1 265349188

I think your profile pic kinda explains some of it.

And the same code in C++ is accepted :( 265398650

Generally I would've suspected Java, but in this case I saw some C++ submissions getting TLE on nearby test cases, and some accepted Java solutions. So I thought there is some problem in my code.

I use C++ and my first solution without some optimizations got TLE, so I guess it does explain something lol

I'm not an expert in Java, but I can suppose a couple of possible causes:

If you are wondering, there is a determined $$$\mathcal O(nm \log(nm))$$$ solution with acceptable constant, and it also can be improved to determined $$$\mathcal O(nm)$$$

Regarding the first point, the solution using DSU is coming faster than DFS and BFS.

#265405138The second point is the main reason for TLE. Instead of precomputing the hashsets, I found them at the end only. The precomputation solution passed in C++ though :(

Regarding using HashSet instead of TreeSet, in Java if there are a lot of collisions, then the buckets internally works as a TreeSet (refer this).

So TreeSet and TreeMap are mainly useful when we want the values in sorted order.

In Problem E , for the Test case x = 4 , y = 3 , z = 1 and k = 6 , the optimal lengths i am getting is 2 , 3 , 1 , then answer will be is 3 ( (0,0,0) , (1,0,0) , (2,0,0) ) . but in problem statement it is given that answer is 4 . Anyone Please Explain !!!

Theres is a better set of lengths: 3, 2, 1, which gives 4 possible positions ((0, 0, 0), (1, 0 0), (0, 1, 0), (1, 1, 0)), and due to ban of rotation in any direction, this set is not the same as 2, 3 , 1

okay , Thanks ! !

Editorial

A: Switch the first letters of both words and print them. https://mirror.codeforces.com/contest/1985/submission/26521678

B: If n=3 print 3 else print 2. https://mirror.codeforces.com/contest/1985/submission/265225459

C: Keep track of sum and max of element as you scan through its prefixes. Count amount of times max = 1/2*sum. https://mirror.codeforces.com/contest/1985/submission/265232206

D: Track first and last #, when traversing grid, answer is the average of those. https://mirror.codeforces.com/contest/1985/submission/265242217

E: 1. Loop(a) through all values from 1 to x. If k divides a, loop(b) through all values y. If k/a divides b. Then c is k/a/b.

https://mirror.codeforces.com/contest/1985/submission/265319163

F: 1. Store a min-heap priority containing time of each attack and attack.

Until boss has 0 health, take top item of queue, and use attack.

For each attack decrease boss's health by attack strength, and insert a new attack of strength of current attack and time of current attack + delay time.

Answer is time of last used attack.

https://mirror.codeforces.com/contest/1985/submission/265293032

G: 1. Answer is ceil(10/k)^r — ceil(10/k)^l.

n^10 = n^8 * n^2.

https://mirror.codeforces.com/contest/1985/submission/265362645

H1: 1. Floodfill(look it up).

Create a row and cols array

During each floodfill,track which rows and cols can be reached(rows and cols within 1 of connected component. and size of connected component. Rows[row] += size, Cols[col] +=size. For each row and col reacheable.

For each '.' add one to its row and col.

Answer is max(max(rows),max(cols))

https://mirror.codeforces.com/contest/1985/submission/265337176

H2(take with grain of salt my solution passed with 1935 ms):

H1 but one must also have a point 2D array to track double counting. This happens in two ways.

For each connected for each row and col reachable, track the possible double counting by adding size to points[row][col].

For each '.' add one to points[row][col]

Answer is max(rows[row] + cols[col] — points[row][col]).

https://mirror.codeforces.com/contest/1985/submission/265384992

Sorry if some of the later solutions are messy.

For D you dont even need to keep track of the average of all rows, only the row with the highest number of #s.

Yes, you could get D by finding the meidan of the row with most endpoints.

I used average of top and bottom point ( firts and last on standard 2D array traversal).

madhavG — How did you develop the idea for G?

Sample cases + testing out some examples. It is obvious that if k>=10, there will be no solutions. Otherwise if k>=5: All solutions have 0 or 1 for all digits. Otherwise if k>3: All solution have 0,1,2 for all digits. So on and so forth.

Do you have a proof that for any $$$k > 10$$$ there are no solutions?

Not really, just intuition.

For digit sum to be multiplied by 10. A 1(smallest nonzero digit), must split into atleast 2 digits. And multiplication by 10, increases digit count by 1, not doubles it. Ergo, k>10 no sols.

Suppose we have a number in the form of 10a+b. The sum of its digits is (a+b)..and let us multiply a number k to it. Suppose k*b is of 2 digits and is equal to 10c+d. Hence we have:

k*(sum of digits)= k*(a+b) butsum of digits(k*n)= sum(10a*k + 10c + d)for the moment consider a*k+c do not have a carry. Hence the sum of digits will be equal to a*k+c+d.

Clearly k*(a+b) = a*k+10*c+d != a*k+c+d as an extra factor of 10 is added here. Similarly this can be extended for multiple digits and even if a*k+c does have a carry.

Thus we can conclude that had It been a carry, then the property would not have been satisfied. It's not a solid proof but it's the best reasoning I could come up with, after the contest. Hopefully it helps.

PS: This kind of a problem had already come on codeforces at some point in the past, where the result won't have been possible if we had carry. I just can't remember when. :(

Can you please explain your point 3/ in H1 madhavG?

"For each '.' add one to its row and col."This to cover for the fact that by changing each row to # you have to not only add all connected components touched by the row, but additionally must add all . that are now #, which would not be covered by connected components as they only include squares that are #

in H2, if there was test like that, it would be TLE?

cause of

my solution 265691252 with approach like your this test takes 7.3 sec on my PC

huh, it says acceoted, you prolly just have a slow PC

My H2 idea is similar , but ending up in TLE in test case 7 , can u help ?

probably due to using pof sets

idea : there is an edge connecting two components if some c or r is replaced . sum of degs can not be more than 3*n*m , now at each component , i am pairing up (r,c) sum over ri*ci <= O(n*m) where ri = no of r connections while ci = no of edges by the column c at the connected component i .Please point out mistakes if any .Thanks in anticipation.

AkiLotus can u help please ?

why is carrot not working ????

it works now

when contest is going, api calls often disabled

My H1 runs surprisingly slow, can someone tell me why? I'm sure it's something in my implementation but I don't know what. Feel free to hack if possible: 265367113

std::set is generally slow. Especially since $$$n.m \leq 10^6$$$.

But in my solution, I used 2 vectors to hash the size values of each component and got a TLE. But when I converted it into set and map, it passed, albeit still with a high time.

Map Submission

Vector Submission

Most probably because of set and map in general, my solution uses set and map too and I got TLE, but I tried some optimizations so it got accepted in 452 ms

You probably don't have to worry about it though, I think your time is still safe

=> Speedrun ABCDEF in 1.5 hour

=> Stare at G for 1 hour

I really hate cheaters. if you're a cheater and reading this duck you. I also wish a shitty days for the president of a certain country for spoiling my contest.

I enjoyed the problems a lot, G and H1 were especially neat. Thanks!

Hint for H2, please. For H1, I individually checked each for each row; what's the size that's getting added if we set all cols in the row to '#, i did the same for cols and chose the max as ans,

Codeforce server becomes very slow specially on div4 contests

After long time ,,,

Cloudfare forces, jokes aside it was a really good contest for me. I am not that good but I xould solve upto E! And I guess F would have required a solution with priority queue, but I was too slow to implement it.

cloudfare blocked me from getting H2 in comp, but I got it within a minute post-comp.

I request this contest to be unrated atleast for me , the servers were not working 98% of the time.

In G, can someone explain why $$$k > 9$$$ doesn't matter?

$$$K = 10$$$, D(N*10) $$$=$$$ D(N) $$$\neq$$$ 10*D(N)

$$$K > 10$$$, D(N*(K + 10 * X)) $$$=$$$ D(N*(K<=9)) $$$<$$$ K * D(N).

Didn't get the second part, how is D(N*(K + 10 * X)) = D(N*(K<=9)) and D(N*(K<=9)) < K * D(N)?

as the case will be only valid when k*(any digit of n) will be a single digit number , as if it will be more than 1 digit the case get invalid (digit sum case). look into my code the case ll y=9/k+1; it will always be 1 . 265330453

if u r asking for a proof idk , but if u run a bruteforce code u will find that when n > 9 , answer is always 0

Why is my code for problem H1 giving TLE on test 10?

I used dfs algorithm keeping ids of each component in the visited grid and stored the size of each of the component ids in a map.

I then traversed the grid row-wise and column-wise to get my answer.

Here is the link to the submission : https://mirror.codeforces.com/contest/1985/submission/265376706

number of component can be $$$\frac{n\times m}{2}$$$ (think of a chessboard). So the $$$id$$$ in your code is $$$O(n * m)$$$, thus your for loop that involves constructing $$$visid$$$ is $$$O(n^2\times m)$$$.

Ohh that makes so much sense. I'll try to optimize it.

Your code probably fails in a test like this:

Your solutions runs in $$$O(max(n,m) * id)$$$ (because of declaring the vector $$$ids$$$ each time). The size of $$$ids$$$ may be large. In order to prevent this, you can use a global $$$ids$$$, and a queue to keep track of the components you choose. In the end of the iteration, you can empty the queue and reset only those $$$id$$$'s that were changed.

Yes it makes sense. I'll try to optimize now.

I got it!! The queue worked and I understood why it was necessary.

Thanks a lot for this hint. This is my first time solving a H1 problem. Just wish it clicked to me during the contest itself

Can someone explain how to hack? https://mirror.codeforces.com/contest/1985/submission/265283368

Just hoping that the cheaters are caught:( . I saw many codes which looks like they have been copied from some other sources.

I was looking at the java submissions for this contest, almost 50% of them are chat-gpt converted codes for harder problems

Yeah i also saw many codes from python and it looked like they had been taken from ChatGpt or elsewhere

can any one tell me what is the wrong 265398472

**There must be an overflow in sum ** for(int i = 0 ; i < y; i++){ sum += v1[i]*((mid/v2[i])+(mid%v2[i]>0)); }return sum >= x;

ok thanks iam just use break and this was the wrong

I have solved F using priority queue Submission, i think its quite complex implementation of mine. Could someone check and tell me whether we have a better and neat approach for the same question. Also I would like to get the hints to solve this using binary search. Thanks

binary search on answer. fix a turn (mid) , and calculate the maximum health damage you can do with mid. then compare it with h.

thank you.

Binary search on answer(number of turns).

SpoilerTo find whether we can make health $$$0$$$ in $$$t$$$ turns, check the damage caused in $$$t$$$ turns $$$>=h$$$, i.e, $$$\sum_{i=1}^{n} \frac{turns*d_i}{c_i} >= h $$$.

Submission Link: 265400088

Also, look at neal's submission for neat implementation using map: 265249231.

thanks a lot for the links.

I also used priority queue.

https://mirror.codeforces.com/contest/1985/submission/265410338

hi, i have a question I solve problem A and B with penalty =17… and my standing is like 20000 in the official…when other users with my performance are in like 14000…I don’t know why is this happening

When will people stop?

In most recent hacks, I didn't even check anything other than these three lines:

and just one test data was enough to hack like 30 submissions which had these lines. Now where is the source of this?

To explain the hack: Apparently, there has been a long-living bug with GCC's

`unordered_map::clear()`

that it keeps its bucket size, so clearing takes $$$\mathcal{O}(x+k)$$$ time where $$$x$$$ is the number of elements and $$$k$$$ is the bucket size. While $$$x$$$ is reset to 0 everytime we call`clear()`

, $$$k$$$ remains the same so we can just insert a whole bunch of elements in the map in the first test case, and with the remaining 9999 cases we can spam $$$n=m=1$$$ so that it calls`clear()`

9999 times, each taking $$$\mathcal{O}(nm)$$$ time where $$$n$$$ and $$$m$$$ comes from the first test case.That's interesting. We should avoid using unordered_map. Is initiating the map locally for each test is better?

In most cases it's better not to use

`unordered_map`

at all. In this case though, either making it a local variable, or just doing`mp = unordered_map<int, int>();`

instead of`mp.clear()`

also works.Initiate local also variables consume time also. At some point, we can get TLE if we declare local variables and it got AC when moving to global variables. But yeah, will keep in mind to avoid using

`unordered_map`

.OOT, observing your hacked solution, I cant help but notice that people do like to write stories in their code :)

See this, 265373769.

Lots of useful statements like

to escape plagarism.

Are such tricks good enough to escape plagarism? MikeMirzayanov Vladosiya

Will any actions would be taken in order to address this? Atleast people who used these unnecessary for loops should be punished.

why my submission of C got hacked?

why this solution got hacked? https://mirror.codeforces.com/contest/1985/submission/265344132

Because you used unordered_set (tc is O(n) for very large n values) ordered set shd work fine

Unordered variants of set and map are pretty easy to hack with one simple idea, which djm03178 described in one of the comments above. From my experience, if your idea does not work with set/map complexity, then it is probably wrong.

Thanks dear. Got the point.

why so many F got hacked? my F: https://mirror.codeforces.com/contest/1985/submission/265337189

agree

ok it's overflow cause i set too high upper bound for binary_search

1

3 2

200000 4

1 1

the sum of damage will be to big i think (may be (2*10^5)^4)

anyone can you give test hack problem F

Idk why I'm posting it now, but here's a testcase for hacking problem F:

1 200000 100 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

In F, if you accumulate the total damage at the first iteration of binary search (

`check(mid)`

), it can go to $$$n*a*mid$$$, with mid going at least to $$$\frac{h*c}{2}$$$ which is around 2e10. So the total accumulated sum can go up to 8e20 at best, which explains the reason why many got hacked in F (it overflows, but overflows to the point where the accumulated sum produces negative results when casted to`int64_t`

. This causes`check(mid)`

to be false (while it is actually true), thus it creates a wrong answer (the range of binary search is now wrong)). To fix this it is usually needed to fast break out of the loop or use`__int128`

.As newbie, I solved 4 problems (current rating 733), will it level up my ratings?

I enjoyed a sound sleep after scoring 6 problems. After waking up, my 'F' got hacked!!! Thanks for not hacking the submission before my sleeping time.

same, bro

Can anybody tell me what is the use of hacks, And what happens if I successfully hacked others solutions??

Hacks here are tests added by users during a contest (Div.1+Div.2, not Educational) or in a hacking phase (Educational/Div.3/Div.4) that satisfy the problem constraints, yet make an Accepted solution (the one you're hacking) either giving different answers from the jury (rendering WA) or stumbling onto TLE/MLE/RTE/etc..

For those rounds with hacking phase, you simply contributed to the final testset. For Div.1/Div.2 rounds, you actually gain points when hacking successfully (but before doing so you have to lock your problem first, thus not being able to resubmit in-contest and now prone to other hacking you should that solution is incorrect as well), though chances are low as present rounds seem to have pretty strong testsets to start with.

Oh! got it, Thanks.

Here is test case for overflow hacking: https://upfile.live/download/7609ae3e/

Hacking is so scary

Can you check question F for me?

Can anyone look at why my E got hacked?

https://mirror.codeforces.com/contest/1985/submission/265354724

Problem F : Can someone please help me in finding the mistake in the following code . It got accepted during the contest but now it is showing hacked.I am not able to find the mistake .

Submission

Thanks

Run your code for the below test case: 1 1 1 200000 1 It overflows and returns 92233720368548 instead of 1.

Can anyone tell me why am I getting Runtime error for my submission 265366493 for H1?

Approach : Mark all the connected components and store their size in a map. When marking a particular row or column, take all component and add their size.

Same approach is passing that test without Runtime Error 265347306 but giving MLE.

my rating is 987 <1400, i have given this contest but it is unrated for me. why is it?