August Long Challenge Fat Hut Solution

Fat Hut Solution

There are NN breakfasts in the restaurant “Fat Hut” where the Chef works. The ii-th breakfast has an attractiveness AiAi and cost CiCi.

The Chef has noticed that nobody takes the jthjth breakfast if there exists at least one breakfast ii such that Ai≥AjAi≥Aj and Ci<CjCi<Cj.

In other words, if a breakfast is less attractive and more expensive than any of the other dishes, then nobody is interested in that breakfast.

The Chef will be happy if all the NN breakfasts have a chance to be taken. Unfortunately, the Chef has no power over prices. On the other hand, he can change the attractiveness of some breakfasts by some real number. However, after the changes, the attractiveness of the ithith breakfast must lie in the interval [Li,Ri][Li,Ri].

He would also like to change the attractiveness of the minimum number of breakfasts. Help the Chef do it.

Also See: August Long Challenge 2021 Solutions

Input Format

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• Each testcase contains N+1N+1 lines of input.
• The first line of each test case contains a single integer NN – number of breakfasts.
• NN lines follow. For each valid ii, the ithith of these lines contains four space-separated integers AiAi, CiCi, LiLi, RiRi – current attractiveness, cost, the minimal and maximal allowed attractiveness after change of ii-th breakfast.

Output Format

For each test case, output in a single line the minimum number of breakfasts the Chef should change so that all the NN breakfasts have a chance to be taken. Print "-1"(without quotes) if it is impossible to achieve the goal.

Constraints

• 1≤T≤1001≤T≤100
• 1≤N≤1051≤N≤105
• 1≤Ci≤1091≤Ci≤109 for each valid ii
• 1≤Li≤Ai≤Ri≤1091≤Li≤Ai≤Ri≤109 for each valid ii
• The sum of NN over all test cases does not exceed 105105
• The initial AiAi-s are pairwise distinct
• The initial CiCi-s are pairwise distinct

Subtasks

Subtask 1 (5 points):

• 1≤N≤1031≤N≤103
• Li=1Li=1 for each valid ii
• Ri=109Ri=109 for each valid ii
• 1<Ai<1091<Ai<109 for each valid ii

Subtask 2 (10 points):

• Li=1Li=1 for each valid ii
• Ri=109Ri=109 for each valid ii
• 1<Ai<1091<Ai<109 for each valid ii

Subtask 3 (10 points):

• 1≤N≤1031≤N≤103
• Ri=109Ri=109 for each valid ii
• Ai<109Ai<109 for each valid ii

Subtask 4 (20 points):

• Ri=109Ri=109 for each valid ii
• Ai<109Ai<109 for each valid ii

Subtask 5 (20 points):

• 1≤N≤1031≤N≤103

Subtask 6 (35 points):

• Original constraints

Sample Input 1 

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

Sample Output 1 

1
2

Explanation

Test case 11: Chef can change first breakfast’s attractiveness to 11. After that, all the 33 breakfasts have a chance to be taken. So the answer is 11.

Test case 22: Chef can change first breakfast’s attractiveness to 22 and third breakfast’s attractiveness to 2.52.5. There is no possible way to change the attractiveness of only one breakfast so that the condition is fulfilled. So the answer is 22.

Sample Input 2 

1
4
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

Sample Output 2 

0

Explanation

Test case 11: Everything is fine already, so Chef has no need to change anything, and the answer is 00.

Solution:

