Same Score

Easy
0/40
0 upvote
Asked in company
MAQ Software

Problem statement

You are given 'N' pairs of integers representing the scores of Bob and Noddy at different points during their rugby match. Each pair ( A[i], B[i] ) represents Bob's score and Noddy's score respectively at the i-th observation.


Find the maximum possible number of times Bob and Noddy could have had equal scores (ties) during the entire match, assuming they started from (0, 0).


For Example : 
Let N = 3, and the score pairs be: (1, 2), (3, 2), (3, 4).
One possible sequence of goals could be:
(0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2) -> (3,2) -> (3,3) -> (3,4)
The ties occur at: (0,0), (1,1), (2,2), (3,3) = 4 times.
Therefore, the answer is '4'.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'N'.
The next 'N' lines each contain two integers, representing Bob's and Noddy's scores.
Output Format : 
Return the maximum possible number of ties between Bob and Noddy's scores.
Note : 
You don't need to print anything. Just implement the given function.
Constraints : 
1 <= N <= 10^5
0 <= A[i], B[i] <= 10^9
All score pairs are given in non-decreasing order
The last score pair denotes the final score of both players.

Time Limit: 1 sec
Sample Input 1 :
4
2 1
2 3
4 3
5 5
Sample Output 1 :
6
Explanation of sample input 1 :
Starting from (0,0), the score pairs are in non-decreasing order: (2,1), (2,3), (4,3), (5,5).
One optimal path could be:
(0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2) -> (2,3) -> (3,3) -> (4,3) -> (4,4) -> (5,4) -> (5,5)
The ties occur at: (0,0), (1,1), (2,2), (3,3), (4,4), (5,5) = 6 times.
Therefore, the answer is 6.
Sample Input 2 :
2
3 0
3 4
Sample Output 2 :
2
Hint

Focus on the difference between consecutive scores

Approaches (1)
Math

Approach:

  • Iterate through consecutive score observations.
  • For each interval, find the range of possible new tie scores.
    • The lower bound is the next integer after the last recorded tie and at least the maximum of the previous scores.
    • The upper bound is the minimum of the current scores.
    • The number of integers in this range contributes to the total ties.
  • Sum up all possible ties across all observations, including the initial tie at (0,0).

Algorithm:

  • Initialize a variable total_ties to 1.
  • Initialize a variable last_tie_score to 0.
  • Initialize variables prev_a and prev_b to 0, representing the starting scores.
  • Iterate through the given n score pairs using an index i from 0 to n - 1:
    • Let curr_a be Bob's score (A[i]) and curr_b be Noddy's score (B[i]) for the current observation.
    • Calculate the starting possible tie score start_x as the maximum of (last_tie_score + 1) and max(prev_a, prev_b).
    • Calculate the ending possible tie score end_x as min(curr_a, curr_b).
    • If start_x is less than or equal to end_x
      • Add 'end_x - start_x + 1' to total_ties.
      • Update last_tie_score to end_x, as this is the highest tie score reached in this interval.
    • Update prev_a to curr_a and prev_b to curr_b for the next iteration.
  • Return total_ties.
Time Complexity

O(N), where 'N' is the number of score observations.

We iterate through all 'N' score pairs once to calculate the maximum ties. Thus, the overall time complexity is of the order O(N).

Space Complexity

O(1).

We use only a constant amount of extra space. Thus, the overall space complexity is of the order O(1).

Code Solution
(100% EXP penalty)
Same Score
Full screen
Console