SEAPAIR - Editorial

ma5termind · November 17, 2015, 3:06am

PROBLEM LINK

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

DIFFICULTY:

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.
alt text

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.

COMPLEXITY

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.