Hello! Codeforces Round 938 (Div. 3) will start at Apr/08/2024 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.
You will be given 6-8 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for the wrong submission in this round is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Problems have been created and written by our team: mainyutin, vmanosin7, ssor96 and ZergTricky.
We would like to thank:
Vladosiya for help with ideas and great coordination of the round;
ace5, Nickir, senjougaharin, vladmart for yellow testing;
natalina for blue testing;
bitthal04 for cyan testing;
Alequisk, Mohamed_Hesham for green testing;
MikeMirzayanov for Polygon and Codeforces platforms.
Good luck!
UPD: There was an issue with the validation of hacks for problem G, but it has now been resolved. All successful hacks will be rejudged. Pretests were not affected by the issue and remain unchanged.
UPD2: Editorial is out.
yay div 3!!!
hopefully i get to 1500
do just rating++)
spoiler hopefully i get 1200
i am new here , i participated in this round and my current rating is around 800 , but now this contest is showing as unrated on my profile . i dont get it , it clearly says -"Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you."
It will take some time for ratings to change
Don't worry! The rating calculation hasn't been completed yet. And there seem to be some issues with Problem G, so the rating update for this round may be further delayed.
ok, thanks
authors pic??
mainyutin orz
No pics with pizza.
Experts be like: I'm out of competition (つ▀¯▀ )つ
I appreciate the creators' effort on this div.
Is that a gan cube :o
Yes, it is GAN 356 M
PB?
Best ~17 sec, average ~26 sec
ooh nice... my best-9s avg-14s ... i think my cube's the predecessor of your cube ... gan 356x
Let this be the round where i shall become Pupil under the Heavens .
It's divine Conviction that i shall fulfil.
In the name of all mighty Behelet behold my Pupil Rank
Thou shall fulfill thy prophecy.
Good luck to everyone! I'll sadly have school but I'll find a way to participate since cf >>>>>>>> school
Contest > School
i think it's time to give it a try to change my color
Very Saaaaaaaaad
I am not participating :(
Hope to be pupil after this contest
Good Luck!!!!!
i am new here , i participated in this round and my current rating is around 800 , but now this contest is showing as unrated on my profile . i dont get it , it clearly says -"Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you." , can you please explain what am i missing.
Hope to be specialist after this contest
Good luck to everyone!
Authors' photos again!
Hope I can get back to my real rank of pupil
orz sir
hi everyone, mwah. i love yall. happy contest day! wish you good luck. mwah. (please downvote me)
should i participate or nah?
yes bro participate believe in yourself
OMG! Another mainyutin round ...
OMG! Another mainyutin round...
The cat is so cool!
cute cat-meme owo
Back to Expert
Bro did a manifestation
lmao
Bhai it's IQ 69. If you have a bad performance in div2 and you are becoming a specialist from Expert and the next contest is div3. Let the rating fall. At least div 3 will be rated.
Why ppl are lately participating comparitively less in contests? I remember seeing 40k registered_participants and 30k actually_participants! (not a long ago) But nowadays it's hardly 20k ppl
Well I bet some people had spring break last week, this week they're back to school.
Queue is too big.
queuedforces :noo:
long queue
The site is unusable for today's round,i have been waiting for 10 min to submit,it keeps loading.
I am sorry but The queue is too annoying today.
then just switch to another problem
That doesn't affect the fact that the queue was still too long
Also being able to get feedback that your answer is correct/wrong in a short amount of time is important in a format where speed is necessary, since it overpenalizes answers that fail the tests since you could be working on a different problem only to return to see that you WA'd on the problem you left
well then check the solution yourself before going to another problem
hope rated
this comment is in queue
For once, I won't believe that my poorly optimized G could survive, so guys, please hack my G submissions till TLE XD
Nice contest overall. I was infuriated by H at first since I skipped a crucial line in the statement, yet after that the problem was really nice, huge kudos to its setter.
My inexperienced self tried pretty hard, but sadly could not even get close. :(
Actually, isn't the worst case a highly composite number like $$$720720$$$ or $$$360360$$$? Then how did it get so close to TL (your solution passed my worst case test in about 1.5 seconds)?
Honestly I couldn't think of anything better than what you just stated. This is weird.
Maybe since a lot of numbers are the same in my testcase, the compiler magically optimizes stuff away? Or another reason might be that the server is slower during contests as opposed to during the hacking phase (I'm probably wrong about this one, if anyone knows about what difference there is, please enlighten me)?
Your first theory actually made sense, since caching, in regular cases, could be considered a CPU trait, and that would help speeding up if your testcases are identical.
Nice idea, I believe most of the time is wasted on (re-)allocation of
visited, if you make it static I believe it would be a massive speed up.Just duct taped my code again and it actually worked: 255770022
Thank you, another thing to remember for future implementations.
Not as massive as I expected. This is more like it should be :)
Is there an explain for this solution?Edit : Got it 255813710
Just got the time to have carefully reworked my codes. Putting stuff to global static, queueless the BFS, etc.
This should be good now, and the runtime is already covering some hacks.
255814613
how come there is such a big gap between this two implementation? (reallocation and looping reset
visited) Isn't both operationsO(n^2)?nice problems
Ahh! I just figured out how to optimize my solution for E.
same man just did D, uploaded the file and submitted with 40 secs left,the submit didnt even register somehow!
can you explain your solution please
Given the constraints of the problem statement, it suffices to code a solution that works in O(N^2) per test case. So, we can brute force over all n to find the largest possible k that can change the characters to 1's.
How do we find out whether this can be done for some k?
If s[i] is '0', then we must flip s[i...i+k-1]. From i=n-k to n-1, we can't create anymore flipping segments. Therefore, after performing some operations, we can check whether s[n-k...n-1] is only 1's. Iff so, then k works.
Of course, flipping each s[i...i+k-1] is O(k), which is slow. Instead, find out how many times s[i] has been flipped. Let this be flips. This can be done using a deque D: whenever s[i] is '0', flip everything from i...i+k-1 (increment flips) and push i+k to D. If i is in D, decrease the current number of flips (decrement flips).
For the remaining k values, check if s[i] = '1'. We follow a similar procedure as before. To check if s[i] is '1', check if flips is even or odd. If it is even, then s[i] did not change. Otherwise, it clearly changed. If i is in D, then decrement flips (as this was an endpoint like other flips).
I hope this explanation makes sense.
RIP python users for F
Why?
My python code for 201^3 dp wasn't nearly fast enough.
Tell other method pls
Thanks broski for writing this, I appreciate it.
You don't need the wacky 3D DP for F. I did a different method and it got AC in Python.
Can anyone please give a test case where my D solution will fail?
How do you handle this case?
1 [9, 9, 9]
2 [9, 9, 9] [9, 9, 1]
Why is this giving a runtime error? My code works when I test it myself
Submission: 255757485
You have an out of bounds array access on line 30
B is harder than F.
I guess not, just do what is asked, nothing tricky is there.
only need to be careful about the conditions that matrix you form should be consistent from every path you choose to build it from.
update: corrected a typo
Think out of the box and B would be really easy.
Take the minimum element of $$$b$$$ is a new $$$a_{0,0}$$$, then construct $$$a$$$. Sort $$$a$$$ and $$$b$$$, and we'll now only need to check if two sorted lists are identical.
$$$1 \le c, d$$$, so it's certain that in a grid, the $$$(0, 0)$$$ cell will have the minimum value, as all other values will be it adding some non-zero positive value in.
Trying to compare B and F is so weird because they're so different since B is a "just code it" problem and F is a logic problem, but I definitely agree with this opinion since F is guess forcable and one of the integers isnt even that relevant (namely 4)
If they increased the integer maximum to be 8 I'd think that would make it a reasonable F problem
I think F should come before D. He's too easy in that order!!!
how to solve F, i have some idea, but was afraid of lot of case work solution so did not went ahead with my intuition
int main() { int tc; scanf("%d", &tc); while(tc--) { int a0, a1, a2, a3; scanf("%d%d%d%d", &a0, &a1, &a2, &a3); int ans = a0/2 + a1/2 + a2/2 + a3/2 + (a0 % 2 & a1 % 2 & a2 % 2); printf("%d\n", ans); } }
Check this solution.
I just followed the instructions step by step 255749602 (Maybe I'll get hacked).
you actually did what I was afraid of during contest, hats off.
how to be confident when writing casework solution, How to let go of this fear what if i miss some condition...
Apart from the computable parts (like time complexity) the rest is up to luck, I keep missing some condition which leads me to 8 WAs in C and E.
I'm not sure if I've got the right answer. I can't prove that my solution is comprehensive anytime soon, I just pray that he is.
Confidence is something that is affected in many ways, with Codeforces Round, just code what comes to mind, short time don't allow to think too much, you should think about the comprehensiveness of the solution at the end of the round.
you can just do dp[201][201][201] for first 3 numbers and 4th number is independent so just add d/2 in answer.
Can someone explain why 255755491 gets TLE for problem D. It should be O(nlogn),right?
Briefly reading your code, I see that you used
multiset::count.However, a quick google search shows that:
That could be it. However, I submitted the same code(255759509) with C++20 and it passes now in 452 ms. UPDATE — Read the comment below
Thanks for the help.multiset .count() was indeed the problem ,i replaced it with multiset.find() and it passes now. Code- 255761397
Video Solutions for all problems:
Video for A-D: Video for E-F: Video for G-H:
what a intresting problem H, sadely could not solve it,
can someone share the hints for it?
First, lets try to solve an easier version of this problem:
Ignore "However, each $$$r$$$ can only be used for at most one tower."
Now, it isn't hard to see that we can handle each tower independently. So, for each tower, for every possible radius. we calculate how much damage the tower will contribute. Then, we just take the maximum of those value. (Since it can be easily shown that $$$r \in [0, 13]$$$, a $$$O(nmkr)$$$ solution would suffice).
Going back to the main problem:
Our issue is that the same $$$r$$$ can't be chosen for more than 1 tower. However, note that this is just a classical maximum weight matching/assignment problem, which can be easily solved using Hungarian algorithm.
I completely missed that little detail about unique radius, but wasn't in time anyway.
You can just do bitmask dp in O(nm2^13)
did not know about this hungarian algorithm, will definately learn about this
Is the intended solution for G not this: Brute for all factors of gcd(a[0][0], a[n-1][m-1])?
If it is, why is the TL so annoyingly tight?
I also tried that and got absurdly close to TL. I even thought that I might have made some idiotic implementation error to have the execution time ramping up...
Fr it was so annoying, I submitted G, confident that it passes, and started coding F. 5 mins later I go back and see, tle on 24 🤡. Then I do some changes, submit, come back and see tle 🤡 Then finally I get it too pass, but it takes close to 2900ms and will get hacked 🤡
I was doing bfs using queue and for some reason it was taking a lot of time. Changing it to simple dfs made the runtime to only 296 ms. For your case however, i think your precomputation of factors is taking a lot of time.
I think that is the intended solution — 255735337
My $$$O(nm\log^2(A))$$$ solution uses 1/10th of TL
My this solution passes in TL easily
contest shows how many problems with greed code that i can't write XD
Is this solution to G hackable. I stored all possible values of the gcd at cell $$$(i, j)$$$. I think it should work because there are at most $$$\log A$$$ values of the gcd on a path. Code:255759157
Can H be solved using maximum weight bipartite matching? I also used the observation that no tower would have $$$r > 20$$$, was this a wrong assumption?
Update: After looking at some other comments, I think I got the issue with my solution.
r would be less than 13
Yes. Please check https://codeforces.net/blog/entry/128243?#comment-1141662
A nice competition!
I enjoy it!
https://codeforces.net/contest/1955/submission/255756584
could anyone tell a counter test case where this fails for D
thank you!
Nice contest. Problems were good. Thanks for the round mainyutin vmanosin7 ssor96 ZergTricky and all testers.
Also, congrats Geothermal on back-to-back wins!
div 2.33
Was the statement for problem A silently modified during the contest? More specifically, was the word "exactly" added or did I just miss it.
Dude I can swear there wasn't the word "exactly" when I first read it, maybe I just missed it...
Also I was mistaken at the term "a promotion", I thought that it can only be used once, but turns out I can use it multiple times. Got 2 WA on problem A lol
Seems like we just missed it... I checked a video and it did say exactly from the beginning. The only difference was that it wasnt bold.
Using a segtree on problem E be like
What's the solution for problem E?
Basically since $$$O(N^2)$$$ passes, you can test every possible $$$K$$$ from $$$N \rightarrow 1$$$ and return the first one that works. This step runs $$$O(N)$$$ times. The question is now: how do you check if operations of size $$$K$$$ can turn a string to all 1s?
First, notice that since this is just an XOR these operations are both commutative, associative, and their own inverse. So there's no point in applying the same operation to the same substring more than once.
With that, notice that if $$$s_0 = 0$$$, there is only 1 operation we can and must perform: invert {$$$s_0 ... s_{k-1}$$$}. Inductively, it is sufficient for us to apply the operation only when the first element in the operation is zero. This step runs also in $$$O(N)$$$, bringing our current total to $$$O(N^2)$$$.
The final step is figuring out how we can apply the operation very quickly. If we prefer typing or templates to critical thinking and reasoning, we can just use a range update / point query data structure like a Segment Tree, Fenwick Tree, Sparse Table, etc. I did this in during the contest 255770625 and made sure to statically allocate my segment tree instead of using
std::vectorso I didn't get hacked. I also manually coded this because I enjoy a nice hand-crafted segment tree (brainrot).However, instead of that beautiful solution, we can do it intelligently by inverting in $$$O(1)$$$ on the fly by keeping track of whether or not we are inverting, and then setting a reminder $$$K$$$ indices ahead to remember to start un-inverting. I did this after the contest 255903468.
Problem G and H are enjoyable. Enjoyed how there was such a simple solution to G if you made the appropriate observation. And problem H was very interesting, I implemented a dp bitmask, but some reason still getting WA on test case 4. I think I may have small bug, but I think the approach is correct.
can someone please tell me why this 255705783 is WA test 1 when I run it locally it gives me the correct output, furthermore when I switch the compiler to c++17 it gives TLE test 3 this time, maybe it's smth abt c++20 that I don't know ?
255760248 Why does this submission exceed TL ? I think the complexity is $$$O(n\cdot(n\cdot \log n))$$$
I realise this is most probably not the intended solution. But if it helps to understand the submission, I have just tried to go over all possible $$$k$$$.
Used PBDS for calculating if a current position has been previously flipped an even or an odd number of times.
For each $$$k$$$, considering all previous operations that have modified a position, I have never flipped a position that is currently a $$$1$$$ and always flipped a position that is currently a $$$0$$$.
IMO $$$\mathcal{O}(n^2 \log n)$$$ is a very dangerous complexity for $$$n = 5000$$$, and I would not gamble on it even with 3s TL.
You could actually improve this part by using a queue instead of a PBDS.
My $$$\mathcal{O}(n^2 \log n)$$$ solution got AC and ran in under a second with Fenwick Tree. 255763784
Thanks for answering. I was also guessing that PBDS is going to cause TLE even if $$$O(n^2 \log n)$$$ could have squeezed past the TL. Thanks for the queue insight too. I realised I know nothing about queues :)
The only thing I could suspect is that PBDS is already a high-coefficient $$$\mathcal{O}(\log n)$$$.
For the queue stuff, just imagine this assuming we're trying length $$$k$$$: store the starting points of all flipping segments in the queue, then when investigating index $$$i$$$, any starting indices up to $$$i-k$$$ has no value. Why a queue? We're iterating indices in ascending order, and added index would later be invalidated in that same order as well, which fits the FIFO nature of a queue.
Yeah, makes much more sense now. Thanks a lot and welcome back to CF contests.
I used PBDS for calculating if the current position has been previously flipped an even or odd number of times. Here's my submission.
I later realized we insert indices in a monotonically increasing fashion in the data structure we maintain. So we can also use vector/queue. With vectors we can use lower_bound and with queue we can pop the indices that are at a distance k of far than current k.
Vector solution: here Queue solution: here
All submissions you've linked are in queue at the moment lol.
But, yeah lesson learnt. Don't be lazy and use sets everytime you want a sorted list.
Now that you have put it this way. Its baffling how obvious this was and yet I missed it.
Want a sorted list. Want integer-positions. PBDS. TLE. Die.
Yeah it was pretty obvious but even I wasn't able to come up during contest so I did it using ordered set. It was only after contest when I realized it can be accomplished using vector.
And as AkiLotus mentioned, queue can be used to eliminate the logarithmic factor and achieve a linear solution.
can anyone explain the idea to solving D?
Sliding window. Just check for every segment of length m if there are atleast k elements in that segment that are present in b. Count can be maintained using a map.
I failed to see the key observation that GCD must be a divisor of both top-left and bottom-right corners, so I ended up solving a more general version of the problem which finds maximum gcd for each path from top-left corner to cell (i,j). Tbh it was a good problem to practice some prime optimizations although it was not intended.
bro my computer crashed during the contest and my coding software was deleted (dunno why) and any custom invocation would take more than 7min (dunno why) so i just had to randomly code on the submission site ToT
I usually use the one from AtCoder, it runs the code and gives the result faster than Codeforces most of the time.
use online compiler like online GDB or other there are many options and they are fast
what's wrong with my c ? pls check[submission:255762443]
F should be in place of B didn't read it during contest
Extremely easy problem F!!!!! -_^
include
int main() { int tc; scanf("%d", &tc); while(tc--) { int a0, a1, a2, a3; scanf("%d%d%d%d", &a0, &a1, &a2, &a3); int ans = a0/2 + a1/2 + a2/2 + a3/2 + (a0 % 2 & a1 % 2 & a2 % 2); printf("%d\n", ans); } }
Spent half contest time to implement the simulation for problem C, couldn't make it but still a great experience.
Thank you guys for a nice contest!
same , you're not alone
I just realised problem G is but a simple BFS ToT
I have an ask for harder version of $$$G$$$ , same constraints , just your starting cell can be any cell inside the first row and finishing cell can be any of the last row , then how to solve it?
How is that any different? Just run dfs from every cell in first row instead of first and check if any cell is visited in last row instead of only bottom right.
Problem G is the same as https://community.topcoder.com/stat?c=problem_statement&pm=16140&rd=18085. Of course, it's not as big of an issue as Div 3s are supposed to be educational anyway, but just putting this out here :D
Can binary search be applied in E to make TC roughly NlogN
No, because function is not monotonic. For example, s=000 k=3 is possible, while 2 is not.
I don't think the function is monotonic
Why using qsort (C/C++) in B can be easily caused by Quicksort hack halyavin.cpp to cause TLE (e.g. 255659588) ?
It's the nature of quicksort algorithm itself to have $$$\mathcal{O}(n^2)$$$ worst case time complexity, thus as long as you know the sorting was a pure quicksort and you know how the pivot was chosen by the library, you could always counter it.
How to E
bruteforce + greedy
How to check if k is valid
well you have to choose some subarrays of size $$$K$$$ to invert and subarrays do have a unique starting index and so you put inversion on an subarray starting from a particular idex at most $$$once$$$ so you start from the beginning , on your current index the value of the character in string is fixed so you can choose that index as starting point of a subarray or not(which is a certain choice), so if you do inversion the cost of that ends $$$K$$$ indexes later and if it's valid it will be at $$$\le n +1 $$$ and if valid you move on to the next index to check validity again otherwise invalid proved
Can anyone suggest a tc where this fails for problem D :(255769513
1 4 3 2 1 1 2 2 2 2 2
Output should be 1
Ohh great! Thanks!
can anyone explain this solution to problem E? i fail to understand how we are checking if integer k is valid or not.
submission1 submission2 Why they are giving different answer? The only difference is in the solve() function only. Is this a CPP Bug or I missed anything? mainyutin
It may not be a reason actually, but most likely it is because you are not clearing your dp after/at the start of the next testcase
Can anyone tell me why my code of problem C 255769305 is giving TLE on testcase 3. I thought deletion in deque is O(1).
The time complexity of your code is O(min(s,k)), s = sum of durability of the ships. As s and k might be too large (k <= 10^15, for example), it would give TLE.
your solution time complexity is min(sum of all the element, k) which in worst case can go upto 2e14 like your are just simulating the process which is not optimal
required optimisation — in the while loop of q.size() and k
take the min of q.front() and q.back() if 2*mn <=k do this {
then reduce mn from front as well as back of deque then if q.front==0 do pop_front() and if q,back()==0 do pop_back()
} else break;
now if d.size() is greater than 0 check can we remove the first element (value should be <= (k+1)/2 if yes pop_front() do same for last element if it exist (<=(k/2))
I spent really a lot of time during the contest trying to make my E solution faster, even though it should have O($$${n^2}logn$$$) complexity, which is with n <= 5000 should pass the 3 second limit. The only thing that helped me was changing long long to int, but even so, it's still very slow. Does anyone have any idea why my E solution is so slow (below is the final one)? And a similar question is about D as well, because I can't see any clear reasons why it is so slow:
E: 255741981
D: 255675779
Edit: Sorry about how code in E looks like, I don't know why it shifted, because for me it was totally normal when I was sending it.
.
I too felt the cheating happened in this contest a lot, my rank was around 160ish before 1 hour end of contest, and i could not solve anything further was only able to solve 5(A-D and G) but somehow so many other peoples solved problems that my rank went to 700+, i was thinking maximum i can slide is around 300-400 but 700+ did not feel organic... I might be wrong but this is what i feel.
I feel like especially in the last 8-10 minutes, the spike of "AC'd" submissions shot up.
Bro this is common if you cant solve good problems , you solve the easy questions fast it doesnt mean that the people below you cant solve the tough one faster than you that happens everytime , the people who have much more knowledge will eventually occupy the rank
pray for me to reach pupil ^_^
Great Contest!!! Very nicely framed
does unsuccessfull hack have panalty in this round,
I tried to hack some solution, but failed will my score be affected by this?
No
Similarly,do successful hack doesn't affect your socre.
Was the cpp's hash function mechanics of unordered_map changed recently ?
cause i can't seem to hack solutions using the default unordered_map like before .
Can someone tell How can we solve G using bfs I was first storing the factors of the last number and then I was doing dfs and each time i find a new pair of gcd between two colunms then I am checking it to be divisible by a factor of last number . Help needed !!!
gcd(matrix[1][1], matrix[n][m])Getting a tle by applying this on 35th testcase
Maybe you made a mistake caused this.
This is a sample 255813710
This is another one but with a lot of resets that slow the process 255812987
problem D first I used map for frequency and I got TLE I removed the map and I used a simple global frequency array but with t 1e4 and the frequency array being 1e6 it is not possible so what should I use here in this case?
you can use same frequency array but you zero it at the end of a testcase using only values in a and b . or you can use an map with custom hash
thanks the first one worked, I actually used a multiset for array m and used count() many time so maybe that's why I got TLE the problem is not in using map here because many people used map and it passed
Toooo many hacks for G.
you may want to rejudge G with a higher time limit, except you had a better intended solution
No I believe intended solution was O(d(maxA)*n*m) ,where d(n) is number of divisors of n , which easily passes the time constraints .
I've seen multiple solutions with the same complexity hacked, you can check the hacks for yourself.
Like this? 255813710
Many people were hacked on G.
Poor pretest.
My 320 hacks on G were about trying to achieve maximum number of possible GCDs for as many cells as possible, so that solutions that hold all GCDs using a slow data structure such as
std::setwill insert a lot of elements. My test made it more than a million elements per test case, and since we can have 20 of 100*100 tests in a single file, these solutions tried to insert more than 20M elements in total, leading to TLE.But it seems like there are far more intense cases, as even my possibly more optimized solution couldn't pass, as well as several LGMs' solutions, and now with all the
Unexpected Verdicts we can assume even testers' solutions are hacked...Thank you for the explanation! I just woke up to a wall of hacks and was about to ask how so many seemingly reasonable solutions got hacked.
std::vector+std::sort+std::uniquewas also hacked.Now just C-array+
std::sort+std::uniqueworks good. https://codeforces.net/contest/1955/submission/255802770https://codeforces.net/contest/1955/submission/255802770 Hacked.
Just heard a news that the validator isn't checking the constraints on the sum of $$$nm$$$ properly, so it's allowing cases like $$$n=100, m=100, t=100$$$
https://codeforces.net/contest/1955/hacks/1012724 This hack basically just repeated my original hack 5 times and it didn't get
invalid input. Writers, please check.I think this is kind of an emergency so I'll just poke them: mainyutin vmanosin7 ssor96 ZergTricky Vladosiya
MikeMirzayanov please take a look at this
Average div3 moment
Yes the test that hacked me uses t=999, n=100,m=100 which is not allowed under problem constraints.
Thanks a lot, working on it.
Now it fixed and all hacks are rejudged. I'm terribly sorry for such bug that I didn't notice.
Greatest hacker ever.
It seems that E is more difficult than F.
Can someone hack my solution in E? 255743941
it's O(n³) with an optimization
G is so humorous!!!
G-question is hacked to fly
what a sight. seeing Geothermal losing and regaining his high ranking after the contest
It seems that the validator for problem G is wrong. The problem said that the sum of n * m cannot exceed 2 * 10^5, but it can be hacked with such data.
can you give a submission for a reference?
Try mine, it will RTE#2226 in cases of violation.
hey, also look at mine, it's gonna FST https://codeforces.net/contest/1955/submission/255724529
The authors should change 2e5 to 1e5, and almost everyone with a logn factor passes
FST for sure, see this comment for countertest ideas. There are better solutions than that.
idk, why the testors had to make the problem so tight, and if yes, then they should have added this in pretests, i had a better solution in mind, but as this one passed, I wasn't bothered to submit another
I don't know either, strict TL isn't a first-time thing. I also got TLE on another "better solution" as well, and that was because of suboptimal alloc. Though, on hindsight, 2e5 usually is a vanilla constraints, so I do feel like them brushing it off is a normal instinct.
By the way, your earlier one won't pass, I just resubmitted to check and make sure — it still fails a test within limit.
yeah, as i said, it's because of the log factor, if the constraints are relaxed, mine might pass.
btw, yours is working?
Yeah, kinda — see the link I left on the first comment of this chain.
(I won't count tests from 36 and beyond as they breached the $$$2 \cdot 10^5$$$ limit for sum of all $$$nm$$$.)
Validate is wrong.
cpp #include <bits/extc++.h> using namespace std; int main(void) { ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr); size_t constexpr T=30; cout<<T<<"\n"; for (size_t t=0;t<T;++t){ cout<<"100 100\n"; for (size_t i=0;i<100;++i){for (size_t j=0;j<100;++j) cout<<114514<<" \n"[j==99];} } return 0; }This passed the check.What is this ? I precalculated divisors for all elements upto 1e6 ( in MlogM time where M = 1e6 ) and solved the overall problem in (approx) cuberoot(1e6) * 1e5 time , still hacked ? solution
max number of divisors for numbers up to 1e6 is 240.
but it is still should be okay to pass
Ohho yeah right , my bad
The time complexity for the Python judge is not being properly set.
I got TLE at test 3 for my submission in python (submission no — 255718411) I got accepted for same code in Pypy 3.6 (submission no — 255806654)
Due to this , I have made additional 2 negatives. It's NOT FAIR If you want you can check in my recent submissions
Your Python submission and PyPy3 submission have different code. What are you complaining about? The Python one uses
list.insertthat is $$$O(n)$$$, and it's $$$O(n^3)$$$ in total, so I think TLE is the correct verdict.Just go to my profile and click on submissions and just click on show unofficial submissions and then check last two submissions (255848468 and 255848184)
So
qsortis a poor way to solve cf problem? Since it can be hacked easily. I did not even imagine that qsort in stdlib have a O(n^2) situation, I thought it should have some method to prevent it from happening because it is in Standard Library! Forcing me turn to a cpp programmer? My rating is gonna drop for this ridiculous reason. ahhhhhhhhhh X(But I think write C in C++ is not a big deal.
You can implement your own sort and copy it if you're committed to using C .
It's not stdlib's fault. It's the algorithm's fault itself, as it has slow worst cases, but average cases being so fast that it is commonly used; yet in an environment where hack is allowed like Codeforces, worst cases actually matter.
Perhaps making your own sort next time? IMO implementing something like merge sort isn't even much more difficult.
Can anyone explain G? I thought this is a simple standard Dijkstra algo to keep track the GCD for each path with PriorityQueue?
Any path must start at (1,1) and end at (n,m) , therefore the gcd of the path must be a divisor of both. Simply check for each divisor if it could be the gcd using dijkstra or bfs.
Your approach is wrong though. A greater GCD on a node won't guarantee greater GCD at the end, in case that GCD was a large but obscure number, which would quickly get diminished later on, while the smaller GCD prevailed.
An example:
If you take $$$19$$$ as the GCD to go for cell $$$(2, 2)$$$, two $$$6$$$ on both possible ways onward from it will delete them all and result in a GCD of $$$1$$$ at the end.
Sorry I still not get it. https://codeforces.net/contest/1955/submission/255758743 is mine.
I did give a bad test to straight-up testing honestly.
Found your counter test though, and it looks even weirder.
How come it outputted $$$4$$$? (supposed answer is $$$16$$$).
I have a feeling that your code overwrote GCDs in a weird manner, leading to only one GCD being chosen and it's hard to tell when it's optimal or not.
When 684 342 19 6 684 then the tracked GCD becomes 1 and stay in the bottom of PQ. And other higher GCS in the other path can be considered in the next run.
Firstly I would like to acknowledge the contest author's effort and thank them. Now I can began my issue with the contest.
I think the statements for problems could have been more clear considering this is a Div 3. Also the explanations for the samples wasn't there or was not even helpful at all. I know that the author is not duty bound to explain the samples but with poor statement explanation I think this should have been done.
I did quite bad in the contest and to check whether I was feeling these issues because I did bad, I slept this off. Now even in the morning I feel the statements could have been better with better sample explanations.
It is so surprising to see so many G solutions are hacked. Given that my rather standard DP solution https://codeforces.net/contest/1955/submission/255745682 is accepted just fine, now I wonder whether I have missed something important, like a more advanced approach that usually works better.
The moment bro drew attention to himself...
Lmao
this can also be hacked sadly, I wrote similar solution and many more similar solution is hacked already.
Now it makes more sense. It appears that the hack used 200 tests of 100x100 matrix, with the sum of n*m being 2000000 which is 10 times of the limit as specified in the problem statement. So it is likely an invalid hack.
Hacked :)
There are tests added by hack, like Test #50, contains 800 sub-tests each with 100x100 input, with a total sum of n x m 8000000, which is 80 times of the upper limit as promised in the problem. Now the whole thing become less interesting due to these invalid hacks.
Very good topic, each level is easy to difficult. Thank you
Can Someone Please Try to hack this: https://codeforces.net/contest/1955/submission/255768412
The problemset was good no cap. but it's really sad to see so many solutions being hacked. There's a lot to improve in testing.
so，is it rated？
fvck G
Wow... with what happening in G, I feel quite disappointed.
I could accept my code TLE'ing due to bad implementation caught in stresstesting, but allowing hacks to let loose because of validators going nuts?
Please, problemsetters, be extremely keen in validator writings. Crosstest and add various validator tests if possible. This is not even the first time in a long while this happened, and this problem even has pretty standard constraints that one shouldn't excuse of difficulty in writing conditional checks, so why letting the issue prevail?
I don't really want to disrespect the authors, the problems themselves are fine, but this time the underneath preparation has an absurdly critical hole that I feel like I need to raise my voice.
Proof that hacks go out of problem statements' defined boundaries, solution RTE with exit code 2226 is my personal indicator when that happens.
The bad thing for me in the contest is, that I solved G directly after D, a similar solution like Geothermal, yet got hacked. The good thing is I participated in VC :)
still I think the contest should be unrated as people who solved G directly after D would be paying prices otherwise :(
I think this will depend on what actually had happened underneath. The best cases would be that only hacks having those breaches, thus those tests could be removed, relevant hacks reverted, and contest rated as usual.
If even the original testset had limit breaches, then nope, unrated for sure (though as I quicktested the original testset was fine).
If we can remove those hacks and solutions can be rejudged then why not, that would be better
Wow I just resubmitted your best Rust solution, just to see it AC with 10x execution time.
Breaching hacks are insane.
unrated
How come this test case passed for Hack
This is 1000*100*100 well beyond limits
The same happened to me. Check this mainyutin.
Any idea why this code gets TLE on problem D ?
the time complexity of
multiset::countis $$$O(n)$$$, not $$$O(\log n)$$$To elaborate on the above comment, it is $$$\mathcal{O(k + \log n)}$$$ where $$$k$$$ is the number of occurences of the sought number in the multiset. So if the frequencies of your numbers are small enough, you can use
multiset::count. But, in general if you want to only check whether a certain number exists in the multiset,multiset::findis strictly better, because it's exactly $$$\mathcal{O(\log n)}$$$, which is always better than $$$\mathcal{O(k + \log n)}$$$.Yes, this is more accurate.
How to write that equation or the formula O(K+logn) sir? If you dont mind can you explain a little bit with an example.
$$$\mathcal{O(k + \log n)$$$(not actually three dollar signs, only one, but it's like this because if I don't put the backticks on either side, it just renders as $$$\mathcal{O(k + \log n)}$$$).$$$( O(K + \log n)) $$$ Thanks master. But how can I properly write this equation- $$$( O(nk^2/w$$$ + $$$k^3/w))$$$ can you tell me please.
$$$\mathcal{O}(\frac{nk^2}{w} + \frac{k^3}{w})$$$This gives you $$$\mathcal{O}(\frac{nk^2}{w} + \frac{k^3}{w})$$$ (actually, I think your way ($$$\mathcal{O}(nk^2/w + k^3/w)$$$) looks better than this one, but you can use whichever one you think looks better). By the way, if you're interested in learning about LaTeX, this is a good place to start: https://artofproblemsolving.com/wiki/index.php/LaTeX:LaTeX_on_AoPS.
Thank you Master. I was going to asking you about LaTeX . Thanks!
thank you!
How was problem C guys? I was struggling to solve to solve it? But Finally I solved it.
A-find if 2*a<=b if so you can buy all ns with a, else buy (n/2)*2 with b and if n is odd add 1 B-sort the matrix and find the first number and then insert it in a vector, add d n times and find the value and insert them all in vector, then add c to the initial value of the matrix row and do this n times too C-Kraken attack (k+1)/2 shots from the start and k/2 shots from the end, just iterate over the array from the start and from the end and decrease the value as much as possible, if it becomes 0 add it to the answer D-store the values of b in map, and the values of first m elements in map, while doing that check if the values is second map were smaller than the value count in first map , if so do matched++, now iterate over the other values of a buy keeping an l(left) remove the left and add the right, simultaneously updating the map ,and updating the matched values as explained. E-Just iterate over all values of length to be the ans, then just reverse the length k segment whenever you find 0 in the string, at last if all are 1s this k is possible, hence find the maximum of such k F-first of all ans is a/+b/2+c/2+d/2 because their xor will be zero as the same value repeats twice, secondly is one of the a,b,c is absent then no further action is required as they wont add to the ans because of the placements of 1's in their binary representation, but is a,b,c are odd that means 1 ans can be extracted out of these 3 values hence ans++
rest ask from a higher rated coder,thanks :-)
Why so many Hacks on G? Even mine is hacked. Whats ideal expected TC for G? Is it better than O(n*m*100). Rating of G has gone from 1900+ (yesterday) to 2500+ (now) on clist :(
The validator is incorrect, so tests which are above the limits can pass as hacks. But a fraction of the solutions are TLE even with a correct validator.
ohhh right thanks, then maybe I will wait till system testing :)
The test validator is wrong.
Can someone explain to me how to approach problem F. I can only think when count of all 1,2,3 and 4 is even and when cnt(4) is even and count 1,2,3 is odd. These could be the 2 cases when bob can win. Unable to code the solution. thanks in advance.
$$$cnt(4)$$$ is independent from the rest, so calculate it separately.
For $$$cnt(1)$$$, $$$cnt(2)$$$ and $$$cnt(3)$$$, I prefer splitting into two cases:
Pick the better case out of the two, then add $$$\lfloor \frac{cnt(4)}{2} \rfloor$$$ in for the final answer.
4 has independent bit compare others(1, 2, 3).
So you can try O(N^3) DP on one, two, and threes.
just calculate dp(one, two, three) + four / 2
255713576 Hey this is my first contest ever and only one of my submission got accepted. The thing is on running the same code for B , C and D I'm getting the required output but here on site it displayed otherwise. I understand that writing in python would slightly impact the time execution but probably shouldn't be the case up until i reach a way higher rating. So it would be great if someone could point out the logical errors if any or if there's way i should be submitting my code, thus providing me with pointers for the same. Thanks
Also in regards to my rating, given the rules i should be eligible to participate and this should be treated as rated for me but it is still shown as unrated.
I like your clean code, but you should optimise it a bit: 255745156
It's normal to perform poorly in first contests, with practice it will get better
i think it's time to give it a try to change my color
The time limit and constraints for G are so stupid
I am curios to know why I got TLE on test 35 in G: 255703960
It is simple, try all divisors of $$$a_{1, 1}$$$ with $$$O(nm)$$$ dp.
We will have maximum 240 divisors (from 720720).
So maximum $$$<5 \cdot 10^7$$$ operation.
std::vectorconstruction can be strange but time limit is 3 seconds, it allows use nearly $$$10^9$$$ operation I think.So how could I gotten TLE?
Some people with the exact same idea still pass for some reason. Very weird constraints and time limit.
I almost have the exact solution too and it TLE'd in test 35. Then, I changed vectors to global regular arrays and it passed.
This is not making sense, this is not testing the coder's ability to code
Yes, I see. But I think it is foolish, 20 times slower than expectation.
As I said,
std::vectorconstruction shouldn't affect very much.Even Jiangly wrote same solution as yours and got TLE,
this solution is so obvious, I did similar, but what I did I precomputed the the divisors till 1e6 in log2(1e6)*1e6 time.
still I have no clue how the hell my solution got TLE.
Take my words with a grain of salt, but my suspect is that the alternating testcases here was not for show, but a deliberate attempt to cause cache misses and thus slowing down any time a "true" test begins, making it work with a worst-case speed every time.
That's why I don't love after-contest hacking phase.
I also encountered this situation, and later I changed vis from a local vector to a global variable and it passed. I guess the 2D vector initialization in C++is very slow
std::vectorconstruction involves dynamic allocation (allocating from the heap). It is not a cheap operation. When $$$t = 10^4$$$ and $$$a_{1,1} = 720720$$$, you are doing it $$$240\times 10^4\times n$$$ times (times $$$n$$$ because you allocate for each of the rows). Which is significantly slower than just constructing once.Also, the nested
std::vector<std::vector<...>>is not fully contiguous in memory, so you also get potential cache misses when you access the next row.Same code works fine locally though.
By locally do you mean your own computer or codeforces custom invocation?
Anyway, my point is that the difference between using a nested vector and constructing it many times, vs using a global array, is not subtle. And this could be a determining factor when the time limit is tight.
can you please tell why vector::assign works faster than just creating it everytime with constructor?
with constructor : 255927707, TLE
with vector::assign : 255927628, 734ms
Well, I believe that when using
vis.assign(n, vector<int>(m)), you are only allocating one size $$$m$$$std::vector(vector<int>(m)). While your code using the constructor, it is allocating $$$n$$$ vector of size $$$m$$$.When you use the
vector::assign, it just tries to copy the second argument (vector<int>(m)) to each of the rows of the nested vectorvis. Because initially every row of your vectorvishad already allocated memory that could at least fit $$$m$$$ elements (you had constructed it outside the lambda with size $$$n\times m$$$), for each of this copy assignment, it doesn't require allocating any more extra memory.tldr: so you are allocating $$$n$$$ times less.
number of heap allocation, worst case:
constructor: $$$t\times d(720720)\times n$$$ = $$$10^4\times 240\times 20$$$ allocations
vector::assign: $$$t\times d(720720)$$$ = $$$10^4\times 240$$$ allocationsH is interesting
=
Looks like CF have problems with allocation, this solution(https://codeforces.net/contest/1955/submission/255842530) works 11s on test generated by this code:
But local run is 2s... When I removed allocation of used in check -- it passed with 0.8s on cf.
when will rating changes come out ?
During the next ~12 hours (I don't remember exactly, most likely even less) after the system testing ends
Because of your terrible hacking in this round, it's fair for you to receive a large number of downvotes.
Be rational at what you are criticizing.
If there would be anything to blame, the most critical would be the absurdly tight TL on G, and even that wouldn't be generally agreed — tight TL isn't the end of the world most of the time.
Hacking due to loose validators is worth criticizing, but not downvotes. Main tests didn't breach it, hacks did, so nothing went wrong within the round. They are also reversible (and already been so at one point, as most of the hacked solutions have been rejudged with a proper testset). What more to blame?
Well, I downvoted cos I can see solutions I have the same complexity with pass for G, while I get TLE. Plus, you're everywhere :D
Can say I am having quite a lot of free time for now XD
why is this contest not showing on my profile rating graph? It's not in all sections either.
System testing underway, still a long while until rating updates, be patient.
okay but I solved 4 questions during the contest and now it shows that I solved only 2, is it also due to system testing? Sorry for too many questions, kinda new here :)
In system testing, all Accepted solutions are rejudged. Your other two are probably still in the queue and not yet rejudged.
We can only wait.
okay, that makes sense. thank you!
system testing is complete, but the contest is still showing as unrated for me. my rating is 826, so this contest should be rated for me, right ??!
Actually, I do think the problem G itself is created badly. I think a good problem should focus on examining the complexity of time or space, rather than optimizing constants, especially for a Div3. In that case, I think the data range should be at least 1.5 or 2 times looser than the optimal solution.
I think it served that purpose normally. Judging that the original testset had nothing too strict in particular, I would say even the judges haven't really considered to stretch the constant optimizing, and only until a legit hack attempted to stress greatly into it, the complete revelation of contestants' bad implementations would begin.
Well, they did, kinda. You could compare some "good" implementations with the "bad" ones — and we only consider the "formal" solution i.e. BFS with all candidate divisors. Sometimes the difference go up to like 5-6 times, signifying the gravity of the issues which, in my opinion, have gone beyond planning.
At this point, to blame the authors or not is pretty much a gray zone. Perhaps the integer constraints should have been $$$10^5$$$, but normally who would put that awkward limit for an array element in a number theory problem?
I, however, believed that FST'd participants would take some responsibilities as well instead of fully diverting the blame. Cache misses and similar memory issues are actual things, and its nature is actually included in some fundamental teachings in computer science. It will be relevant if you wanted to pursuit this career later on, nonetheless.
So perhaps we might be agreeing to disagree. It's fine that way though. I would only hope that we wouldn't bring down our judgment recklessly based on short-lived emotion bursts.
Since it has already been rejudged, I'll retract some of my criticism from this incident.
Can anyone tell what might be the reasons of showing correct answer in compiler and wrong in codeforces?
Most of the time due to undefined behaviors (UBs), and as your compiler/machine/etc. isn't fully identical to that at Codeforces, UBs will have different effect on different places.
see my last code g wrong on test case 1. I have defined each variable
Now I'm confused, like your WA1 submission is of an obviously wrong idea. I wonder how could any env give correct output with that...
Peak Codeforces moment.
Will the submissions to problem G that only fail on invaild tests be rejudged? Like this submission and this submission
of course yes bro
https://codeforces.net/contest/1955/submission/255667514 Why is my solution giving TLE, can someone please tell(problem B Progressive Square)?
Unordered map caused it, probably? Blowing up unordered_map, and how to stop getting hacked on it
Add this line after you declare your unordered_map. It should work. I was getting the same error. dups.reserve(n*n);
too many downvote :)
Why are you downvoting this post so much? I think even with the problem G's issue it was a great contest
F should be before C
Should be before D for me. I agree F is too easy but C is just implementation
Yesterday, it told me during the contest that my solution for problem B was accepted and it was shown in th rankings too. Today, it says that my submission for problem B is still "in queue". And the rankings don't show that I solved problem B either. Why is this? Can someone please help me out.
This is known as system testing phase. Your solutions are being checked again and if they run correctly you will be given the points... Don't worry
Thanks a lot! It is resolved now.
Is it because a lot of Problem G solutions are getting TLE which is slowing down systest? The testing progress bar only went up by 2% in 30 min...
probably not only problem G...
It would've been nice to wake up to positive delta. Now I need to worry about whether my submissions for D & E will pass systest or not... :(
guys fst is your skill issue please stop downvoting
I believe people are downvoting because of the problem G mess, not cause of fst.
Can anyone help me figure out why my solution to D got TLE? Seems $$$O(n)$$$ to me.
https://codeforces.net/blog/entry/62393
255708545 TLE 13
same code with random hash 255716909
So it means testcase 13 was designed to maximize the collision for the default hash function, making the worst-case $$$O(n^3)$$$; am I right?
Yes
how this code got accepted with 2999 ms in problem G
The time limit is 3000 ms, and it took 2999 < 3000, so it passes. :)
there are a code with less time complexity with TLE like this code
HELP HELP How to know when not to use Unordered Maps? or should i use just Maps always? Got TLE in 'B' bcuz of this BS
check this blog out: https://codeforces.net/blog/entry/62393
Rule of thumb for Codeforces: always use a stable data structure if you aren't sure how to protect yourself while using heuristic ones.
That applied to a variety of things: quicksort, hash tables, etc., even RNG.
Problem D ; RIP python users, most of the solutions got TLE for test case 11. My solution as well got TLE for test case 11 (sad face). Please look into this if possible
Don't use unordered hashmap in python or C++ as they are easily hackable. If you still want use string of integer as key or use some randomizer.
what could I use instead in problem D? I also used dict and faced TLE on test 13: https://codeforces.net/contest/1955/submission/255744391
check it https://codeforces.net/blog/entry/62393
255708545 TLE 13
same code with random hash 255716909
It's possible to solve D without
setordict-- see my submission for example."Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you."
Can anyone help me to understand why am I not rated in this contest even though I'm eligible.
This has been my second contest on here, but why is it showing up as unrated? "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you." — doesn't this mean it should be rated for me?
Rating hasn't been updated yet. Wait for a few more hours until it's calculated.
A<B<D<C<F<E
Problem D — Python
Directly create a dictionary with key as integers from array — TLE -> 255910556
Converted the integers in array to strings and then created the dictionary- AC — 255910798
Why??? :((
Why is this submission 255757792 for problem G giving TLE on test 35, but when using the same test on custom invocation, it finishes under 2 seconds. Don't the judge and custom invocation use the machine????
My bad, I was using 1000 test cases instead of 10000.
use global vector<vector>
Does allocating memory from the heap take that much time?? because even if I declared it as global, I would still have to clear the vector at the beginning of each iteration.
You reallocate it $$$100$$$ times. The time limit is too tight, so it got TLE.
absurd checking, i was waiting to become specialist today, but -4 i get
EID MUBARAK to all muslim brothers !!
.
..
Eid Mubarak to Every coder
Eid mubarak to you brother.
Eid mubarak to every coder
Eid Mubarak
Eid Mubarak !
this comment is in queue
Problem E is the same as a problem for 2023 practice in my school.link