INTCONCA - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

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. :slight_smile:

6 Likes

I really dont know why my solution is not passing TLE. The complexity is 4NlogN(time to concat two numbers).
Link to my solution : Solution: 52375192 | CodeChef

@ajit123q do you have something against data structures?

https://www.codechef.com/viewsolution/52376246
https://www.codechef.com/viewsolution/52377329
https://www.codechef.com/viewsolution/52378003
https://www.codechef.com/viewsolution/52379864

Why is using a segment tree to calculate range frequency such a big deal? it would easily pass under 2 - 3s
I spent 30 mins optimizing this nonsense.

Please keep into consideration the constraints from next time.

3 Likes

I believe you can solve the problem in \sout{O(N)} using using two pointers. It’s still O(NlogN), but it should be more efficient that the editorial approach

for _ in range(int(input())):
    n, L, R = map(int, input().split())
    a = sorted(map(int, input().split()))

    c = 0  # Final answer

    ls = []  # Stores the minimum value such that it's greater or equal to L (for each index i)
    rs = []  # Stores the minimum value such that it's lesser or equal to R (for each index i)

    # Left pointer, Right pointer
    l, r = 0, n-1

    for i in range(n-1, -1, -1):
        while l < n and (not L <= int(str(a[l]) + str(a[i]))):
            l += 1

        ls.append(l)

    for i in range(n):
        while r >= 0 and (not int(str(a[r]) + str(a[i])) <= R):
            r -= 1

        rs.append(r)

    ls.reverse()

    s = 0
    for i in range(n):
        x = rs[i] - ls[i] + 1  # Number of possible j for the ith index
        if x > 0:
            s += x

    print(s)

Solution link: Solution: 52382916 | CodeChef

It’s true that they could’ve accommodated the constraints for segment tree, but they constraints seem very typical (N \leq 10^5, \sum{N} \leq 10^6), and any less might have made it so that sub-optimal solutions pass.

It would easily pass in 2s there was no need to modify the existing constraints. Only a change in TL was required.

I get the intuition behind the right variable but unable to get it for the left variable in solutions provided in the editorial. I mean in the setters solution why has he added d-1 to the numerator of the left variable. Can someone help me with that?

2 Likes

Exactly. All 3 solutions have used that same line, without any explanation whatsoever. It’s not even intuitive.

That is done to get the ceil value of the fraction, for right we are taking floor value

1 Like

But you are sorting the array. This operation alone pushes the time complexity of your solution at least to O(N log N).

1 Like

Thanks! That’s a nice solution. Too bad that the time limit was too tight. Though there are two relatively easy ways to improve your code:

  1. Use fenwick tree instead of segment tree: Solution: 52385990 | CodeChef
  2. Optimize ‘func’ a little bit (divide by 100 instead of 10 on each loop iteration): Solution: 52386002 | CodeChef
  3. Apply both of these optimizations: Solution: 52386021 | CodeChef

Fenwick tree and Segment tree have the same time complexity, but Fenwick tree has a better constant factor. Segment tree is usable in more situations because it is more versatile, but Fenwick tree may be preferable if it does exactly what needs to be done.

Running a profiler showed that the function ‘func’ was one of the worst performance bottlenecks in your code. This is not very visible in the codechef tests, but I think that the codechef tests are just not trying too hard to construct the slowest possible testcase. The following naive Ruby script generates a random testcase, which seems to be more difficult to handle than the codechef testscases:

t = 10
puts t
t.times do
  n = 100000
  l = rand(1 .. 10 ** 15)
  r = rand(l .. 10 ** 15)
  puts "#{n} #{l} #{r}"
  puts n.times.map { rand(1 .. 10 ** 7) }.join(" ")
end

On my 2.8 GHz processor, the timings are the following:

  • Your original code: 1.60 seconds
  • Fenwick tree: 1.15 seconds
  • Func optimization: 1.29 seconds
  • Fenwick tree+func optimization together: 0.78 seconds
1 Like

Hi, I just want to discuss…normally in Codechef , 1s time limit allows for solutions upto 10^8. How come is it now that even NlogN is not passing? I am not blaming anyone …just trying to figure out the right approach to think on seeing a problem.
Without coding and submitting a solution, it’s hard to know whether NlogN is allowed or not…cz if we think on the stricter side, we might end up not being able to solve a problem because of trying to over optimise it although NlogN may be allowed in that case.

1 Like

Thanks a lot for your response. The idea of dividing by 100 is really cool and yeah I will try learning fenwick eventually. :slightly_smiling_face:

Logically, ans should be
no. of pairs <= R - no. of pairs <= L - 1
For getting pairs < L, shouldn’t you use the same upper_bound formula for L - 1?
I mean the number of pairs < L is the same as the number of pairs <= L - 1.

I think instead of following the above editorials, it’s much intuitive to count pairs <= R, and count pairs <= L - 1, and then subtract the two.
In other words,

right = (r - arr[j]) / power[len];
left = (l - 1 - arr[j]) / power[len];
    
if(left <= right)
ret += upper_bound(all(arr) , right) - upper_bound(all(arr) , left);

This is much easier to understand.

1 Like

Welp, that’s a facepalm moment, though it should still be more efficient than the editorial approach

We are finding the first index which matches the left criteria and for right we are finding the first index that does not fit on the right criteria, so our window length becomes rightIdx - leftIdx. If we get a fraction value for L, the array elements are integers so we can safely say that the number >= ceil of L satisfies the condition. Similarly for fraction value of R, since elements are integers, so the last possible valid value would be floor of R.

Hi,I had asked you a question. Will it be possible for you to give your opinion to that?

Time complexities are just approximations. Using Big O notation, you’ll likely not get the exact number of operations. For example,

n = int(input())
c = 0
for i in range(n):
    for j in range(i):
        c += 1

print(c)

The number of operations this code takes is N*(N-1)/2 (which is still an approximation as constants operations weren’t counted), but in Big O notation, the number of operations become O(N^2)

Constant coefficients are not included in the final result. Therefore, if your O(NlogN) solution has a constant factor of 4, which would be the case for a segment tree, then it’s going to be 4 times as slow as an NlogN solution.

The reason why fenwick trees are faster than segment trees is due to the fact that the constant coefficient of a fenwick tree is small than that of a segment tree

But is it possible to guess beforehand what amount of a constant factor can pass the TL?