Program C++:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define  vi  vector<int>
#define  vii vector< pair<int,int> >
#define MOD 1000000007
struct dish{
    double att,cost,l,r;
};
bool cmp(dish a , dish b ){
    return a.cost<b.cost;
}
int main() {
   int t; cin>>t;
   while(t--){
       int n; cin>>n;
       dish arr[n];
       for(int i=0;i<n;i++){
           cin>>arr[i].att>>arr[i].cost>>arr[i].l>>arr[i].r;
       }
       sort(arr,arr+n,cmp);
       int flag = 1 ;
       for(int i=1;i<n;i++){
           dish prev = arr[i-1];
           dish cur = arr[i];
           if ( cur.r <= prev.l  ){
               flag=0;
               break;
           } 
       }
       if(flag==0){
           cout<<"-1\n";
       }
    //   vector< vector< pair< double ,int > > dp( 2, vector< pair< double ,int> >(n) );
      // 0 is unchanged 
      // 1 id changed 
      vector< pair<double,int> > dp[2];
      dp[0].resize(n); dp[1].resize(n);
      double delta = 0.0000001;
      dp[0][0].first = arr[0].att; dp[0][0].second = 0 ;
      dp[1][0].first = arr[0].l  ;  dp[1][0].second = 1;
      for(int i=1;i<n;i++){
          dish cur = arr[i];
          pair<double,int > op1 ,op2 ;
          op1.second = op2.second = 2*n ;
          op1.first = op2.first =  cur.att;
          
          if( dp[0][i-1].first < op1.first ){
              op1.second= dp[0][i-1].second;
          }
          if( dp[1][i-1].first < op2.first ){
              op2.second = dp[1][i-1].second;
          }
          
          if(op1.second == op2.second ){
              if( op1.first < op2.first ){
                  dp[0][i] = op1 ;
              }
              else{
                  dp[0][i] = op2 ;
              }
          }
          else if(op1.second < op2.second ){
                dp[0][i] =  op1 ;        
          }
          else{
              dp[0][i]=op2 ;
          }
          
         op1.second = op2.second = 2*n ;
          // changed 
          
          //talk tp last unchange
          double changed = max( dp[0][i-1].first+delta , cur.l ) ;
          if( dp[0][i-1].first < changed && changed <= cur.r ){
              op1.first = changed ;
              op1.second = dp[0][i-1].second+1;
          }
          changed = max( dp[1][i-1].first +delta , cur.l );
          if( dp[1][i-1].first < changed && changed <= cur.r ){
              op2.first = changed ;
              op2.second = dp[1][i-1].second+1;
          }
          if(op1.second == op2.second ){
              if( op1.first < op2.first  ){
                  dp[1][i] = op1 ;
              }
              else{
                  dp[1][i] = op2 ;
              }
          }
          else if( op1.second < op2.second ){
                dp[1][i] =  op1 ;        
          }
          else{
              dp[1][i]=op2 ;
          }
          
      }
      int ans;
      ans = min( dp[0][n-1].second, dp[1][n-1].second );
      if( ans == INT_MAX){
          cout<<"-1\n";
      }
      else{
          cout<<ans<<"\n";
      }
   }
}

# cook your dish here
import sys,os,io
input = sys.stdin.readline # for strings
# input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline # for non-strings

PI = 3.141592653589793238460
INF =  float('inf')
MOD  = 1000000007
# MOD = 998244353


def bin32(num):
    return '{0:032b}'.format(num)

def add(x,y):
    return (x+y)%MOD

def sub(x,y):
    return (x-y+MOD)%MOD

def mul(x,y):
    return (x*y)%MOD

def gcd(x,y):
    if y == 0:
        return x
    return gcd(y,x%y)

def lcm(x,y):
    return (x*y)//gcd(x,y)

def power(x,y):
    res = 1
    x%=MOD
    while y!=0:
        if y&1 :
            res = mul(res,x)
        y>>=1
        x = mul(x,x)
        
    return res
        
def mod_inv(n):
    return power(n,MOD-2)

def prob(p,q):
    return mul(p,power(q,MOD-2))    
  
def ii():
    return int(input())

def li():
    return [int(i) for i in input().split()]

def ls():
    return [i for i in input().split()]



# Python program to find
# length of longest
# increasing subsequence
# in O(n Log n) time

# Binary search (note
# boundaries in the caller)
# A[] is ceilIndex
# in the caller
def CeilIndex(A, l, r, key):

	while (r - l > 1):
	
		m = l + (r - l)//2
		if (A[m] >= key):
			r = m
		else:
			l = m
	return r

def LongestIncreasingSubsequenceLength(A, size):
	tailTable = [0 for i in range(size + 1)]
	len = 0 
	tailTable[0] = A[0]
	len = 1
	for i in range(1, size):
		if (A[i] < tailTable[0]):
			tailTable[0] = A[i]
		elif (A[i] > tailTable[len-1]):
			tailTable[len] = A[i]
			len+= 1
		else:
			tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i]
		
	return len



for t in range(ii()):
    t+=1
    n = ii()
    store = []
    for i in range(n):
        l = li()
        store.append([l[1] , l[0]])
    store.sort()
    a = []
    for i in range(n):
        a.append(store[i][1])
    # print(*a)
    ans = 0
    if 1 in a:
        ans = (a[0] != 1)
        a[0] = 1
        
        x = LongestIncreasingSubsequenceLength(a,n)
        print( ans + n - x)

    else:
        print( n - LongestIncreasingSubsequenceLength(a , n))