PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: perucmpamypa
Tester: Miten Shah
Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Longest Increasing Subsequence
PROBLEM
Given the description of N breakfast, where i-th breakfast is described by tuple (A_i, C_i, L_i, R_i) denoting that i-th breakfast has attractiveness A_i, cost C_i, and the attractiveness of this breakfast should remain between range [L_i, R_i] after all operations.
We want to make sure there’s no pair (i, j) such that A_i \geq A_j and C_i \lt C_j, as no one would choose breakfast j then.
You are allowed to change the attractiveness of the minimum number of breakfasts while keeping them within their attractiveness range.
QUICK EXPLANATION
- Sort the breakfasts by cost, so the problem becomes to make the sequence of attractiveness strictly increasing while keeping the maximum number of breakfasts unchanged.
- Process the elements one by one, and try to maintain active subsequences of unchanged elements.
- We can maintain B_i denoting the minimum attractiveness x, such that there exists a subsequence of original attractiveness of breakfasts of length i with its last element x.
- When processing the current breakfast, all B_i \geq R are discarded, as the current breakfast cannot be chosen to get a strictly increasing sequence by extending those.
- If there exists any breakfast having R_i \leq max_{j \lt i} L_j, then the answer is not possible in that case.
EXPLANATION
Let’s see what it means to remove all pairs (i, j) such that A_i \geq A_j and C_i \lt C_j. This implies that if for some pair (i, j), if C_i \lt C_j, then A_i \lt A_j, otherwise if C_i \gt C_j, then A_i \gt A_j. We shall never have C_i = C_j, as costs are pairwise distinct.
As the cost of breakfasts remains the same throughout, we can sort the breakfasts in increasing order of cost. The above condition reduces to changing attractiveness of breakfasts so that A_i form a strictly increasing sequence.
After sorting, now the problem reduces to, Given (A_i, L_i, R_i) for N breakfasts, change the attractiveness of minimum number of breakfasts such that A_i forms a strictly increasing sequence, and L_i \leq A_i \leq R_i for all i.
Simplified problem
Let’s assume L_i = -\infin and R_i = \infin for all i. We are given just A_i for each breakfast, and we need to change the minimum number of breakfasts, so as to make A_i into a strictly increasing sequence.
We can view the problem from changing the minimum number of elements to preserving the maximum number of elements of the original sequence A, such that we can replace the remaining elements to form an increasing sequence.
This problem is well known, we need to change N - X elements, where X is the longest increasing subsequence of the given sequence A.
Original problem
The original problem poses additional constraint on Simpler problem, that L_i \leq A_i \leq R_i shall hold for all i.
If there exists any pair (i, j) where i \lt j and L_i \geq R_j, then it is simply not possible to make A into strictly increasing sequence, as A_i \geq A_j shall hold. We can see that it is possible in all other cases to make A into an increasing sequence.
Proof
One way is to change A_i = max(A_{i-1} + \epsilon, L_i), leading to A being an increasing sequence.
We can just maintain a maximum of L_i to check this condition.
Now, we need to minimize the number of changes, or maximize the number of A_i not changed.
Let’s use the idea from the simpler problem. Process each A_i one by one, and maintain active lists. Specifically, we maintain B_i to denote the minimum attractiveness, such that there exists a subsequence of already processed breakfasts, which has length i, and the last element of that subsequence is B_i.
We need to figure out the impact of processing the current A_i on the B array. Similar to finding LIS, we can see that we must find the smallest p such that B_p \geq A_i. It means that we can extend the subsequence of length p-1 by adding A_p at the end, to get an increasing subsequence of length p with the last element A_p, which is smaller than B_p. So, we replace B_p with A_i.
In case there’s no such p, then all active lists have B_p \lt A_i, so we can extend any of them to get a larger subsequence. If we had C subsequence before the current element, we now have another active list of length C+1 with the last element A_p.
The above logic forms the core of finding LIS, so it is explained in detail in the above link as well, in case of any confusion.
An important observation is that B is always a strictly increasing
Now, we are only left with the situation, that some A_i might get replaced with value \gt R_i. Let’s assume we have found LIS of A and index x is not included, but index u and v are included such that u \lt x \lt v and there’s no element included in the range [u+1, v-1].
Then A_u \gt A_x \gt A_v shall hold. It may happen that A_u \geq R_x, which may lead to A_x \gt R_x$ which voilates our condition.
This happened because when processing x-th element, we let active sequence ending at A_u continue, even though A_u \geq R_x.
Hence, to maintain A_i \leq R_i, we shall discard all active lists B_p such that B_p \geq R_i when processing i-th element. Since B is increasing, this means removing a (possibly empyty) suffix of B.
Hence, we have taken care of all conditions except one. If there’s some pair (i, j) such that L_j \geq A_i for j \lt i, then we cannot keep A_i as part of subsequence, so we don’t add A_i to our active lists.
TIME COMPLEXITY
Sorting takes O(N*log(N)). Finding an appropriate position in B takes O(log(N)) every time which may happen at most N times. There are at most N additions in B, and thus at most N deletions.
This leads to the overall complexity of O(N*log(N)) per test case.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+1;
struct breakfast{
int c, l, a, r;
bool operator<(const breakfast& b){
return c < b.c;
}
};
int t, n;
breakfast b[N];
int main(){
ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
cin >> t;
while(t--){
cin >> n;
for(int i = 0; i < n; ++i)
cin >> b[i].a >> b[i].c >> b[i].l >> b[i].r;
sort(b, b+n);
vector<int> v;
int max_l = 0;
bool fail = false;
for(int i = 0; i < n; ++i){
int l, a, r;
tie(l, a, r) = tie(b[i].l, b[i].a, b[i].r);
if(r <= max_l){
cout << "-1\n";
fail = true;
break;
}
while(!v.empty() && v.back() >= r)
v.pop_back();
if(a > max_l){
int pos = upper_bound(v.begin(), v.end(), a) - v.begin();
if(pos == v.size())
v.push_back(a);
else v[pos] = a;
}
max_l = max(max_l, l);
}
if(!fail)
cout << n - v.size() << "\n";
}
}
Tester's Solution
// created by mtnshh
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define err() cout<<"--------------------------"<<endl;
#define errA(A) for(auto i:A) cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define ft first
#define sd second
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
#define endl "\n"
const ll INF = 1e15;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cerr << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const int maxt = 100, maxn = 1e5;
const int maxA = 1e9;
const ll N = 100005;
vector<pair<ll,pair<ll,pll>>> v;
void solve(ll n){
v.clear();
set<ll> A, C;
rep(i,0,n){
ll a = readIntSp(1, maxA), c = readIntSp(1, maxA), l = readIntSp(1, maxA), r = readIntLn(1, maxA);
v.pb({c, {a, {l, r}}});
assert(a >= l);
assert(r >= a);
A.insert(a);
C.insert(c);
}
assert(A.size() == n);
assert(C.size() == n);
sort(all(v));
ll mx_last = 0;
V d;
d.pb(-INF);
rep(i,0,n){
ll a = v[i].sd.ft, l = v[i].sd.sd.ft, r = v[i].sd.sd.sd;
if(r <= mx_last){
cout << -1 << endl;
return;
}
while(d.size() and d.back() >= r)
d.pop_back();
ll j = upper_bound(all(d), a) - d.begin();
if(a > mx_last){
if(j == d.size())
d.pb(a);
else
d[j] = a;
}
mx_last = max(mx_last, l);
}
cout << n - d.size() + 1 << endl;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll t = readIntLn(1, maxt);
ll tot_n = 0;
while(t--){
ll n = readIntLn(1, maxn);
tot_n += n;
solve(n);
}
assert(tot_n <= maxn);
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class FATHUT{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
int[][] A = new int[N][];
for(int i = 0; i< N; i++)A[i] = new int[]{ni(), ni(), ni(), ni()};
//Sorting by cost
Arrays.sort(A, (int[] i1, int[] i2) -> Integer.compare(i1[1], i2[1]));
int[] LIS = new int[1+N];
//LIS[i] denotes the smallest element x, such that there exists
//- an increasing subsequences of attractiveness of processed breakfasts
//- length i
//- last element x
int sz = 0, Lmax = -1;
for(int i = 0; i< N; i++){
int x = A[i][0], L = A[i][2], R = A[i][3];
if(R <= Lmax){
pn(-1);
return;
}
while(sz > 0 && LIS[sz] >= R)sz--;
if(x <= Lmax)continue;
int lo = 1, hi = sz;
while (lo < hi){
int mid = lo + (hi-lo)/2;
if(LIS[mid] >= x)hi = mid;
else lo = mid+1;
}
if(hi > 0 && LIS[hi] >= x)LIS[hi] = x;
else LIS[++sz] = x;
Lmax = Math.max(Lmax, L);
}
pn(N-sz);
}
static void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
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 FATHUT().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. Suggestions are welcomed as always. 
