PROBLEM LINK:
Setter: Soumyadeep Pal
Tester: Samarth Gupta
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
EASY
PREREQUISITES:
Binary search
PROBLEM:
We are given an array A of N integers. We need to find the number of pairs (i,j) where 1 \leq i,j \leq N and L \leq CONC(A_i,A_j) \leq R . Here CONC(A_i,A_j) is defined as the number obtained by concatination of A_i and A_j.
QUICK EXPLANATION:
-
Let len(x) be the number of digits in x.
-
Get the mathematical expression CONC(A_i,A_j) in terms of A_i, A_j and len(A_j). We will get CONC(A_i,A_j) = A_i \cdot 10^{len(A_j)} + A_j.
-
Iterate over j from 1 to N, fix A_j and then compute total number of A_i possible from the derived mathematical expression and the bounds mentioned in the problem statement. Then, we will get that A_i must be present in some range which can be solved by sorting the array and performing binary search.
EXPLANATION:
Let us first sort the array A.
Let len(x) be the number of digits in the number x. For example, len(12345) = 5.
Let us try to formulate CONC(x,y) in terms x, y and len(y). CONC(x, y) is nothing but the number xy. This can be written as x \cdot 10^{len(y)} + y. For example, if x=123 and y=45,
xy = 12345 = 123 \cdot 10^2 +45.
Now, the problem can be solved simply by fixing A_j. From our conditions we have,
CONC(A_i,A_j) \leq R
\implies A_i \cdot 10^{len(A_j)} + A_j \leq R
\implies A_i \cdot 10^{len(A_j)} + A_j \leq R
\implies A_i \cdot 10^{len(A_j)} \leq R - A_j
\implies A_i \leq \frac{R - A_j}{10^{len(A_j)}}
Similarly, from the condition involving L, we get A_i \geq \frac{L - A_j}{10^{len(A_j)}}.
Therefore, we can solve the problem by simply iterating over j from 1 to N, find the range where our A_i could be i.e, \frac{L - A_j}{10^{len(A_j)}} \leq A_i \leq \frac{R - A_j}{10^{len(A_j)}}. Then, we need to find the total number of elements within this range which could be done simply by performing binary search.
TIME COMPLEXITY:
O(N\log N) for each testcase.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests--)
{
int n;
ll l, r;
cin >> n >> l >> r;
vector<ll> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
vector<ll> pow10(17, 1);
for (int i = 1; i <= 16; i++)
{
pow10[i] = pow10[i - 1] * 10;
}
ll ans = 0;
for (int j = 0; j < n; j++)
{
int len = 0;
ll cur = a[j];
while (cur)
{
cur /= 10;
len++;
}
ll right = (r - a[j]) / pow10[len];
ll left = (l - a[j] + pow10[len] - 1) / pow10[len];
if (left <= right)
ans += (upper_bound(a.begin(), a.end(), right) - lower_bound(a.begin(), a.end(), left));
}
cout << ans << endl;
}
return 0;
}
Setter's solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[100005], n, l, r;
void solve(int tc) {
cin >> n >> l >> r;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
int ans = 0;
for (int i = 0; i < n; i++) {
int x = a[i], d = 1;
while (x > 0) {
x /= 10;
d *= 10;
}
int left = (l - a[i] + d - 1) / d;
int right = (r - a[i]) / d;
if(left <= right)
ans += upper_bound(a, a + n, right) - lower_bound(a, a + n, left);
}
cout << ans << '\n';
}
signed main() {
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++) solve(i);
return 0;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
int count(int x){
int pw = 1;
while(x)
pw = pw*10, x /= 10;
return pw;
}
int main() {
// your code goes here
int t = readIntLn(1, 1e4);
int sum = 0;
while(t--){
int n = readIntSp(1, 1e5);
sum += n;
assert(sum <= 1e6);
long long l = readIntSp(1, 1e15);
long long r = readIntLn(l, 1e15);
vector<long long> vec(n);
for(int i = 0 ;i < n ; i++){
if(i == n - 1)
vec[i] = readIntLn(1, 1e7);
else
vec[i] = readIntSp(1, 1e7);
}
sort(vec.begin(), vec.end());
long long ans = 0;
for(int j = 0; j < n ; j++){
// L <= 10^d * A[i] + A[j] <= R
int d = count(vec[j]);
long long hi = (r - vec[j])/d;
long long lo = (l - vec[j] + d - 1)/d;
ans += (upper_bound(vec.begin(), vec.end(), hi) - lower_bound(vec.begin(), vec.end(), lo));
}
cout << ans << '\n';
}
readEOF();
return 0;
}
Please comment below if you have any questions, alternate solutions, or suggestions.