Closed Tuples

Debugging Help
#1

Problem Info

My Work

#include <iostream>
#include <vector>
#include <algorithm>

#include "debugging.h"

using std::cout;
using std::endl;
using std::vector;

constexpr int MOD = 1e9 + 7;
constexpr int MAX_SIZE = 1e5;
constexpr int MAX_TUPLE = 1e2;

long long pow_mod(long long base, long long exp) {
	base %= MOD;
	long long result = 1;
	while (exp > 0) {
		if (exp % 2 == 1) // if n is odd
			result = result * base % MOD;
		base = base * base % MOD;
		exp /= 2; // divide by two
	}
	return result;
}

long long mod_inv(long long n) {  // sauce is same as above
	return pow_mod(n, MOD - 2);
}

// https://codeforces.com/problemset/problem/1462/E2 (input ommitted due to length)
int main() {
    vector<vector<long long>> choose_table(MAX_SIZE + 1, vector<long long>(MAX_TUPLE + 1));
    for (int s = 0; s <= MAX_SIZE; s++) {
        long long curr = 1;
        for (int t = 0; t <= MAX_TUPLE; t++) {
            choose_table[s][t] = curr;
            curr = curr * (s - t) % MOD * mod_inv(t + 1) % MOD;
        }
    }

    int test_num;
    std::cin >> test_num;
    for (int t = 0; t < test_num; t++) {
        int size;
        int tuple_size;
        int max_diff;
        std::cin >> size >> tuple_size >> max_diff;
        vector<int> arr(size);
        for (int& i : arr) {
            std::cin >> i;
        }
        std::sort(arr.begin(), arr.end());

        long long valid_tuples = 0;
        for (int i = 0; i < size; i++) {
            int largest = std::upper_bound(arr.begin(), arr.end(), arr[i] + max_diff)
                    - arr.begin() - 1;
            int valid_elements = largest - i;
            valid_tuples = (valid_tuples + choose_table[valid_elements][tuple_size - 1]) % MOD;
        }
        cout << valid_tuples << '\n';
    }
}

I first precalculate all the values of \binom{N}{M}, and then I used a binary search to see the largest value given the minimum value.

For some reason though, this TLEs, even though it should(?) meet the target complexity.

#2

This implementation uses an insane amount of memory, but it still passes :smiley:.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vl = vector<ll>;

const ll MOD = 1e9+7;
const ll MAX_N = 2e5 + 1;

ll C[MAX_N][101];

void findChooses(){
    for(int i=0; i<=MAX_N-1; i++){
        for(int j=0; j<=min(i, 100); j++){
            if(j == 0 || j == i){
                C[i][j] = 1;
            } else {
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
            }
        }
    }
}

ll choose(int n, int r){
    return C[n][r] % MOD;
}

void solve(int tc){
    int n, m, k; cin >> n >> m >> k;
    vl a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    ll ans = 0;
    for(int i=0; i<n; i++){
        int tuples = upper_bound(a.begin(), a.end(), a[i] + k) - a.begin() - i;
        if(tuples >= m){
            ans += choose(tuples-1, m-1) % MOD;
        }
    }
    cout << ans % MOD << endl;
}

int main(){
    findChooses();
    int t; cin >> t;
    for(int i=1; i<=t; i++){
        solve(i);
    }
}
#3

cin.tie(0)->sync_with_stdio(0)

#4

Did you test it with that?

(also i fixed it, it just took precalculating the inverses)

#5

no

#6

lmao

#7

lol, i just tested it

TLE on test case 1

#8

The long long multiplication and inverse mod is probably at least 20x slower than Pascal’s triangle like in @jessechoe10 's solution.

#9

Yeah, but my solution uses too much memory xD.