CHVSDO - Where is my solution getting WA

Hi discuss,
This problem Cheems VS Doge CHVSDO is from a recent contest.
I want to know where my code has failed. I picked up a successful submission and stressed it with mine on around 1200 randomly generated testcases satisfying the constraints, but no success at all : ( Maybe it’s some trivial edge case.
Can I get the input/output for the same or the test case on which my code fails?

Approach :
I’ve used a segmented sieve like approach to find the count of all prime divisors and after that the classic subset sum to find the answer modulo.
My submission

@rishabhrathi22

1 Like

I encountered the same issue and was getting MLE on stress testing locally just because i used arrays. !!

@light301 Your code was absolutely right but missed one corner case. Think what would be your answer when L=1. Since 1 is not a prime number so , number of prime factors of 1 is “0”.
So the total number of subsets having sum S would be doubled , because for every subset we can get a new subset by including “0” to that set.

eg - 1 6 2
Your output : 7
Correct output : 14 ( forming a new subset of every subset by including 0 )

3 Likes

@riser01 has correctly explained the edge test case. You can also wait for the editorials. They will be updated in a day or two.

1 Like

Yea. I’ve got it! Should’ve calculated dp for sum = 0 too. Thanks!!

1 Like