Well it has been almost 5 days and i am not able to find the mistake in the logic or code for the given problem. It passed subtask 1 which gave 20 points. Its just failing in the #7 #8 and #9 test case rest all cases passed .
I dont know if there is any problem with test cases.
Used approach - sort the given sums, find the duplicates, as they are sum of the entire sequence. For each duplicate find that the there exist a pair for which sum is the value of dupliacte. If any number is left without a pair break from loop and try again for other duplicate…
Problem - CodeChef: Practical coding for everyone
My submission - CodeChef: Practical coding for everyone
Did you make sure that other duplicates are exactly summing up to the targeted sum (S)?
S is basically a1 + a2 + … + an and can be computed by summing up all prefix, suffix sums provided and then dividing by (n + 1).
After looking at your solution, I’m surprised that it didn’t TLE. I think the problem might be in your logic, most probably. A duplicate need not be the sum of the sequence.
The sum of the sequence will be fixed as “The sum of Prefixes and Suffixes, divided by n+1”. This is because for every Prefix Sum up to some index, there is a Suffix Sum for the index after that, their sum together gives the sum of the original sequence.
Second of all, there are probably a lot of things that you can learn here.
-
You can use sort(a,a+n); to sort the array in C. You don’t need to write the merge sort for it every time.
-
There is a built in function for calculating GCD.
ll gcd = __gcd(x,y);
-
You’ll need to write your own power function based of fast exponents O(logEXP) as the values might overflow and calculating by repeated multiplication might give TLE.
ll yourPowerFunction(ll base,ll exp)
{
if(exp==0) return 1;
ll z=yourPowerFunction(base,exp/2);
z=(z*z)%MOD;
if(exp%2) z=(z*base)%MOD;
return z;
}
-
To take the modulo inverse, you can just raise that number to the power MOD-2;
ll InvMod = yourPowerFunction(number,MOD-2);
-
It is recommended to create the array of Factorials and Inverse Factorials beforehand.
-
Use good variable names instead of a,b,c,d,e, etc. It makes the code easy to understand.
3 Likes
Can you give a more detailed account of the logic you used.
On a cursory glance it seems you got atleast part of the logic correct(except the Sum observation) as it is giving the right answer for many examples although it is difficult to tell since the code is convoluted.
But the problem can be solved in a much cleaner way, just check the editorial.
Was facing same issue earlier.