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, MC3297, 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
As someone who loves newbies, I hope this contest helps your rating!
I hope Pupil people directly reach Expert and get rid of two divisions
I despite them
My planned post-contest discussion stream
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!
Now i need to wait for the next Div. 4
The round feels more solid with sum and cry as problem setters! :)
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 :)
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 :^)
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
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
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
Most casual announcement ever.
What is the penalty of resubmission in this round?
10 minutes
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
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
Hope to reach pupil, also good luck to everyone!
All the best guys :))
what do these lines means? "ICPC rules + 12-hour open hacking phase.** Untrusted participants are not included in the official rank list."1.
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"
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. XDWow, 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 \gt 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.
Try to brute force the valid $$$n$$$ and see what does it look. It is pretty trivial after you see the pattern.
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.
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
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?
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 \gt =10$$$ there exist no $$$N$$$.
For $$$K \lt 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
even problem G got leaked
Is G a troll Problem???
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.
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.
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$$$.
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.
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.
Simple binary search works
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
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.
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.
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 :(.
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.
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
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
Editorial
A: Switch the first letters of both words and print them. https://codeforces.me/contest/1985/submission/26521678
B: If n=3 print 3 else print 2. https://codeforces.me/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://codeforces.me/contest/1985/submission/265232206
D: Track first and last #, when traversing grid, answer is the average of those. https://codeforces.me/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://codeforces.me/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://codeforces.me/contest/1985/submission/265293032
G: 1. Answer is ceil(10/k)^r — ceil(10/k)^l.
n^10 = n^8 * n^2.
https://codeforces.me/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://codeforces.me/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://codeforces.me/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 \gt 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
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
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
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.
In G, can someone explain why $$$k \gt 9$$$ doesn't matter?
$$$K = 10$$$, D(N*10) $$$=$$$ D(N) $$$\neq$$$ 10*D(N)
$$$K \gt 10$$$, D(N*(K + 10 * X)) $$$=$$$ D(N*(K<=9)) $$$ \lt $$$ 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://codeforces.me/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)$$$.
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.
Can someone explain how to hack? https://codeforces.me/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.
I also used priority queue.
https://codeforces.me/contest/1985/submission/265410338
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
why this solution got hacked? https://codeforces.me/contest/1985/submission/265344132
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.
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.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.
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.
My solution for question F got hacked thereafter I submitted the same solution and it got accepted, then the solution got hacked. Please help!!
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.
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://codeforces.me/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$$$.
can someone tell why is dsu giving tle in H1
Can someone help me to understand this discrepancy?
that's because in standings there are only trusted participants
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.
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 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.
SoCloseButStillSoFar
Good contest!