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, nika-skybytska, willy108, ScarletS, mark, yuan-shen, Proof_by_QED, htetgm, buffering, TheYashB, 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 Proof_by_QED.
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
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
:)
My 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 get WA, TLE, RE, etc.
Untrusted participants = people who haven't yet participated in 5 rated rounds.
Thanks
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 -1073741571means 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:
could 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.
The 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) but sum 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).
To 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 callclear(), $$$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 callsclear()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_mapat all. In this case though, either making it a local variable, or just doingmp = unordered_map<int, int>();instead ofmp.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 toint64_t. This causescheck(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?
ps i have solve 5 questions
Your rating will be updated after system testing.
ok, thanks
One of my fav Contests. Finally contests with less math and more algorithms.
Loved it
when are the ratings updated?
After system testing.
My solution for question F got hacked thereafter I submitted the same solution and it got accepted, then the solution got hacked. Please help!!
Same with me. And why are the ratings not updated with new test cases then?
yes send me all solution of your last algroave contest they dont allow me to send msg more than 2 in same hour so i can't msg u there
I believe that the hack tests aren't yet added into the set. Best that we should wait until system testing finishes (which... I'd assume to be ~4-6 hours from now).
Can there be a possibility of hack been removed??
Realistically, no chance. Unless hacks are of invalid inputs that validator code from the round setters failed to catch, I don't see why (in most of the time) one should remove a hack test that would discern correct answers from wrong ones.
Don't use unordered set and map
But it is not showing system testing. If many have similar solutions , if mine is hacked then those solutions should also be considered as wrong submissions right?
Yeah. System testing will come much later, and it will include all the hacks presented. In a way, don't worry, those "similar solutions", if really similar, would fail eventually.
Why system testing has not even started yet? Is there something unusual or it is normal?
When will the ratings be updated??????
Problem F guarantees that the sum of h and n over all test cases does not exceed 2*(1e5) ... However, it seems like this constraint has not been enforced in quite a few hacks generated.
For example, https://mirror.codeforces.com/contest/1985/hacks/1041402/test
Nah, the test you showed clearly falls within constraints.
There's only one test with $$$h = n = 2 \cdot 10^5$$$, which is just right at the upper bound limit for both $$$\sum h$$$ and $$$\sum n$$$. Notice that there are no limits on $$$\sum a$$$ or $$$\sum c$$$.
Apologies, I though the constraint was ∑(h+n) <= 2*(1e5)
just virtualled it, a w div4 round as expected from the problemsetters orz
(i wouldve had a +100 delta if i had actually taken it :( sadge ) (help i used unordered_set by habit for h1, please no hack) (random gibberish, i am sleep deprived and have no concept of social cues anymore)
Why is this under unrated for me i did solve 3 question and i am under 14
the contest rating changes have not been finalized i assume?
Ig sooo yeah
can someone tell why is dsu giving tle in H1
I have done it using DSU you can see my solution https://mirror.codeforces.com/contest/1985/submission/265381378
Anyone please tell me why I am getting downvote in this comment
hey did you get it?
I am getting TLE on H1 here 265560987
solved without dsu 265581885
Here's my bfs submission for H1 if u r looking for
very good problem!
What does -1 indicates in the problem dashboard?
if this is for problem F, you were most likely hacked, but you can check what happened by double clicking the -1
has the result come for this contest?
C was little difficult for me , but it it was fun upsolving it.
When would this system testing ends? When we can see our final results ( final rating change) does anyone have any idea ?
that was awesome
I submitted my code for contest 952 (Div-4) Problem B 6 minutes before the contest ended, and it was accepted yesterday. However, today it is showing that it is still in the queue. Why is this happening?
System testing
They are conducting a second test
while system testing, they run the code for new testcases. So basically you code is there in queue for getting tested on new testcases.
okay...thanks for the info
so as of now , system testing is done what about updates in ratings ?? does anyone has any idea ?
I think within 2hrs
what ! is there any predictor that can show the estimated change ?
bro stay relaxed its ur 1st contest, there will be numerous contest! go and watch movie till then!
carrot extension
they just dropped it i guess
Could anyone please tell why my rating has not been updated?
Leave it
Div was very special
Why is it that my score has reached 1200, but I am still a newbie
Can someone help me to understand this discrepancy?
that's because in standings there are only trusted participants
Finally became pupil. Thank you for this round. Onto specialist now :D
Hello I want to ask about something I solve 2 questions in div 4 correctly from first try and my rate decreased why ?!
In simple words, at your rating, a better performance is expected from you.
It's more about the ranking than solving 2 problems.
Okay but I should have at least increased by less than 10 points, for example
tomato
Why am i getting TLE in my submission for H1 ? 265560987
I've just VP and solved 6 problems.
SO SORRY THAT I CAN'T PARTICIPATE OR ELSE I WILL GET MUCH RATING
Can someone please see what is the inefficiency here? When I manually run it on custom invocation in codeforces it says "Memory limit exceeded" however I have passed all the matrices by reference. Also, the code given here for graph paths — 1 is getting accepting by using a recursive implementation of binary exponentiation. I have used iterative implementation, still it is not accepted. Kindly have a look. This is for problem Graph Paths -1 of CSES under mathematics section
nvm I got the mistake
I participated in the contest but one of my solution "significantly coincides with solutions deified/265366837". I have not engaged in any type of such activities i know that for sure as my solutions are different from any other for which i got a rank of 187 whereas "deified" who had copied(without my consent)/similar code has got a rank of 523. If someone did a little bit similar syntax and now i am excluded from the context then i am not participating in any further context. Please look into the matter.
yes i know him. He is one of the top coders of JU. Please look into the matter.
I participated in this contest and have been accused for Plagiarism, with the user newbie333 265377444 while here is my submission 265318802. I have had no prior contact to the user, though our answers are visibly similar, Like idk how real are the chances of this happening, but i believe the approach written in solution is very standard.
Also there is a significant difference between the time of submission between us around an hour or so, Please consider this as mere coincidence and make this round rated for me again.
bro never expected this from you...
Actually, i'm only the normal participant like everyone and make sure that almoost all my answers are mine. When i received this report from the system, I'm extremely stunning that problem. To be honest, i do not know TarunAga prior in the real and even virtual life. how this happens?
I strongly agree with TarunAga opinion and his post, and i warrant that my submission was so late than his one about 1 hour, but this can not prove me as Plagiarism. I reckon that this issues should verify again and please consider is as a coincidence. Eventually, I hope the system to rate point for us again.
SoCloseButStillSoFar
Dear Contest Organizers, cry and MikeMirzayanov
I hope this message finds you well. I participated in the Codeforces Div. 4 round on Tuesday, June 11, 2024, at 20:05 UTC+5.5. I recently received a message stating that my code matches with many other submissions. I would like to sincerely clarify that I did not share my code with anyone, nor did I copy it from any source.
The problem I solved involved a straightforward implementation of a priority queue, which is a common approach and could easily result in similar code among different participants. Below is my code for your reference: 265367242
The solution relies on basic operations with priority queues and vectors, which can result in similar implementations by others independently. I am confident that this overlap is purely coincidental given the simplicity and commonality of the approach.
I kindly request you to review my case. I assure you of my honesty and integrity in this competition. Please make this round rated for me.
Thank you very much for your understanding and support. cry, MikeMirzayanov
Best regards, AnchalJain06
Dear cry
I participated in the Codeforces Div. 4 round on Tuesday, June 11, 2024. Today I received a message my solution of problem F is similar many other solution. I don't know how is it possible? Here is my last year contest submission 182009452 181980838 and this problem F solution is 265365007 . My last contest code and previous year contest code pattern is the same . And In this problem F , I used binary search for finding minimum number of turn and avoid TLE. I don't know why some of solution is the same. I suggested you check all of problem solution. I think you are understand easily.
Thank you.
Hi cry,
I wish to challenge the plagiarism case raised in front of me a week after the contest. I have been accused of coincidentally copying my solution for problem F from about 50 people. I do not know how, in the right mind, it was done or if anyone even looked at the codes. I am hoping that was automated so no one noticed. However, I compared my code to that of about ten people on this list. My code has been claimed to plagiarise the input style and the usage of the priority queue. Specifically, 2 loops for the input and a while loop for the priority queue. Now, I do not understand how anyone would claim that it comes under plagiarism because my code style, template, macros, and everything else are on point, like all my submissions I have ever made on this website. Not just in the contest but literally throughout my submission on this website. 265376036 is my submission for the problem. And I'll provide you with some more codes that have been claimed to be plagiarising with me. You can look at the solutions and everything.265299387 265380885 265377283 265359673. The parts being shown to be the same are how code is used on all of my codes. Please look into it.
orz
Hey there, I participated in this contest and it is showing my solution is copied from some 30+ ppl after a week. I think this was a pretty straight forward priority queue implementation qn. Now I don't know how that can happen as I use VSCode while writing the code. I was so happy that I was able to solve a lot of qns as the questions this time had less math involved and more algos. Please look into it. You can check that my other submissions also follow a similar pattern.
Regards
I tried running my code on ideone in default setting and someone copied my code and I was not aware about that.
Tomato
Good contest!