### MrPaul_TUser's blog

By MrPaul_TUser, history, 13 days ago,

Hello, Codeforces!

I'm glad to invite you to amazing (we've tried to make it such) Codeforces Round #748 (Div. 3) which will start on Oct/13/2021 17:35 (Moscow time). This round is made by me (MrPaul_TUser), a significant contribution to the round was also made by MikeMirzayanov and BledDest.

The round contains 6-8 problems. The difficulties of the problems are expected 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 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. We tried to make really strong tests — just like you will be surprised if many solutions fail after the contest is over.

You will be given 6-8 problems and 2 hours 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) 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 trusted participants of the third division, you must:

• take part in at least two 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.

Thanks to _c_k_r_, Vladosiya, spotless, Yousry, powergee101, ncduy0303, I_Remember_Olya_ashmelev, A_Killer, OlegZubkov, mahade31, arjunsanjeev7, and UpS0lver for testing the round and improving tasks.

Good luck and have fun!

UPD Editorial

• +190

 » 13 days ago, # |   +32 Looking forward to an interesting round!
•  » » 12 days ago, # ^ |   +4 Yeah Ofcourse !! good luck man.
•  » » » 12 days ago, # ^ |   +3 Good luck bro!!!
•  » » 11 days ago, # ^ |   +5 This was really interesting round !! it has created confidence to continue competitive programming...
 » 13 days ago, # |   +3 Hoping for a good contest :)
 » 13 days ago, # | ← Rev. 3 →   +41 Looking forward to change my color :) Spoilervrintle to vrintlePlot twist: SpoilerDidn't expected this would be my last Div3 round..Plot twist again: SpoilerGot hacked on E! T_T
•  » » 13 days ago, # ^ |   +29 SpoilerI like your confidence, All the best
•  » » » 13 days ago, # ^ |   +20 SpoilerWhere are rest of your heads ? reference
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   +10 Actually, he is frightened coz dussehra is coming !!! :)
•  » » » » » 11 days ago, # ^ | ← Rev. 2 →   0 cracked me up lol. good one.
•  » » » » » 11 days ago, # ^ |   0 Nice one...Lol
•  » » » 12 days ago, # ^ |   +2 @coder_ravan You didn't get his joke. Just check the spoiler .. lol
•  » » 13 days ago, # ^ |   +6 brilliant, bro!
 » 13 days ago, # |   +17 My first unrated round.
 » 13 days ago, # |   +5 Nevermind, but can someone remove cheaters in last round
•  » » 13 days ago, # ^ | ← Rev. 2 →   +12 +1
•  » » » 13 days ago, # ^ |   +6 I know bro... I feel sad a bit and very unfair
•  » » » 11 days ago, # ^ |   +1 Now, I am feeling it . :(
•  » » » 11 days ago, # ^ |   0 That's not true, in the round before the last one, I got +24 after the contest, getting to 1599, and then, cheaters were caught and I hit 1600! Additionally, seeing this comment, we can conclude that cheaters have been/are being caught for the last round as well. Codeforces staff puts in a lot of effort, please don't belittle it with baseless accusations/claims.
•  » » 13 days ago, # ^ |   +5 Could anyone explain me about what happened in the last round?
•  » » » 12 days ago, # ^ |   +6 apocalypse and destruction
•  » » » 11 days ago, # ^ |   0 I became eligible to participate in this round. :P
 » 13 days ago, # |   -10 I hope I get +160 or higher rating points after this round. Good luck to you all.
 » 13 days ago, # |   0 Hello everyone! Good luck to everyone to write this contest and adjust the rating well!)
 » 13 days ago, # | ← Rev. 3 →   0 -1
•  » » 13 days ago, # ^ |   +2 VERY UNPAIR
•  » » 13 days ago, # ^ |   +1 It would be nice to recalculate the rating for honest users.
•  » » » 13 days ago, # ^ | ← Rev. 2 →   -20 +1
•  » » » » 13 days ago, # ^ |   0 It is sad(
•  » » » » 13 days ago, # ^ |   +14 Did you just say "Shame!!!"? What in the world do you think gives you the right to say that? Even you know that it's not a right thing to say, else you wouldn't be cowering behind an alt. Please don't ruin the comments section of every blog you see. If there are some issues, create a blog or comment on blogs that already exist for that issue.
•  » » » » » 12 days ago, # ^ | ← Rev. 3 →   -33 -1
•  » » » » » » 12 days ago, # ^ | ← Rev. 2 →   +33 So you think that it is fair not to remove the cheaters? Where did you see him say it is fair not to remove cheaters ? Aren't you making up the truth? Do you think it's fun to deliberately destroy the environment of the comment section? Aren't you ashamed of yourself? And you just put the blame on Codeforces? It don't even take 1 hour to remove cheaters & update the ratings but don't know why they are not doing this from last 2 weeks. Don't you know that admins have to do a lot of things every day? And how can you be so confident? Less than an hour? Don't you know how much manpower and material resources it takes to run a website? Do not know how cumbersome it is to process all the competition information of more than 20000 contestants and then calculate the rating? Take your brain before you talk, and don't talk nonsense if you don't understand these things, okay?Also, can you stop yelling "Remove cheaters! Remove cheaters!" in the comment section of each official blog? You think admins doesn't know these things? Don't know how many contests recently? Don't you know how much admins workload? Please, be considerate of others. You're happy to make others hate you, aren't you? I didn't want to say anything at first, but I can't stand seeing the comment section like this. I hope this is the last time I get angry about such kind of shitposts.Sorry for my bad English.
•  » » » » » » » 12 days ago, # ^ | ← Rev. 3 →   +23 As an ex-admin of several huge online projects, I would like to agree with EasonCF: you can't imagine what enormous amount of work such kind of projects require.And the subject of the problem is insanely ridiculous: cheaters? Does it really bother you??? Rating? Are you serious? You've got a lot of great CP problems WEEKLY! Great tests, fantastic database of solutions and editorials, archive, and what are you talking about: cheaters and rating??? Be ashamed!
•  » » » » » » » » 11 days ago, # ^ |   0 Big fan of all the positivity you just radiated :)
•  » » 12 days ago, # ^ |   0 Can you create a blog for this problem??
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 The last provided ratings will be rolled back and then updated as usual I guess :)
 » 13 days ago, # |   0 Will be great a competition for sure :)
 » 13 days ago, # |   0 div3 contests are lub
 » 12 days ago, # |   +20 Despite my earlier criticism , I have come to appreciate naman1601's light hearted memes under every contest announcement. I would request him to bless us with another light hearted meme.P.S. He just became purple again. Everyone please upvote him as a congratulations.
