Johnny The Gambler Problem

Johnny is a gambling addict. He entered a casino and started playing a game with the dealer. The game is as follows: the dealer deals a sequence of N cards, each card containing a number C[i] and asks Johnny how many pairs (j, k) such that j < k and C[j] + C[k] = X. If Johnny answers correctly he wins, otherwise the dealer wins.

Input Format

The first line of input contains an integer T, the number of test cases. T test cases follow, Each test case start with the value of 0 <= X <= 2*10^3 followed by the number of cards 0 < N <= 10^5 followed by N numbers representing the numbers on the cards 0 <= C[i] < 10^3.

Output Format

There should be T lines, containing the following format.

k. S

Where k is the test case number (starting at 1), a single period, a single space and S representing the number of valid pairs (j, k) as described above.

Sample Input

Sample Input

1

10 3 1 5 9

  1. 1

if plz someone help me with this question … always receiving time limit exceeded

@lovi asked similar question - how to find pairs in array with sum == k

The question is how many test cases are in test file.

1 Like

i see a O(nlogn) solution. j is going through [1;105], and then you binary-search X - C[j] in C.

T being small or big, it should be ok. :slight_smile:

sry 0 <= C[i] < 10^3 … not 103

also I updated 105 to 10^5 in your question, is it correct?

I like solution with map, and while C[i] is small we can replace map with array and it becommes O(n) :wink:

See my answer here.

As @betlista mentioned, since in this problem the numbers are up to 1000 you can use array instead of map in my solution and get O(N + maxC) solution.

But it may appear that there are many tests with small N in one test file. Say 100000 tests with N up to 5. Then this new solution may get TLE too since we always should iterate over array of size 1000. If I would be the author of this problem I would definitely create such test file :slight_smile:

One way to avoid this is to use O(N^2) brute-force for very small N, say N smaller that 45. For array of size 45 we have approximately 1000 pairs so brute-force will have the same time as counting solution. But then we can create a test file where all N are near 45 and T=10000 or higher and this new solution can also get TLE.

To avoid TLE for any evil possible tests we need another hacky array mark[1000] that is initialized by zeros before reading tests. When we handle t-th test (t=1,2,…,T) mark[Ci] == t if and only if Ci appears in array C[] of the current test. So we shouldn’t initialize it by zeros again. We also shouldn’t initialize array cnt[1000]. The value cnt[Ci] will be actual only if mark[Ci] == t. Otherwise it may contains some garbage from the previous tests. Finally to make efficient loop for calculating the answer we should save all different values that we met during reading in some array.

So during reading of our array if we read number Ci for which mark[Ci] < t then it means that we did not meet this number in the array before. So we should assign mark[Ci] = t, assign cnt[Ci] = 0 and add it to the list of unique values. And as in the previous solution we of course should do cnt[Ci]++ for each read Ci. So the C++ code for this part may look as follows:

int mark[1000] = {0};
int cnt[1000] = {0};
int lst[1000];
scanf("%d", &T);
for (int t = 0; t < T; ++t) {

int X, N;
scanf("%d, %d", &X, &N);
int len = 0;
for (int i = 0; i < N; ++i) {
    int Ci;
    scanf("%d", &Ci);
    if (mark[Ci] < t) {
        cnt[Ci] = 0;
        mark[Ci] = t;
        list[len++] = Ci;
    }
    cnt[Ci]++;
}

//now lst contains all different values among C[i]

// compute the answer. see below
}

Loop for computing the answer also requires some careful consideration. Now we have list lst[1000] that contains len elements that are all unique values among our array. We iterate by this list and for the current value val if val == X-val than add cnt[val] * (cnt[val]-1) / 2 as described in my previous post. Otherwise in order to not count the same pair twice val should be greater than X-val and mark[X-val] should be equal to t. Otherwise cnt[X-val] can be some garbage value from the previous tests. So the code looks as follows:

typedef long long LL;
LL ans = 0;
for (int i = 0; i < len; ++i) {
    int val = lst[i];
    if(val == X - val) {
        ans += LL(cnt[val]) * (cnt[val] - 1) / 2;
    } else if(X - val < val && mark[X - val] == t) {
        ans += LL(cnt[val]) * cnt[X - val];
    }
}
printf("%lld\n", ans);

Alternatively you could check condition X-val > val but then it may appear that X-val >= 1000 so next look up at mark[X-val] will be incorrect in this case. So you should either make mark of size 2001 or to save memory check condition X-val < 1000. In any case the way described above is better.

This solution has complexity O(N + min(N,maxC)) = O(N).

3 Likes

yea right.

//