DmitryGrigorev's blog

By DmitryGrigorev, history, 3 years ago, translation,

(Idea of the problem Div2A — ScreaMood)

(Developer of the problem Div2A — DmitryGrigorev)

Code

(Idea of the problem Div2B — kirillbogatiy)

(Developer of the problem Div2B — DmitryGrigorev)

Code

(Idea of the problem Div1A — Mr.Hakimov)

(Developer of the problem Div1A — Mr.Hakimov)

Code

(Idea of the problem Div1B — DmitryGrigorev)

(Developer of the problem Div1B — PeregudovSergey)

Code

(Idea of the problem Div1C — ----------)

(Developer of the problem Div1C — ----------)

Code

(Idea of the problem Div1D — DmitryGrigorev)

(Developers of the problem Div1D — ---------- и DmitryGrigorev)

Code

Read this comment of saketh about another approach for this problem.

(Idea of the problem Div1E — DmitryGrigorev)

(Developer of the problem Div1E — TheWayISteppedOutTheCar)

Code

• +105

 » 3 years ago, # | ← Rev. 2 →   +10 For Div1 D can someone help me prove/disprove how is this strategy working: For any node L to get minimum sum we choose two children u and v such that dp[u]-2*n*sz[u] and dp[v]-2*n*sz[v] are smallest among all the children? My code: 55909246
•  » » 3 years ago, # ^ |   +5 I'm not sure about your strategy. But I find that the complexity of your code can be reduced into O(n) by using bubble sort to obtain the minimum and second minimum value.
•  » » 3 years ago, # ^ |   0 I support the question.
•  » » 3 years ago, # ^ |   +8 It looks like your code also fails on saketh's test case here.Correct answer is 1019. Your code outputs 1018.
•  » » » 3 years ago, # ^ |   +8 Here's the input:35 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 19 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I just ran my code on this example. Its giving correct output- 1019 https://ideone.com/UAyyqj
•  » » » » 3 years ago, # ^ |   +10 Interesting. I guess the order of input data matters. We need the degree three vertex to be the root. Input I used35 1 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 1 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 1 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35https://ideone.com/kPEg0m
 » 3 years ago, # | ← Rev. 2 →   +3 Thanks for the great editorial!I have a question about Div1C editorial. In definition of x, isn't it supposed to be the maximum x (instead of minimal) that satisfies the mentioned condition?If I'm wrong, can you please tell me why?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 But money isn't a problem at all for Serge, so Serge is buying the most expensive dish if there is at least one remaining. There is a typo in the editorial. Also if you check editorials source code for that problem, you will see that it finds maximal X.
 » 3 years ago, # |   +53 In D, we only need to consider the two best dp values for each unique subtree size. With that observation, there's no need for CHT: we can just check all pairs quadratically and it will still be fast enough.
