You are not logged in. Please login at to post your questions!


codeforces educational round problem d

can anyone tell me how to solve this problem

asked 12 Dec '17, 23:22

manaranjanfav's gravatar image

accept rate: 0%

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: code.


answered 13 Dec '17, 04:18

meooow's gravatar image

6★meooow ♦
accept rate: 48%

edited 13 Dec '17, 04:24


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) dishant_185★

The lucky ones who used python xD

(13 Dec '17, 11:05) abdullah7686★

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

(13 Dec '17, 11:12) sdssudhu6★

@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) abdullah7686★

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) meooow ♦6★
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.

Sum of differences for all pairs in O(n)

My solution


answered 13 Dec '17, 12:02

gitesh18's gravatar image

accept rate: 0%

edited 13 Dec '17, 16:04

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 12 Dec '17, 23:22

question was seen: 738 times

last updated: 13 Dec '17, 16:04