# SEAPAIR - Editorial

### Panel Members

Problem Setter: Sergey Nagin
Problem Tester: Istvan Nagy
Editorialist: Sunny Aggarwal
Contest Admin: Praveen Dhinwa
Russian Translator: Sergey Nagin
Mandarin Translator: Hu Zecong
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora

Easy-Medium

### PREREQUISITES:

Mathematics, Sorting, Greedy.

### PROBLEM:

Given an integer A ( 0 <= A <= 10^{100} ) and N pairs of integers of the form (X, A/X) where X is an integer and A/X denotes the integer division of A by X.
It is also given that in no more than K such pairs the value of A/X is calculated incorrectly. Find the number of possible values of A modulo 10^9+7.

### QUICK EXPLANATION

For a given pair (X, A/X), if value of A/X is calculated correctly then the possible set of values that A can take according to this X can be represented
as a range from L to R where L = X * (A/X) and R = X * (A/X) + X - 1. We can represent all the given pairs as ranges (L, R) and as it given that in no
more than K such pairs the value of A/X is calculated incorrectly, answer will be the count of values that belongs to atleast N-K ranges.

### EXPLANATION

Let us represent i^{th} pair of integer as range L_i to R_i. Now, in order to calculate the number of integers that belongs to atleast N-K ranges, represent
a range as 2 separate pairs (L_i, 0) and (R_i, 1) where 0 denotes a marker for the starting of a range and 1 denotes a marker for ending of a range. Sort
all the 2*N pairs according to the first value.

Let us consider the following example to understand the solution better.

N = 3, K = 1

(X_1, A/X_1) = (30, 2)

(X_2, A/X_2) = (40, 2)

(X_3, A/X_3) = (50, 2)

Representing given pairs of integers as ranges:

(L_1, R_1) = (30 * 2, 30 * 2 + 30 - 1) = (60, 89) = (60, 0) and (89, 1) where 0 denotes starting marker and 1 denotes ending marker.

(L_2, R_2) = (40 * 2, 40 * 2 + 40 - 1) = (80, 119) = (80, 0) and (119, 1)

(L_3, R_3) = (50 * 2, 50 * 2 + 50 - 1) = (100, 149) = (100, 0) and (149, 1)

Sort the given ranges according to 1^{st} value.

(60, 0), (80, 0), (89, 1), (100, 0), (119, 1), (149, 1)

Now, maintain a counter to keep track for the number of ranges that an integer belongs to. Whenever a starting marker is encountered increment the counter variable by 1
and decrement it by 1 whenever an ending marker is encountered. Look at the below image to understand it better.

Now use this counter to calculate the count for the numbers that belongs to atleast N-K ranges. Look at the following fragment of code.

int mod = 1000000007;
int counter = 0; // initialising counter to 0
int previous = 0;
for(int i=0; i<2*N; i++) {
if(A[i].second == 0) {
counter ++; // incrementing counter on starting marker
if( counter == N - K ) {
previous = A[i].first; // value where we find our counter = N - K
}
} else {
counter --; // decrementing counter on ending marker
if( counter == N - K - 1 ) { // it means the value of counter upto this point
// was at least N - K
ans += A[i].first - previous + 1;
ans %= mod;
}
}
}


NOTE: If K = N then all the given values of A/X_i may be incorrect. In that case any value in the range \in [0, 10^{100}] can be a value for A. Therefore, the answer to
such case is (10^{100}+1) \% (10^9+7).

Please refer tester’s solution for better understanding of solution.

O(N\log(N))

### AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.
The tester’s solution can be found here.
The editorialist’s solution can be found here.

### SIMILAR PROBLEM

Geeks For Geeks

3 Likes

This is my first experience of writing editorials for Codechef. Please provide your suggestions to make them better.

2 Likes

This is how I did it: https://aleigorithms.wordpress.com/2015/11/22/sereja-and-pairs/

//