codeforces educational round problem d

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

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.

Sum of differences for all pairs in O(n)

My solution

2 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

@abdullah768 I think you can use unsigned long long and have a sign variable to solve it in C++.

@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.

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