### I_love_tigersugar's blog

By I_love_tigersugar, 11 months ago,

1255A - Changing Volume

Author: UncleGrandpa925. Prepared by UncleGrandpa925

Tutorial

1255B - Fridge Lockers

Author: prof.PVH ft. MikeMirzayanov. Prepared by UncleGrandpa925

Tutorial

1255C - League of Leesins

Author: MikeMirzayanov. Prepared by UncleGrandpa925

Tutorial

Author: Prof.PVH. Prepared by Prof.PVH

Tutorial
Source code

1254B1 - Send Boxes to Alice (Easy Version)

Author: MofK. Prepared by UncleGrandpa925

Tutorial
Source code

1254B2 - Send Boxes to Alice (Hard Version)

Author: MofK. Prepared by MofK and UncleGrandpa925

Tutorial
Source code

1254C - Point Ordering

Author: ngk. Prepared by ngk

Tutorial
Source code

1254D - Tree Queries

Author: prof.PVH Prepared by prof.PVH

Tutorial
Source code

1254E - Send Tree to Charlie

Author: MofK Prepared by: MofK

Tutorial
Source code
Tutorial of Math and Games

• +144

 » 11 months ago, # |   0 Auto comment: topic has been updated by prof.PVH (previous revision, new revision, compare).
•  » » 11 months ago, # ^ |   -40 when 601 round will be rated
 » 11 months ago, # |   -12 Why my submissions are skipped? :/
•  » » 11 months ago, # ^ |   -14 Same code was submitted by other handle.
•  » » » 11 months ago, # ^ |   0 How can I know who did it?
•  » » » » 11 months ago, # ^ |   0 cf will send an email did you use Ideone ?
 » 11 months ago, # |   -27 orz
 » 11 months ago, # |   +10 For Problem D I just sorted the adjacency list by size of the subtree (then flatten it with euler tour). That way even if nodes are heavy I can update all the subtrees in $sqrt(N)log(N)$ since it will have at most $sqrt(N)$ different value in sizes and I can update several subtrees of the same size in one single range update (because they are in one complete range in the euler tour) and you want to add the same value $\frac{1}{n}d(n-sz)$ to all of them.
•  » » 11 months ago, # ^ |   +9 Hacked. Each update for a subtree size should call only 1 Fenwick Tree update instead of 2. Or you can do this.
•  » » 11 months ago, # ^ |   0 I did the same thing and was getting TLE, but then I realized that I can optimize the worst case if I batch update queries for the same node, so if there is 1 node that has sqrt(2*n) different values, worst case will be Q/2 modifies which should reduce the constant by 2 and make it work. It now passes.https://codeforces.com/contest/1254/submission/65470890
•  » » 11 months ago, # ^ |   0 I use similar idea about different subtree size. But I also divede the queries into sqrt(Q) parts then get a O(NsqrtN) off-line algorithm: We use an array to modify the updates and calculate the presum after each part. Then for each query with type 2, we just need to calculate the updates from the queries with type 1 in the same part. For all Nsqrt(N) such pairs of queries, we sort them by dfs order using bucket sorting. Then we insert the pairs into corresponding vertex's vector, then for each vertex we calculation the values of all the queries corresponding to it one by one with the vector containing its subtrees with different size and their dfs orders, just like a merge sorting.Code:65993177
 » 11 months ago, # |   +9 prof.PVHFor editorial of Div2E2/Div1B2, shouldn't it be min(Si%k, k - Si%k) instead min(Si%k, (k-Si)%k)?And btw, anyone has the link for the markups used for blogs/comments on CodeForces?
•  » » 11 months ago, # ^ |   +9 It was fixed, thank you!
•  » » 11 months ago, # ^ |   0 does the idea of grouping k chocolates into their coordinates meridian work? I did it on contest, but got wa on pretests of E1 (but not on pretests of E2) and not sure if it is a bug or wrong solution.
•  » » » 11 months ago, # ^ |   0 I think it will work, but then the hard part here is you don't know the number of candies in each part to determine the median.
•  » » » » 11 months ago, # ^ |   +8 I did it in the contest (65365892). Basically, you just divide all candies into groups of $K$ and move each group into its median box. Just need to be careful because the number of candies at a time can exceed $K$.
•  » » » » » 8 months ago, # ^ |   +5 So E1 editorial solution can be done for E2 also with some modifications (or a lot of modifications :D). Am I right?
•  » » » » » 2 months ago, # ^ |   0 How can we prove that median will give optimal answer
 » 11 months ago, # |   0 Notice that we can map the given rectangle to an array. In other words, there exists a path in the rectangle that goes through every cell exactly once. can someone explain this part
