Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

robertlewantest's blog

By robertlewantest, history, 8 months ago, In English

Given an array of N positive integers. You can make any number of elements in it negative such that every prefix sum of the array remains positive i.e >0. Find the maximum number of elements you can make negative.

Example 5 2 3 5 2 3

Answer= 3. This can be converted to 5 -2 3 5 -2 -3

N is 10^5 Ai<=10^9.

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

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

loop on the array and keep c as sum of the array and while c > A[i] subtract the A[i] and increament the ans.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

could it be like a knapsack prob???

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

    and we would use dp , so that it wouldnt give tle

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

      N is 10^5 i dont think it works

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

        yeah no but using dp with knapsack, it would be O(n), we could at every position i store the max number of element we can make negative and if we reaach on that point again, we just use it, im not 100% sure whether this would work or not, im in the process of learning dp.

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

          If u want to use dp u need to maintain current sum as well in the state and ai<=10^9, so it is not feasible

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

            yeah ig, it would make it a 2D dp, and that would give memory limit exceeded, could you send the question link??,i could give it a try, tho most prolly wont be able to.

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

              I don't have link bro.. some friend asked this question to me

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

                oo :/, welp but im sure this isnt possible without using dp.

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

    How?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this solution may work , only because we have N positive integers in the array at the initial state .

Make a segment tree for the given array

Now make a copy of original array and sort it.Doing so we help to give us the smallest number to run our check function.

Now starting from the smallest number, find the fist occurrence from right side (greedy approach), check if it can be turned into negative with the help of segment tree ( get sum 0,i ) and if its True, turn it and update the segment tree with update( i, -2*a[i] ) and ans++.

If its a False, skip this number and move on to the next ... do so for all

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

    It sounds like a good idea, but the problem is that checking the amount on the prefix [0; i] is not enough.

    Consider this example: 4 3 2, first you'll make a negative two, because 4 + 3 > 2, than you'll make a negative three, because 4 > 3, however, after such actions, the sum on prefix [0; 2] will become negative (4 - 3 - 2 = -1).

    To solve this problem, you can maintain in the leaves of the segment tree not the elements of the array, but the prefix sums of the array.

    Now, when you change one of the elements (for example, element i), you will need to increase all the prefix sums containing the given element (that is, do the operation -= 2 * a[i] on the segment [i; n - 1]).

    And for the function of checking a given number, it will be enough to take the minimum prefix sum, containing this element and check that it is greater than 2 * a[i] (that is, do the minimum search operation on the segment [i; n - 1] and compare it with 2 * a[i]).

    But I'm still not sure that this solution works correctly and it's worth to prove it strictly.

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

      Let's look at the operation of the algorithm using the same example. After building a segment tree, the numbers 4 7 9 will be stored in the leaves (these are prefix sums of an array). Now algorithm will try to make the two negative and it will succeed, because the minimum prefix sum on the segment [2; 2] is equal to nine, which is greater than 2 * 2. That's why segment tree will be updated to 4 7 5. Then algorithm will try to make the three negative, but it'll be unsuccessful, because minimum prefix sum on segment [1; 2] is equal to five, which is less than 3 * 2.

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

        Yes, may be there must be a much simpler solution to this.

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

          I think that this solution is the best, it's pretty easy and I believe that it's correct.

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

      Thanks for the careful observation, using lazy propagation , it can be managed under Nlog(N).

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

ig can be done with heaps

would be happy if someone finds some wrong testcase, cause greedy's are weird

void solve(){
    int n;cin>>n;
    vector<int> a(n);
    for(int&x:a) cin>>x;
    priority_queue<int> neg;
    neg.push(-1e18);
    priority_queue<int,vector<int>,greater<int>> pos;
    pos.push(1e18);
    int sum=0;
    int count=0;
    for(int i=0;i<n;i++){
        while(pos.top()<neg.top()){
            int x=pos.top();
            int y=neg.top();
            neg.pop();
            pos.pop();
            sum-=x;
            sum+=y;
            pos.push(y);
            neg.push(x);
        }
        if(sum-a[i]>0){
            sum-=a[i];
            neg.push(a[i]);
            count++;
        }else{
            pos.push(a[i]);
            sum+=a[i];
        }
    }
    cout<<count<<endl;
}
»
8 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it
let mut sum = 0;
let mut q = BinaryHeap::new();
for a in aa {
    q.push(a);
    sum -= a;
    if sum <= 0 {
        sum += 2 * q.pop().unwrap();
    }
}

println!("{}", q.len());
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u pls explain ur logic

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

      Here is the sum and queue after each element:

      adding 5: 5 []
      adding 2: 3 [2]
      adding 3: 6 [2]
      adding 5: 1 [5, 2]
      adding 2: 9 [2, 2]
      adding 3: 6 [3, 2, 2]
      3
      
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hi vstiff, what is the intuition behind this and why this works?

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

          I really don't know what to explain here, no math, no constructives, no observations. Just remember what you negated and revert if you negated too much.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Who else failed to solve this problem during Amazon OA test.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have saved your blog so i can comeback later (when i start learning dp and graph) so can you post the solution in comments so i can read it later? thanks.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

play genshin impact