### NemanjaSo2005's blog

By NemanjaSo2005, history, 9 months ago,

Hello, Codeforces!

Riblji_Keksic and I are glad to invite you to Codeforces Round 911 (Div. 2), which will start on Nov/26/2023 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.

The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially.

All problems are invented and prepared by Riblji_Keksic and me.

Special thanks go to n0sk1ll and TimDee for their great work during the testing process of the round.

And of course, I would love to thank the people who made this round possible:

We hope that you will participate and enjoy the round!

Update 1: The score distribution is 500 — 1000 — 1250 — 2000 — 2250 — 3000

Update 2: Congratulations to the winners:

Div. 2:

All participants:

First solvers:

A. people_plus_plus in 0:01

B. A_G in 0:04

C. WLZ in 0:04

D. A_G in 0:12

E. Superposition in 0:17

F. turmax in 0:26

Update 3: Editorial

• +338

 » 9 months ago, # |   +139 Codeforces Round 911 whats your emergency?
•  » » 9 months ago, # ^ |   +88 My Rating is dead.
•  » » » 9 months ago, # ^ |   -7 Can you explain more, why is your rating dead?
•  » » 9 months ago, # ^ |   0 I got stuck o B, please help!!
•  » » » 9 months ago, # ^ |   0 When you think of the parity of numbers, there are three distinct situations that can be easily proven. 1) If all three numbers are either odd or even, then the answer will be 1 1 1.2) If two of the numbers are even and the other one is odd, then the answer will be the odd number.3) If two of the numbers are odd and the other one is even, then the answer will be the even number.
•  » » » » 9 months ago, # ^ |   -14 Yeah thanks I already solve it, just joking
•  » » » » 9 months ago, # ^ |   0 for a = 1, b = 3, c = 7 can you tell stepwise how can I achieve all numbers as 1
•  » » » » » 9 months ago, # ^ |   0 Erase 2 and 3 three times and write 1 each time. Then you have 4 1s, no 2s, and 4 3s. Now use the following procedure: erase 1 and 3, writing 2. Then erase 2 and 3, and write 1. This decreases the number of 3s by 2, and doesn't change the number of 1s. Do this twice, and you have 4 1s and nothing else.
•  » » » » » » 9 months ago, # ^ |   0 Ohk got it, I was stuck on the approach that I would need sufficient number of 1s beforehand to make number of 2s and 3s equal didn't consider the 1s which are generating. Thank you.
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 1,3,7 notice that if the other two of the numbers are the same you can always get the answer for A 1 3 7 -> 2 2 6 > 3 1 5 > 2 2 4 > 3 1 3 > 2 2 2More generally, the strategy is to alternate increasing the the one we are picking and the minimum of the other 2 numbers until the third number decreases and reaches the other number. So if we are picking A and b < c, we alternate between A and B until b=c.
•  » » » » 9 months ago, # ^ |   0 thanks
•  » » » 9 months ago, # ^ |   0 Since, 1^2^3 = 0, after any operation you cannot change the xor. So if xor != 0, then only xor can be achieved, it can be achieved by doing n-1 operations. Otherwise, all can be achieved by the following operations, let's say you want xor to be 1, then if 2 and 3 exists then do operation on them, otherwise do it on 1 and other existing number. This will ensure that at least one 1 exists in array after any operations.
•  » » 9 months ago, # ^ |   +3 my laptop is on fire send the firefighters
•  » » 9 months ago, # ^ |   +3 Just a small thing, sir!
 » 9 months ago, # |   +46 Definitely a round I enjoyed testing! NemanjaSo2005 Riblji_Keksic orz
•  » » 9 months ago, # ^ |   0 Hope we'll enjoy the round.
 » 9 months ago, # |   +9 Canon round.
•  » » 9 months ago, # ^ |   0 become specialist in this one, canon event
•  » » » 9 months ago, # ^ |   0 let's see who becomes specialist first
•  » » » » 9 months ago, # ^ |   0 challenge accepted!
•  » » » » 7 months ago, # ^ |   0 You won! 😅, wanna race to Expert now?
•  » » » » » 7 months ago, # ^ |   0 Yes Let's race to expert next!!!
 » 9 months ago, # |   +10 As a tester,the problemset is dramatic.Hope you enjoy it :)
•  » » 9 months ago, # ^ |   0 Thanks, But i think is about how dramatic is => how enjoyable the contest ARE?
•  » » 9 months ago, # ^ |   0 RIP
 » 9 months ago, # |   +46 Yet another Serbian round?orz
 » 9 months ago, # |   +5 Hope I can reach the specialist again in this round.
 » 9 months ago, # |   +31 THE BESTEST IN THE WORLD EVER 100% SERBIAN ROUND
 » 9 months ago, # |   +4 Back to back div2s every day let's go
 » 9 months ago, # |   +8 As a tester, the problems are exciting!
 » 9 months ago, # |   -59 It is the first time for that guy to prepare a contest, I am a little worried ...
