Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Counterexamples to my claim?

  1. May 30, 2017 #1
    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, ...,


    b0, 1, b1, 1, ...

    Are there any simple counterexamples?
  2. jcsd
  3. May 30, 2017 #2


    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?
  4. May 30, 2017 #3
    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.
  5. May 30, 2017 #4
    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.
  6. May 30, 2017 #5
    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)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted