### 74TrAkToR's blog

By 74TrAkToR, history, 3 months ago, translation,

Hello, Codeforces!

I am happy to invite you to my Codeforces Round #830 (Div. 2) which will be held at Oct/23/2022 13:05 (Moscow time). The round will be rated for all the participants with rating strictly less than 2100 before Oct/23/2022 10:50 (Moscow time).

The tasks were created and prepared by 74TrAkToR. I would like to thank everyone who helped me a lot with round preparation.

During the round you will need to solve 5 problems, some of which have subtasks. You will have 2 hours to solve them.

Score distribution will be announced shortly before the round.

We wish you good luck and high rating!

UPD: Score distribution: $750-750-(1000-1000)-(1250-1250)-3000$

UPD: Editorial

• +248

 » 3 months ago, # |   +29 Sleepforces
 » 3 months ago, # |   +45 Orz to gyh20 for testing twice :O
•  » » 3 months ago, # ^ |   -181 Instead of writing your shit on every post , you can consider practice more. Asses everywhere.
•  » » » 3 months ago, # ^ |   +27 Says a newbie
•  » » » » 3 months ago, # ^ |   -177 Not a noobie kiddo, have you heard of ALT??
•  » » » » » 3 months ago, # ^ |   +65 ALTs are prohibited by the codeforces rules
•  » » » » 3 months ago, # ^ |   +9 Don't be so ignorant. He actually has a maximal rating of a whopping 1069 on his alt!
•  » » » 3 months ago, # ^ |   +19 So your first comment on codeforces is aimed at trying to roast me (which failed horribly)? Too bad.
•  » » » » 3 months ago, # ^ |   -105 No need to roast someone with contribution <0 . Just reminding not to shit everywhere.
•  » » » » » 3 months ago, # ^ |   +14 Says a person who ranks last place with an "ALT"
•  » » » » » » 3 months ago, # ^ |   -75 This one's is special, aimed at getting rating<0 ;) And one more thing, you should practice some good problems, 400 is a big number for pupil lol .
•  » » » » » » » 3 months ago, # ^ |   +37 Trying so hard to solve a problem, eh? Spoiler
•  » » » » » » » » 3 months ago, # ^ |   0 Haha.. Good one! haiender288
•  » » » » » » » 3 months ago, # ^ |   0 Yeah I am practicing good problems you idiot
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0
•  » » » » 3 months ago, # ^ |   0 I love chromate00.
 » 3 months ago, # |   +75 The round will be rated for all the participants with rating strictly less than 2100. Due to CFR #829 (as you know, the round ends 30min before this round), it seems not clear enough.According to this comment, the round will be rated for all the participants with rating strictly less than 2100 right before CFR #829 starts, and the order of rating calculation is #829 $\rightarrow$ #830 right? (Let's make it well-defined like the problem statements so that to avoid needless troubles!)
 » 3 months ago, # |   +30 there are two contests on the same day! why?
•  » » 3 months ago, # ^ |   +27 Both rounds are based on on-site contests, so they have to be the same day due to on-site contests being the same day.
 » 3 months ago, # |   0 As a tester who has not yet had time to participate in the test, the current number of upvotes is 74, orzorzorz.
 » 3 months ago, # |   +39 Feels like those high school exam days where you take Paper 1 and Paper 2 with 30 mins break between each other
•  » » 3 months ago, # ^ |   0 Are you talking about IB exams?
 » 3 months ago, # | ← Rev. 2 →   +3 As a tester, I want to get valeriu's attention.
 » 3 months ago, # |   0 At least one contest could be at usual time on that day.
 » 3 months ago, # |   +3 Two contests one after another [DIV2] :)
 » 3 months ago, # |   +13 It's like participating in ICPC but with a 30 min break. Nice way to prepare for ICPC orz
 » 3 months ago, # |   0 India vs Pakistan (cry emoji)
•  » » 3 months ago, # ^ |   +1 Literally. Would have been great if they would have shifted at-least one of the two contest during the normal 8:05 pm IST(Hope emoji)
•  » » 3 months ago, # ^ |   0 Missed it!! (cry emoji)
 » 3 months ago, # |   +39 JEE Advanced vibes.
•  » » 3 months ago, # ^ |   0 These old days :)
 » 3 months ago, # |   0 It gives me board exam vibes!! Paper 1 & 2 exam on the same day with 30 minutes gap. Best of luck everyone.
 » 3 months ago, # |   0 no way, two rounds in a row
 » 3 months ago, # |   -6
 » 3 months ago, # |   0 The judger will be so happy during the triple system test:)
 » 3 months ago, # |   0 two contests in a day sounds interesting..
 » 3 months ago, # | ← Rev. 2 →   +3 Please note that this contest doesn't start at a usual time. And there is also a contest (#829) on the same day.
 » 3 months ago, # |   +10 Hoping to cross 2100! Good luck!
