Why is the last testcase for SEATSTR2 failing for this code?

general
,
1

I am not sure why this code is failing for the last testcase for SEATSTR2 problem.
Here is my solution. Can someone please help me with this?

1 Like
2

It is failing because of this line

sim += (long long)(al[i]*al[j]*al[k]*al[l]*3) % MOD; //no of swaps 2, disjoint, case: abcd

sim += (long long)(al[i]*(al[i]-1)*al[j]*al[k]) % MOD; //no of swaps 2, disjoint, case: aadc

sim += (long long)(al[i]*(al[i]-1)*al[j]*al[k]) % MOD; //no of swaps 2, disjoint, case: aadc

due to overflow errors. Make sure to multiply maximum two numbers and then take MOD. Here multiplication of 4 numbers may go upto 10^20 in worst case, which may not fit in long long.

Hope this helps.

3

Well I finally managed to get AC. Here is my solution. I did’t get the idea how multiplication of 4 frequencies may go upto 10^20 as the maximum value of n possible is 10^5. So I tried to store the number of similar strings possible for each case as x1, x2, x3, x4, x5 (excluding the original string) instead of in a single variable and then calculated them accordingly and I got AC.

But still I did not understand the difference between the two solutions. Here is my previous solution which was failing on the 4th testcase. @kevinsogo Can you please explain this?

4

Hey ash_code, here is the mistake in your code, i.e. the line which you changed from the wrong answer to accepted solution:

sim += (long long)(al[i] * (al[i]-1) * al[j]*(al[j]-1) * pow_mod(4)) % MOD;

Here is the your modified code which gives AC for 100 points. Also, there was no need to typecast it to long long either. You can look at the solution. No extra variables used. Also, your method to calculate the above statement as

x5 += (ll) ((al[i] * (al[i]-1)/2) * (al[j] * (al[j]-1)/2)) % MOD;

is wrong according to modular arithmetic. May be the test cases were weak or just don’t know how your solution passed :stuck_out_tongue: .

For more queries, you can ask in the comments below. If you feel you are satisfied with the answer, mark it as accepted.

Happy coding :slight_smile:

5

Consider the case when the string consists of length 10^5 and only 4 characters, each occurring (10^5 / 4) times. See here that sim += (long long)(al[i]al[j]al[k]al[l]3) % MOD; will exceed the long long limit.

6

Ok I got this. But look at my AC solution, in that I haven’t used this but still got AC. Why is the output for the two solutions are different then?