•  » » 9 months ago, # ^ |   +15 You can talk when you become master.
•  » » » 9 months ago, # ^ |   +37 It is the first time for that guy to prepare a contest, I am a little worried ...
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   +21 It is the first time for that guy to prepare a contest, I am a little worried ...Jokes aside, yes, it is the first contest for both of us. We don't have much experience, so round will definitely have some flaws. But please provide us feedback after the contest so that we can improve in the future.
•  » » » » » 9 months ago, # ^ |   +70 My comment was directed towards TimDee, bullying someone based on rating.I hope everything goes well with the round. Don't worry about it.
•  » » » » » » 9 months ago, # ^ |   +3 Yeah, I got that. The point of my comment was to say that even I am a bit nervous about the round, but yeah, hopefully everything will go good.
•  » » » » » » » 9 months ago, # ^ |   -9 haahah
•  » » » » » » » » 9 months ago, # ^ |   -9 hahahahahahaha
•  » » » » » » » » » 9 months ago, # ^ |   -8 hahahahahah
•  » » » » » » » 9 months ago, # ^ |   0 Your contest was awesome. Problem C was a great introduction for me (an absolute beginner) to DFS. I learned something new today. Your effort is greatly appreciated, thank you!
•  » » » 9 months ago, # ^ |   +23 Does being master guarantee being a good problem setter?
•  » » 9 months ago, # ^ |   +20 When did Nemanja or I gain the reputation of being "that guy"?
 » 9 months ago, # |   +9 Good luck for everyone! ;)
 » 9 months ago, # |   +57 As a tester, NemanjaSo2005 Riblji_Keksic orz for preparing amazing problemset!
•  » » 9 months ago, # ^ |   +28 As a tester, NemanjaSo2005 Riblji_Keksic orz for being Serbian!
 » 9 months ago, # |   0 I love this contest marathon we've ended up having! ;)
 » 9 months ago, # |   0 as an arab, I cant wait for this round
 » 9 months ago, # | ← Rev. 2 →   0 I wish...this round became a better one (enjoyable) than previous all..!
 » 9 months ago, # |   +7 3 rounds in 3 days wrooom!!!
•  » » 9 months ago, # ^ |   0 Contestants with aot profile pictures have +200% chance to have positive delta on the rounds I author.
•  » » » 9 months ago, # ^ |   +9 what about clowns?
•  » » » 9 months ago, # ^ |   +8 It has been proven to be true! rating++
 » 9 months ago, # |   0 Another serb round???
 » 9 months ago, # |   0 Good luck everyone ^_^
 » 9 months ago, # |   0 911 R.I.P
 » 9 months ago, # |   +29 A 911 contest on 26/11 ? The numbers are too heavy to be considered a coincidence
•  » » 9 months ago, # ^ |   0
 » 9 months ago, # |   +7 Division 1 participants can participate :
 » 9 months ago, # |   0 Hoping to reach pupil today
•  » » 9 months ago, # ^ |   0 same here
 » 9 months ago, # |   +6 30000 score problem, nice!
•  » » 9 months ago, # ^ |   +33 Yeah, it is actually NP hard, so if you solve it you prove P=NP.
 » 9 months ago, # |   +3 am i seeing it correctly, or the score distribution for problem F really is 30,000(bang).
•  » » 9 months ago, # ^ |   0 Thanks for pointing it out. I corrected it.
 » 9 months ago, # |   +17 NemanjaSo2005 best problem setter!!
 » 9 months ago, # |   -7 Fun fact : $\text{E + F} > \text{A + B + C + D}$.
•  » » 9 months ago, # ^ |   +31 rainboy round :(
•  » » 9 months ago, # ^ |   +10 Seems like F > A + B + C + D + E
 » 9 months ago, # |   -18 Can someone tell me whats the job of testers, if you need to correct the problem statement, text case explanation by a big margin in contest time? This is disgusting.
•  » » 9 months ago, # ^ |   0 We made just small changes to make problem more understandable. If you knew what problem A was originally you would understand what testers are for.
 » 9 months ago, # |   +11 Keksic left on seen ......Me: Us bro us
 » 9 months ago, # |   -11 If I knew more algorithms/ theory about Number theory could have got D, the main idea is so obvious
•  » » 9 months ago, # ^ |   +20 In which way exactly it is obvious for you if you do not know the theory? Can you please explain the "obvious main idea?"
•  » » » 9 months ago, # ^ |   -10 GCD convolution. A similar problem was asked a few time ago: https://mirror.codeforces.com/contest/1884/problem/D
•  » » » » 9 months ago, # ^ |   +18 Sure, the trick involved is similar. Note that the problem (and solution) isn't similar, you can't call two problems using same trick or algorithm or data structure similar. (By the same logic, every binary search problem is simillr?) Also note that problem doesn't require you to brainlessly find number of pairs having GCD equal to i, also maybe look up the author solution and see that it's different as well (but yes, problem can be reduced to 1884D trick, that's how I solved it during testing, still that knowledge only helped me to know how to find number of pairs with fixed gcd, not to solve the problem.)In sfarsit, vreau sa spun ca Nila Ucsepop m-a dezamagit cu faptul ca nu a luat aur la Stelele Matematicii.
•  » » » » » 8 months ago, # ^ |   -8 Is there any specific name of this trick ? I want to learn , just curious.
•  » » » » » » 8 months ago, # ^ |   +8 Not sure about exact name, but it's one of ways to do PIE here so read about it.
•  » » » » » » » 8 months ago, # ^ |   -8 Actually I found nothing on google about PIE.. Is there any full form of PIE.
•  » » » » » » » » 8 months ago, # ^ |   +5 Inclusion-Exclusion Principle
 » 9 months ago, # |   +6 queueueuueueueueueueforces
 » 9 months ago, # |   +3 SpeedForces
 » 9 months ago, # |   0 QUEUE!!! ANY TIME EXTENDED?
 » 9 months ago, # |   +7 I will keep trying to solve div2 problems :) I hope one day I will overcome the obstacles
