×

# Solving ARRAYTRM

 0 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 3★sanjayk 16●2●2●6 accept rate: 0%

 0 Very sad to see that no one answered here answered 01 Sep, 13:01 5★kaushala 27●3 accept rate: 0% @kaushala now answered. (02 Sep, 03:37) joffan4★
 0 @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. answered 02 Sep, 03:36 4★joffan 484●7 accept rate: 10%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,481
×503
×8

question asked: 28 Jul '14, 11:57

question was seen: 1,942 times

last updated: 02 Sep, 03:37