PROBLEM LINK:
Author: Sayan Poddar
Tester: Abhishek Paul
Editorialist: Sayan Poddar
DIFFICULTY:-
HARD.
PREREQUISITES:
DP, Priority Queue
PROBLEM:
Output a single integer, the maximum number of chakras one can absorb without dieing.
EXPLANATION:
We process the chakras from left to right. At the same time, we maintain the list of chakras we have taken so far. When processing chakra i, if we can absorb i without dying, then we absorb it. Otherwise, if the most negative chakra we’ve taken is more negative than chakra i, then we can swap out chakra i for that chakra. To find the most negative chakra we’ve taken, we can maintain the values of all chakras in a minimum priority_queue. This runs in O(nlogn) as well.
To prove that this works, let’s consider best solution where we take exactly k chakras. The solution involves taking the k largest values in our priority queue. Then when considering a new chakra, we should see whether swapping out the new chakra for the kth largest chakra will improve the answer.
Since the priority queue is strictly decreasing, there will be a cutoff K, where for k at most K, the answer is not affected, and for larger than K, we swap out the kth largest potion. It turns out this process is equivalent to inserting the new chakras value into the priority_queue. For those positions at most K, they are not affected. For the chakras larger than K, the elements get pushed back one space, meaning that the smallest element is ignored.
This can also be seen as an efficient way to transition from one layer of the dp table to the next.
SOLUTIONS:
Setter's Solution: Python
import heapq as h
for _ in range(int(input())):
n=int(input())
a = list(map(int, input().split()))
l=[]
x=0
for i in range(n):
x=x+a[i]
h.heappush(l,a[i])
if x<0:
x=x-h.heappop(l)
print(len(l))
Tester's Solution: Java
import java.util.*;
class Sept1
{
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int t=Integer.parseInt(sc.nextLine());
while(t>0)
{
int n=Integer.parseInt(sc.nextLine());
String s[]=sc.nextLine().split(" ");
int a[]=new int[n];
for(int i=0;i<n;i++)
{
a[i]=Integer.parseInt(s[i]);
}
PriorityQueue<Integer> p=new PriorityQueue<>();
int sum=0;
int count=0;
for(int i=0;i<=n-1;i++)
{
sum=sum+a[i];
p.add(a[i]);
count++;
if(sum<0)
{
int k= p.remove();
sum=sum+(-1)*k;
count--;
}
}
System.out.println(count);
t--;
}
}
}