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"; } } }
Program Python:
# 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))
Codechef Long Challenges
August Long Challenge 2021 Solutions
- Olympics Ranking
- Problem Difficulties
- Chef and Bulb Invention
- Array Filling
- Special Triplets
- Geometry 1
- Charge Scheduling
- Chef and Digits of Large Numbers
- Fat Hut
- Alternating LG Queries