PROBLEM LINK:
Setter: Rami
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Greedy, Observation, flows.
PROBLEM:
Given N basket of candies where ith basket contains A_i candies and M friends. For each friend, you want to offer him candy, but the friend accepts candies, if and only if the candy is either from first L_i baskets or from last R_i basket where L_i and R_i is given for each friend.
Find out the maximum number of friends you can make happy by giving them candies.
EXPLANATION
Let’s consider a simpler generic solution by modeling this problem as a flow problem. We have one source and one sink, N nodes for baskets and M nodes for friends, and following flows.
- Each friend node is connected to the source with capacity one. (One being the number of candies he can eat).
- Each basket node is connected to sink with a capacity equal to the number of candies in that basket.
- For each friend node, it is connected to the first L_i basket nodes and last R_i basket nodes.
We can see, there can be nearly N*M edges for the third category, making this solution too slow to pass. Even if we build a segment tree style flow solution, this solution is too slow to pass. But it’s good to understand it anyways.
Let’s consider a simple problem first. Assume R_i = 0 for all friends.
Now, it is easy to see that if we want to give candies to the maximum number of friends, we should start giving candies greedily starting from the friend with lowest L_i, since this is the first friend to miss candy if we offer candies to others first.
Consider an example with two friends, first having L_i = 1 and other having L_i = 2 and two baskets, each containing one candy. Now, we can see that candy from the first basket is acceptable to both, while candy from the second basket is acceptable to the only second friend. So, the optimal strategy is to give candies from leftmost non-empty basket to the ones with the lowest L_i and so on.
Let’s come back to the original problem.
Assume we are offering candy in order of increasing L_i as above, and whenever friend doesn’t accept candy, we make a note to offer him candy while checking on the basis of R_i.
Seems optimal, a probable solution, but is wrong. Yes, it followed the same principle, but there is a flaw.
Consider the following example.
4 2
1 0 1 0
1 2
2 1
In this example, we offered candy to the first friend from the first basket, leaving the second friend to be offered candy when we are offering candies from the right side. But, as we see, R_1 > R_2, so having to offer candy to the first friend would have been more beneficial to us. In this example, our greedy gives 1 as the answer, while we can easily satisfy both friends.
Let us rethink now.
We went wrong when we had already given candy to some friend with small L_i but large R_i, and later fell short to offer candy to a friend with large L_i but small R_i.
But friends means sharing, right?
Let us assume, the First friend, when saw that second friend didn’t get candy, gifted him his candy since he knows he has a better chance to get candy, since having larger R_i.
Let’s us modify our greedy now. We shall offer candies to friends in the same order, but whenever we find a friend unable to get candy, the friend who already has candy and has largest R_i if have R_i greater than that of the current friend, He offers him candy. This way, in the second pass, we shall have friends with larger R_i than before, and we can see, that we have improved for the better, and this is optimal.
I’ll add a concrete proof later.
For example, let’s assume S_{in} is the source, S_{out} is the sink, A and B denote two friends with L_i = 1, R_i = 3 and L_i = 2 and R_i = 2 respectively and four nodes X_i denoting node representing ith basket.
In the first case, There shall be flow S_{in} > A -> N_1 -> S_{out} and cycle in residual graph S_{in} -> B -> N_1 -> A appears with flow 1 unit. Canceling this cycle is basically the friend A gifting candy to friend B, hence, this strategy works same way as cycle cancelling theorem.
Now, we know the strategy to offer candies, implementation can be handled using 2 multisets, first multiset containing R_i for friends who have candy, and second multiset for friends who did not get candy when offering on basis of L_i.
TIME COMPLEXITY
Time complexity is O(N+M*logM) due to sorting and multiset operations.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sc second
#define fr first
using namespace std;
const int M = 1e6+100;
int n,m;
pii l[M];
bool take[M];
int candy[M];
int main() {
int t;
cin>>t;
while(t--){
cin>>n>>m;
for(int i=0;i<n ;i++)scanf("%d",&candy[i]);
for(int i=0 ;i <m ;i ++){
scanf("%d%d",&l[i].fr,&l[i].sc);
l[i].fr--;
l[i].sc = n-l[i].sc+1;
l[i].sc--;
take[i] = 0;
}
sort(l,l+m);
//cout<<endl;
//for(int i=0 ;i <m ;i ++)printf("%d %d\n",l[i].fr,l[i].sc);
int pr = 0,r=0;
ll s =0;
set<pii>st;
for(int i=0 ;i < m ;i++){
while(pr <= l[i].fr){
s+=candy[pr];
pr++;
}
if(s){
s--;
take[i] = 1;
r++;
}
}
int r1 = r;
for(int i=0 ;i < n ;i ++){
while(r1 && candy[i]){
r1--;
candy[i]--;
}
}
vector<int>tryR;
for(int i=0;i <m ; i++){
st.insert({l[i].sc,i});
if(!take[i]){
tryR.push_back((st.begin())->fr);
st.erase(st.begin());
}
}
sort(tryR.begin(),tryR.end());
reverse(tryR.begin(),tryR.end());
s =0 ;
pr = n-1;
for(int i=0 ;i < tryR.size() ; i++){
while(pr >= tryR[i]){
s += candy[pr];
pr--;
}
if(s){
s--;
r++;
}
}
printf("%d\n",r);
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int a[1234567],l[1234567],r[1234567];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
int i;
f(i,1,n+1){
cin>>a[i];
}
a[0]=1;
a[n+1]=1;
vii vec;
rep(i,m){
cin>>l[i]>>r[i];
vec.pb(mp(l[i],i));
}
sort(all(vec));
int st=1;
multiset<int> seti;
vi lef;
multiset<int>::iterator it;
int gg=0;
rep(i,m){
while(a[st]==0)
st++;
seti.insert(r[vec[i].ss]);
if(st<=vec[i].ff){
a[st]--;
gg++;
}
else{
it=seti.end();
it--;
lef.push_back(*it);
seti.erase(it);
}
}
sort(all(lef));
st=0;
rep(i,lef.size()){
while(a[n-st]==0)
st++;
if(st+1<=lef[i]){
//cout<<st<<" "<<a[n-st]<<endl;
a[n-st]--;
gg++;
}
}
cout<<gg<<endl;
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class FRICAN{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), m = ni();
int[] basket = new int[n];
for(int i = 0; i< n; i++)basket[i] = ni();
Person[] p = new Person[m];
for(int i = 0; i< m; i++)p[i] = new Person(i, ni()-1, n-ni());
Arrays.sort(p, (Person p1, Person p2) -> Integer.compare(p1.left, p2.left));
MyTreeSet<Integer> AllRightRange = new MyTreeSet<>();
int ptr = 0, ans = 0;
int[] pendingRightRange = new int[m];int cur = 0;
for(int i = 0; i< m; i++){
while(ptr < n && basket[ptr] == 0)ptr++;
AllRightRange.add(p[i].right);
if(ptr <= p[i].left){
basket[ptr]--;
p[i].done = true;
ans++;
}else{
int x = AllRightRange.first();
AllRightRange.remove(x);
pendingRightRange[cur++] = x;
}
}
ptr = n-1;
Arrays.sort(pendingRightRange, 0, cur);
for(int i = cur-1; i>= 0; i--){
while(ptr >= 0 && basket[ptr] == 0)ptr--;
if(ptr >= pendingRightRange[i]){
ans++;
basket[ptr]--;
}
}
pn(ans);
}
class Person{
int ind, left, right;
//left -> [0, left]
//right -> [right, N-1]
boolean done;
public Person(int i, int l, int r){
ind = i;
left = l;
right = r;
done = false;
}
}
//Ordered MultiSet
class MyTreeSet<T>{
private int size;
private TreeMap<T, Integer> map;
public MyTreeSet(){
size = 0;
map = new TreeMap<>();
}
public int size(){return size;}
public int dsize(){return map.size();}
public boolean isEmpty(){return size==0;}
public void add(T t){
size++;
map.put(t, map.getOrDefault(t, 0)+1);
}
public boolean remove(T t){
if(!map.containsKey(t))return false;
size--;
int c = map.get(t);
if(c==1)map.remove(t);
else map.put(t, c-1);
return true;
}
public int freq(T t){return map.getOrDefault(t, 0);}
public boolean contains(T t){return map.getOrDefault(t,0)>0;}
public T ceiling(T t){return map.ceilingKey(t);}
public T floor(T t){return map.floorKey(t);}
public T first(){return map.firstKey();}
public T last(){return map.lastKey();}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new FRICAN().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 