Блог пользователя Bhaskar13

Автор Bhaskar13, история, 4 года назад, По-английски

Only removal of elements is allowed(no reordering/sorting)
e.g:
Let the array be [-1, 5, 2, -8, 7]
then using all elements sum = -1*1 + 5*2 + 2*3 + -8*4 + 7*5 = 18
removing -1, -8 sum = 5*1+2*2+7*3 = 30
removing only -8 sum =-1*1 + 5*2 + 2*3 + 7*4 = 43(ans)


If arr is [-1, 5, 2, -8, 7, 101], then ans =30 + 606 = 636 instead of 43 + 101(5)=548

I thought of this below strategy
going from last ele to first in array, If that ele >=0 or remSum + (i+1)*a[i] >=0,
I will add the ele to a list at 0 index
where remSum =0 initially or sum of elements already to list


using this, I will add 5 to list first;for ele = -8, 4(-8) + 7 >= 0 false, I willnot add it to list.Later I will add 2, 5, then list will be [2,3,5]. For -1, -1*1+(2+3+5)>=0 true, so I will add to list, [-1,5,2,7] 43 ans

for second arr, 101+7+4(-8)>=0, so I will add to list


I was assuming intial elements are present, that's why i am multiplying a[i] with (i+1) instead of number of elements present(which I didn't find)

My friend was asked this in a test. If someone can discuss correct strategy or point me to already existing editorial/problem in codeforces or any other CP site, it would be great

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

We can have a 2-d DP where dp[i][j] denotes the maximum sum from 1 to i (1-based indexing) such that we have deleted exactly j elements from 1 to i. The recurrence relation is therefore DP[i][j] = MAX(dp[i-1][j]+val, dp[i-1][j-1]) where val is (i-j)*arr[j] and the final ans is MAX{dp[N]}

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

EDIT: This approach is wrong

Notice that taking an element increase the sum of the array by sum of all the elements in suffix(don't count the elements which we have already decided to not keep in the array) starting from that element (i+1 increases by 1 for all the elements ahead and the current element is added). So if this is positive use that element, otherwise don't.

In the 1st array

sum from 7 = 7 (>0), use it

sum from 8 = -1 (<0), don't use it

sum from 2 = 2+7 = 9 (>0), use it

sum from 5 = 2+7+5 (>0), use it

sum from -1 = -1+2+7+5 (>0), use it

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    when I solved this way for
    { -1, 5, 2, -4, 7 }, it gave 34
    but
    { -1, 5, 2, 7 } clearly gives 43

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      My bad, that was a really stupid mistake.

      How about this. We maintain 2 variables, totalSum and sum. totalSum is sum including the weights (multiplied with i+1) and sum is just their sum. So now iterate from last to first again and if(totalSum+sum+currentElement>totalSum) use the current element and make totalSum = totalSum + sum + current element and make sum = sum + currentElement.

      Finally totalSum should give you correct answer.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        totalSum+sum+currentElement>totalSum
        IS this intentional
        sum+currentElement>0
        This is not diffrent from your 1st comment

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

That's CF573E