•  » » 12 days ago, # ^ |   +98 lighthearted meme
 » 12 days ago, # |   0 Looking forward to increase my rating.
 » 12 days ago, # |   -8 Hope the difficulty level of is not equal to Div.2 which is the case with most Div.3 contest these dayz.
 » 12 days ago, # | ← Rev. 2 →   0 I believe I can finally be a student on CF. Good Luck everyone!
•  » » 12 days ago, # ^ |   0 You mean pupil?
 » 12 days ago, # |   +1 In div-3 do all questions have same score? Like A and F have same value upon solving?
•  » » 12 days ago, # ^ |   -9 no, rating distribution will be updated later most likely.
•  » » » 12 days ago, # ^ |   +2 no, in Div 3 and Education rounds the scores for all tasks are the same.
•  » » » » 12 days ago, # ^ |   0 oh, right my bad.
 » 12 days ago, # |   +10 It really hurts when rating is exactly 1600 :(
•  » » 12 days ago, # ^ |   0 Yeah !! a little less and would have a big positive delta and would have been stable as an expert. But the reverse can also happen. Little less than expert, take part and it decreases more. In this case, you would have missed the expert and would have been disappointing :|
•  » » 12 days ago, # ^ |   +33 And now you're 1599 lol
•  » » 12 days ago, # ^ |   0 Can't say I understand but I guess I can
 » 12 days ago, # |   +1 Hoping to be a blue coder to change my profile picture xD
 » 12 days ago, # |   0 ah yes, all that's left is to convince my parents to let me stay up till 1am. Or...Or do I speedrun solving 2 problems in 1 hour, and get deleted?
 » 12 days ago, # |   +4 Spoiler
 » 12 days ago, # |   0 Looking forward to this round!
 » 12 days ago, # |   0 After messed up Codeforces Educational Round 115 and Codechef starters 15 , I am looking forward to this round as my mood changer round :) .
 » 12 days ago, # |   0 why always on weekdays
 » 12 days ago, # |   0 Best of luck to everyone on this round!
 » 12 days ago, # |   0 Wish all participaters all good fortune
•  » » 12 days ago, # ^ |   0 Participants. :)
 » 12 days ago, # |   0 But what if you're a beginner like me who hasn't taken part in two rated contests yet?
•  » » 12 days ago, # ^ |   0 it says it'll be rated anyway. we're just being excluded from the official standings, i don't think it'll affect us in any way tho
•  » » » 12 days ago, # ^ |   0 True.
•  » » » » 12 days ago, # ^ |   0 yes,
 » 12 days ago, # |   0 Note that the start time is unusually usual.
 » 12 days ago, # |   +1 I hope everyone can raise rating
•  » » 12 days ago, # ^ |   +8 That's impossible.
 » 12 days ago, # |   0 Hoping to become green after this round. Wish me a bit of good luck.
 » 12 days ago, # |   0 Questioncan i get green tonight ?
•  » » 12 days ago, # ^ |   0 Only if You're able to solve Problem G (XD)
•  » » » 12 days ago, # ^ |   0 but why?
•  » » » 12 days ago, # ^ |   0 There is no problem X.
•  » » 12 days ago, # ^ |   0 Sure.
 » 12 days ago, # |   +1 Allfather bless me so that my color changes (to the better side) this time.
 » 12 days ago, # |   +3 Hi, Im New, but what languages will be accepted, like python c++?
•  » » 12 days ago, # ^ |   +3 both, my dear friend! There are still more language available for you :)
 » 12 days ago, # |   +12 Today is my birthday, and I will participate in this round.... Yoooo
•  » » 12 days ago, # ^ |   +1 Wish u Happy birthday and High ratings too.
•  » » 12 days ago, # ^ |   0 Happy birthday!Good luck!
•  » » 11 days ago, # ^ |   0 Wish you a very happy birthday! May you acheive high rating!
•  » » 11 days ago, # ^ |   0 Wish you a Happy Birthday!
 » 12 days ago, # |   0 Hope my color changes after this round ! )
 » 12 days ago, # |   0 It's cool that the penalty for a wrong attempt will be 10 minutes
 » 12 days ago, # |   0 I hope to stay newbie after contest :)
•  » » 12 days ago, # ^ |   0 dude you have solved 1000+ problems
•  » » » 12 days ago, # ^ |   0 unfortunately, most of them were trivial, i hope the coming well be better
•  » » 11 days ago, # ^ |   +5 You are an inspiration truly! You are trying hard and didn't give up! [user:Khedr_]Best of luck!
•  » » » 11 days ago, # ^ |   0 thanks :)
 » 12 days ago, # |   0 Good luck.
 » 12 days ago, # |   0 I wish I could be green coder after this round!
 » 12 days ago, # |   0 Hoping for change my color =))
 » 11 days ago, # |   +6 As a tester, I tested… GL&HF
 » 11 days ago, # |   +1 I hope that the penalty of all contests will be 10 minutes instead of 20, not only Div3
 » 11 days ago, # |   0 I'm not reading Announcement comments anymore.. Man I feel too old
•  » » 11 days ago, # ^ |   +3 You're old in this platform.
 » 11 days ago, # | ← Rev. 2 →   -11 had a terrible contest
 » 11 days ago, # |   +6 I hope my rating will reach 1900 after this contest Good luck !!!!
 » 11 days ago, # |   -24 [
 » 11 days ago, # |   +1 Any hints on F?
•  » » 11 days ago, # ^ |   0 DP
•  » » 11 days ago, # ^ |   0 I think it can be solved using digit dp.
 » 11 days ago, # |   0 solved G faster than rainboy pog