•  » » 11 months ago, # ^ |   0 Sorry for the word choice. I have rewritten the tutorial for easier reading.
•  » » » 11 months ago, # ^ |   0 Thanks ,I get it now
 » 11 months ago, # | ← Rev. 2 →   +3 I don't understand why the round was rated for me. On what basis did you decide that the mistake in problem B did not affect me ? This mistake completely ruined my contest. I wasted 100 min in B. And when I up-solved C and D I could solve them quickly. this could have been a very good contest for me but now I lost 50 points. and yet you refuse to make round unrated
•  » » 11 months ago, # ^ |   +9 did you submit the form?
•  » » » 11 months ago, # ^ |   0 I am exactly in his position. Wasted a lot of time for b. I filled the form,but with no effect.
•  » » » » 11 months ago, # ^ |   0 Me too.
•  » » » 11 months ago, # ^ |   0 Yes. I did. and I explained in detail what happens even sent a message to MikeMirzayanov
 » 11 months ago, # | ← Rev. 4 →   +8 How I did D:Call a vertex heavy if it has more than $T$ neighbours. For updates at $u$, first update the complement of the subtree rooted at $u$. Then, if $u$ is heavy, just keep track of the update at $u$. Otherwise, update the subtrees rooted at the children of $u$. This is $O(T\log(N))$.For queries at $u$, first query the value at $u$. Then, jump upwards to the next heavy vertex until we reach the root, and update the answer with the values at these heavy vertices. This is $O(\log(N)+N/T)$. Setting $T=\sqrt{N/\log(N)}\approx93$ gives $O\left(Q\sqrt{N\log(N)}\right)$ total. Runs in under half a second on system tests but I found an input that makes it run in 2.6 seconds.(seems like a less intelligent version of this $O(N\log(N))$ solution: https://codeforces.com/blog/entry/71534?#comment-559222)
 » 11 months ago, # |   +122 An alternative solution for D. Tree Queries.It's obvious that for each "modify" operation we can spend $O(degree_x \log n)$ time naively updating the answer using BIT in the tree-dfs order. And now we can get some improvements. For each node we initially choose one of its sons of the largest size. For a "modify" we only update its father's "subtree" and the heaviest son's subtree. And for each query, we not only calculate the answer in the BIT, but also jump up to the query node's ancestors that haven't updated the query node yet and calculate the extra answer.It can be shown that there are at most $O(\log n)$ such ancestors to deal with. So the total complexity is $O((n+q) \log n)$, with quite a small constant.Code: 65403262
•  » » 11 months ago, # ^ |   +26 Beautiful solution!
 » 11 months ago, # |   +8 My solution to Tree Queries: For a set of updates, we can easily calculate their contributions to each node in $O(n)$ time -- for each node $u$ we get the sum of $d$ of all operations that $v=u$, then iterate all neighbours of $u$. Since we do not need to support online query, the updates can be done with difference in linear complexity. Also it's easy to tell an update's contribution to a specific node $u$: we just need to get the size of the subtree of $u$ when we root at $v$. This can be done in $O(n\log n) - O(1)$ complexity. We calculate the contribution to each node every $\sqrt n$ operations, and when query on a node we consider the latest $\sqrt n$ updates' contribution to it. This works in $O(n\log n+n\sqrt n)$ time.
 » 11 months ago, # |   0 Can someone explain in Div2E2, how can we assume that if we are taking k-S[i]%k from i+1 th element then it will not become negative ( does it have enough candy to give). The author has said something related to this doubt as 'S[i]>S[i+1]'. Can someone give an intuitive proof of th this. Thanks in advance.
•  » » 4 months ago, # ^ |   0 lucifer_1502 Did you get it? If yes, then can you please explain? I've spent 4hrs on this problem, but couldn't come to a conclusion.
 » 11 months ago, # | ← Rev. 6 →   0 In div2 E1 or (div1 B1) how to prove that maximum number of divisors of a number less than 10^5 is 240 (It is given in editorial but no proof has been provided) .Thanks !
