tanmay2798's blog

By tanmay2798, history, 5 weeks ago, In English

Two players are playing a game. They have been given a array of numbers (Array A). Player 1 starts by picking any number.

A player may choose any number adjacent to other player's last pick. If no such number exists, he can choose any number from the remaining unchosen ones. You cannot pick a number which has already been picked by any player.

The two players pick numbers alternatively. Assume both the players play optimally.

The score of a players is the sum of the numbers he has chosen. What is the maximum score Player1 can obtain?

Constraints:

2 <= length of A <= 100000

1 <= A[i] <= 1000

Example:

|A| = 5;

A = {40, 200, 20, 15, 20}

Answer: 240.

Explanation: Player1 chooses 200. Payers2 chooses 40 (among 40 and 20). Player1 chooses 20 (among 20, 15, 20), Player2 chooses 15 (he's only choice). Player1 chooses 20 (last array element).

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
Auto comment: topic has been updated by tanmay2798 (previous revision, new revision, compare).
»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

If the size of the array is even then I guess we need to just calculate the alternate position of sum (odd_sum and even_sum) and the answer would be max(odd_sum, even_sum).

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice. I figured that. Do you have any solution for the odd length case?

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Pick the maximum element and now the problem reduces to the even case and solving with respect to the Player 2 with slight modification on the basis of the index of maximum element.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        If the maximum element is at even index (indexing from 1), then there will be 2 sub problems of odd length. Are you suggesting to recursively solve for both?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, however going by constraint, you'll have to use dp.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I thought of this, but instead of choosing the highest value element, I thought I would have to choose every element and recur on both sub parts.

            Can you explain why you think this greedy choice will work here?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    for the full solution i think we need to calculate it for each suffix and prefix.