Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Bhaskar13's blog

By Bhaskar13, history, 5 weeks ago, In English,

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

 
 
 
 
  • Vote: I like it
  • +2
  • 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 Bhaskar13 (previous revision, new revision, compare).

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

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]}

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

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 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

      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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

          K

          I am a retard. ig O(n^2) dp is the answer then

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

That's CF573E

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
public static int myStrategy(int[] arr) {
	int n = arr.length;
	int remSum=0;
	List<Integer> list =new ArrayList<>();
	for(int i=n-1;i>=0;i--) {
	    if((i+1)*arr[i]+remSum>=0) {
		list.add(0,arr[i]);
		remSum +=arr[i];
	    }
	}
	int ans=0;
	for(int i=0;i<list.size();i++) 
	 ans += (i+1)*list.get(i) ;
	return ans;
    }