•  » » 11 days ago, # ^ |   0 btw G felt too easy for its position...
•  » » » 11 days ago, # ^ | ← Rev. 3 →   0 can you give me idea how to solve G, i got stuck on it used dfs and take max depth of node , give me bad output.edit my bad i mean problem E sry
•  » » » » 11 days ago, # ^ |   0 dfs? how?
•  » » » » 11 days ago, # ^ | ← Rev. 2 →   +12 my $O(n+q)$ solution for pG:note that we can change between $($ and $)$ (similarly, $[$ and $]$) at no cost, let's transform $($, $)$ into $a$ and $[$, $]$ into $b$then we can subdivide each even length substring into blocks of length 2. there are 4 possible blocks: $aa, bb, ab, ba$.A block of $aa$ or $bb$ cost 0, while $ab$, $ba$ cost 1. $aa, bb$ cancels themselves, and $ab, ba$ cancels each other. (both $abba$ and $baab$ cost 0) so the problem reduced to find how many $ab$ and $ba$ blocks are there in a range, and cancel them while possible.the answer is the difference between the number of $ab$ and the number of $ba$ in a given range, using prefix sum can solve each query in $O(1)$ time with $O(n)$ preprocessing.
•  » » » » » 10 days ago, # ^ |   0 Thanks bro!I never imagined G could be that easy so never gave it an honest try T_T
•  » » » » 11 days ago, # ^ | ← Rev. 2 →   0 in pE do DFS $k$ times result in a worst-case $O(nk)$ time complexity, it occurs when the tree is also a "chain" (edges are $(1, 2), (2, 3), ..., (n-1, n)$)
 » 11 days ago, # |   0 nice problems :)
 » 11 days ago, # |   0 Is D2 about iterating over the numbers which have more than half of the bits set in $[1,2^{N}]$ ?
•  » » 11 days ago, # ^ |   +1 you should just get the difference of between every 2 elements in the array and try all of their divisors
•  » » » 11 days ago, # ^ |   +3 Yeah dumb of me to not notice that, btw please accept my apologies I hacked your E :(
•  » » » » 11 days ago, # ^ |   +21 That's the evilest thing I have ever seen
•  » » » » 11 days ago, # ^ | ← Rev. 3 →   +1 How is it TLE when I'm moving from the leaves directly to the next operation leaves Edit OMG I forgot to add break after i edited my code the last time it was correct
•  » » 11 days ago, # ^ | ← Rev. 4 →   +16 My method:If any element appears >= n/2 times, answer is -1.Otherwise: for each choice of reference value a(i) from the array, consider the set of differences abs(a(j) — a(i)) for all j. Where the difference is 0, increment a counter z. Otherwise find the factors of abs(a(j) — a(i)), which can be done in O(sqrt(max(a))) time. Keep a count of how many times each factor occurs. Any factor such that count(factor) + z >= n/2 is a possible answer, and the max of these candidates is the final answer. Remember to reset the factor counter for each choice of reference value a(i). Total time complexity O(N^2 * sqrt(max(a)) )Solution: link
•  » » » 11 days ago, # ^ |   0 Nice :)
•  » » » 11 days ago, # ^ |   0 this was my exact solution lol
 » 11 days ago, # | ← Rev. 2 →   0 hoooolly shit that was intense i accidentally solved D1 like how it should be solved in D2
 » 11 days ago, # |   +1 :( ? Why D1. n<=40 but sum (n) <= 100 ?
 » 11 days ago, # |   0 Any idea how to do D1? I tried doing it by taking the GCD of all the differences of pairs but I was getting WA on test case 3
•  » » 11 days ago, # ^ |   0 first find the minimum element, then take GCD on the difference between the minimum value and each element (except the ones with minimum value). output -1 if all elements are same.
•  » » » 11 days ago, # ^ |   0 Thanks. I iterated through all the NC2 possible differences and was sure the answer is right . But I was using a long long gcd function which was giving gcd(0,negativeno) some overflowed value . I changed it to int and it got AC .
•  » » 11 days ago, # ^ |   0 I guess you forgot to sort array
•  » » » 11 days ago, # ^ |   +4 Sorting array is unnecessary. Any member of the array can be used as the reference value.
•  » » 11 days ago, # ^ |   0 You are also required to check if all items are equal. In such case, answer is -1(Infinite)
•  » » 11 days ago, # ^ |   0 I checked your solution here https://codeforces.cc/contest/1593/submission/131802472and you have an integer overflow issue as you use vll a(n); which expands to vector of which ll expands to unsigned long long int.When you perform a[i] - a[j] and it is unsigned, you must take extra precaution.
•  » » » 11 days ago, # ^ |   0 Thanks a lot , I will keep this in mind :)
 » 11 days ago, # |   0 Quite interesting problemset! Thanks for this round!
 » 11 days ago, # |   -8 Really nice D2
•  » » 11 days ago, # ^ |   +5 How did you do it?
 » 11 days ago, # | ← Rev. 2 →   0 Really liked the problems!Can anyone point out my mistake on B? SubmissionI used bitmasks to simulate the removed numbers, implementation was buggy as it keeps getting WA on test 2
•  » » 11 days ago, # ^ |   0 Anyway it will get TLE as your time complexity is O(n*2^n) where n <= 18, and for T <= 10^4 it will get TLE. I also implemented similar solution initially, https://codeforces.cc/contest/1593/submission/131774681 But it gave TLE.
•  » » » 11 days ago, # ^ |   0 Thank you, will keep that in mind
 » 11 days ago, # |   0 What the heck is this second test for E?
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 Edge case when $n <= 2$, output should be 0
•  » » » 11 days ago, # ^ |   0 My output is 0 for this...
•  » » 11 days ago, # ^ |   0 Same question (:
•  » » 11 days ago, # ^ |   +1 have you checked? 1 1 1 me and my friend have lost this case:)
•  » » » 11 days ago, # ^ |   0 Sure, but... Not in my case :(
•  » » » 11 days ago, # ^ |   0 Not in mine too..
•  » » » 11 days ago, # ^ |   0 bro me too.... missed this one :(
•  » » 11 days ago, # ^ | ← Rev. 3 →   0 n = 5, k = 1; 1 5; 1 5; 2 5; 3 5; 4 5;That helped me
•  » » » 11 days ago, # ^ |   0 Not in my case :(
•  » » 11 days ago, # ^ |   0 Case when 3(or more edges are outgoing from a single edge). Consider the case: 7 2 1 2 2 5 5 6 2 3 3 4 4 7 Removing the first set of leaf nodes, shall not make node-2 as leaf. Your solution does. I had the same problem, figured out but couldn't implement. Your Answer — 1 Expected Answer — 2
•  » » » 11 days ago, # ^ |   0 oh, yes, it makes sense, thank you!
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 1 7 2 1 6 1 5 3 1 6 7 1 4 1 2 expected : 0
 » 11 days ago, # |   0 can someone help me by telling what i am doing wrong in Problem-Esolution link : https://codeforces.cc/contest/1593/submission/131852543
