### komendart's blog

By komendart, history, 6 years ago, translation,

Someday I will arrange C and D correctly :)

675A - Infinite Sequence

Firstly, in case c = 0 we should output YES if a = b else answer is NO.

If b belongs to sequence b = a + k * c where k is non-negative integer.

So answer is YES if (b - a) / c is non-negative integer else answer is NO.

Code

675B - Restoring Painting

x a y

b m c

z d w

Number in the center may be any from 1 to n because number in the center belongs to all subsquares 2 × 2. So, let's find answer with fixed number in the center and then multiply answer by n.

Let's iterate over all possible x. Sums of each subsquare 2 × 2 are the same so x + b + a + m = y + c + a + m and y = x + b - c.

Similarly, z = x + a - d and w = a + y - d = z + b - c.

This square is legal if 1 ≤ y, z, w ≤ n. We should just check it.

Also we can solve this problem in O(1).

Code

675C - Money Transfers

We have array ai and should make all numbers in it be equal to zero with minimal number of operations. Sum of all ai equals to zero.

We can divide array into parts of consecutive elements with zero sum. If part has length l we can use all pairs of neighbours in operations and make all numbers be equal to zero with l - 1 operations.

So, if we sum number of operations in each part we get ans = n - k where k is number of parts. We should maximize k to get the optimal answer.

One of the part consists of some prefix and probably some suffix. Each of other parts is subarray of a.

Let's calculate prefix sums. Each part has zero sum so prefix sums before each part-subarray are the same.

So we can calculate f — number of occurencies of the most frequent number in prefix sums and answer will be equal to n - f.

Bonus: how to hack solutions with overflow?

Code

675D - Tree Construction

We have binary search tree (BST) and should insert number in it with good time complexity.

Let we should add number x. Find numbers l < x < r which were added earlier, l is maximal possible, r is minimal possible (all will be similar if only one of this numbers exists). We can find them for example with std::set and upper_bound in C++.