•  » » 3 months ago, # ^ |   +10 I hope to cross 1600 and become expert! Good luck for you too!
•  » » » 3 months ago, # ^ |   +1 I hope to cross 1400. Good luck to you too
•  » » » » 3 months ago, # ^ |   +1 I hope to cross 1200. Good luck everyone
 » 3 months ago, # |   +1 Finally, I can Fall down 2 times a day!
•  » » 3 months ago, # ^ |   +14 Sir You can also say that I can go up 2 times a day
 » 3 months ago, # |   0 I can't take part in the contest because I must go to school tomorrow.I'm very sad.
•  » » 3 months ago, # ^ |   +7 School on Sunday!!!!
 » 3 months ago, # |   0 Consicutive two contest! Wasn't it better if second contest will postpone between 23rd and 29th October?
 » 3 months ago, # |   -14 pls shift one contest by 8 pm other wise we will miss india vs pakistan match fully
 » 3 months ago, # |   +2 Hope to become specialist by doing this contest.
•  » » 3 months ago, # ^ |   0 Salute to your account
 » 3 months ago, # |   +14 Question: what if I show a 2100-crossing performance during the earlier Round #829 and then participate in this Round #830? Will #830 get unrated for me after #829 rating adjustments?
•  » » 3 months ago, # ^ |   0 Carry in post "rated for all the participants with rating strictly less than 2100 before Sunday, October 23, 2022 at ***"
•  » » » 3 months ago, # ^ |   0 So I think you will rating for both matches anyway
•  » » 3 months ago, # ^ |   +12 2100-crossing performance indeed :) Spoiler
 » 3 months ago, # |   +7 From 3 contests on 3 consecutive days to 3 contest in 1 day, codeforces has gone wild :)
 » 3 months ago, # |   +5 As a tester, my 4th goal this year was achieved.
•  » » 3 months ago, # ^ |   +13 orzorzorz, you are the only Japanese among my friends on codeforces. Hope we can become good friends in the future.
 » 3 months ago, # |   0 how can we register 830 now? I cannot find it in contest
•  » » 3 months ago, # ^ |   +3 use this
•  » » » 3 months ago, # ^ |   0 Thanks! I just missed the complete list button on my phone somehow.
 » 3 months ago, # | ← Rev. 2 →   0 If my rating become more than 2100 after I take part in the round 829 and then I take part in round 830,will my rating be calculated based on the rating lower than 2100 or more than 2100?
 » 3 months ago, # |   +10 Score Distribution?
•  » » 3 months ago, # ^ |   0 Shortly before round
 » 3 months ago, # | ← Rev. 2 →   +20 CodeForces using largest common prefix as title for common contests? It went incorrect for today's contests. Needs to be fixed Seems Good
 » 3 months ago, # |   +1 The most balanced round I have ever seen, grats!
 » 3 months ago, # | ← Rev. 4 →   +18 POV: YOU'VE TAKEN PART IN THE SANEST ROUND ON CODEFORCES EVER.
 » 3 months ago, # |   0 How to solve c1?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +21 Consider what happens if we remove any element $a_i$ from the subsegment. The sum will reduce by $a_i$. The bits that are on in $a_i$ will be flipped in the XOR. The best case is that the xor reduces by $a_i$, which happens when all the bits in $a_i$ are on in the XOR. So the value of $f(l, r)$ can never be increased by removing elements, only the size of the subsegment can be reduced. C2s solution involves using this to realize the optimal solution will remove at most $\log(max(a))$ non-zero elements from each side since each element must disable at least 1 bit in the XOR. So you can solve it in $O(n \log^2(max(a)))$.I'm not actually sure what the partial solution for C1 uses, maybe fixing each possible left end and binary searching on the right end?
•  » » » 3 months ago, # ^ |   +3 fixing each possible left end and binary searching on the right end? Yes
 » 3 months ago, # |   +5 Why does trying only the first 30 non-zero elements from each side WA (177636235), but 60 gets AC (177636753)? Shouldn't it be the max number of bits in a_i (i.e, 30) since any position contributes a non-negative amount to f(l, r), so we can only remove each bit at least once without reducing the max value.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Picking first 31 non-zero elements is the optimum, not 30 elements.
 » 3 months ago, # |   0 By number of solves, C1/D1 must be something very obvious. Absolutely lost any shape:)
 » 3 months ago, # | ← Rev. 2 →   +3 Felt silly writing a DFS solution for problem A after being stuck for a while but at least it passed lol 177632733
•  » » 3 months ago, # ^ |   0 i've implemented sparse table xd
 » 3 months ago, # |   0 What is the intended solution to B? I bricked on it for way too long before just coding the overkill dp.
