Here is my code based on the above approach …
I also coded it during the contest itself … 
I don’t know what choose(sx, 2) means, but you can read my comment above if it helps 
Someone please fix the “Access Denied” issue!
1 Like
@akumar3 : I saw your solution for this problem.
https://www.codechef.com/viewsolution/5863202
Can you tell why have you incremented curr when i = 0 in processResult() ?
That is because the case with 0 remainder is special.
For every two prefixes with equal remainder, we have 1 substring which is divisible by 3;
Now consider following string:
33
Prefixes:
3, 33 (both gives remainder 0 when divided by 3)
If you apply above formula, you will get ‘1’ substring which is divisible by 3.
But here both the original prefixes are also divisible by 3.
To account this fact, we have to update our formula for the case when remainder is 0, so if we have N prefixes which gives remainder 0; our answer will be:
= (N(N-1))/2 + N (original prefixes)
= (N*(N+1))/2
1 Like