can anyone tell me how to solve this problem http://codeforces.com/contest/903/problem/D
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_i-1, 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:
[1].
[1]: http://codeforces.com/contest/903/submission/33171417
3 Likes
I saw your code on problem C and wondered what you did!! It would be great if you can explain how you did!
1 Like
The lucky ones who used python xD
3 Likes
@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.
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.
2 Likes
Yes, I also didn’t look at the constraints carefully 
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
1 Like