Chef and Array DPS INOI Contest

Could someone please tell me why the below code is leading to a WA?

This was my approach

Let sum[i] be the cumulative sum at index i of array arr[]. Note that I am indexing from 1, not 0. So sum[N] is the sum of all elements of the array.

There are 2 cases:

  1. sum[N] is a multiple of 3 and N>=3

Again 2 sub cases:

a) sum[N] = 0

Here, I calculate the number of 0s in the sum array excluding the last element (I don’t want an empty set at the end) which is stored in k. The answer is k*(k-1)/2 (all possible combinations of the 0s giving number of ways)

b) sum[N] not = 0

Both k and s are set 0. s gives the actual answer.

From the end of the sum array, if sum[i] is equal to 2/3rd of sum[N] increment k. Now, if we come across sum[i] which equals 1/3rd of sum[N] add k to s and continue till 1st element of sum array.

  1. sum[N] is not a multiple of 3 or N not >= 3

Answer is 0

Solutions are not made visible yet,any reasons?

This question was identical to one of codeforces’s question. You can check the editorial here


Sorry, the contest is already over, but I didn’t realize that the solutions were not made visible yet. I have edited it now with a different link.

This is pathetic! I used the wrong data type for k. :frowning: Thank you so much! I got to know the test case for which my code was failing.