•  » » 11 days ago, # ^ |   0 Same request: 131819309
•  » » 11 days ago, # ^ |   0 Draw the following case on paper. Spoiler1 6 2 2 5 4 3 6 2 1 5 4 5
•  » » 11 days ago, # ^ |   0 consider this example.n=6 k=2 treeCorrect answer: step 1 -> 1 4 6 removed step 2 -> 2 5 removed Answer is 1Your answer step 1 -> 1 4 6 removed step 2 -> 2 5 3 removed Answer is 0
 » 11 days ago, # |   +87 I liked the problems, but this is really irresponsible behaviour. I understand sometimes issues may escape the testing phase too, but quietly changing the statement without announcements trying to not address the that there was an issue is not acceptable. I spent a lot of time trying to debug my initial submission, and finally when I couldn't believe that this was incorrect, I tried refreshing the page.
•  » » 11 days ago, # ^ | ← Rev. 3 →   +9 Following up on this, problem E did not have limit of sum of K over test cases, neither had tests which had this large sum. I don't understand why authors didn't put max tests? Weak tests in general on many problems, as you can see from the number of hacks and FSTs.
 » 11 days ago, # |   0 Constraint of problem D1 was a trap.
 » 11 days ago, # | ← Rev. 4 →   0 Isn't this solution correct for problem E Number of nodes left = total nodes — number of nodes which have distance less than equal to k to the closest leaf node.
•  » » 11 days ago, # ^ |   +8 1 6 2 1 2 2 5 5 6 2 3 3 4 Your answer should be 1, but using the above logic, you will get 0
•  » » » 11 days ago, # ^ |   0 Got it. Thanks
 » 11 days ago, # |   -23 Was giving the contest from an alt, logged in to orig to see friends standings, forgot to switch, did a wrong submission on E ;-; RIP me back to green ig :( Atleast if I had gotten AC on E, would have been worth it, but got a runtime error ;-;
•  » » 11 days ago, # ^ |   0 bro also the sample was not strong in most problems
 » 11 days ago, # |   0 How to solve C?
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 Check my submission: 131779632I used prefix sums and binary search :)
•  » » 11 days ago, # ^ | ← Rev. 2 →   +2 the cat moves exactly $n-1$ times, so the total times you can move a mouse is also $n-1$.To save as many mice as possible, always move the mouse nearest to the hole first. You can sort the array of the distance of each mouse to the hole, then try to save the mice from the nearest until the total distance exceeds $n-1$.
•  » » 11 days ago, # ^ |   0 Its easy sort the array . Take currentTime and t . Sort array and from last , for each mice calclulate the t = n — arr[i] this time will be to go into Hole . also add cnt++ . Add t to currentTime. If at any point , currentTime >= arr[i] break and print cnt
•  » » 11 days ago, # ^ |   0 My idea to C was basically greedy . claim: making the mice closest to the hole move is the most optimal strategy proof : I guess it is by Exchange Argument consider a better solution exists . and this is not optimal so we move the mice ahead which is not the ending one . so making this mice move over larger distance . in place we could have moved more mice near the hole into the hole . so clearly our strategy is optimal
 » 11 days ago, # |   0 really nice contest! in problem b can anyone tell me if there a bug in my code or its not supposed to use bitmask due to constraints https://codeforces.cc/contest/1593/submission/131838191 sorry for bad english
•  » » 11 days ago, # ^ |   0 I think you have a problem with this : 1 <= t <= 10000.meaning : t * pow(2, k). (2 <= k <= 19).
•  » » » 11 days ago, # ^ |   0 ok thanks i calculated the time complexity too but i thought it may pass XD sorry another question can you tell me if my code is correct or not i amnot very familiar with bitmask
•  » » » » 11 days ago, # ^ |   0 Yes, I think it's correct.Just for criticism I think it would be better if you could replace this line : for (long long i = 1, w = pow(2, k); i < w; i ++) with this : for (int i = 1; i < (1 << k); i++) 
•  » » » » » 11 days ago, # ^ |   0 ok thanks alot
•  » » » » » » 11 days ago, # ^ |   0 glad to help
 » 11 days ago, # |   0 Looking at the hacks, I foresee many TLEs on E, especially for those that BFS from leaves and keep track of degree of the nodes
•  » » 11 days ago, # ^ |   +3 If done smartly this approach is fine. Only perform updates when a node is trimmed, and the total number of updates is equal to the total number of edges, which is N-1. Why should that TLE?
•  » » » 11 days ago, # ^ |   0 Ok looking closer at the ones that got hacked and unsuccessful hacks by galen_colin (don't wanna tag for no reason), during one cycle of BFS they push the next elements into a separate queue/DS, and then replace the queue/DS. Maybe overhead from replacement is causing the TLE.
•  » » » » 11 days ago, # ^ |   0 Yes I see. I just used a priority queue and did it Djikstra-style to avoid anything like that. That's not to say I won't be hacked though — who knows :)
•  » » » » 11 days ago, # ^ |   +4 I think the problem is that sum of k is not bounded and many people (including three of my div 1 Ukrainian friends and myself) just had a while(k--) loop or something similar.
 » 11 days ago, # |   -9 The problems were good but the samples were really weak
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 samples are not supposed to be strong lol... what's next? all tests are opened?
•  » » » 11 days ago, # ^ |   +1 They could've added a test case for -1 in problem D1
•  » » » » 11 days ago, # ^ |   0 imo, finding of cornercases must be a part of a solution
•  » » » » » 11 days ago, # ^ |   -12 Imo there is no need for pretests at all let hackers do the deed.Seriously this round is a joke.
•  » » » » » » 11 days ago, # ^ |   0 samples!=pretests
•  » » » » 11 days ago, # ^ |   0 They did, I forgot that, got WA on pretest-6.
 » 11 days ago, # |   0 missed (
 » 11 days ago, # |   0 I know you are impatiently waiting for the editorial, so I've decided to share with you my easy-to-understand solution for problem A. int t; cin >> t; while (t--) { int a, b, c; cin >> a >> b >> c; cout << max(max(b, c) + 1 - a, 0) << ' '; cout << max(max(c, a) + 1 - b, 0) << ' '; cout << max(max(a, b) + 1 - c, 0) << '\n'; } 
