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

×

codeforces educational round problem d

can anyone tell me how to solve this problem http://codeforces.com/contest/903/problem/D

asked 12 Dec '17, 23:22

manaranjanfav's gravatar image

3★manaranjanfav
235
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.

link

answered 13 Dec '17, 04:18

meooow's gravatar image

6★meooow ♦
7.1k718
accept rate: 48%

edited 13 Dec '17, 04:24

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

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

link

answered 13 Dec '17, 12:02

gitesh18's gravatar image

4★gitesh18
336
accept rate: 0%

edited 13 Dec '17, 16:04

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×682
×6
×3

question asked: 12 Dec '17, 23:22

question was seen: 738 times

last updated: 13 Dec '17, 16:04