•  » » 8 months ago, # ^ |   0 omg penguin in your avatar looks so much like me:P
•  » » » 8 months ago, # ^ |   0 grey penguins fighting !!!
 » 9 months ago, # |   0 Problem B is a nice application of the classical puzzle: A shop sells 1 chocolate at $1. you can exchange 3 wrappers for 1 chocolate. if you have $15, how many chocolates can you get? Problem C is a gentle introduction to Tree DP (although arguably you could remove the DP array and deal directly with DFS return value instead).
•  » » 9 months ago, # ^ |   0 How is b related to that puzzle?
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 If you have $(x, \ y, \ target)$, assuming $x \leq y$, then you could first convert it to $(0, \ y - x, \ target + x)$. Then, for each $(y - x)/2$ chocolate of the middle kind, you utilize one chocolate from the end to convert it to $(1, \ y - x - 1, \ target + x - 1)$. Hence, we need at least $(y - x)/2$ chocolates of the third kind for this to be possible. The catch (in this problem, as well as in the puzzle) is that you don't have to directly check $(y - x)/2 > target + x$, since chocolates/wrappers are generated on the fly, so you could utilize the generated ones as well.Submission
•  » » » » 9 months ago, # ^ |   0 For this question it is always possible if the other 2 have the same parity. The logic for that is you can keep going back and forth until the other 2 are the same value.
 » 9 months ago, # |   +11 D is too hard for me :(
 » 9 months ago, # |   +4 This is almost the same as B
 » 9 months ago, # |   +2 How to solve D?
 » 9 months ago, # |   0 Why my this solution for problem C is giving TLE — https://ideone.com/uV3iX5can someone pls help
•  » » 9 months ago, # ^ |   +10 Per-leaf approaches can die vs. trees shaped like long-handled brooms. Your early-out will only work if the earlier answers are better than the ones that come afterwards. Otherwise, it's possible to get stuck traversing the treetrunk/broomhandle repeatedly as you improve your overall answer for each leaf.To avoid this, you can use the return/post portion of a dfs, or you can do a full topological sort. Basically you want to avoid repeatedly processing vertices, but you also want to make sure a vertex is processed after all of its children.
•  » » » 9 months ago, # ^ |   0 Thanks for your reply. Means the only approach that will work is dfs? Or in my approach can any optimisation be done to pass?
•  » » » » 9 months ago, # ^ |   0 I said 'can' not 'have to' -- but the options I listed fit the problem pretty well.If you really want to start with only the leaves, you'd still have to track whether or not all children have been processed yet, maybe punting a current node to the back of the queue if not... which leads to an opportunity for sadness: even if you shuffle the queue order, a tree shaped like a wide comb with short teeth will mean you're going to have a lot of vertices getting punted as they wait for the ones on the end to get processed...
•  » » » » » 9 months ago, # ^ | ← Rev. 5 →   0 Got accepted with the same code with pruning. https://mirror.codeforces.com/contest/1900/submission/234642669
 » 9 months ago, # |   +3 How to solve D?
•  » » 9 months ago, # ^ |   0 How to optimise O(n^2) solution is the better question
•  » » » 9 months ago, # ^ |   0 I also tried my luck with that O(n^2) solution even though I was sure it would get a TLE.
 » 9 months ago, # |   +8 i liked problem C and was very satisfied by solving it.
 » 9 months ago, # |   0 How to solve B?
•  » » 9 months ago, # ^ |   0 i got stuck on this for a whole hour lol ;-;Bassically, first get the mod 2 of them, if they are all equal the answer is "1 1 1", else, the answer is the number with a different mod of the other two.sorry for bad english.why this works? i don't now, proved by AC
•  » » » 9 months ago, # ^ |   0 Note that 1 1 2 -> 1 3 -> 2. So you can always decrease the number of 1/2/3s by two.
•  » » » » 9 months ago, # ^ |   0 And when you can't decrease anymore you are at most one step away from the answer: https://mirror.codeforces.com/contest/1900/submission/234491758
•  » » » 9 months ago, # ^ |   0 If you can't prove this solution then what was your intuition behind it
•  » » » » 9 months ago, # ^ |   0 1 1 2 2 2 3 3 3 3 this 1 and three will cancel out each other which in turn will also increase count of two so now it will be2 2 2 2 2 3 3 if now i will cancel 2 and 3 then it will become 2 2 2 2 3 1 now cancel 3 and 1 2 is your answer
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 Let the total sum of all 3 numbers be X. Now if we exclude 1st number i.e X-a1. if this number modulo 2 is 0, we can remove pairs i.e two numbers from the other 2 numbers and we can get all numbers with color a1. Similarly check for other 2 numbers
•  » » 9 months ago, # ^ |   0 B was kind of tricky for me at start but the approach that i come up with while giving contest was let a,b,c be the no.'s if any two of them have diff%2==0 then other one will be marked as 1 if all three are having even diff then all will be marked as 1
•  » » 9 months ago, # ^ |   +23 i don't know if it an intended solution but u can solve it with dp: https://mirror.codeforces.com/contest/1900/submission/234459457
•  » » 9 months ago, # ^ |   0 I used a method using even/odd. I solved some test cases of my own and found out that when theres 2 evens the one that is odd is the only one that can be the result any way u solve. same if theres 2 odds. also found that it can never result in 2 of them being 1's.. and the last scenario that remains is that if all are even or odd. then its ( 1 , 1 , 1 )
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 input -> a(1) b(2) c(3)//consider aif (abs(b-c)%2 == 0) print 1 else print 0//consider bif (abs(a-c)%2 == 0) print 1 else print 0//consider cif (abs(a-b)%2 == 0) print 1 else print 0because we can tranfrom all of other two numbers to the number we consider -example we consider A1.we operate B and C to A(tranfrom B,C to A) the remaining of this operate is abs(B-C)2.we operate a remaining with A and operate again with a remaining then we get A (this operation need two remainings and we can do this until we run out the remaining)3.so if the remaining of abs(B-C) is even,array will not have a remaining. sry for bad english
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 BEST EXPLAINATION EVER :PLet's solve for digit $1$.If there is atleast one $2$ on the board, u can use that to delete one $3$ and add an extra $1$ on the board. Using this extra $1$ and one more $3$, we can create the lost $2$ back on the board. So, if u see the pattern, we can use one digit of some type (in this case digit $2$) to reduce the other type (in this case digit $3$) by $2$ in each step, so all it remains is the remainder with $2$ i.e., $c \% 2$Similarly if there is atleast one $3$ on the board, use it to reduce the $2$ to $b \% 2$.Now, that both have been reduced to their remainder with $2$, it is only possible to completely erase them if both are either $0$ or $1$ i.e., $b\%2==c\%2$.Similarly, you can do for digit $2$ and digit $3$ as well. Here is my code.
•  » » 9 months ago, # ^ |   0 no of 1 = a no of 2 = b no of 3 = cif you want to remove 2s and 3s completely you have to make b = c. This is only possible if |b-c| is even. Ex: let a = 25, b = 9, c= 19. Apply operation to 2s and 3s Five times. You would get a = 20, b = 14, c = 14. Apply operation on 2s and 3s 14 times and you will be left with only 1s. Check this with |a-c| and |a-b|.
 » 9 months ago, # |   0 Could someone please tell why I'm getting TLE? 234480936