•  » » 11 days ago, # ^ |   +8 Wow, very simple and efficient code. But I write all possible way with if else statements that what newbies do.
 » 11 days ago, # |   0 Can someone help me figure out why am I getting a different output (which is one more than the required output) when on codeforces judge, but when I run it locally on my compiler it gives the correct output for the same test case.Here is my submission
•  » » 11 days ago, # ^ |   0 Because you are including death[0] in your answer. death[0] is not set anywhere, so its value on your local machine may differ to that on the server.
•  » » » 11 days ago, # ^ | ← Rev. 3 →   0 Nice catch, but after fixing that, I have a similar problem but this time a 3 instead of 1, I tested it on my compiler and it gives the correct result,SubmissionPS: I have realised my solution is incorrect but I still want to know the reason for the inconsistency in the outputs for future reference.
•  » » » » 11 days ago, # ^ |   0 It's very difficult to say for sure but I have (recent) experience of similar things and my finding has always been that I've been accessing something that I didn't mean to, or that I didn't think was there, by mistake.A hypothesis might be that your adj is not resetting itself in the same way online (since you are not explicitly clearing the elements). But I confess I cannot say for certain.
•  » » » » 11 days ago, # ^ |   0 You're setting some death[i] to be 1, but I think you might be assuming that the others would be 0, which is not correct.
 » 11 days ago, # |   0 Why multisource bfs isn't working in E?
•  » » 11 days ago, # ^ |   +5 Reading your code, your method appears to be "ans(node) = min distance from node to any leaf". This method is not correct. Consider why this is incorrect with the below case, to which the answer is 1 but to which your code gives 0. During the 2nd iteration, node 1 remains.16 21 21 33 41 55 6
•  » » » 11 days ago, # ^ |   0 Got it. Thanks
 » 11 days ago, # |   0 Can Anyone Help Me Out to find why am i getting wa for problem E ,My Submission : 131857557
•  » » 11 days ago, # ^ |   0 You also fail the case mentioned in this comment
•  » » » 11 days ago, # ^ |   0 Thanks , will look into it :)
 » 11 days ago, # | ← Rev. 3 →   +4 These types of Solutions are getting hacked with TLE, but it doesn't seem to exceed TL. This is O(KlogK) solution. Perhaps this is because of Java?Correct me if I am wrong. Thanks.
•  » » 11 days ago, # ^ |   +4 I don't use java much but Arrays.sort(a) in java has worst-case time complexity of order n^2. Therefore the worst-case time complexity of your program is n^2 which gave tle.You can read more here
•  » » » 11 days ago, # ^ |   +3 Oh okay, thanks for the information. So there are more chances of java solutions getting hacked whenever sorting is needed in the solution, right?
•  » » » » 10 days ago, # ^ | ← Rev. 3 →   +4 Yes, you are correct. I have seen tons of solutions in java getting hacked on codeforces due to Array.sort(a). You should switch to Collections.sort(a) or suffle array before using Array.sort(a)Array.sort(a) uses quick sort only on primitive data types. So if there is no primitive data type Array.sort() is ok.An example of Collections.sort() can be seen here in the SecondThread solutionNotice that he uses collections.sort and fastio for speeding up the code. Collections.sort() wont get hacked as the worst case of it is nlogn
 » 11 days ago, # |   0 Submitted this after the contest as an experiment. Can anyone please suggest why wouldn't it work?
 » 11 days ago, # | ← Rev. 4 →   0 Anyone else with the following on Test case 2 for E wrong answer 37th numbers differ - expected: '1', found: '0' ? What is this test case possibly? I did multi-source bfs starting with all the leaves of the tree.
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 I have this WA too, but i did dfs from a random leave
•  » » 11 days ago, # ^ |   0 I don't know but I do know that even making the smallest mistake, things that you think are OK to ignore will cause trouble in this problem, in my code I had to add just 1 if statement and it would have worked fine :( .
•  » » 11 days ago, # ^ | ← Rev. 3 →   0 1 1 0 Yours gives 0. Ans should be 1Edit: My bad k >= 1
•  » » » 11 days ago, # ^ |   0 My code gives 0 for this case.
•  » » 11 days ago, # ^ |   +2 1 6 2 1 2 2 5 5 6 2 3 3 4 The ans should be 1. Multisource bfs gives 0
•  » » » 11 days ago, # ^ |   0 Can't understand the test case. What is n and k here ?
•  » » » » 11 days ago, # ^ |   0 6 and 2
•  » » » » » 11 days ago, # ^ | ← Rev. 6 →   0 Found the mistake. Thanks. Its possible to solve using multi-source bfs but at every step you also have to subtract the degree of the parent of the leaf node and push it in the queue only if its degree == 1
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 try only pushing those nodes which are connected to the current node being processes(u) after removing u from the tree in the multisource bfs. If you didn't do it this way!
 » 11 days ago, # |   0
 » 11 days ago, # |   0 A simple and easy to understand — Implementation for problem b : 131798547
 » 11 days ago, # |   0 I think anyone needs it :3 : https://www.youtube.com/watch?v=sZxP4zkSLSE
 » 11 days ago, # |   0 It seems that D2 has many suceesful hack. Is pretest weak or some conercase ?
 » 11 days ago, # | ← Rev. 3 →   -9 when I run this code on some other compilers like gfg ide, visual studio I get correct O/P for sample test case 1st but on codeforces I am getting W/A on test case 1st, IDK how this happens ??Code:https://ide.geeksforgeeks.org/zN7ERcyWaB