•  » » 3 months ago, # ^ |   0 1111000000111100 can be written as 1010 (size == 4)and the answer is just size-1.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 1111000000111100 can be written as 1010 (size == 4) [ It will always be of the form 0101010.... or 10101010..... ]The reason why we can convert this string to this form is that you will never apply a operation on the same group, example 11001100 if you apply operation on index 0, then it will be 00110011. If you apply operation on index 1, then it will be 01001100. But see that it is unnecessary as you can directly apply the next operation on index 2 and not on index 1 after applying operation on index 0. Once we transform string, We are supposed to iterate on this 1010(example taken from above) and when you notice 1st '1' the answer will be remaining length because we need to invert the remaining. Since this is '1' next will be '0', so you will apply operation on that '0' which will make it '1' and next of it will be changed from '1' to '0' so you have to keep on applying the operation remaining length timesExample 10 answer is 101 answer is 00101 answer is 21010 answer is 3
•  » » 3 months ago, # ^ |   +3 My solution greedily flipped the first block of 1s it found while iterating and kept a variable for if everything was "flipped" or notExample:10011 01100 (flipped = true, find next block of flipped 1s)00011 (flipped = false)2 in total#177620466
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 Dont know about the intended solution but mine was something like this. You can break the string into blocks as follows: (000..000111...1)[][][] where [] can contain either 0s or 1s. Till the end of (000..000111...1) we dont do anything then count the number of [] blocks. The answer is this count. The intuition was that no matter what you will have to perform atleast 1 operation to flip a block []. Can you tell me your dp solution?
•  » » 3 months ago, # ^ |   0 ans = number of alternating 0's and 1's starting from 1st one from the left
 » 3 months ago, # |   0 What was the process for D1? I got stuck thinking about k-mex because it felt like it would time out no matter what lol.
•  » » 3 months ago, # ^ |   0 maybe just a brute force
•  » » 3 months ago, # ^ |   0 Mine passed the pretests, but Im skeptical about the system testing. Until the final moment before submitting was not sure if it will pass or not.
•  » » 3 months ago, # ^ |   +3 My solution that passed pretests was just to memoize answers since the answer for a query can never reduce unless elements are deleted from the set. So next time we can just check from the memoized multiple.I think this probably becomes $O(q \log q)$ or something similar which is good enough to get AC, thought I didn't bother analyzing it properly, I just guessed it was something simple looking at the solve count.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +4 UPD: Sorry it was wrong
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 I did it similarly, for a given K stored the k-mex in a map. Next time if K came up then set k-mex = max(mapped value of K, next largest multiple of k less than the current smallest non-negative element not present), and stored this in the map. But how is the complexity coming up to be O(q*logq) can you explain that?
•  » » » » 3 months ago, # ^ | ← Rev. 4 →   0 Edit: Deleted.
•  » » » » » 3 months ago, # ^ |   0 During the contest, it was the q/2 case that I was the most worried about because I was also using sets and map. Im glad the logic came out to be correct and it got accepted. Thanks a lot for the detailed explanation !!!!
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   +3 Can you explain why the $k$-mex is updated at most $q / k$ times for each $k$? If we have alternating inserts and queries of the form $+ k, ? k, + 2k, ? k, + 3k, ? k, \dots$, we are updating the $k$-mex $q / 2$ times instead of at most $q / k$.
•  » » » » » » 3 months ago, # ^ |   0 You're right. The proof is incorrect. I believe the bound is correct though, and we need a more complicated argument. I'll think more and try to post a correct proof soon. But yeah, it's clear that the lower bound holds.
•  » » » » » » » 3 months ago, # ^ |   0 Have you found the correct proof yet?
•  » » » » » » » » 3 months ago, # ^ |   0 No, sorry. I spent several hours on it and typed at least three times my ideas, but then they failed. I am happy to post some ideas here if you are interested.
•  » » » » » » » » 3 months ago, # ^ |   +6 I have asked a group theorist (really smart guy). Hopefully, we'll get a proof (or a counter example) soon.
•  » » » 3 months ago, # ^ |   0 Oh, I was definitely overthinking it then. Need to not be blind during contests lol
 » 3 months ago, # |   +3 Time limit exceeded on pretest 18, What can I say?won't use unordered_map any more
 » 3 months ago, # |   +9 ABD-forces
•  » » 3 months ago, # ^ |   +4 TBH BAD-forces. Not "bad", but based on the number of submissions xD
 » 3 months ago, # |   -8 In C, how to handle bits that are present in exactly 3 elements? Or if there is no need to handle them separately at all?
 » 3 months ago, # |   0 How to solve D1? By the looks of it seemed like some kind of precomputation as there were strictly no removals??
 » 3 months ago, # |   +2 Spent 30 minutes on A debugging code when I realized my function to calculate if $gcd$ of an array is equal to $1$ looks like this: `int f(int n, vector a) { int ans=a[0]; for(int i=1; i
 » 3 months ago, # |   0 How to not be blind during contest? Even though ai = 0 is given in sample of both C1 and C2 but I still ignored and wasted too long .
