Help With Find The Numbers (IARCS OPC)

Problem Link: https://www.codechef.com/IARCSJUD/problems/FINDNUMS

My Approach: n1, n2, …, nk have to satisfy two conditions: n1+n2+…+nk = S and n1.n2…nk = P. The second condition implies that ni is a divisor of P for all valid i hence we can narrow down the search using this fact**. So I factored the number P and stored its divisors. Next I implemented a recursive solution to fill each variable and solve the sub problem with one less variable to fill each time. I did this only for (k-1) variables as the kth variable is fixed automatically by the first condition.

**I came to this conclusion because I found that any number less than or equal to 1000 has at most 32 divisors (for reference https://www.geeksforgeeks.org/querying-maximum-number-divisors-number-given-range/), which means a total of 64 (taking both the negative as well as positive divisors as the problem only says integers and not positive integers) resulting in a total of 64^4 = 16777216 possibilities which can easily be searched through in time.

Link to Submission: https://www.codechef.com/viewsolution/40431844

But now the problem is that this code gives a WA on one test case and I can’t figure out why. Can anybody please help?

[If you have had a look at the code can you also tell me what happens if I pass something like solve(varUsed++,…) instead of solve(varUsed+1,…). I know it results into an error, but why?]

Anybody?
@truly_great, @ssrivastava990, @therealnishuz

Spoiler

S, \ P = 0

But the constraints say, 1<=S<=1000 and 1<=P<=1000.

Oh, I didn’t see that.

The output file for that one test case is probably wrong. If you comment that part where you’re pushing -ve numbers, then it gives AC. I don’t find anything wrong in your solution.
Regarding your second query, if you pass varUsed++, you’ll get TLE because of working of ++ operator. The value is used first and then incremented. So, 0 will be passed everytime and your code will be stuck in an infinite recursion. You can use ++varUsed instead as in this case value will be incremented first and then used. You can read about postfix and prefix operators.

2 Likes

informative