Solution:

#include<bits/stdc++.h>
using namespace std;
 
 
int main(){
 int t,a,b,x;
 cin >> t;
 while(t--){
  cin >> a >> b;
  
  int A[a],B[b];
  for(int i=0;i<a;i++) scanf("%d", &A[i]);
  
  scanf("%d", &B[0]);
  for(int i=1;i<b;i++){
   scanf("%d", &x);
   B[i] = max(B[i-1],x);
  }
  
  int M=-1,id=-1;
  for(int i=0;i<a;i++){
   x = upper_bound(B,B+b,A[i]) - B;
   if(x > M){
    M = x;
    id = i;
   }
  }
  cout << id << endl;
 }
 return 0;
}

The problem you are tackling is about determining which prince can cross the maximum number of hurdles in a race, given each prince's jumping strength and the height of the hurdles. If two or more princes cross the same number of hurdles, the prince with the smallest ID should be declared the winner.

Problem Breakdown

You are given:

  1. N: The number of princes.
  2. K: The number of hurdles.
  3. A[i]: The jumping strengths of the princes.
  4. D[i]: The heights of the hurdles.

For each test case:

  • You need to determine how many hurdles each prince can cross based on their jumping strength.
  • The prince who crosses the maximum number of hurdles is the winner. In the event of a tie (multiple princes can cross the same number of hurdles), the prince with the lowest ID wins.

Approach

1. Understanding the Inputs and Outputs

  • Input:
    • First, we have the number of test cases t.
    • For each test case:
      • We have two integers: N (number of princes) and K (number of hurdles).
      • Then an array A of size N which contains the jumping strengths of the princes.
      • Another array D of size K which contains the height of the hurdles.
  • Output:
    • For each test case, output the ID of the prince who can cross the maximum number of hurdles.

2. Steps to Solve the Problem

  1. Read Input:

    • For each test case, read the number of princes and the number of hurdles.
    • Read the jumping strength array A for the princes.
    • Read the hurdle height array D.

  2. Preprocess Hurdles Array:

    • To efficiently determine how many hurdles a prince can cross based on his jumping strength, you can preprocess the hurdle heights.
    • Sort the hurdles array D. Sorting will allow us to use binary search to quickly determine how many hurdles a prince can cross.

  3. Determine Maximum Number of Hurdles Each Prince Can Cross:

    • For each prince, using their jumping strength A[i], use the upper_bound function on the sorted hurdles array D to determine how many hurdles they can cross. This function returns the first index in the array D where the hurdle height is strictly greater than the prince's jumping strength. This index gives us the number of hurdles that the prince can cross.

  4. Track the Winner:

    • Keep track of the prince who crosses the most hurdles. If two princes cross the same number of hurdles, choose the one with the smaller ID.

  5. Edge Case Considerations:

    • All hurdles are lower than the smallest prince’s jumping strength.
    • All hurdles are higher than the highest prince’s jumping strength.
    • Edge cases with small values of N and K, like N=1 or K=1.

3. Optimized Algorithm

To make the solution efficient, considering the constraints (N and K can be as large as 10610^6), we focus on using an efficient approach with sorting and binary search.

Here’s a step-by-step explanation of the code:

Code Walkthrough


#include<bits/stdc++.h>
using namespace std;

int main() {
    int t, N, K, x;
    cin >> t;
    
    while (t--) {
        cin >> N >> K;

        vector<int> A(N), D(K);

        // Reading the jumping strengths of princes
        for (int i = 0; i < N; i++) {
            cin >> A[i];
        }

        // Reading the heights of hurdles
        for (int i = 0; i < K; i++) {
            cin >> D[i];
        }

        // Sort the hurdle heights to allow binary search
        sort(D.begin(), D.end());

        int maxHurdles = -1; // Track the maximum number of hurdles a prince can cross
        int winnerId = -1;   // Track the ID of the winning prince

        // For each prince, determine how many hurdles they can cross
        for (int i = 0; i < N; i++) {
            // upper_bound gives us the first index where the value in D is strictly greater than A[i]
            // Therefore, the number of hurdles the prince can cross is this index
            int hurdlesCrossed = upper_bound(D.begin(), D.end(), A[i]) - D.begin();
            
            // If this prince crosses more hurdles, or crosses the same but has a smaller ID, update winner
            if (hurdlesCrossed > maxHurdles) {
                maxHurdles = hurdlesCrossed;
                winnerId = i;
            }
        }

        // Output the ID of the winning prince
        cout << winnerId << endl;
    }
    
    return 0;
}