•  » » 3 years ago, # ^ |   0 Sorry for my not understanding…… But doesn't it have a complexity of $O(n^2)$ when facing a graph that each vertex has an edge to the same vertex?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +8 At each node, it’s quadratic in the number of distinct child subtree sizes. Your tree has a node with many children, but they have only one distinct subtree size.
•  » » 3 years ago, # ^ |   0 I had the same idea. This clearly takes O(n sqrt n) but I'm wondering if there's a tighter bound.
•  » » » 3 years ago, # ^ | ← Rev. 4 →   +18 I think it's way faster than that, like $n \log \log n$. Credit due to dinosaurs and danielfleischman.Suppose $f(n)$ is an upper bound on work done on a tree with $n$ nodes. We need $f(n) \geq k^2 + \sum_i { a_i \cdot f(i) }$ for any $a_i$ where $\sum_i a_i \cdot i = n - 1$ and $a_i$ has $k$ non-zero elements.Let's write $f(n)$ as $n \cdot g(n)$, and let's rewrite $\sum_i { a_i \cdot f(i) }$ as $\sum_{i < \sqrt{n}} { a_i \cdot i \cdot g(i) } + \sum_{i \geq \sqrt{n}} { a_i \cdot i \cdot g(i) }$.The first sum is at most $\sum_{i < \sqrt{n}} { a_i \cdot i \cdot g(\sqrt{n}) }$ which is at most $n \cdot g(\sqrt{n})$. The second sum is at most $\sum_{i \geq \sqrt{n}} { a_i \cdot i \cdot g(n) }$ which is at most $\sqrt{n} \cdot g(n)$.$^\dagger$Finally, $k^2 \leq 2\sqrt{n}$. So $f(n) \geq k^2 + \sum_i { a_i \cdot f(i) }$ becomes $n \cdot g(n) \geq 4n + n \cdot g(\sqrt{n}) + \sqrt{n} \cdot g(n)$.Dividing by $n$ gives $g(n) \geq 4 + g(\sqrt{n}) + g(n)/\sqrt{n}$. $g(n) = 4\log \log n$ satisfies it for sufficiently large $n$.$\dagger$ The root of a tree on $n$ nodes cannot have more than $\sqrt{n}$ child subtrees each with at least $\sqrt{n}$ nodes.
•  » » » » 3 years ago, # ^ |   +18 I think that $n \log \log n$ is also the worst case. We can construct a tree with a structure similar to the Sqrt-tree in which each node with subtree size $x$ has $O \left ( \sqrt{x} \right )$ children with distinct subtree sizes of at least $O \left ( \sqrt{x} \right )$. There will be at least $O \left ( \log \log n \right )$ layers that take $O \left ( n \right )$ time each.
•  » » » » 3 years ago, # ^ |   +20 Could you explain why $\sum_{i \geq \sqrt{n}} { a_i \cdot i \cdot g(n) }$ is at most $\sqrt{n} \cdot g(n)$ with more detail? For example, what if the node has only one child whose size is $n-1$ ?
•  » » » » » 3 years ago, # ^ |   0 I am wrong, sorry. Do you see how to fix it?
•  » » » » » » 3 years ago, # ^ |   +10 I don't know how to fix it either. A progress is that there exists a worst case in which $a_i \in \lbrace 0,1\rbrace$. Proof: First observe that $f(a+b) \geq f(a)+f(b)$. Let $m$ be the largest number which satisfies $a_m > 0$. If there exists an $a_i >1$, it doesn't take less time to let $a_i=a_i-1, a_m=a_m-1,a_{i+m}=a_{i+m}+1$(after this operation, $m$ becomes $i+m$).And I wrote a dp program which runs in $O(n^{2.5})$ to calculate the worst time. When n=500, the worst time is about 2700 operations. When n=5000, the worst time is about 31000 operations. It seems the time complexity is really something like $O(n \log \log n)$ or $O(n \log n)$.
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +10 If we assume that $f(n)$ is convex, it means that $f(x-1)+f(y+1) \ge f(x)+f(y)$ where $x \le y$. Following from this convex property and $a_i \in \lbrace 0,1\rbrace$, there is a worst case such the sizes of the children of any node with subtree size $n$ are $1, 2, 3, ..., k, n-1-\frac{k(k+1)}{2}$. Consider the heavy path from any node with subtree size $n$ to a leaf. Whenever we do $O \left( k^2 \right)$ work and move down to the heavy child, the size of the subtree decreases by $O \left( k^2 \right)$, so the total work of this heavy path is $O(n)$.Each time a node changes the heavy path it's on while moving to the root, the subtree size will be squared, so each node will be included in $O(\log \log n)$ heavy paths. It follows that the time complexity is $O(n \log \log n)$.
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 3 →   +10 Good proof!We can prove $f(n)$ is convex as follows, i.e. $f(n+1)-f(n) \geq f(n)-f(n-1)$.If $f(n)$ is convex when $n \leq k$, then it can be proved that $f(n) \leq c \cdot n \log \log n+d(n \leq k+1)$ using your proof. Just let $f(n)=n \log \log (n)$ since the constants $c,d$ make no sense(by now) and $f$ represents the upper bound. We only need to prove $g(x)=x \log \log x - (x-1) \log \log (x-1)$ is an increasing function.Though $g$ isn't always increasing, it's increasing when $x > 10$. We can assign some constants to $f(x) (x \leq 10)$ to ensure $f(x)$ is convex when $x \leq 10$. Then we add a proper constant $d$ to $f(x) (10 •  » » 3 years ago, # ^ | +10 Oh, we knew this solution but we thought its something like$n^{\frac{3}{2}}$. Great thanks to you for this comment. •  » » 3 years ago, # ^ | 0 I am struggling to even see the correctness. Can you please give me some details?  » 3 years ago, # | 0 DmitryGrigorev for div 1 c what you mean by the line.. "Now to find the answer we can use a segment tree that maintains a balance between the number of dishes and the number of pupils for all suffices of values"which segment tree to use what balance we need to mantain. what to add in segment tree?. can you explain this more. •  » » 3 years ago, # ^ | 0 Sort all pupils and dishes with value, add them from big to small, dishes are$+1$, pupils are$-1$, the answer is the maximal$k$that sum of$[k,1000000] > 0\$.
•  » » » 3 years ago, # ^ |   0 But how to find this maximal k? What to store in nodes?
•  » » » » 3 years ago, # ^ |   +1 Use segment tree to count the maximum suffix sum.
•  » » » » » 3 years ago, # ^ |   0 And check every suffix? It'll be comething like O(n log n). Or maybe there is more efficient algo? Can you help me plz?
 » 3 years ago, # | ← Rev. 2 →   0 sir , my approach was same for question 1180b , but it failed at 9 th pretest .. reason was the big product value. i used 'long long int ' and i am not aware of any data type bigger than that. i solved using c language . please help ,how to overcome that.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/contest/1180/submission/55892852here is my solution ,see 9th test
•  » » » 3 years ago, # ^ |   0 C++ can't handle big integer using inbuilt data type, at max i saw int128 something, so instead u can deal with logarithm of numbers and operation performed will be addition .even if u implement in python for handling big integers,it will rise tle,i guess.
•  » » » 3 years ago, # ^ |   0 You don't need to calculate the product, just work out its sign. This is easy, since after the loop all the ais are negative (if x>= 0 then |-x-1| > |x|). As such the product is negative if and only if n is odd.
 » 3 years ago, # | ← Rev. 2 →   0 sir , i got the same approach in 1179b ,but was confused to think about the case in which case is not possible and we need to print -1 there ..... by this algo even if some points repeat , it will be very hard to keep on check on each point visited and will further will take a long time ,resulting in TLE ...... can you please give me an example where we cant visits all cell block and hence -1 prints .... thank you;
•  » » 3 years ago, # ^ |   0 we never will print -1 because we always have a way which is mentioned above to visit the all cell block.
•  » » » 3 years ago, # ^ |   0 ohh, i wasted alot of time thinking that where will we use -1 ,even though i got basic algo concept of it within two minute . so i didn't attempted that at last. very sad.
 » 3 years ago, # |   -8 What is CHT?
•  » » 3 years ago, # ^ |   0 where i have written CHT ??? or its a general question?
•  » » » 3 years ago, # ^ |   0 It's a general question.Would you please tell me what CHT is?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +8 no bro , i too heard it first time... it sounds like a technique or algo ,dont knowedit got this on wiki == https://en.wikipedia.org/wiki/Circle_Hough_Transform
•  » » » » » 3 years ago, # ^ |   0 Hahaha I agree with quachtridat. CHT is Convex Hull Trick. Idk how you got that link, but maybe reading it a bit would tell you "Image processing" is not something you would think of here.
•  » » » » 3 years ago, # ^ |   +3 I think it is "Convex Hull Trick."
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I would like to point out here, to editorialist, that it would be appreciated not to use short forms in tutorial/explanation so that people who don't know about it don't get further confused with something else. Even if you don't write the full form in the paragraph, maybe mention at the end, like below. If you let's say talk about CHT, and DSU.Here ( just example )CHT means Convex Hull Trick.DSU means Disjoint Set Union, etc
•  » » » 3 years ago, # ^ |   +3 To me it is not hard to get the acronyms provided that they are aforementioned in a short paragraph, because I got that CHT thing by quickly skimming through the tutorial for 1179D again when I saw his comment, but that is probably just me though :|Also I think it is just as good to write a word's acronym right after itself, like "Convex Hull Trick (CHT)."
 » 3 years ago, # |   +1 In DIV2 problem B why is the following statement required: "if (n != 3 || (v[0] != -3 || v[1] != -3 || v[2] != 2))"Even without this line the code is being ACCEPTED.submission
•  » » 3 years ago, # ^ |   0 Didn't you answer your own question? If it is accepted then the statement is not required ( this is true, assuming tests are not weak ). And I can assure you, tests are not weak. A lot of people had submissions fail on system tests. To properly answer your question, No, that line is not required. Another tip: instead of trying to understand code provided, it is a better practice to read the explanation and try to write the code yourself.
•  » » » 3 years ago, # ^ |   0 Oh, I see. And thanks for the tip, I'll keep it in mind from now.
 » 3 years ago, # |   +3 " Now to find the answer we can use a segment tree that maintains a balance between the number of dishes and the number of pupils for all suffices of values. " What do they mean by maintaining balance and suffices of values? In div1 C.
 » 3 years ago, # |   0 Can someone please help me in fixing my code , it passed 8 pretests but blowed up on 9th onethe link of the code is given below https://codeforces.com/contest/1180/submission/55891316
•  » » 3 years ago, # ^ |   0 Try this: 5 -3 -3 1 1 -1I think you need to use operation on minimum element (not abs min) when n%2==1 my acc output: 2 -3 -2 -2 -1 your: -3 -3 -2 1 -1 In second and third tests all values equals after using operation on non-negative elements and it's not important what element changed.(sorry for my english)
 » 3 years ago, # |   +1 Nice editorial.
 » 3 years ago, # |   0 Maybe in problem A for di2 you mean O(1)?
•  » » 3 years ago, # ^ |   0 Although the editorial code calculates it in O(1), it’s still possible to calculate it in O(n).
•  » » » 3 years ago, # ^ |   0 Hey, can you help me in understanding the function used in editorial code? How did he got that?
•  » » » » 3 years ago, # ^ |   0 You can calculate the answer for small values of n by hand (draw a picture) and look for a pattern.
 » 3 years ago, # |   0 I think solution of Problem B of DIV 2 (1180B) is wrong. Because it's written that if the product is already positive, it's the answer. Else to apply the operation to the minimal number is obviously optimal. But I got the solution accepted when I applied the operation to the maximal number in the array and found it more sensible. Am I right here ? if not please correct me.
•  » » 3 years ago, # ^ |   0 Yes it's the minimal number In your code you chose the minimal number too PS: The minimal number is the maximum after taking absolute values of all
•  » » » 3 years ago, # ^ |   0 I think I understood the meaning of Minimal as the smallest number in an array. Now I understood the solution. Thanks!
•  » » 3 years ago, # ^ |   0 Author solutions means, that you should do all numbers maximum on modulo (because abs(-a-1) > abs(a)). And if we have even count of numbers, which are maximum on modulo it is the answer.(because — * — = +). But if count of numbers is not even we sholud find minimum of these negative integers, and we will do maximum positive integer. Maybe you mean find maximum on modulo?
 » 3 years ago, # | ← Rev. 2 →   +6 In case you're looking for a proof/ intuition behind why the approach in 1180B — Nick and Array — works, here is some food for thought:When n is odd, increasing the magnitude of all the elements will leave us with a negative product because of odd number of negatives.. So we have to apply the transformation on one of the elements again -- which will make the product positive again.Let's just concentrate on the magnitude of numbers - we have a series of numbers to multiply — a1 * a2 * a3 * ... an — we have to decrease the magnitude of one of these by 1. Which element do you pick? — You pick the one with the highest magnitude Why does this work? we have to maximize (a1 * a2 * a3 * ... an) -- so we can think of it as maximizing the sum of their logarithms — (log|a1| + log|a2| + log|a3| + .. log|an|) .. Because of how log function "straightens out", the decrease in log value will be the least when |ai| is the highest -- we are looking further right on the log graph — that's why you choose the one with the highest magnitude and decrease it
•  » » 3 years ago, # ^ |   0 Great to see how you put it in logarithms.I did pick the lowest element (in magnitude) at first smh, but later found out a test that invalidated my solution.
 » 3 years ago, # |   0 In Div. 2 E/Div. 1 C, shouldn't it be the maximum x instead of the minimum?
 » 3 years ago, # | ← Rev. 4 →   0 In div1B, the coordinates can be expressed as one dimension，that is i,j=x*m+(y-1). The jump is i->j->i... for all i-j and j-i are different, the algorithm is proved. My code:55987211
 » 3 years ago, # |   +8 For div1 C it is not written anywhere that people will leave after buying one dish so it is possible that people buy other dishes with remaining money but the solutions accepted doesnt seem to handle these cases for example- 2 1 99 1 1 1 2 1 100 for this testcase answer should be -1 but output is coming 1 can someone explain how??
 » 3 years ago, # |   -9 https://codeforces.com/contest/1180/submission/56009139 Any idea why I am getting TLE for 1180B?
•  » » 3 years ago, # ^ |   0 Why downvote?
•  » » » 3 years ago, # ^ |   0 Aah did a silly mistake in gettings values into a[n]. Damn.
 » 3 years ago, # |   0 Why I got TLE in the problem DIV2 D when I use endl but got AC in the '\n'? TLE Submission: https://codeforces.com/contest/1180/submission/56012176 AC submission: https://codeforces.com/contest/1180/submission/56012511
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 When you use endl, it is basically the same as '\n' but it also flushes cout and thus works a little bit slower. In fact, this optimization is usually pretty useless, in this problem replacing long long with int was enough.
•  » » » 3 years ago, # ^ |   0 Thank you.
 » 3 years ago, # | ← Rev. 3 →   0 In problem C-Div1, shouldn't the answer be "maximum" x which satisfies the condition that the number of dishes with cost ≥x is strictly more than the number of pupils who have more than x togrogs?
 » 3 years ago, # | ← Rev. 3 →   0 The std of Div1 D prints 180 while my program prints 181 when inputting this data onto them:152 13 24 25 46 37 18 69 110 911 212 1113 1114 415 2When we connect node 8 and node 10, we can get a better answer 181.So is there a bug in std? Or have I misunderstood the problem?My submission: http://codeforces.com/contest/1179/submission/56058316(By the way, the data are so weak that both my code and std accepted the problem...)
 » 3 years ago, # |   0 Can anybody explains the idea behind how segment tree is used to solve this problem https://codeforces.com/contest/1180/problem/E? From the editorial its not clear.
 » 3 years ago, # |   0 can somebody help me with the following code: https://codeforces.com/contest/1180/submission/56155460
•  » » 3 years ago, # ^ |   0 Your declaration takes a very huge amount of memory, namely. ll a[101001111]; `This is a (long long) array of 101001111 elements of 64-bit size. The amount is approximately: 101001111 * 64 / (8 * 1024 * 1024) ~ 770.58 MB, which is larger than 256 MB allowed in the problem statement.
 » 3 years ago, # |   0 i still didn't understand div 2 B why aren't we considering the fact that pos nos are even or odd??because on converting odd no of postive integer we will end up with negative product. pls reply
•  » » 3 years ago, # ^ |   0 I find this approach to be easier and intuitive. First you need to convert all elements to non negative integer that is either zero or positives. Now you just need to sort the array and then make elements negative pairwise so that you can get maximum product at the end. If your array length is odd then you don't need to add any condition you just need to leave the last element as it will handle itself the maximum product. For example if your array is -2 -4 -1 0 0 1 2 3 then after converting them to non negatives it becomes 1 3 0 0 0 1 2 3 now after sorting and making the elements pairwise negative you will get 0 0 0 1 1 2 3 3 --> -1 -1 -1 -2 -2 -3 -4 -4 now you can restore your array order by sorting it with index for that you can store it in pair.
 » 3 years ago, # |   0 Can someone please explain div2 A editorial? I am not able to understand the sequence given in the editorial code.
 » 3 years ago, # | ← Rev. 2 →   0 Div1D problem statement not clear. and how is the no of simple paths for11 22we cannot get a simple path of len>=2 max it could be 1 as its only one pair of vertices.
 » 3 years ago, # |   0 For Problem D, Div. 1, from what I understood they say that dp[L] = min(dp[p1] + dp[p2] + (n — szp1 — szp2) ^ 2). I agree with that, but then they say that we get n^2 + dp[p1] − 2⋅n⋅szp1 + dp[p2] − 2⋅n⋅szp2 + 2⋅szp1⋅szp2. Shouldn't it be n^2 + dp[p1] − 2⋅n⋅szp1 + dp[p2] − 2⋅n⋅szp2 + 2⋅szp1⋅szp2 + szp1^2 + szp2^2?
 » 3 years ago, # |   0 For Div2 B can someone help me in telling the basic idea of the problem and how will we achieve the strategy discussed in the tutorials
 » 3 years ago, # | ← Rev. 2 →   0 Can someone help me for 2nd question . I have used the same approach but still not getting anshttps://codeforces.com/contest/1180/submission/57356003
»
3 years ago, # |
0

Can anyone tell my how do I modify my code for problem Tolik and His Uncle? Here is my code:

include<bits/stdc++.h>

using namespace std;

int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n,m; cin>>n>>m; int top,base; top=1;base=n; while(top<=base) { if(top<base) { for(int i=1;i<=m;i++) { cout<<top<<" "<<i<<endl; cout<<base<<" "<<m-i+1<<endl; } } else { int cnt=0; for(int i=1;i<=m;i++) { if(i%2) { cout<<top<<" "<<++cnt<<endl; } else cout<<top<<" "<<m-cnt+1<<endl; } } top++;base--; } }

•  » » 3 years ago, # ^ |   0 I got a TLE. Thanks.
 » 3 years ago, # |   0 In div1D, what is the meaning of the sum A, B and C? Thanks in advance
 » 2 years ago, # |   0 in div2C i was getting MLE bcz i was using deque but same logic using vector works fine enough can anyone plz explain why this is so
 » 16 months ago, # |   0 Well i spent almost 2 hours on problem B(Nick and Array). Nice and tricky problem anyway!!!