FATHUT - Editorial

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. :slight_smile:

1 Like
  • Sort all on basis of C in decreasing and iterate on it.

  • Let dp[i] - maximum number of breakfasts’ attractiveness we can keep still if we keep ith breakfast’s attractiveness still ( ith in sorted C list )

  • Ans will be n - max( All dp[i] ) ( min changes = total - max Non-changes )

  • Define possible(x, i) → bool value telling if it’s possible to keep ith attractiveness at x and still get some answer.

  • Basically All afterL < x and all beforeR > x ( afterL is L of intervals coming afterwards in C list )
    O(1)

Calculating dp[i] ( Simple ) :

  • Check if given we can move current attractiveness, can we get some answer?? ( basic checks of all afterL and beforeR with currentL and currentR) . If Not then set dp[i] = n + 1 which will give result as -1 in end.

  • Check if we can make current Attractiveness still i.e. possible(A[i], i) = true and set extra = 1 else extra = 0

  • dp[i] = max(dp[j] where A[j] > A[i] ) + extra ( We can only make those j still which have their A[j] > A[i] , given we are making A[i] still )

  • If A[i] would have been < say 10^5 , getting above result is simply rangeMax(A[i], last) but since A[i] are distinct, hence we can coordinate compress and achieve same result O(Logn)

  • Final ans = n - max(All dp[i]) :slight_smile:

Clean Submission: CodeChef: Practical coding for everyone

3 Likes

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.

I have a confusion. Let me know if i am missing something.

For the test case,

4
2 3 1 1000000
4 5 1 1000000
3 4 1 1000000
5 2 1 1000000

Sorting by C gives,

A → 5 2 3 4
C → 2 3 4 5

A is not a strictly increasing sequence but it seems this testcase requires 0 changes.

5, 2 is fine as there is no < C before it with A > 5 and so on.

You are messing with the requirements, all the breakfasts except <5,2> would not be picked since their cost Is higher but attractiveness is not

1 Like

Nevermind. Thanks. Feeling really bad as I was working with the wrong requirements (thinking, jth breakfast only cares about breakfasts before it). I read Ai≥Aj as, i also needs to be less than j. And this converted the problem into a relatively more difficult problem. (Wondering what would be the efficient solution if we had this constraint) :neutral_face:

Could someone please explain why the setter’s and tester’s solutions give different outputs for the following testcase?

1
5
9 1 6 9
8 2 4 9
5 3 5 7
7 4 7 10
10 5 10 10

@taran_1407 @mtnshh could someone please reply or do you all believe in just creating a problem, publishing the editorial late even though you had 10 days to prepare it, and then forgetting about it altogether?

1 Like

The wrong version of setter’s solution was added here, which is corrected now. Now both submissions give same output.

Sorry for the inconvenience there.

The people working to create and test problem are also humans with responsibilities, college students or working professionals. It’s simply not possible to immediately follow up for all stuff immediately.

@taran_1407 Is there a solution when all A[i] after the changes must also be integers?

Hi @yami27
I think we can modify the above solution as follows

  • Just before considering each breakfast, increment all B_i by 1. This can be done using a constant delta d such that B_p+d denote actual attractiveness. This would lead to replacing B_p with B_p+d everywhere. Before considering each breakfast, we just need to increment d by one.
  • Instead of discarding B_p with B_p+d \geq A_i, discard ones with B_p+d \gt A_i

I think this one should work, but I haven’t tested it. Maybe try running a simulation with the above modifications with brute force (trying all subsequences to keep, and choosing rest optimally)

1 Like

1
4
1 1 1 3
2 2 1 3
2 3 1 3
3 4 1 3
Here the answer returned by the setters code is 0. However, it is not possible to make a change here so the answer returned should be -1. Here A_2>=A_3 and C_2<C_3. Incase any real number can be added or subtracted, the answer should still be 1.
@taran_1407 request you to please take this test cases into consideration and let me know where I went wrong, or the question is missing some small detail.

Constraints mention pairwise distinct A_i, so your test cannot appear in test data.