•  » » 9 months ago, # ^ |   0 Isn't my solution at most works in O(2 * (10 ^ 7))? Shouldn't it fit in the time limit?
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Seems like the solution is OK, but implementation is brr...Maybe i am not correct, but "vector < vector > >b(100001);", " while (pow(j, 2) <= a[i])" can make your program slow.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 How can 3d vector and squaring slow the program? I mean like why?
•  » » » » » 9 months ago, # ^ |   0 easily! I am pretty sure, that if you change pow to "while (i * i < j)" it become faster.
•  » » » » » » 9 months ago, # ^ |   0 Ok, thanks, i'll try that
 » 9 months ago, # |   +4 I wonder what is the solution for D... There are a couple of thoughts on factorization, but nothing seems to fit in time limits.
 » 9 months ago, # |   +6 B > C ;)
•  » » 9 months ago, # ^ |   0 It took me ages to even understand C :/.
•  » » » 9 months ago, # ^ |   0 you just have to know how to use DFS
•  » » » » 9 months ago, # ^ |   0 gotta get better... I am decent with pattern style questions but I need to practice data structures more for some reason I always have issues implementing them with the code. also dp cant ever figure out that shit.
•  » » » » » 9 months ago, # ^ |   0 practice makes perfect
•  » » » » 9 months ago, # ^ |   0 Could anyone tell me what is wrong with my implementation? I got the wrong answer in pretest 2. I used dfs + dp. https://mirror.codeforces.com/contest/1900/submission/234485614
•  » » » » » 9 months ago, # ^ |   0 Take a look at Ticket 17164 from CF Stress for a counter example.
•  » » » » » 9 months ago, # ^ |   0 It looks like dp[] for internal nodes updated multiple times when started from different leaves.Dfs is usually walking from top to leaves calculating something along the way: https://mirror.codeforces.com/contest/1900/submission/234501347
 » 9 months ago, # |   +27 not saying it was a bad contest at all, but problem D was very similar to problem 645F(https://mirror.codeforces.com/contest/645/problem/F) such that it was the case of k=2 for that problem.
•  » » 9 months ago, # ^ |   +1 I just read it and it doesn't seem in any way similar, unless I don't know actual solution. However, i don't think that comparing the trick used in solution/solution itself is best way to describe similarity of two problems.Still, I may miss something, so could you please elaborate about what exactly they're similar in? =)
•  » » » 9 months ago, # ^ |   +26 say you have the solution of the problem for k=2.you can solve D like this: n=1 q=n-1, k=2 sort the array and give the elements of it in each query. the sum of all querys except the last one is the answer.
•  » » » » 9 months ago, # ^ |   0 Hm, right, it makes sense. Though i still don't agree that "solution to this problem can also solve this problem" makes those two similar (sometimes it can, but here it's not the case, since problems ask for different things (I mean, 645F should be heavily simplifies to arrive to today's D, like, limit K to 2, sort array, do queries adding sorted array elements ...))
•  » » » » » 9 months ago, # ^ |   +21 Anyway, thanks for your problemsetting I really enjoyed your contest.
•  » » » » » » 9 months ago, # ^ |   0 (I wasn't setter, I was tester, but still thanks for feedback :D) so I ping NemanjaSo2005 for good contest
 » 9 months ago, # |   +17 Cool problems, Thanks!!
 » 9 months ago, # |   +1 Is answer in D smaller than long long max?