Explanation of the Code

  1. Input Reading:

    • The number of test cases is read, and for each test case, we read the number of princes (N) and the number of hurdles (K).
    • Arrays A and D are filled with jumping strengths and hurdle heights, respectively.

  2. Sorting the Hurdle Heights:

    • The hurdle array D is sorted to allow efficient look-up using binary search. Sorting takes O(Klog⁡K)O(K \log K).

  3. Binary Search Using upper_bound:

    • For each prince, we calculate how many hurdles they can cross using upper_bound. This function performs a binary search to find the first element in the hurdles array that is greater than the prince’s jumping strength.The problem you are tackling is about determining which prince can cross the maximum number of hurdles in a race, given each prince's jumping strength and the height of the hurdles. If two or more princes cross the same number of hurdles, the prince with the smallest ID should be declared the winner.

      Problem Breakdown

      You are given:

      1. N: The number of princes.
      2. K: The number of hurdles.
      3. A[i]: The jumping strengths of the princes.
      4. D[i]: The heights of the hurdles.

      For each test case:

      • You need to determine how many hurdles each prince can cross based on their jumping strength.
      • The prince who crosses the maximum number of hurdles is the winner. In the event of a tie (multiple princes can cross the same number of hurdles), the prince with the lowest ID wins.

      Approach

      1. Understanding the Inputs and Outputs

      • Input:
        • First, we have the number of test cases t.
        • For each test case:
          • We have two integers: N (number of princes) and K (number of hurdles).
          • Then an array A of size N which contains the jumping strengths of the princes.
          • Another array D of size K which contains the height of the hurdles.
      • Output:
        • For each test case, output the ID of the prince who can cross the maximum number of hurdles.

      2. Steps to Solve the Problem

      1. Read Input:

        • For each test case, read the number of princes and the number of hurdles.
        • Read the jumping strength array A for the princes.
        • Read the hurdle height array D.

      2. Preprocess Hurdles Array:

        • To efficiently determine how many hurdles a prince can cross based on his jumping strength, you can preprocess the hurdle heights.
        • Sort the hurdles array D. Sorting will allow us to use binary search to quickly determine how many hurdles a prince can cross.

      3. Determine Maximum Number of Hurdles Each Prince Can Cross:

        • For each prince, using their jumping strength A[i], use the upper_bound function on the sorted hurdles array D to determine how many hurdles they can cross. This function returns the first index in the array D where the hurdle height is strictly greater than the prince's jumping strength. This index gives us the number of hurdles that the prince can cross.

      4. Track the Winner:

        • Keep track of the prince who crosses the most hurdles. If two princes cross the same number of hurdles, choose the one with the smaller ID.

      5. Edge Case Considerations:

        • All hurdles are lower than the smallest prince’s jumping strength.
        • All hurdles are higher than the highest prince’s jumping strength.
        • Edge cases with small values of N and K, like N=1 or K=1.

      3. Optimized Algorithm

      To make the solution efficient, considering the constraints (N and K can be as large as 10610^6), we focus on using an efficient approach with sorting and binary search.

      Here’s a step-by-step explanation of the code:

      Code Walkthrough


      #include<bits/stdc++.h>
using namespace std;

int main() {
    int t, N, K, x;
    cin >> t;
    
    while (t--) {
        cin >> N >> K;

        vector<int> A(N), D(K);

        // Reading the jumping strengths of princes
        for (int i = 0; i < N; i++) {
            cin >> A[i];
        }

        // Reading the heights of hurdles
        for (int i = 0; i < K; i++) {
            cin >> D[i];
        }

        // Sort the hurdle heights to allow binary search
        sort(D.begin(), D.end());

        int maxHurdles = -1; // Track the maximum number of hurdles a prince can cross
        int winnerId = -1;   // Track the ID of the winning prince

        // For each prince, determine how many hurdles they can cross
        for (int i = 0; i < N; i++) {
            // upper_bound gives us the first index where the value in D is strictly greater than A[i]
            // Therefore, the number of hurdles the prince can cross is this index
            int hurdlesCrossed = upper_bound(D.begin(), D.end(), A[i]) - D.begin();
            
            // If this prince crosses more hurdles, or crosses the same but has a smaller ID, update winner
            if (hurdlesCrossed > maxHurdles) {
                maxHurdles = hurdlesCrossed;
                winnerId = i;
            }
        }

        // Output the ID of the winning prince
        cout << winnerId << endl;
    }
    
    return 0;
}

      Explanation of the Code

      1. Input Reading:

        • The number of test cases is read, and for each test case, we read the number of princes (N) and the number of hurdles (K).
        • Arrays A and D are filled with jumping strengths and hurdle heights, respectively.

      2. Sorting the Hurdle Heights:

        • The hurdle array D is sorted to allow efficient look-up using binary search. Sorting takes O(Klog⁡K)O(K \log K).

      3. Binary Search Using upper_bound:

        • For each prince, we calculate how many hurdles they can cross using upper_bound. This function performs a binary search to find the first element in the hurdles array that is greater than the prince’s jumping strength.