https://www.hackerrank.com/challenges/jim-and-the-jokes

[thafnhlong]

1. Với m, d, ta có thể tìm ra base10.

2. d=12; m=31 là giới hạn: = 312+31 = 37; bỏ đi 1 event 0 = 36 events

Vậy tối đa sẽ có 36 events khác nhau (1,2...35,6).

3. d, m hợp lệ là khi d < m (trong hệ 2 thì chỉ tồn tại 0 và 1)

4. Event X có K ngày thì K ngày bắt cặp với nhau sẽ là tổ hợp chập 2 của K = kC2 = (K*K-1)/2

5. N=10^5 tại 1 event sẽ có số cặp là (1e5)*(1e5-1)/2 = 4999950000 lớn hơn kích thước lưu trữ của int

Duyệt qua từng phần tử chuyển d,m sang hệ 10 được x table[x]++

int base10(int d, int m){
    int ret=0;
    int i=1;
    while(d>0){
        int cur = d%10;
        if (cur >= m) return 0;
        ret+= cur*i;
        i*=m;
        d/=10;
    }
    return ret;
}

long solve(vector<vector<int>> dates) {
    int size = dates.size();
    if (size<2) return 0;

    //31-12 = 3*12+1 = 37
    long table[38] = {0};

    for(vector<int> date: dates){
        int m= date[0];
        int d = date[1];
        int base = base10(d, m);
        if (base < 1) continue;
        table[base]++;
    }

    long ret = 0;

    for(int i=1;i<38;++i){
        long cur = table[i];
        if(cur > 1){
            ret+= 1.0*cur*(cur-1)/2;
        }
    }

    return ret;
}