•  » » 11 days ago, # ^ |   0 Try with language GNU G++17 9.2.0 (64 bit, msys 2) .
•  » » » 11 days ago, # ^ |   0 I am already running into G++17
 » 11 days ago, # |   +1 Anyone solved E in O(n) by finding 2nd largest length from every node to leaves?
•  » » 11 days ago, # ^ |   0 Nice idea :)I think your algorithm is actually O(K + N log N) though. You use set (insertion log N). I think this explains your long run time — set is slow and you perform a lot of insert and erase operations.If you wanted this to be truly O(N) you could store, for each node, just the two greatest distances you currently have, and update them in place without need for actually sorting (either through use of set or otherwise).
•  » » » 11 days ago, # ^ |   0 I brute forced like everyone.
•  » » 10 days ago, # ^ |   0 Yup! I did just now
 » 11 days ago, # |   0 Why there is so much hacking in E? Which test case it is failing???
•  » » 11 days ago, # ^ |   0 The majority of hacks seem to be time limit related, where the user has, K times over, created a whole new queue which could have size of up to N.
•  » » » 11 days ago, # ^ |   0 How though? I believe only the new leaves would be added to the queue and that should be of the order of the nodes since any leaf would be added at most once. here's my code // Initially, queue is populated with leaves. Set removed = new HashSet(); int remaining = n; while (remaining > 0 && k > 0) { k--; Queue next = new LinkedList(); while (leaves.size() > 0) { int leaf = leaves.poll(); removed.add(leaf); remaining--; for (var nbr : connections.get(leaf)) { // neighbouring nodes if (removed.contains(nbr)) { continue; } neighbours.put(nbr, neighbours.get(nbr)-1); // neighbour counts if (neighbours.get(nbr) == 1) { next.add(nbr); } } } leaves = next; } return remaining; Sorry for the poor variable naming. Link to submission
 » 11 days ago, # | ← Rev. 2 →   0 Nice problems, but weak testcases. Thanx.
 » 11 days ago, # |   0 Were the weak tests on D1 and D2 on purpose? MrPaul_TUser
•  » » 11 days ago, # ^ |   0 for E tooo. (my code giving TLE after the contest.) can you please answer why this code giving tle.
 » 11 days ago, # | ← Rev. 2 →   +67 really strong tests
 » 11 days ago, # |   -11 Thanks for easy +150 points(as cf predictor says)
 » 11 days ago, # |   0 guys i solved 3 problems my ranking 6000, does it mean i will get green or their is no way ?
•  » » 11 days ago, # ^ |   0 It seems like it's going to increase, but not that much to become green)
 » 11 days ago, # |   +6 Some people hacked a lot of solutions, it's hard to read a lot of solutions (at least for me) and find which ones can be hacked and which ones are not.I think there is a way to test a lot of solutions automatically. Is that true ? and is it allowed ? and do you have any idea how to do that ? it would be great if you can help.
 » 11 days ago, # |   0 I got wrong on TC2 on C (my submission).... Please help!
•  » » 11 days ago, # ^ |   0 I ran your code. use this  if(i==k)break;  at last in while loop.
•  » » » 11 days ago, # ^ |   0 yes! got AC...a little bit sad for that silly mistake..however!Now I get relife that my idea wasn't wrong.
•  » » 11 days ago, # ^ |   0 If you would like a testcase that fails:10 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999It has to do with not checking for your vector being out of bounds when you incremented i.
•  » » » 11 days ago, # ^ |   0 oo..thanks!
 » 11 days ago, # |   0 Here's my Solution to E 131874293. Do you guys have a better approach or this solution is fine.
•  » » 11 days ago, # ^ | ← Rev. 4 →   0 I think the algorithm itself is fine, and the implementation has room for improvement.deg is not necessary, you can use ar[i].size() instead.leafs and new_leafs can actually be vector rather than setAnd consider output '\n' for new line instead of endl since endl flush the output buffer each time, which may make the running time longerYou can refer to my submission, which has basically the same algorithm as yours and has 3x faster in running time.
•  » » » 11 days ago, # ^ |   0 Thanks for your time, also isn't set better for removal of leaf nodes.?
•  » » » » 11 days ago, # ^ |   0 But in leafs and new_leafs, all removals are removing all elements, which is actually clear the set.If you need to remove individual elements, using set is better (so we use set not vector for the adjacency list in this problem).
•  » » » » » 11 days ago, # ^ |   0 Ohhk thanks I didn't see I was clearing later
 » 11 days ago, # |   -32 I have a serious concern about the problem A.Is it fair to allow such submission getting AC?To compare, this one gets TL. Of course, the only difference is the line 3: #pragma GCC optimize ("O0")I guess that checker must prohibit the loop elimination explicitly when compiling the solution, because that's what GCC does in this case.Would be nice to listen to the contest authors' opinion. cc MikeMirzayanov MrPaul_TUser