•  » » 9 months ago, # ^ |   +1 Yes, I think N choose 3 < long long max
•  » » 9 months ago, # ^ | ← Rev. 3 →   +20 $\binom{80\,000}{3}\cdot100\,000\approx8.5\cdot10^{18}$$2^{63}-1\approx9.2\cdot10^{18}$
•  » » » 9 months ago, # ^ |   0 Yeah, that makes sence, Thank you. I was too nervous during contest and didn't come up with this
 » 9 months ago, # |   +24 Is $E$ following? Build condensation of graph (find strongly connected components and make them 1 vertice, the graph becomes acyclic). And then just dp on DAG to find path with greatest number of vertices (sum not the vertices in condensation, but for each vertice in condensation number of original vertices in it). (Why do we have to minimize some cost then? It doesn't change the problem)
•  » » 9 months ago, # ^ |   +8 I thought of this too. There can be multiple longest paths in a DAG
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 This method is correct, at least I have temporarily passed it1->2 1->3 2->4 3->4 There are two logest paths in a DAG 1->2->4 and 1->3->4
•  » » 9 months ago, # ^ |   +13 The graph may not necessarily be connected, therefore there might be multiple paths with the same longest length but different weights.
•  » » 9 months ago, # ^ |   0 Yes. Then you can store dp as pair {length, sum} and update it as the statement requires it.Кстати, стоимость просят минимизировать т.к. у тебя может быть более одного множества вершин формирующих путь максимальной длины и соответственно на этом и строится задача, хотя ограничение довольно искусственное, но без него задача была бы слишком стандартной наверное)
•  » » » 9 months ago, # ^ |   0 It is still very standard
•  » » » » 9 months ago, # ^ |   0 After you observe that you must condensate the graph, yes. It's not too trivial to arrive to that observation.
 » 9 months ago, # |   +21 Any hints for F?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +22 i think its something along the lines of: figuring out that at most O(logn) operations will be done on an array A do the operations on the whole array and memorize the array after every query, lets call A_k array A after k operations to solve queries [L,R], if you consider just the elements of A_1 in [L,R], lets call the array of those elements B, you can see at most 2 elements(one from the front and one from the back) should be added to B then you can just simulate the queries(smartly) only looking at the left and right boundaries and maintaining the left and right boundary in A_k that corresponds to the array that is left after simulating k operations on the array in interval [L,R] in A UPD: you will also have to add O(logn) elements to the front and the back of the array that you are maintaining in the query while simulating the operations(because some elements from the begining and the end of your query interval could have been deleted by the rest of your array)
 » 9 months ago, # |   +1 Is D mobius?
•  » » 9 months ago, # ^ |   0 I saw someone solve it with mobius, although i know nothing about it. Do I really need to know mobius to reach expert, I solved ABC in 19 minutes?
•  » » » 9 months ago, # ^ |   0 Not really it's rare, i would recommend focusing on more common topics first
•  » » 9 months ago, # ^ | ← Rev. 2 →   +11 I solved it without mobius (hopefully :)Hint: iterate over all possible GCDs
•  » » » 9 months ago, # ^ |   0 aren't there O(n^2) gcds?
•  » » » » 9 months ago, # ^ |   0 gcd is bounded by 10^5.
 » 9 months ago, # |   +61 I'm willing to bet money that problem A was inspired by Minecraft.
 » 9 months ago, # |   +41 Minecraft water logic in A, nice
 » 9 months ago, # | ← Rev. 2 →   +8 I enjoyed thinking about problems ABCD,Thanks you for the contest. by the way any hints for optimizing (n ^ 2) solution of problem D
 » 9 months ago, # |   0 Please tell me what topics I need to solve problems like D and E (also to become expert: in general) thankyou so much :3
•  » » 9 months ago, # ^ |   +5 problem D was a combination of number theory(gcd), combinatorics and inclusion-exclusion principleproblem E was a combination of graph theory(for SCC compression) and simple DP on DAG(to calculate maximum length of a path and its smallest value)
 » 9 months ago, # |   +3 Was too rusty on my Möbius reduction to solve D in time sadly :c. ABC were good, as well as E, which wasn't straight up untouchable while still proving hard!
•  » » 9 months ago, # ^ |   0 Did you end up solving it using mobius?
•  » » » 9 months ago, # ^ |   0 what is mobius?
•  » » » » 9 months ago, # ^ |   0
•  » » » » 9 months ago, # ^ |   0
•  » » » 9 months ago, # ^ |   0 In the end no, but it simplifies down to calculating this: (then subtract a thing, divide by 2 and multiply by $n$, more or less) $\Sigma^n_{i=1} \Sigma^n_{j=1} \gcd(a_i, a_j)$Which should be very similar to the last example in this blog post, but for gcd instead of lca. I couldn't wrap my head around those last transitions though.
•  » » » » 9 months ago, # ^ |   0 can you explain more please i did get to o(n ^ 2) solution but i can't understand how can i optimize it using mobius
•  » » » » » 9 months ago, # ^ |   0 I doubt I can really explain it better than the blog post I linked. There is this function $\mu$ which is multiplicative and you can use the linear sieve to calculate its values quickly, and it has this interesting property which... yeah I'll just refer to the blog post.
•  » » » » 9 months ago, # ^ |   0 There is (n-j) term here i think for instead of multiplying by n
•  » » » » » 9 months ago, # ^ |   0 The first thing is you sort the array in descending order. Then if I'm not mistaken: $$\Sigma^n_{i=1} \Sigma^n_{j=i+1} \Sigma^n_{k=j+1} f(a_i,a_j,a_k)$$ $$= \Sigma^n_{i=1} \Sigma^n_{j=i+1} \Sigma^n_{k=j+1} \gcd(a_j,a_k)$$ $$= n \cdot \Sigma^n_{j=2} \Sigma^n_{k=j+1} \gcd(a_i, a_j)$$ $$= n \cdot \frac{\Sigma^n_{j=2} \Sigma^n_{k=2} \gcd(a_i, a_j) — \Sigma^n_{i=2} \gcd(a_i,a_i)}{2}$$Sike, I am mistaken. You are right, line two $\ne$ line three.
•  » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +1 BRUHHHHHHH
•  » » 9 months ago, # ^ |   0 Do you really need that for D?
•  » » » 9 months ago, # ^ |   0 Judging by the comments here no, some people solved the problem without it
 » 9 months ago, # |   +12 Problem A is basically minecraft infinite water source.
 » 9 months ago, # |   0 please quickly upload the editorial, so that I can understand problem D
