Fat Hut solution codechef

Fat Hut solution codechef


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 AiAjAi≥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.

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 AiAiCiCiLiLiRiRi – 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

  • 1T1001≤T≤100
  • 1N1051≤N≤105
  • 1Ci1091≤Ci≤109 for each valid ii
  • 1LiAiRi1091≤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):

  • 1N1031≤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):

  • 1N1031≤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):

  • 1N1031≤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: Click here

Leave a Comment