can anyone tell me how to solve this problem http://codeforces.com/contest/903/problem/D asked 12 Dec '17, 23:22

I solved it in a straightforward way. The number of times we add $a_i$ to the total sum is simply the number of elements to the left of $a_i$ which are not equal to $a_i1$, $a_i$, or $a_i+1$. Similarly, the number of times we will subtract $a_i$ from the total is the same as above but for elements on the right instead of left. So a procedure that calculates the first sum will give you the second sum when used on the reversed array. The procedure can be implemented using a map as counter. Here is my solution: code. answered 13 Dec '17, 04:18
1
I saw your code on problem C and wondered what you did!! It would be great if you can explain how you did!
(13 Dec '17, 10:55)
3
The lucky ones who used python xD
(13 Dec '17, 11:05)
@abdullah768 I think you can use unsigned long long and have a sign variable to solve it in C++.
(13 Dec '17, 11:12)
@sdssudhu I suppose it could be done that way but most of us didn't even consider the fact the the value would exceed 10^18 until the announcement popped up.
(13 Dec '17, 11:19)
(13 Dec '17, 11:44)
1
Yes, I also didn't look at the constraints carefully :P Glad I used Python! @dishant_18 for problem C the answer is the maximum number of occurrences of any element. I have just used Python's Counter collection to do the heavy lifting. Not sure why they kept constraints low enough for $\mathcal{O}(n^2)$ solutions o.O
(13 Dec '17, 15:52)
showing 5 of 6
show all

This problem can simply be solved by keeping the sum of differences between every element which can be calculated in O(n) and then subtracting the differences with a value equal 1 or 1 using a map. But this solution failed due to integer flow in C++. Edit : The integer overflow problem can be solved by using long double instead of long long.Refer to my solution. answered 13 Dec '17, 12:02