•  » » 11 months ago, # ^ |   +10 Hi. To prove that, you can either factorise all intergers from $1$ to $10^5$ to count the number of divisors it has, or just google search for the list of highly composite numbers. For estimation purposes, the number of divisors a number $n$ has is about $O(n^{1/3})$
 » 11 months ago, # |   +8 In problem B1, it suffices to iterate through only the prime divisors (taking as k) of the total number of chocolates.
•  » » 11 months ago, # ^ |   0 Absolutely
 » 11 months ago, # |   0 Can anyone explain this for me :"A number ≤10^5 has at most 240 divisors". I tried to create number that can have most divisors but all I found was 128 divisors (120120). Thanks in advance.
•  » » 11 months ago, # ^ |   +1 So that's why they said "at most" XD... Moreover 120120 is greater than 10^5 XD...
•  » » 11 months ago, # ^ |   +1 I checked... it's actually 83160 with 128 factors.
•  » » » 11 months ago, # ^ |   0 okay, got it, thanks!
•  » » » 11 months ago, # ^ |   0 In div2 E1 or (div1 B1) how to prove that maximum number of divisors of a number less than 10^5 is 240 (It is given in editorial but no proof has been provided) ?
•  » » 11 months ago, # ^ |   +1 Sorry, it is in 83160 with 128 divisors. I mistook this problem for the original problem(which has a constraint of 1e6)
•  » » » 11 months ago, # ^ |   0 thanks, but I still wonder how to get maximum number of divisors for number with value that does not exceed some specified boundary.
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   +1 Please see my comment above. There also exists a way of backtracking. You just need to backtrack for a sequence of $k_1, k_2,...k_n$ such that $(k_1+1)*(k_2+1)*...*(k_n+1)$ is maximum, ${p_1}^{k_1}*{p_2}^{k_2}*...*{p_n}^{k_n}$ $\le N$ and $k_1 \ge k_2 \ge k_3 ... \ge k_n$ But on practical I think referring to the highly-composite number list is a more convenient way
•  » » » » » 11 months ago, # ^ |   0 thanks, I will note it for later use.
 » 11 months ago, # |   0 @prof.PVHpls explain this..STATEMENT : "Now it is clear that we will divide the array into segments, such that sum of each segment is divisible by K, and move all the chocolates pieces in that segment into one common box."lets say my input array is : [ 6 7 9 7 6 7 7 ] now the sum of the array is 49 ... and optimal divisor(k) for this array would be 7 ... Why do I need to move all the candies into common box ?we can see that we need to pass one candy from index '2' to index '0' and one candy from index '2' to index '4'... and that would 4 seconds... and we are not moving all the candies to any common box..so can please explain that statement
•  » » 11 months ago, # ^ |   +3 That statement is about the easy version, where each element is 0 or 1.
•  » » » 11 months ago, # ^ |   0 sam721I realised that I after posting the comment :p ... my bad, I opened both questions, and I thougth I was reading E1, but I was actually reading the E2 :p .
 » 11 months ago, # |   0 I still don't understand tutorial for feeding chicken? Does anyone have better explanation?
•  » » 11 months ago, # ^ |   0 You can solve the 1xn problem assigning equal or almost equal quantities of rice fields to each chicken, for example, if there are 32 rice fields and 6 chickens, you go 6, 6, 5, 5, 5, 5, giving the non-rice fields in between the rice fields to the corresponding chicken.Now "cut" and "stretch" the original rectangle into one long strip or array of 1x(r*c). You can do that in several ways, like zig-zag, spiral, etc, and solve like above.
•  » » » 11 months ago, # ^ |   0 I guess the hardest trick for me was to understand that it doesn't matter how many fields belong to one chicken. It is all about rice per chicken.Zig Zag was another trick.
 » 11 months ago, # |   0 There is a way that cost $O((n+q)\log n)$ for problem D.Here it is.
 » 11 months ago, # |   0 please help me in solving problem B1 SEND BOXES TO ALICE(EASY VERSION). it's giving me wrong ans in test case 7...
 » 11 months ago, # |   +10 Problem E2 is very nice ! Thank you!
 » 11 months ago, # |   +10 Div2 Task E2 is awesome.
 » 10 months ago, # |   0 fridge locker is completely a case of circular rotation
 » 8 months ago, # |   +3 In problem E2, is there a proof (or at least help me understand) for this fortunately true statement : " The only concern is that: is there any scenario when there exists some i such that $S_i > S_{i+1}$, which is indeed a violation? Fortunately, the answer is no. ".? Thanks <3.