•  » » 11 days ago, # ^ |   -8 Well, I'm kinda confused with people's reaction. Could somebody from those who downvoted to comment on that?
•  » » » 11 days ago, # ^ |   +13 Why in the world would getting AC by this submission not be fair? Modern compilers nowadays apply an overwhelming number of optimizations, you cannot know all of them for sure. Which of the optimizations must be considered "unfair"?Loop elimination is one of the simplest optimizations a compiler can do. If G++ is able to do it while others are not, well, one has to blame the other compilers for that.
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   0 Which of the optimizations must be considered "unfair"? I didn't tell the optimization itself was unfair. And I know well what compiler optimization is.Also, I didn't participate the contest and I don't ask for some other people's solutions to be retested, etc.I'm just pointing out that the solution which presumes 10^13 operations to be performed gets AC verdict.Moreover, it does perform those when being compiled with -O0 or -O1. I guess, there's also some sort of flag to disable such optimization while having -O2 or -O3 enabled too.So my intention was to raise a question about potential elimination of those optimizations while testing a solution.Why? Because the compiler must not influence the correctness of the solution. And the solution above is wrong indeed, it must not be accepted as a valid one, IMHO.
•  » » » » » 10 days ago, # ^ |   +10 The solution is not wrong. It gives correct answers for all the tests. If it is compiled without optimizations, then it will get TLE, but it does not mean that it's wrong.But the question is: where is the margin between optimizations which influence correctness and optimizations which do not?If you really want to be sure that your code will not be affected by obstinate optimizations, then write code in the assembly language. The processor will unquestioningly execute all the instructions you would write.After all, this is not a theoretical olympiad in informatics where participants are supposed to describe the algorithm and prove its complexity. If we code in high-level programming languages, then it's essential for a compiler to speed up the code wherever it's possible.
•  » » » » » » 10 days ago, # ^ |   -10 The solution is not wrong. It gives correct answers for all the tests. The fact that it gets AC for all test doesn't mean it's not wrong. But the question is: where is the margin between optimizations which influence correctness and optimizations which do not? Of course we can't answer this for sure, but at least loop elimination prohibiting could be a good place to start.I don't insist on it, I was just curious of the authors' opinion.Anyway, what motivated me to start this conversation was getting AC by the wrong solution, and I'll keep claiming it is wrong just because it's not completely correct (whether or not you agree with such interpretation).
•  » » » » » » » 10 days ago, # ^ |   +10 Once again: the solution is not wrong. It's slow. It's a slow correct solution. Not all correct solutions are supposed to fit into the time limit, as well as not all slow solutions are supposed to be rejected. Some of them may pass, though. at least loop elimination prohibiting could be a good place to start Sorry, but this is not a constructive way of discussion.Here is the discussion on turning on some optimization flags (-O3, -funroll-loops etc.) for G++ by default on Codeforces. You can't stop progress.
 » 11 days ago, # |   +11 Has anyone done F using meet in the middle technique, instead of using normal dp. In which divide the string into 2 parts and checking each part individually ? I tried but got TLE in TC 7. Though I think it will pass if 2s is given as approx complexity is $O(2^{n/2}*{n/2})$
 » 11 days ago, # |   -17 It's sad. I thought about question B for 2 hours and still didn't think of it. I think it's much harder than div2
