edgerunner's blog

I need HELP pls
By edgerunner, history, 10 months ago, In English

How to choose n/2 (n is even) elements from the array such that their sum is minimum and no two elements are adjacent to each other: [4, 2, 1, 1] 1 + 2 = 3 [3, 3, 3, 0, 4, 0] 3 + 0 + 0 = 3 [2, 0, 11, 2, 0, 2] 0 + 2 + 2 = 4

can we do it greedy? (no dp pls)

  • Vote: I like it
  • -14
  • Vote: I do not like it

»
10 months ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

we must choose n/2 element so choose index 1,3,5 or 2,4,6 in case of lenght six and minimum of both is answer.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You have to choose all odd indexes or all even indexes so just test the sum of these two and see which one is minimum.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but choosing from both odd/even indexes maybe optimal: 1,3,6 etc.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Then you can't take n/2 element.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        we must take n/2 elements with min sum, pls reread the description

        → Reply
»
10 months ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

Initialize 2 prev elements (podd=0,peven=0) and 2 cur elements (codd=0,ceven=0) Let's say the array is 1-indexed, then:

if the index is odd then: codd=a[i]+podd;

if the index is even then: {ceven=a[i]+min(podd,peven); podd=codd; peven=ceven;}

And Final answer will be: min(codd,ceven)

This will work because we have to take n/2 elements.

[PS: Although this is just space optimized O(1) DP, but the thought process is mostly greedy and easier to understand]

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you, will need time to digest)

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your Welcome

      You just have to think along the lines:

      • Each odd-even index pair (not even-odd only odd-even) will have exactly ceil(index/2.0) number of elements, not more not less because if it contains more then there will definitely be some elements before them that are adjacent, if it contains less then you can't make n/2 elements from the remaining pair.
      Example:
      • the odd index will/can take only from the previous odd index from the previous odd-even pair because if it takes from the previous even then it will be adjacent to it.
      Example:
      • the even index can take from both previous odd-even index pair (NOTE: previous odd-even pair, not the previous odd or even index otherwise just the previous odd index will be adjacent)
      Example:
      → Reply