•  » » 9 months ago, # ^ |   +1 Calculating the sum of (gcd) of the two smallest numbers in all three-member subsets of a given set.
•  » » » 9 months ago, # ^ |   0 thank you for the reply, but I meant that I want to understand the solution. My bad :(
 » 9 months ago, # |   0 D is very interestring problem... i like it
 » 9 months ago, # |   +4 freaking hard D
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Problem D is pretty like to this 1884D - Counting Rhyme problem. There we should use a trick with inclusion-exclusion in dp for calculating all pairs of integers, that have fixed gcd. But these two problems are different from classical problem and we should modificate this dp.
•  » » » 9 months ago, # ^ |   0 The inclusion-exclusion principle is relatively hard for D. It took me roughly an 1.5 hour to come up with it because I forgot this idea.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +5 Unluck :(I was stucked on problem B :)))))))May be you didn't solve too many problems with different tricks(I automatically recognized this trick when I have seen the problem)
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 I am waiting for system testing to end so that I can try my D solution I solved it like 1 min after contest, and couldn't send it. :(And it gave me TLE
 » 9 months ago, # |   0 In problem C, why my code is TLE when I use dfs by recursion, and I AC when I use dfs by Stack ?Besides: My other Code use O(nlog(n)) but it's TLE : https://mirror.codeforces.com/contest/1900/submission/234458841
•  » » 9 months ago, # ^ |   0 I also had the same nlogn solution but got tle:( turns out it's not actually nlogn
•  » » 9 months ago, # ^ |   0 Pass the string s in dfs() by reference too. Solution Accepted
•  » » » 9 months ago, # ^ |   0 I'm so careless, tks! And What about my O(nlog(n)) code?
•  » » 9 months ago, # ^ |   0 I think you got a bit unlucky, pass the string by reference in dfs and you should get AC. Creating a linear copy of string in each dfs call made it $O(n^2)$.
•  » » » 9 months ago, # ^ |   0 I'm so careless, tks! And What about my O(nlog(n)) code?
•  » » » » 9 months ago, # ^ |   0 The height of the tree is not guaranteed to be $log(n)$, so worst case is again $O(n^2)$
•  » » » » » 9 months ago, # ^ |   0 In the case height of tree is n then Leave of tree is one so it's O(n), and in the case max Leave of tree is n/2 then height of tree is log(n) so it's O(nlog(n))
•  » » » » » 9 months ago, # ^ |   0 I found case my code is O(n^2):
•  » » » » » » 9 months ago, # ^ |   0 Got accepted with same approach using pruning https://mirror.codeforces.com/contest/1900/submission/234642669
 » 9 months ago, # |   +5 Feedback: In my opinion, B and C were a little too easy, and D was a little too hard. Maybe not, but the jump in difficulty from C to D was really huge for sure. Either: 1) make B,C harder or 2) make D easier (or a little bit of both). Other than that, that was a great contest, especially given that it's your guys' first time setting, good job!
•  » » 9 months ago, # ^ |   0 Agreed
 » 9 months ago, # | ← Rev. 3 →   +7 Thanks for the authors for this round ! Here is my advice about the problems (uncorrelated to my performance) AOne of the best div2 A I solved ! Simple statement, simple solution, there is an idea but it's not "random math problem with gcd in it". Btw, is it inspired from minecraft ? BVery cool problem about invariants. It is maybe a bit standardish but I think that considering the target audience of div2 B it is a great problem ! CI feel sorry for saying this but this problem is way too easy/standard in my opinion. It is an interesting educative problem but I think it's way too standard (it would probably have been fine if it was the only standard problem in the round). DI liked this problem a lot. I wanted to bash with things like mobius inversion but ended up coming up with a cool dp sol (which is apparently standard according to other comments). EFun fact: I opened the round a bit late, I wasn't planning of competing. I read E and implemented it on the spot. This problem is a very cool problem to practice strongly connected components, however I believe it might be way too standard. Again, it would've been fine if it was the only standardish problem in the round but I think that the CDE combo is not perfect :/Congratulation to the authors though, the problems were still of good quality and I appreciate the fact that AB were not left behind !!Looking forward to another round of yours :))