We should keep sorted tree traversal (it's property of BST). So x must be right child of vertex with l or left child of vertex with r.

Let l hasn't right child and r hasn't left child. Hence lowest common ancestor (lca) of l and r doesn't equal to l or r. So lca is between l and r in tree traversal. But it's impossible because l is maximal possible and r is minimal possible. So l has right child or r has left child and we know exactly which of them will be parent of x.

That's all. Time complexity is .

Code

675E - Trains and Statistic

Let the indexation will be from zero. So we should subtract one from all ai. Also let an - 1 = n - 1.

dpi is sum of shortests pathes from i to i + 1... n - 1.

dpn - 1 = 0

dpi = dpm - (ai - m) + n - i - 1 where m belongs to range from i + 1 to ai and am is maximal. We can find m with segment tree or binary indexed tree or sparse table.

Now answer equals to sum of all dpi.

Code

• +110

 » 6 years ago, # |   +31 Lightning fast editorial. Respect mate.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +27 And better yet, lightning fast system testing. It's 4:00 JST, and I would've woken up a lot more to see if I passed systests.
•  » » » 6 years ago, # ^ |   +3 Systests are done already?! Blessup
 » 6 years ago, # |   +6 What is the idea for solving B in O(1)?
•  » » 6 years ago, # ^ |   +5 when comparing x,y,z,w, we can determine which are the smallest and largest, and determine the difference (more important). If the difference is d, than there can be only (n-d) variations for x,y,z,w
•  » » » 6 years ago, # ^ | ← Rev. 6 →   +3 Thanks! It turns out I used that exact idea, but I still managed to mess up and had O(N) code as in the following. n, a, b, c, d = map(int, input().split()) lo = min(a+b, a+c, c+d, b+d) hi = max(a+b, a+c, c+d, b+d) ans = 0 for x in range(1, n+1): ans += max(0, n-hi+lo) #n-(hi-lo) print(ans)facepalm intensifies
•  » » » » 6 years ago, # ^ |   -8 diff=hi-lo ans=n*(n-diff) //try this O(1)
•  » » 6 years ago, # ^ |   -19 I found an interesting solution that scales easily to bigger problems: long long n,a,b,c,d,x; cin >> n >> a >> b >> c >> d; f.push_back(a+b); f.push_back(a+c); f.push_back(b+d); f.push_back(c+d); sort(f.begin(), f.end()); x = f[3] - f[0]; cout << n * max(0ll, n - x); 
•  » » » 6 years ago, # ^ |   0 Thank you my friends :)
•  » » » 13 months ago, # ^ |   0 good.I solved the problem like this too.
•  » » 6 years ago, # ^ |   0
•  » » 20 months ago, # ^ | ← Rev. 5 →   0 I did it in this way. 1. #include using namespace std; int main(){ long long int n,a,b,c,d; cin >> n >> a >> b >> c >> d; long long maxi = abs(abs(a-d)+abs(b-c)); long long int ans = (long long int)(n*(n-maxi)); cout << max(0LL, ans); }
 » 6 years ago, # | ← Rev. 2 →   +34 For problem E, can anyone explain why such dp works? Or how to prove such dp is correct? Sorry for my bad English :)
•  » » 6 years ago, # ^ |   +19 We want to calculate distance from i to j. If j < a[i] then distance is 1. Otherways, it is optimal to move to cell with maximal a[i] (to maximize our range at next step). That is, distance[i][j] = distance[m][j] + 1, where m is cell with maximal a[i].
•  » » » 6 years ago, # ^ |   0 Finally understand. Many thanks!
•  » » » 6 years ago, # ^ |   0 We can simply take minimal dpm+m instead of maximal a[i]. But why it is optimal to move to cell with maximal a[i]?
•  » » » » 6 years ago, # ^ |   +3 Choosing the maximal a[i] do not mean we must go to it after this move; it means that there are more positions to choose when we go next (as we can choose any position between i+1 and a[i]). The more choices we have, the better solution we may get.
•  » » » » » 6 years ago, # ^ |   0 "The more choices we have, the better solution we may get". Here we are making a greedy move. What is the intution/logic/proof behind it?
•  » » » » » » 6 years ago, # ^ |   0 That is to say, getting more choices won't make the answer worse. You can choose not to follow this choices, but the answer won't be worse than when we have fewer choices.
•  » » » 6 years ago, # ^ |   0 Na2a You said that we have to maximize our range at next step, so why isn't it optimal to move to a cell with maximal (a[i] + i) ?
•  » » » » 6 years ago, # ^ |   +6 Because range of jump is [i, a[i]] not [i, i + a[i]].
•  » » » » » 6 years ago, # ^ |   0 Oh silly question! Thanks!
 » 6 years ago, # | ← Rev. 3 →   -11 B: "Let's iterate over all possible x"How can it be O(1) after this?
•  » » 6 years ago, # ^ |   +3 He said "Also we can solve this problem in O(1)." So above was O(n) solution, but it could be done for O(1).
•  » » » 6 years ago, # ^ |   +1 Thank you, it's clear now :))
•  » » 6 years ago, # ^ | ← Rev. 4 →   +4 The O(1) solution is mentioned but not actually given. You can use the following formula, n·(max(0, n - max(a + b, a + c, c + d, b + d) + min(a + b, a + c, c + d, b + d))). Proof is left as an exercise to the reader, of course. B-)
•  » » » 6 years ago, # ^ |   0 can u please elaborate it with example.i am not getting the logic behind it. thanks in advance.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +4 Consider only the four unknown corners of the 3 × 3 box. Note that if any one corner's value is known, the values of the other three corners are fixed. Without worrying about the condition that the 2 × 2 boxes have the same sum, there are n possible sets of values for the four corners (read the previous sentence).However, say you have n = 5, a = 1, b = 1, c = 2, d = 2. If the bottom-right corner has value 5, the top-left corner must have value 7 for the top-left and bottom-right 2 × 2 boxes to have the same sum. Thus, the number of possible sets of values for the four corners is at most n - greatest_difference_among_{a + b, b + d, c + d, a + c}. This is because these are the fixed values such that if one corner's value is determined, there is only one possibility for the other three corners based on a, b, c and d.Now consider case n = 1, a = 1, b = 1, c = 2, d = 2. In this case, n < greatest_difference_among_{a + b, b + d, c + d, a + c}. Thus, the difference cannot be compensated for regardless of what four values of n you choose for the four corners. Finally, the total number of sets of values for the corners is max(0, n - greatest_difference_among_{a + b, b + d, c + d, a + c}),  or max(0, n - (max(a + b, b + d, c + d, a + c) - min(a + b, b + d, c + d, a + c))) which is the same as my original comment, max(0, n - max(a + b, b + d, c + d, a + c) + min(a + b, b + d, c + d, a + c)).
•  » » » » 6 years ago, # ^ |   0 There is some minimum value for x (let's call it xmin), such that all the remaining variables y, z, w become valid (that is, they are in the range [1..n]). There is also maximum value xmax that still holds y, z and w in the valid range. The trick is to understand that for all the values in between xmin and xmax we can always make the triple y, z, w valid. If xmin = 5 and xmax = 9 then x = 6, x = 7, x = 8 are also valid (we don't need to check them explicitly).
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 You can check my O(1) submission: http://codeforces.com/contest/675/submission/17948800Basically, the intuition is that e.g. for the top two 2x2 squares, since a and m are common, we get: x + b = y + c => y = x + b — c. Analogously, z = x + a — d, w = x + a + b — c — d. We want 1 <= x,y,z,w <= n and thus:1 <= x <= n1 <= y <= n -> 1 <= x + b — c <= n -> 1 + c — b <= x <= n + c — b1 <= z <= n -> 1 <= x + a — d <= n -> 1 + d — a <= x <= n + d — a1 <= w <= n -> 1 <= x + a + b — c — d <= n -> 1 + c + d — a — b <= x <= n + c + d — a — bWe find the most restrictive numbers for x, i.e. the smallest on the right side and the biggest on the left side, we get the difference, add 1 to it and multiply it by n to get the final answer.
•  » » » » 6 years ago, # ^ |   0 Thank you toss for the beautiful explanation. Can you explain why answer is max(0, n - max(a + b, b + d, c + d, a + c) + min(a + b, b + d, c + d, a + c)).How we got the a+b, b+d,c+d and a+c terms?
•  » » 6 years ago, # ^ |   0
 » 6 years ago, # |   +49 Why codeforces shouldn't know that task D was on HR 23 days ago?Click
 » 6 years ago, # |   +1 Will be russian version of editorial available?
 » 6 years ago, # |   +5 I think there is a error in the solution to E. m must be chosen from range [i+1,a[i]] not [i+1,n-1]. The code is also given as such
•  » » 6 years ago, # ^ |   +3 Fixed, thanks
•  » » 6 years ago, # ^ |   0 You're correct
 » 6 years ago, # |   0 For Problem D, my submission 17949387 O(NlogN) got a TLE, while 17954833 passed. Is this because of the test data set, or is the first submission actually slower and if so, why?
•  » » 6 years ago, # ^ |   +5 The first submission is not , since it is naive BST and hence might get unbalanced to have O(N) height  = O(N2) performance over N insertions.
•  » » » 6 years ago, # ^ |   0 Thanks :)
•  » » » » 6 years ago, # ^ |   0 @xmrisha how is your second solution works? Can you tell me detailed explanation. Thank You.
 » 6 years ago, # |   +6 My dad, a vietnam veteran, told me that there's one thing that always sticks with kids and adults no matter how old they are.Napalm.
 » 6 years ago, # |   -10 For problem B, referring to :"Help Vasya find out the number of distinct squares the satisfy all the conditions above. Note, that this number may be equal to 0, meaning Vasya remembers something wrong.Two squares are considered to be different, if there exists a cell that contains two different integers in different squares.Output Print one integer — the number of distinct valid squares."Is is me who understood that all squares should be distinct (for example the input 1 1 1 1 1 should give 0 because the only answer is a matrix of 1 where the squares are not distinct) or is it the problemset ?
 » 6 years ago, # |   +12 How the solution of C Works? Seriously :O
•  » » 6 years ago, # ^ |   +4 Example case: 15 0 0 0 -15 The prefix sum: 15 15 15 15 0 As you can see, the answer is 1 since 15 occur 4 times The repeated prefix sum means there are 4 part which produce zero (in case 15)Let i is the array position where 0<=i<5 The first part is i=0 and i=4 -> we directly move the money from i = 0 to i = 4 since zero sum is guaranteed. The second part is i = 1 -> 0 move The third part is i = 2 -> 0 move The fourth part is i = 3 -> 0 moveSo the answer is 1. Conclusion number of repeated prefix sum means number of parts if the sum of subarray from 0 to x is the repeated prefix sum.
 » 6 years ago, # |   0 My solution of problem B was exactly like you. But only missed the condition for comparing w,z,y (<=n) . And got WA.
 » 6 years ago, # |   0 I've solved E with something like binary-lift. #code
 » 6 years ago, # |   +11 why can this submission accept? http://codeforces.com/contest/675/submission/17948510 who could make a hack data to kill it, help!
 » 6 years ago, # | ← Rev. 2 →   0 Dont understand why we have to choose m such that Am is maximal, it seems like greedy Update: Got it, larger am will always cover other choices
 » 6 years ago, # |   0 can someone explain the o(1) solution for problem B? i did it in o(n);
•  » » 6 years ago, # ^ |   +3 You have 3 different explanations from above :) Ask clarifying questions to one of those comments.
 » 6 years ago, # |   0 Problem D is almost same with this problem: https://www.hackerrank.com/contests/womens-codesprint/challenges/mars-and-the-binary-search-tree
 » 6 years ago, # |   +3 How to hack this O(N^2) solution?? http://codeforces.com/contest/675/submission/17956511
 » 6 years ago, # |   +1 Can anyone explain the solution of problem C ?
•  » » 6 years ago, # ^ |   0 Suppose that the money is as follows ----> -1 2 -3 5 3 -6Then the prefix sums will be -----> -1 1 -2 3 6 0 Since the highest frequency is 1 so our k=1 and answer = N-1Another Example be ------> 15 -5 5 -15 Prefix Sums ---> 15 10 15 015 is repeated twice so answer = 4-2 = 2 transfers one from 15 to -15 and 5 to -5
•  » » 6 years ago, # ^ | ← Rev. 3 →   +40 A segment of x bank accounts which sums to zero needs x-1 money transfers to make all bank account money =0 . For eg:- 5 0 -5 i) First we transfer 5 from first bank account to second bank account. Now accounts look like this 0 5 -5 ii) Then we transfer -5 from second bank account to third bank account. Now accounts look like this :- 0 0 0 Thus is 2 ( 3-1 ) transfers I made all account's money to zero.Now suppose there are k segments in given array whose sum is equal to zero. Let length of segments be x1,x2,....,xk . Now for first segment we take x1-1 transfers , for second x2-1 .... and for kth xk-1 transfers. Total number of transfers = x1-1+...... xk-1 = (x1+x2+x3+....xk)- (1+1+...ktimes) = n — kIf we want to minimize total number of transfers we have to maximize value of k( Remember we assumed number of segments to be k )So what can we do to maximize value of k ?Let f[1],f[2],f[3],....f[n] denote cumulative sums of given array. f[i] = a[1] + a[2] +.... a[i]f[j] = a[1] + a[2] + ..... a[j] Suppose f[i]=f[j] then a[1] + a[2] +.... a[i] = a[1] + a[2] +.... a[i] + a[i+1] + .... a[j] Therefore , a[i+1] + a[i+2] +..... a[j] =0 Also since the sum of array as a whole is given to be zero . Remaining array sum is also zero. a[j+1] + a[j+2] .... a[1] + a[2] + .... a[i] =0Therefore we got 2 segments with sum =0 when we had two cumulative sums same.Now suppose f[i] = f[j] = f[k] for some 1<=i,j,k <=n , i
•  » » » 6 years ago, # ^ |   +8 Great Explanation Mayank Pratap. Codeforces should hire you to write editorials.Then it will a lot easier.Godspeed Bro.
•  » » » 6 years ago, # ^ |   0 Best explanation on C I've read. Thank you.
•  » » » 6 years ago, # ^ |   0 At last understand it..simply awesome.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Very detailed and great explanation.
•  » » » 6 years ago, # ^ |   0 but how to handle the case when the segment is a prefix and a suffix ?
•  » » » » 6 years ago, # ^ |   0 segment with a prefix and a suffix is included in his example, such as : a[k+1]+....a[1]+...a[i]=0
•  » » » 6 years ago, # ^ |   0 Thanks for nice explanation. I thought the solution over 2 hours. Finally, I could understand this problem after reading your explanation.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Here is an example that can help me to understand problem C.Now why we find the prefix sum and check their equality??? This is the key point to understand this problem. Suppose that the bank accounts are as follows ----> a: 3 5 -7 3 4 -8 and according to the problem it is confirmed that: 3+5+(-7)+3+4+(-8) = 0; same as a[0]+a[1]+a[2]+a[3]+a[4]+a[5] = 0;the prefix sum---->: 3 8 1 4 8 0 And we see that 8 occurred twice at 1 and 4 positon.And Because of 8 occurred twice we can write,=>a[0]+a[1] = a[0]+a[1]+a[2]+a[3]+a[4] =>a[2]+a[3]+a[4] = 0And we know that Initially a[0]->a[1]->a[2]->a[3]->a[4]->a[5] we need 5 operations to make all zero. We know thata[0]+a[1]+a[2]+a[3]+a[4]+a[5] = 0 and we evaluate so far a[2]+a[3]+a[4] = 0 so that, a[5]+a[0]+a[1] = 0 Now we divide the main array(a[0]+a[1]+a[2]+a[3]+a[4]+a[5] = 0) to two sub array(a[2]+a[3]+a[4] = 0 and a[0]+a[1]+a[5] = 0)and we reduce the two operations(two connections) from the main array.connection 1 : a[1]->a[2]; which is reduced from main array........................ connection 2 : a[4]->a[5]; which is reduced from main array........................Now we need a[2]+a[3]+a[4] = 0 by a[2]->a[3]->a[4] (2 operations) And a[0]+a[1]+a[5] = 0 by a[0]->a[1]->a[5] (2 operations) Now optimal results = 2+2=4;
•  » » » 6 years ago, # ^ |   0 thx :)
 » 6 years ago, # |   0 Can anyone explain how problem C solution hit your mind. I mean to say how to have a good proof for that.
•  » » 6 years ago, # ^ |   +1 hope my explaination helps.. ;)
•  » » » 6 years ago, # ^ |   0 Thank you ! But i already solved that one :)
 » 6 years ago, # |   0 Can someone provide a more detailed explanation for problem C ?
 » 6 years ago, # |   0 Can somebody explain why Solution C "prefix sums" is correct answer? thanks.
•  » » 6 years ago, # ^ |   0 See this
•  » » 6 years ago, # ^ | ← Rev. 4 →   +1 Obviously the answer is less than the number of banks, which shows that when you put all these banks on a ring and use some roads to connect these banks, there are at least one road where no money goes through in the optimal way.Let's cut one road, break the ring into a list and iterate all the banks. It is easy to see that whenever the prefix sum becomes zero, we can find a way to transfer money in the banks we have iterated so we can cut the next road. Now we just need to iterate the road we cut at first and maintain all prefix sums. Every time we fix the current road and cut the next road, all prefix sums would simultaneously increase or decrease by a number, which depends on the order you iterate, so we just need to maintain the offset.
 » 6 years ago, # |   0 Can anybody provide a more detailed explanation for DIV2 E?
 » 6 years ago, # |   0 In Problem B, why are we multiplying the answer by n?
•  » » 6 years ago, # ^ |   0 note that center '?' can be in range 1~n, whatever other '?' is.
 » 6 years ago, # | ← Rev. 2 →   -6 Actually I don't know what is happening but when I run my c++ program on my laptop for Codeforces Round 353 Problem D, it gives correct result, but when I run it on codeforces, it gives different result. It is not that it has happened to me first time. So I would request you to please have a look at this so that I do not face this problem in future.
•  » » 6 years ago, # ^ |   0 I don't know how this works in your computer but one of the problems is here : if(it==my.end()){ ans = (*(it--)).f; (*(it--)).s.s = true; } when it==my.end() , then it isn't element, so haven't .first ! if you used -- for going back before using it, you must write it like this --it.also notice that in every place you used it--, it's value is really changed and isn't temporary.
•  » » » 6 years ago, # ^ |   0 I have changed from it-- to --it. It has passed the first test case but the problem is still there as it failed the 2nd test. You said that "also notice that in every place you used it--, it's value is really changed and isn't temporary.", but I am overwriting its value in each iteration.New code submitted: http://codeforces.com/contest/675/submission/17962900
•  » » » » 6 years ago, # ^ |   0 I didn't say that you must change all it-- to --it. I just want to note their difference for you .and for 2nd test check these part of your code : else{ x = (*(--it)).s.s; y = (*it).s.f; if(x){ ans = (*it).f; (*it).s.f = true; }else{ ans = (*(--it)).f; (*(--it)).s.s = true; } } 
 » 6 years ago, # |   0 Hello. How to use spoilers ?
•  » » 6 years ago, # ^ |   0 ClickChoose last drop down in writing window, then click on spoiler. Add your text between > and <
 » 6 years ago, # | ← Rev. 3 →   +3 Some comments:In problem C, As mentioned in the tutorial, a segment of x bank accounts which sums to be 0 needs x - 1 transfers to make all bank accounts to be 0. So the basic idea is to break the whole circle into as many such segments as possible. Suppose the prefix sum are f[1], f[2], ..., f[n]. For any i and j, if we have f[i] = f[j], then a[i+1] + a[i+2] + ... + a[j] = 0 and a[j+1] + a[j+2] + ... + a[n] + a[1] + a[2] + .. + a[i] = 0. So, the problem can be transferred into a problem of finding the mode of the prefix sum list.In problem E, Since we have dpi  =  dpm  -  (ai  -  m)  +  n  -  i  -  1, i + 1 ≤ m ≤ ai, we can also find maximal dp[m] + m rather than maximal a[m]. The idea of finding maximal a[m] comes from the intuition that we can reduce the answer if we go to a city which can go to as many cities as possible. The idea of finding maximal dp[m] + m comes from the formula itself. So I think finding maximal dp[m] + m will be more rational.
 » 6 years ago, # |   0 Problem B: How to be sure that 64-bit integer will be enough for total valid combinations count, and there is no need to use BigInteger? It's seems that total valid and invalid combinations count is 10^5*10^5*10^5*10^5*10^5 = 10^25 which obviously can't be represented by 64-bit integer.
•  » » 6 years ago, # ^ |   0 There is only 10^5 * 10^5 different correct positions, because every position can be set by two numbers
 » 6 years ago, # |   +1 Hi, For problem D, I have the following submission http://codeforces.com/contest/675/submission/17953025 It uses a balanced binary search over the possible intervals so it's clearly O(n*log(n)). Yet, it timesout on test case 7. Solution is similar to the proposed one, so I guess the only thing that slows it down to get a timeout is the fact that C# is slower than C++, which might not be fair taking into account that it shouldn't be about what language you use. I might be wrong and not realise the test-case where it's not O(n*log(n)), but I really can't see how.
•  » » 6 years ago, # ^ |   0 Your algorithm has problems when the input is a decreasing array. It has nothing to do with the speed difference between C# and C++.
•  » » » 6 years ago, # ^ |   0 Can you give more details or a test-case I can try? Tried 3 / 3 2 1 and it seems to work fine.
•  » » » » 6 years ago, # ^ |   0 The problem is that its time complexity is O(n^2) for decreasing arrays. You have the test case. Just try appropriate size, like 10^5.
•  » » » » » 6 years ago, # ^ |   0 That's not true. Binary search over an inverse-sorted array is still O(log n). I have just tried it and for 100k descending value elements it makes 1468961 comparisons inside the binary search. Less than n*log2(n)
•  » » » » » 6 years ago, # ^ |   0 Found the problem. It seems that C# Insert and Remove are O(n) operations.
 » 6 years ago, # |   0 Hello guys, Can someone tell me why is my solution for D receiving TLE ? I am pretty sure i am adding elements here in log N p.e and printing out solution per node in log n... Submisson: http://codeforces.com/contest/675/submission/17963314Cheers!
•  » » 6 years ago, # ^ |   0 You code a solution that's O(n) for every insertion. Test it locally with: 100000 1 2 3 4 ... The tree generated with this has a form like a list: 1 -> 2 -> 3 -> ...So, for every insertion you transverse all the tree, since, O(n)
 » 6 years ago, # |   0 I solved problem D using segment tree RMQ but I didn't have the time to code it during the contests . submission : 17964060
•  » » 6 years ago, # ^ |   0 nice one.... I like the approach
 » 6 years ago, # |   +3 There is simpler solution of problem D: 17964559 Idea is: for each "child place" (i.e. place where new node can be added) we keep minimal number which will be placed there.
 » 6 years ago, # |   0 Can someone explain what is wrong with my solution of problem D ? My code link
•  » » 6 years ago, # ^ |   0 Hello there ! I actually had the same problem and i managed to figure it out on my way to school. The main problem with your solution is that there is a possiblity that tree your construct which contains list of increasing elements will act like linked list which means that every new insertion in tree will act in O(N).
•  » » » 6 years ago, # ^ |   0 I used a standard bst code. Can you please explain how it can be in O(n).
•  » » » » 6 years ago, # ^ |   0 Take a look at this input: 1,2,3,4....99. In order to insert 99th element in BST you would have to traverse trough 98 nodes as every element after root's is strictly higher then it.Your tree will not have left subtree as it would only have right one due due increasing sequence.
•  » » 6 years ago, # ^ |   +3 This solution might lead to unbalanced BST. This leads to O(N) height and O(N^2) insertions. 
 » 6 years ago, # |   +3 Hey, I am still not able to understand the solution for problem C. :/ If someone could help me see the solution in a simpler way ? i went through the comments where this comment was suggested. I still couldnt figure it out. From the editorial i have understood the part till dividing it into parts and if length l the l-1 operations so if k parts ans = n-k. After this i cant understand. Any help please ?
•  » » 6 years ago, # ^ |   0 Hi @rg18 . I was also facing the same difficulty as you. Exactly the part you mentioned, I was unable to understand. After trying for a long time I understood what the editorial tried to say. Look the part you cannot understand is basically a method to find the number of subarrays with sum equal to zero. And by the term prefix they mean cumulative sum. Eg: Consider the array 2,-1,3,4,5. The prefix sum array would be 2,1,4,8,13. With this much fact I would urge you to sit with a pen and paper and try understanding what the editorial means. If you cannot read on. Consider the following array A=[5,5,5,-10,2,4,-2,3,-7,-5] Let us calculate the prefix/cumulative sum prefix[]=[5,10,15,5,7,11,9,12,5,0] {Note: The last term of prefix[] must be zero since it is mentioned in the question that all the terms of A[] will sum up to 0.} Now let's consider the subarrays with sum equal to zero. The subarrays are: prefix[1] to prefix[3] (0 based indexing) prefix[4] to prefix[8] prefix[9] to prefix[1] Now notice the term just before prefix[1] in the prefix array. Again notice the term at prefix[3]. It is again 5. This shows that the maximum number of repetitions of an element in the prefix[] is the number of maximum subarrays of sum 0. Do let me know if you still have any doubts. :D
•  » » » 6 years ago, # ^ |   0 But I still do not understand why this works. I understood it for this example.
 » 6 years ago, # |   0 This is the first problem set, what I try to solve in codeforces :D)
 » 6 years ago, # |   0 can someone explain problem E more clearly?,thanks.
 » 6 years ago, # |   0 could somebody plz explain D in a bit more detail!!
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 Sorry if my explanation is tedious.Let's consider the second example: 4 2 3 1 6At first, our BST is empty, so the root value will be 4. That means that all values that lie in the interval [1, 3] will go to the root's left, and all values that lie in the interval [4, 10^9] will go to its right.So, at the moment we have two candidate places to put our next number: [1, 3] (value=4) and [5, 10^9]{value=4}.If we insert the next value we find that it should to go the root's left because 2 is in [1,3]. Since we have filled the root's left children, we must remove the interval [1, 3]{value=4} and add two new ones: [1, 1]{value=2} and [3,4]{value=2}. So now we have the following candidates: [1, 1]{value=2}, [3,4]{value=2} and [5, 10^9]{value=4}.If we do the same thing with all sequence values we will know all parent values and we will keep an updated information about where new values should go. It is not necessary to keep the empty intervals (i.e: those that its right value is smaller than its left), since that means that no value can be a child of that node.In order to know quickly on what interval a new value should go you can keep them sorted by its right values, then for a number x find the first interval right that it is greater or equal than x. You can do this because you know the interval is unique (as the BST paths are).You can check my solution for more clarification: http://codeforces.com/contest/675/submission/18001556
•  » » » 6 years ago, # ^ |   0 thank you but could you plz explain why the LCA of an interval one of the values of the interval
•  » » » 6 years ago, # ^ |   0 You solution seems buggy to me. Could you please explain how does set::upper_bound() select the proper interval from the set. Shouldn't it be set::lower_bound() instead?As per my understanding, if the set contains three interval,i.e. [1,1]{2}, [3,3]{2} and [5,1000000000]{4}and now I insert the element 3, upper_bound({3, 3, 3}) should select the interval [5,1000000000]{4} (see the definition here). Clearly, this messes up the solution.Let me know, if I am wrong here.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 lower_bound is first ">=", upper_bound is first ">". Yes, names are very confusing.
 » 6 years ago, # |   0 Can somebody explain why in problem E we should change the indexing to 0-based?Using the reasoning described in the editorial the dp formula I find is:dp[i] = dp[m]+(m+n)-(a[i]+i),which works just fine.I don't see however why the indexing should affect our formula and why it comes out different.
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 It was just more comfortable for me to use 0-based indexing. You can use 1-based indexing if you want.
 » 6 years ago, # |   0 Can anyone please explain this dp[i] = dp[m] - (a[i] - m) + n - i - 1 in 675 E? Thanks!
 » 6 years ago, # |   0 Can someone please explain how is the recurrence dpi = dpm - (ai - m) + n - i - 1 actually derived. I understand that for any pair i,j dp[i][j] = 1 + dp[m][j] where m is the index which has the greatest value of ai. Yet, I fail to understand how is the recurrence derived from it ? thanks, in advance!
•  » » 6 years ago, # ^ |   0 Yes, I know that editorial for E is too short, sorry about that.ρi, j = 1 for j = i + 1... mρi, j = ρm, j = 1 for j = m + 1... aiρi, j = 1 + ρm, j for j = ai + 1... n - 1Sum of ρi, j for j = m + 1... n - 1 equals to dpm + n - 1 - ai Sum of ρi, j for j = i + 1... m equals to m - iSo, sum of ρi, j for j = i + 1... n - 1 equals to dpi = (dpm + n - 1 - ai) + (m - i) = dpm - (ai - m) + n - 1 - i
•  » » » 6 years ago, # ^ |   0 Now it is much clearer! Thanks! One more doubt, Why do we add ( n - 1 - ai ) with dpm for j = m + 1... n - 1 ? Thanks in advance!
•  » » » » 6 years ago, # ^ |   0 Becasue dp[m] = sum of all ρ(m, j) for j = m+1....n-1 But this is equal to 1 for j= m+1... aiHence, the number of 1's repeated are only for ai+1 ... n-1 as for m+1 ... ai, this is already included in dp[m].
•  » » » » » 6 years ago, # ^ |   0 Thanks! I missed ρi, j = 1 + ρm, j for j = ai + 1... n - 1 :)
•  » » » 6 years ago, # ^ | ← Rev. 6 →   0 ρi, j  =  ρm, j  =  1 for j  =  m  +  1... aiThis is only possible when a_m >= a_i, which may not be necessary. Am I going wrong somewhere?
•  » » » » 6 years ago, # ^ |   0 We must choose maximal possible am because we want to maximize range on the next step.aj ≥ j + 1 for each j by the statement.am ≥ ai + 1 if we choose m = ai. So, maximal possible am ≥ ai + 1.
•  » » » » » 6 years ago, # ^ |   0 Ahh, it suddenly struck me. Thanks for the beautiful problem. I can sit whole day long just admiring the problem.
•  » » » 4 years ago, # ^ |   0 So in the above formula you are effectively subtracting the paths we will not visit when we go to m (m,m+1.... a[i]), but how can you be sure that the cost of visiting these paths in dp(m) is 1?
•  » » » » 4 years ago, # ^ |   0 Got it, never mind
 » 6 years ago, # |   0 Can someone please explain problem D. The code in tutorial looks simple but can't get it.I understand that a naive approach can lead to N*N complexity. How do we skip looking at each values before inserting something. Sounds like we are reading things on the basis of minimum and maximum so far but not quite understanding the use of set upper bound etc.Please explain.
•  » » 6 years ago, # ^ |   0 Consider the inputs, 1) 5 7 so far. If 6 comes where do you insert it ? — as lchild of 7. 2) 7 5 so far. If 6 comes where do you insert it? — as rchild of 5. So any node coming will be inserted into either as rchild of l or lchild of r, l -> maximal number less than the given r -> minimal number greater than the givenif only one of them exists, our problem is solved.But if both are present, we need to establish the fact that only one of them will have a place for the coming node which can be proved easily. Note that both l and r cant have the children simultaneously as that would contradict how we chose l and r. Also, Let l hasn't right child and r hasn't left child. Hence lowest common ancestor (lca) of l and r doesn't equal to l or r. So lca is between l and r in tree traversal. But it's impossible because l is maximal possible and r is minimal possible. (taken from editorial)So it's only about finding l and r if they exist, and finding which one can be parent (done by creating a map to store lchild and rchild of all nodes)
 » 6 years ago, # |   0 "Let l hasn't right child and r hasn't left child. Hence lowest common ancestor (lca) of l and r doesn't equal to l or r. So lca is between l and r in tree traversal. But it's impossible because l is maximal possible and r is minimal possible. So l has right child or r has left child and we know exactly which of them will be parent of x." Could Somebody plz explain the above paragraph.
 » 6 years ago, # | ← Rev. 2 →   0 For problem E, where did (a_i — m) come from? Doesn't that assume that a_m >= a_i?
 » 6 years ago, # |   0 In problem D, st.upper_bound(a); gives AC http://codeforces.com/contest/675/submission/18177277 whereas upper_bound(st.begin(),st.end(),a); gives TLE. http://codeforces.com/contest/675/submission/18177176. What could be the reason...?
•  » » 6 years ago, # ^ |   0 std::upper_bound binary searches through your container and uses std::advance internally to move the searching iterator.Now you must be aware of the difference between random access iterators, and bidirectional iterators (set iterators are bidirectional but not random access). With random access iterators, you can access say the 5th element in a vector v using v[4] [which is equivalent to *(iter + 4), assuming iter is initially pointing to v.begin()], i.e., you can access the elements of the vector randomly. Whereas in a set, this is not possible, you will have to increment the iterator linearly (++iter or --iter) in order to access the next or previous elements, so in order to access the 5th element in a set s, you will have to increment iter 4 times (++iter) [also assuming that iter initially points to s.begin()]In your second solution, std::advance will need to increment the searching iterator linearly each time it is called, which results in the additional linear complexity of N on average each time std::upper_bound is called, where N is the distance between the first and the last element in the specified range.On the other hand, I assume s.upper_bound(a) [your first solution] internally works in a different manner, since it is a method of the same class, which means it can have different access, and therefore, better performance.Check cplusplus for more information.
 » 6 years ago, # | ← Rev. 2 →   0 Can somebody explain me how this greedy approach works in Div 2 E.(ie) choosing the m from the maximal a[i].Can you give me a more formal logic or proof for it? According to me it should be dp[i]=max(dp[m]+m-i) where m belongs to [i+1,a[i]] which makes it a n*n*log(n) approach instead of n*log(n)
•  » » 6 years ago, # ^ |   0 Hope, those comments will be useful for you: first, secondYour formula is a bit wrong. But even if it was right I don't understand why it's . If we calculate dp naively we get O(n2) solution. Also we can keep dpm + m in segment tree and find maximum in what leads to solution.
 » 5 years ago, # | ← Rev. 2 →   0 In DIV-2C — "So, if we sum number of operations in each part we get ans = n - k where k is number of parts." Can anybody provide me a prove of this statement? How to verify its correctness?
 » 5 years ago, # |   0 In Restoring Painting, I don't understand why we need to multiply the ans by n;
 » 3 years ago, # |   0 komendart Please Explain the dp transition and describe why does it work. I can not understand this transition of dp calculation.
 » 2 years ago, # | ← Rev. 2 →   0 Wow I use DFS which turns out to be such an overkill for problem C: hahaha
 » 20 months ago, # |   0 Can someone pls how the get function works for E? int get(int l, int r) { pair ans{-1, -1}; for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) ans = max(ans, tree[l++]); if (r & 1) ans = max(ans, tree[--r]); } return ans.second; }