# C/++/# Counterexamples to my claim?

Tags:
1. May 30, 2017

### SlurrerOfSpeech

I'm trying to solve a problem that amounts to:

Given b0, ..., bn-1 where1 <= bi, find the max of |a0 - a1| + |a1 - a2| + ... + |an-2 - an-1| where 1 <= ai <= bi.

I'm 100% confident that each ai is either 1 or bi.

I'm 90% confident that the elements a0, ..., an-1 are either

1, b0, 1, b1, ...,

or

b0, 1, b1, 1, ...

Are there any simple counterexamples?

2. May 30, 2017

### Staff: Mentor

Can you give a context for your question? Is this some intuitive problem or is it based on some concrete example that someone might already know about?

3. May 30, 2017

### willem2

it's easy to see, that for all ai-1 and ai+1, ai has to be 1 or bi.
- if ai is smaller than both ai-1 and ai+1, setting it to 1 will make the sum bigger.
- if ai is biggger than both ai-1 and ai+1, setting it to bi will make the sum bigger.
- if ai is between ai-1 and ai+1 setting it to 1 or to bi
will make the sum bigger.
The only case where the last possibility doesn't work, is when one of the neigbours is 1 and the other >= b. In that case the maximum sum is the same whatever ai is.
You can force such a situation with a 1,2,3,1 sequence. a1 can be anything <=2.
A non-conforming sequence with a larger sum of differences isn't possible.

4. May 30, 2017

### SlurrerOfSpeech

An algorithms problem I'm trying to solve https://www.hackerrank.com/challenges/sherlock-and-cost

The solution I tried is essentially

X = [1, b0, 1, b1, ... ]
Y =[b0, 1, b1, 1, ... ]
max(diffs(X), diffs(Y)]

and was surprised that it didn't pass all test cases.

5. May 30, 2017

### willem2

To get the maximum, all ai can be either 1 or bi, but it doesn't have to be an alternating pattern of 1s and bis.
B = (10,1,1,10) needs A = (10,1,1,10)