•  » » 4 months ago, # ^ |   0 _LNHTD_ Did you get it? If yes, then can you please explain? I've spent 4hrs on this problem, but couldn't come to a conclusion.
 » 6 months ago, # | ← Rev. 3 →   0 Div2. E2/ Div1. B2:"But if you have solved the problem to this phase already, you can easily realize that we only need to consider prime k, because if k is composite then picking any prime divisors of it will lead to either a better result or an equal result."Why and how?UPD: Understood. If all $a_i$ are to be made divisible by some composite say p*q (p and q are primes), then they are also made to be divisible by p and q, at (in the worst case) the same cost. So it is sufficient to only consider the primes (as they guarantee an equal, if not better, answer).
•  » » 4 months ago, # ^ |   0 Can you please explain in Div2E2, how can we assume that if we are taking k-S[i]%k from i+1 th element then it will not become negative ( does it have enough candy to give). The author has said something related to this doubt as 'S[i]>S[i+1]'. Can you give an intuitive proof of this? Thanks in advance.I've already spent hours but couldn't get to any conclusion. the_hyp0cr1t3
•  » » » 4 months ago, # ^ |   0 If $S_i \% k \le (k - S_i \% k)$, then it is optimal to move $S_i \% k$ chocolates from $S_i$ to $S_{i+1}$.Otherwise $(k - S_i \% k) < S_i \% k$. It is optimal to move $(k - S_i \% k)$ chocolates from $S_{i+1}$ to $S_i$. We know that $S_{i+1} \geq S_i$, so there are at least $S_i \% k$ chocolates in $S_{i+1}$. And $(k - S_i \% k) < S_i \% k$. So there are always enough.
•  » » » » 4 months ago, # ^ |   0 the_hyp0cr1t3 I tried to prove it this way, I do not understand where am I getting wrong
•  » » » » 4 months ago, # ^ |   0 How does Si+1>=Si implies that there are at least Si%k chocolates in Si+1?
•  » » » » » 4 months ago, # ^ |   0 $S_i$ has at least $S_i \% k$ chocolates, so $S_{i+1}$ also has at least that many.
•  » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Si+1 is greater than Si%k but how can we prove that it is greater than Si+k-Si%k because will be taking chocolates out of ai+1 i.e. si+1-si?
 » 5 months ago, # |   0 In Div1 B1 why moving all the ones to $temp[(i+i+p-1)/2]$ is optimal than to moving ones to $(temp[i]+temp[i+p-1])/2$ ??
 » 4 months ago, # |   0 Hi, MofK, question regarding following statements:The only concern is that: is there any scenario when there exists some i such that Si>Si+1, which is indeed a violation?Since S[i]=sum(a[0]..a[i]), thus S[i+1]-S[i]=a[i+1]. If S[i]>S[i+1], then a[i+1]=S[i+1]-S[i]<0. To my understanding, all a[i], either before or after any operation, should be positive. If I were correct, then there should be no case that S[i]>S[i+1].Anything I am missing here?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 happy15 But how do we make sure that ai+1 will remain positive after the most optimum choice of operation for that case when Si%k>k/2
 » 4 months ago, # |   0 We can enforce the solution to iterate each Si from 1 to n−1 and always choose to decrease if there is a tieIn fact, even if we choose to increase for every tie, we can enforce a non-decreasing sequence. We just have to fix and follow it.
•  » » 4 months ago, # ^ |   0 Can you please explain in Div2E2, how can we assume that if we are taking k-S[i]%k from i+1 th element then it will not become negative ( does it have enough candy to give). The author has said something related to this doubt as 'S[i]>S[i+1]'. Can you give an intuitive proof of this? I've already spent hours but couldn't get to any conclusion. Thanks in advance. mshiladityam
 » 4 months ago, # | ← Rev. 2 →   0 I am getting WA on test case 7 for the problem 1254B1 - Send Boxes to Alice (Easy Version), the code seems to be logically correct to me, where am I getting wrong?: 86285300UPD: Fixed