•  » » 3 months ago, # ^ |   0 Ffff i forgot that too
 » 3 months ago, # |   0 Sad
 » 3 months ago, # |   +10 I don't really understand why memorized brute force for D1 run so quickly.Can anybody prove the time complexity?
•  » » 3 months ago, # ^ | ← Rev. 4 →   -10 Cause if you iterated too much to calculate the answer, it means you added the element just as many times.Total "for loop" of all queries "?" executes asymptotically around the same number of times as addition of the elements with "+" (maybe by log times better)Not a strict proof but intuition thoughIt reminds of range(0, n, 1) + range(0, n, 2) + range(0, n, 3) and this is supposed to be bound to n log nProbably it is possible to build strict proof around this
•  » » 3 months ago, # ^ | ← Rev. 2 →   -10 I think it is to do with the number of divisors.Since $k|x$ and $\dfrac xk\le2\times 10^5$ i.e. $k\ge\dfrac x {2\times10^5}$, I guess the number of $k$ which satisfy these conditions is about $1000$.
•  » » 3 months ago, # ^ |   -10 Your value of memoized answer will change only when you insert the memoized answer in set. So the maximum number of times your answer pointer will move in all queries is O(q)
•  » » 3 months ago, # ^ | ← Rev. 2 →   -8 Edit: Deleted.
 » 3 months ago, # |   -16 everyone downvote me please i got into a challange to reache -100 contribution.LMAO:)
 » 3 months ago, # |   +5 A day well spent
 » 3 months ago, # |   +9 The C1 is so intresting! Though I haven't solved it in contest,I really love it .
 » 3 months ago, # |   +4 Can't complain as this round was based on an Olympiad, but would suggest to have fairly easier problem A in upcoming rounds so that all the actual participants are involved in rating calculation.
•  » » 3 months ago, # ^ |   0 B < A without a doubt. And I suppose a considerable amount of newbies notice the term "GCD" in the question and just abandon.
 » 3 months ago, # | ← Rev. 2 →   +1 codeforces not geometryforces not mathforces not sleepforces not speedforces
 » 3 months ago, # |   +5 Is the rating going to be calculated based on my rating after round 829 or before it?
 » 3 months ago, # |   0 Stuckforces
 » 3 months ago, # | ← Rev. 2 →   0 This contest went well for me but first one was disaster for me ,feeling very frustrated, feeling like my career & dream is getting finished ,very sad,cp was something that I loved and it gave me some worth when started but seems like things are not going anywhere now
•  » » 3 months ago, # ^ |   0 It happens sometimes man, just hold in there. Hope it gets better for you :)
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 people can have bad contests but the level of inconsistency that I am showing is detrimental, in first contest I did 800 perf and in the second 1600 ;the difference is 2 times, and this has been for long and I think the way I am performing and practicing I am not doing justice to my talent and I am certainly much more than just a cyan ;and my level of skill won't create any real impact or threat in national contests which is frightening; but yes as I can't give up I should quickly find ways to do well in national level & cf
•  » » 3 months ago, # ^ |   0 Same bro #829 is not that good for me but #830 is fine
•  » » 3 months ago, # ^ |   0 Well, for me a well performed contest may just mean I'm lucky. And many ups and downs of my ratings actually reflect my true level. Maybe you should focus more on what you learned from every contest rather than the ratings.
 » 3 months ago, # |   +1 This round is great.when will be rating change.before rating change becomes quickly than now.i'm looking forward to rating change
 » 3 months ago, # |   0 FSTed , sad TaT.The pretest of div1B is too weak...Problems are great , especially div1D
•  » » 3 months ago, # ^ |   -8 Ehrm, this is #830, which had Div.2 only. Maybe you are looking for #829 instead?
•  » » » 3 months ago, # ^ |   0 Ohh sorry I post it at wrong place. But how can I delete it?
•  » » » » 3 months ago, # ^ |   -8 It's fine (for now), Codeforces doesn't support deleting comments more than 3 minutes ago, so unfortunately you cant delete the comment
 » 3 months ago, # |   +23
 » 3 months ago, # | ← Rev. 2 →   0 this contest is good
 » 3 months ago, # |   0 E limit too tight, got -18 and AC during contest
 » 3 months ago, # |   0 good luck everybody!!! i think this contest will awesome. Hopefully I will reach cyan??
 » 2 months ago, # |   0 Minor thing: for D, when it says k-MEX is the minimum nonnegative integer, then doesn't 0 work for a lot of the test cases provided?