•  » » » 9 months ago, # ^ |   0 I explained it here. I hope it's clear enough
•  » » 9 months ago, # ^ |   0 can you tell me why this solution won't work:https://mirror.codeforces.com/contest/1900/submission/234481346
•  » » 9 months ago, # ^ |   0 Expain your DP on D
•  » » » 9 months ago, # ^ | ← Rev. 6 →   +5 First I considered the easier problem of finding the sum of $gcd(a_i,a_j)$.Let $dp[d]$ be the number of pairs having their gcd equals to $d$. Once you know all rhe $dp[d]$, the answer is just $\displaystyle\sum_d dp[d] \cdot d$.Let $M$ be the maximal value of $a_i$ (here $M = 10^5$). Notice $dp[M]$ is the number of pairs of elements that are divisible by $M$.Let's compute $dp[d]$ Assume $dp[k]$ is known for all $k > d$. We know $dp[d]$ is at most the number of pairs of elements that are both divisible by $d$. However, among these pairs, we need to remove the ones whose gcd is not $d$. Such pairs will have gcd $2 \cdot d$ or $3 \cdot d$ etc.You can use the exact same approach to solve the problem (except you are counting triplets so you should sort the array first to know how many elements are larger)Code 234513315
•  » » » » 9 months ago, # ^ |   0 Thank you, I'll study this method. My solution during round was working with complexity $O(M \cdot uv)$ where $u$ is $M^{\frac{1}{3}}$ and $v$ unknown for me, but it gladly AC.Your solution is working $O(M \cdot M^{\frac{1}{3}})$ I guess.
 » 9 months ago, # |   +7 bruh 911 contest on 26/11. it cant be a coincidence bro. https://en.wikipedia.org/wiki/2008_Mumbai_attacks https://en.wikipedia.org/wiki/September_11_attacks
•  » » 9 months ago, # ^ |   0 ☠
 » 9 months ago, # | ← Rev. 4 →   0 Thanks for the contest!
 » 9 months ago, # |   +2 Solving Backwards D-C-B-A, hope I will reach CM one day, By the way very nice problem D, and glad that I solved it in the contest itself.
•  » » 9 months ago, # ^ |   0 Can you please explain your approach for Problem D?
•  » » » 9 months ago, # ^ |   +3 Sort the array,Now for every element ai push the index i in map of the factors of ai. After completing this step for all elements, for each key in map you will get the indexes where the elements present are divisible by this particular key.Now gcd will be some number inside our keys in map.Iterate from highest keys to lowest keys , as answer for any key will also depend upon the answer for multiples of that key.=> Remember map[i][j] represents and index b/w 0-n , such that element at that index is divisible by i, formally a[map[i][j]]%i=0Particularly, dp[i] += i*j*(n-map[i][j]-1) (because for jth element in map[i], you can select any 1 element from 0 to j-1 , jth element and any 1 among n-1-map[i][j], as these 3 numbers will give you a valid tuples (ap1,ap2,ap3) whose gcd = gcd(ap1,ap2) = i.Also you have to subtract the contribution of multiples of i, as if i divides 2 numbers then it doesn't necessarily mean i will be the gcd of these 2 numbers.Hence, dp[i] -= dp[i*j]/j for all j
•  » » » » 9 months ago, # ^ | ← Rev. 5 →   +4 This is fucking amazing. Thank you for this. Edit: I paraphrased above answer a bit with better formatting.
•  » » » » » 9 months ago, # ^ |   0 Actually, compexity is $O(n \cdot A^{\frac{1}{3}})$
•  » » » » » » 8 months ago, # ^ |   0 Huh? How? Iterate factor until sqrt(A) takes $\sqrt{A}$ time, no?
•  » » » » » » » 8 months ago, # ^ |   0 We only interested in factors of number $A$, so we will iterate not in all number from $1$ to $\sqrt{A}$, but iterate in vector of factors $S$ of nubmer $A$, then $|S| \approx A^{\frac{1}{3}}$
•  » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Also check this, solution with compexity $O(A \cdot \log{A})$ https://mirror.codeforces.com/blog/entry/122677?#comment-1088299
•  » » » » 9 months ago, # ^ |   0 Thanks a lot. Just one more thing: In the last line, "$dp(i) -= dp(i*j)/j$ for all j," j is in range 2 to $\frac{\text{highestKey}}{i}$, right?
•  » » » » » 9 months ago, # ^ |   0 Yeah because after that , all the states will be zero.
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   +1 And actually for higher keys we will subtract for the factors of that higher key, and will add for them afterwardss when our loop will arrive eventually to them.
•  » » » » » » 9 months ago, # ^ |   +1 Yeah. I felt that the problem was a bit difficult to be Div2D.
•  » » » » » » » 9 months ago, # ^ |   0 Yeah maybe, it is 2000 rated as per clist.
•  » » 9 months ago, # ^ |   0 Shouldn't have solved backwards, you're sacrificing a lot of free delta from A and B
•  » » » 9 months ago, # ^ |   +1 I know, but I want to get myself accustomed to solve D in live contest, as after solving A,B,C either there isn't much time left for me or my brain becomes fucked up to think for D calmly.
•  » » » 9 months ago, # ^ |   0 damn bro, how are you improving so fast!! ;)
•  » » » » 9 months ago, # ^ |   0 Thanks!
 » 9 months ago, # |   0 Can someone who was able to solve E can explain why this won't work for E, or report any points i missed: code#include #define ll long long #define pb push_back #define rep(i,a,b) for (ll i = a; i < b; i++) #define inf 1e18+1 using namespace std; ll n; vector adj[200001]; // vector visited(200001,0); vector distance(200001,0); vector mx(200001,0); map> memo; ll a[200001]; vector visited(200001,0); pair dfs(ll u){ if (visited[u]) { return memo[u]; } visited[u] = true; ll longest = 0,mn = 0; for (auto x:adj[u]){ pair res = dfs(x); if (res.first>longest){ longest = res.first; mn = res.second; }else if(res.first==longest){ mn = min(mn,res.second); } } memo[u] = make_pair(longest+1,mn+a[u]); return memo[u]; } void solve() { ll m; cin>>n>>m; rep(i,0,n){ cin>>a[i]; } rep(i,0,m){ ll u,v;cin>>u>>v; u--;v--; adj[v].push_back(u); } ll ansd = 0,ans = 0; rep(i,0,n){ pair res = dfs(i); if (ansd> t; while (t--) { solve(); memo.clear(); fill(visited.begin(), visited.end(), false); } return 0; } 