•  » » 11 days ago, # ^ |   0 you should have just google the properties of numbers which are divisible by 25 and then it was just an implementation that's what I did
•  » » » 11 days ago, # ^ |   0 I didn't think about it at all. I only need the numbers of 25, 50, 00 and 75. I've been thinking about how to greedy simulation deletion, so I went astray. I even use search to write, but I know it will timeout
•  » » 11 days ago, # ^ |   0 https://codeforces.cc/contest/1593/submission/131784183Give It a look made too easy to understand for others
•  » » » 11 days ago, # ^ |   0 Thank you. I understand
•  » » » » 11 days ago, # ^ |   0 Welcome !!
 » 11 days ago, # |   0 Can 131830101 be hacked? I didn't stop the while (k--) loop even after the queue (q in my code) is empty and my solution has extra $\log N$ factor because of std::set.
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 after q becomes empty the while (k--) does nothing (and won't consume a lot of time) because the for (int sz = LEN(q); sz > 0; --sz) inside your while (k--).
 » 11 days ago, # |   0 Can somebody please explain where I am going wrong in problem E? My Submission This code is giving wrong answer on Test 3.My Approach: First, I found the centroid of the tree. Then I ran a DFS from this centroid and maintained an $ans$ vector where $ans_i$ will store the number of operations after which $i^{th}$ node will be removed. 1. ans[leaf node]=1. 2. ans[node having only one child] = ans[child]+1. 3. ans[any other node] = Second_Max(ans[all children])+1.I am taking second maximum because for a node having $C$ children, atleast $C-1$ of its children must be removed for this node to become a leaf node(removable).Final answer will be number of nodes having $ans[node]>k$.Thanks in advance.
•  » » 11 days ago, # ^ |   +1 oooooh! Don't know where is the error but the logic is extraordinarily..
•  » » 11 days ago, # ^ |   0 Can you prove that taking the centroid of the tree is always correct in your solution?
•  » » » 11 days ago, # ^ |   0 Well, it was kind of a intuition. But I think about it this way, since centroid is kind of a balance point because it divides the tree into forest of subtrees with size at most half of original, so centroid must be last one to be removed if we follow the procedure from the problem. Please correct me if I'm wrong.
 » 11 days ago, # |   0 Hello everyone here, Yesterday I solved 3 problems and got an accepted verdict. Today about half an hour back it still showed an accepted verdict. But now 2 out of 3 problems are showing a queue verdict. May I know the reason for this?
•  » » 11 days ago, # ^ |   0 system rejudging your problem now !!!
•  » » » 11 days ago, # ^ |   0 Oh, Thank You so much. Was not aware of this.
•  » » 11 days ago, # ^ |   0 Just system testing all the submissions. Don't worry.
•  » » » 11 days ago, # ^ |   0 Oh nice, now it is 2 out of the 3 submissions have received an "accepted" judgement. Hoping for the 3rd one to get judged.
 » 11 days ago, # | ← Rev. 4 →   -20 We tried to make really strong tests — just like you will be surprised if many solutions fail after the contest is over.You intentionally gave n <= 40 in d1 where O(n) soln is easily working just to mislead participants in directly using brute force without much thinking , however if u would have given n in range 1e5 then this thing wouldn't have happened , so it is really not expected from ur side , And also in problem C , u gave time limit 4 seconds and as a result of which some O(1e9 range) solutions got accepted and now they failed system tests.Just because of your really strong tests i got +2000 my expected place since i solved d1 before b and c so it was really disheartening to see :(Those who are downvoting will get to know how it feels when it happens to them :)
•  » » 11 days ago, # ^ |   +9 That's your problem. They all remind that passing pretests doesn't mean to pass system judge :))
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 When you will be at the receiving end you will understand. I hope you will remember what you preached at that moment.
 » 11 days ago, # | ← Rev. 15 →   0 TLE.Just changed vector with array and now it is accepted. It feel very bad (T_T) During the contest my solution was accepted and after systest it gave TLE). First time I had got under 2000 rank. It was meant a lot for me. And now this happened because of vector vs array:| SpoilerAlways, prefer to use arrays rather than vectors.PS: Do anyone know how to use vectors as fast as arrays?PS: TLE code accepted on removing #define int long long.PS: But, creating dynamic array example: int*m = new int[k + 1]; gives MLE. 131911303PS: Global vector working fine.By the way nice contest ^_^. IMO there should have such testcases during the contest so that we can correct this things during the contest.
•  » » 11 days ago, # ^ |   0 You were using a map, not vector.
•  » » » 11 days ago, # ^ |   0
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 I had put wrong link by mistake. Sorry for that.
 » 11 days ago, # |   -45 Dear MrPaul_TUser and MikeMirzayanovTesting the D2 question cases seems very inappropriate !See my submission , it gets wrong on test 56! While it received accept in pretests. It costs me a sharp drop in rankings so from near 1500 i become 3500 because of weak testcases! So i really please you to reduce the testcases for D2 and rejudge this question. 131848968
•  » » 11 days ago, # ^ |   +26 You mean your code fails on a certain testcase meaning that your code isn't correct within the given constraints and hence the testcases which your code can't handle should be removed?Nice
•  » » » 11 days ago, # ^ |   -23 No i mean that the failure was because of the poor testcases , if this testcase was able in the pretests me and many of contesters could find and fix the problem! And this tragedy did not happen. I noticed that many of the codes that were accepted for the D2 problem are wrong now, with nearly 1,000 codes, a number of hacks and a large number of them due to poor test cases. This should not have happened !
 » 11 days ago, # |   0 Can anyone explain why my submission causes RTE, please? 131823111 Same code in Python3, I passed test
•  » » 10 days ago, # ^ | ← Rev. 3 →   0 Technically, in C and C++ (and most other languages I guess), any integer other than 0 is considered true, so your comparator function that you passed into the sort function to sort your input in descending order is not working as intended, I replaced return a.first - b.first; with return a.first > b.first and the code worked perfectly.
•  » » » 10 days ago, # ^ |   0 thanks a lot!!
 » 11 days ago, # |   +8 I can't get over this that was my best performance since I started on this site I had a break command in my previous WA submission for E and i fixed everything but deleted the break by mistake it passed and got hacked :'( I could have reached expert without that stupid break command went from 250 to 670 someone give me 10 bags of tissues :'( :'( :'(
•  » » 11 days ago, # ^ |   +10 Don't worry man. Just do your best next time.
•  » » 11 days ago, # ^ |   0 dont feel bad man.these things help you alot in future to be carefull next time
•  » » 11 days ago, # ^ |   0 dont worry bro! soon u ll become expert
 » 11 days ago, # |   +5 When will the rating changed?
 » 11 days ago, # |   +1 When will the rating changed?
•  » » 11 days ago, # ^ |   0 System testing has not finished yet for God's sake!
•  » » » 11 days ago, # ^ |   0 I just saw it finish, and now it 99%.
•  » » » » 11 days ago, # ^ |   0 You did not see it finish. That was an optical illusion. :)
 » 11 days ago, # |   0 Why do I see this contest in my unrated contest. My rating is < 1600
•  » » 11 days ago, # ^ |   0 The rating hasn't updated yet. You need to keep waiting for a while until the rating get updated.
•  » » 11 days ago, # ^ |   0 You may be not a trusted participant because you played only one rated round before this one.
•  » » » 11 days ago, # ^ |   0 Sorry, now I see you have already played 2 rated rounds.
 » 11 days ago, # |   0 I often see it is written in the open hack or system testing phase that only trusted participants. What does this mean?
•  » » 11 days ago, # ^ |   0 Read the announcement carefully and you'll find: 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 trusted participants of the third division, you must:take part in at least two rated rounds (and solve at least one problem in each of them),do not have a point of 1900 or higher in the rating.
 » 11 days ago, # |   +1 When will the editorial be released Waiting for the explanation of D2 and E problems
 » 11 days ago, # |   0 Well, I have waited for 4 hours from the open hacking ended. However, I didn't see any signs about rating. I'm very nervous and I want to ask when will Codeforces rate? Thanks and I know a lot of people are waiting like me =))
•  » » 11 days ago, # ^ |   0 Now it has been updated :)
 » 11 days ago, # |   +7 i am wondering(HELP) what is the significance of n is even in D1 problem
•  » » 11 days ago, # ^ |   0 Nothing. This detail is more important in the harder version, D2.
 » 11 days ago, # | ← Rev. 2 →   +1 nitin_05ashokesen02Even though they cheated in the latest round, they got rated instead of being skiped.
•  » » 10 days ago, # ^ |   0
 » 11 days ago, # |   0 Thank you for your contest, it was great. Can I ask how long will there be a new contest?
 » 11 days ago, # | ← Rev. 6 →   0 Can we use meet in the middle for D2??
•  » » 10 days ago, # ^ |   0 Possibly someone smarter than me will have a way but I can’t see it. For me this is brute force over all possible smallest values of your set where you try to find the largest factor which exists in N/2 of the differences with that element (itself included).
•  » » » 10 days ago, # ^ | ← Rev. 2 →   -8 Now, I think that (meet in the middle one)approach would result in TLE since in that approach you will divide the array into 2 equal sizes and look for all possible subsequences that would result in TC(2^20) which is roughly 10^6 and if you try all possible values of k you will get TLE
•  » » » » 10 days ago, # ^ |   0 No, that’s not how it works. See this comment
 » 11 days ago, # | ← Rev. 2 →   +3 In problem C: "The actions are performed until any mouse hasn't been hidden or isn't eaten."That should be while not until. Every programmer should know it regardless of English proficiency.
 » 11 days ago, # | ← Rev. 2 →   0 Congratulation @Viettran, 8528190072TuanHD
 » 11 days ago, # | ← Rev. 2 →   +13 It's sad to see that top1 and top2 in div3 are cheaters (U need to use unofficial leaderboard to see them). They have multiple submissions to different problems within one minute using completely different templates xD MrPaul_TUser maybe something can be done about that, althought I doubit it.
 »