What is the last test-case (Task#13) for SUBSFREQ?

My Java solution runs less than 2 seconds on all test cases, except the last task (Task#13) for which it runs over 4 seconds. I have made all the optimizations that I never compute a combination or its inverse or their sum twice. I don’t know what’s wrong with it. Could someone please shed some light on it? Theoretically, it’s linear solution (or O(NlogN) due to inverse computations with powers)

1 Like

try with linear inverse algo instead of nlogn approach.

#define mod 1000000007

ll modmul(ll a, ll b) {
    return ((a%mod) * (b%mod)) % mod;
}

lli fact[1000001];
lli inv[1000001];
lli fact_inv[1000001];
void calc_fact_inv()
{
    inv[0] = fact[0] = fact_inv[0] = 1;
    inv[1] = fact[1] = fact_inv[1] = 1;
    for(lli i=2;i<=1000000;i++)
    {
        fact[i]  = modmul(fact[i-1],i);
        inv[i] = (mod - (mod/i) * inv[mod%i] % mod) % mod;
        fact_inv[i] = modmul(fact_inv[i-1] , inv[i]);
    }

}

My inverse factorial computations are also linear if you look at it. In some places, the inverses are computed with powers. Overall, I don’t think the inverses are the reason for the TLE. Even for N=500,000, NlogN should be fine.

1 Like

You have nested loops of the form

for (int i = 0; i <= N; ++i) {
for (int k = currentCount + 1; k<C; k++) {
do stuff
}
}

which could be O(n^2) loops.

1 Like

It’s linear in the number of elements in the input. In the code snipped you shared, the outer loop is iterating over distinct elements, and the inner loop is over their counts. In total, it’s equal to the number of elements in the input. It also runs under 2 seconds in all test cases except the last one. So I believe it’s not quadratic.

Rest of the test cases passed for me too. I faced NZEC for the last test case. I maintained a 2D table of size (max_frequency_count * unique values in array). It threw Out Of Memory error in my Intellij while testing with test case like

N = 5*10^5

first N/2 values are unique and next N/2 values are same.

1 2 3 4 5 6 … 250000 250001 250001 250001 … 250001

Time complexity is 250000^2 which is O(N^2)
Space complexity is 250000^2 which is again O(N^2) -> this caused the NZEC for me.

1 Like

Sorry I think you’re right! It’s going up to the max frequency… I can now generate a counter-example for that… I had tried to generate a lot of big tests to stress my solution, but they all run under 1.5 seconds locally. Anyway, thanks for pointing that out! Very appreciated!

Yes, exactly! A test case like that would fail my solution. At least I now know what the problem is.
I did crazy amount of optimizations with combination computations which I might use in the future, but none helped. I was fooled by the idea that I’m iterating over distinct numbers with their frequencies, in fact, I’m iterating over distinct numbers with max frequency.

My solution didn’t have any symptoms for OOM, but subtle flaw for TLE…

Good Luck!

1 Like

I have now fixed the trouble with my solution here.

@kool , I have also taken an array like yours but instead of max_frequency_count, the arrays for unique value is of its frequency length. Might be useful for you!