•  » » 9 months ago, # ^ |   0 You need to consider strongly connected components. Currently you are running a dp on a graph that has cycles (well sometimes you can use dp even when you have cycles)...If you are still not convinced, try thinking about why you think your solution is correct
 » 9 months ago, # |   +2 For problem D,any particular reason we are not required to output the answer mod some prime. In the current form, the maximal answer can $nC3*max(a[i])$ which if not calculated carefully (finding the ncr part and then multiplying) can overflow.
•  » » 9 months ago, # ^ |   0
•  » » » 9 months ago, # ^ |   0 I agree with that. However if we are not careful and in the worst case where n= $8* 10^4$ with all array values as $10^5$, if we are not careful and write the code as ans=ans+(i*freq*(freq-1)*(freq-2))/6ll;  ans=ans+i*(freq*(freq-1)*(freq-2))/6ll; It can overflow. I know this is mostly my fault but still I feel that mod would have been a better option here
•  » » 9 months ago, # ^ |   0 I got FST in the last test case due to this... Also, it would have been cool if these overflow test cases were included as pre-tests.
 » 9 months ago, # |   +8 I feel like problems today were more educational than usually, you just should know the main approach for problems like these and then they're easy, otherwise really hard to come up with
 » 9 months ago, # |   +15 Nice contest. Problems were well designed and fun to solve. Thanks for the round NemanjaSo2005 Riblji_Keksic and all testers.
 » 9 months ago, # |   0 Yo it was a great contest!
 » 9 months ago, # |   -15 There was a long queue in last 10-15 minutes. Then still it's considered as rated round. Disappointed :(
•  » » 9 months ago, # ^ |   0 There is no queue lol
•  » » » 9 months ago, # ^ |   0 I submitted my last solution 11 minutes earlier of the deadline but still didn't get verdicts till the end
 » 9 months ago, # | ← Rev. 3 →   0 good contest
 » 9 months ago, # |   0 This game was very interesting, but at the beginning I treated question B as question A, thinking that question B was question A, which caused me to be stuck for 30 minutes. I finally finished writing question C before thinking about question B, so I think The difficulty of the first three questions in this game is A
 » 9 months ago, # |   0 Please tell me how you think about problem D and what is the breakthrough point?
•  » » 9 months ago, # ^ |   0 +1How to improve number theory with dp?
•  » » 9 months ago, # ^ |   0 I didn't know how to solve it with dp, but I passed it during contest.Idea is following: let $x$ be divisor of $a[i]$ ($a[i] \mod{x} = 0$). Let's $q[v]$ is the number of such $a[j] (j < i)$ that $v$ is divisor of $a[j]$. Let's iterate over all divisors $x$ of $a[i]$ and sum over $q[x]$ is the answer.
 » 9 months ago, # |   0 orz fallleaves07
 » 8 months ago, # |   0 orz
 » 8 months ago, # |   0 Task B's statment was too unclear for me
 » 8 months ago, # |   0 How did people_plus_plus solve a problem in 1 second???
•  » » 8 months ago, # ^ |   +3 I am friend of authors, they told be problem A for sure
 » 8 months ago, # |   0 Can someone Please explain why I am getting a TLE in this solution for problem C 234510811
•  » » 8 months ago, # ^ |   0 You are passing the entire string for each dfs call, which makes it O(N^2)
•  » » » 8 months ago, # ^ |   0 Thank you sir
 » 8 months ago, # |   +1 I got message from the system that my solution of C is same as other coder. my code: https://mirror.codeforces.com/contest/1900/submission/234467535 other's code: https://mirror.codeforces.com/contest/1900/submission/234459009i didnt copied anyone's code, the solution is very straightforward. Easy codes can look similar. Please remove this penalty
 » 8 months ago, # | ← Rev. 2 →   +1 I got a message from the system that my solution of C coincides with another code:Just see the difference between the coding style between those two codes. I have no idea how did this happen. I wrote a very simple solution just using BFS. i think it is normal that easy codes look similar to each other. Please reconsider this and remove my penalty.
 » 7 months ago, # | ← Rev. 4 →   0 For C what is worong  ll ans = 1e8, n;string s; ll l[maxn], r[maxn];void dfs(ll v, ll op = 0){ if (l[v] == -1 && r[v] == -1) ans = min(ans, op); if (l[v] != -1) dfs(l[v], op + (s[v] != 'L')); if (r[v] != -1) dfs(r[v], op + (s[v] != 'R')); }void run(){ cin >> n >> s; for (int i = 0 ; i < n ; i ++){ cin >> l[i] >> r[i]; l[i]--;r[i]--; } dfs(0); cout << ans << nl; }