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

×

Solving ARRAYTRM

Hey Guys I need your help in solving http://www.codechef.com/problems/ARRAYTRM/ I'm not able to arrive at a straight logic to solve this problem. I could only infer the following: The difference of difference b/w the elements of chosen set and left-out elements could differ by k+1 after each operation. I don't know how to approach this problem. Would really appreciate any help, specially how to attacked the problem and used the intermediate inferences to reach to the logic.

thanks in advance.

asked 28 Jul '14, 11:57

sanjayk's gravatar image

3★sanjayk
16226
accept rate: 0%

edited 28 Jul '14, 11:59


Very sad to see that no one answered here

link

answered 01 Sep, 13:01

kaushala's gravatar image

4★kaushala
273
accept rate: 0%

@kaushala now answered.

(02 Sep, 03:37) joffan5★

@sanjayk You made the most important observation, that the difference between two elements can only ever be changed by a multiple of $(k+1)$. So, taking the given values $\bmod (k{+}1)$, only those in the same residue class can be zero at the same time. Thus we need at least $n{-}1$ of the values in the same residue class $\bmod (k{+}1)$ to allow "YES".

To show that this condition is sufficient, select all such values except those with maximum value to increase, and repeat until all have the same value. Then decrease to zero.

link

answered 02 Sep, 03:36

joffan's gravatar image

5★joffan
9038
accept rate: 12%

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:

×2,535
×533
×8

question asked: 28 Jul '14, 11:57

question was seen: 1,982 times

last updated: 02 Sep, 03:37