Is a dp solution of this is not possible? I thought of using dp[index][sum][Hash of Array] and see if storing my previous answer helps. But it still got TLE . Did anyone solve it by dp?
Thanks for your nice editorials as always taran!!
Is a dp solution of this is not possible? I thought of using dp[index][sum][Hash of Array] and see if storing my previous answer helps. But it still got TLE . Did anyone solve it by dp?
Thanks for your nice editorials as always taran!!
Hi,
Is it possible for you to suggest test cases for which my solution is failing.
Link: CodeChef: Practical coding for everyone
I have tried generating random testcases, my answers matched with those given by an accepted solution.
My approach is similar to that given in editorial. I generate permutations by decreasing max value to be appended and recur on it.
Thanks
I used DP to solve this problem in O(N*S^3). Didn’t got accepted during the contest because I didn’t checked for invalid input when all numbers are different from -1 but their sum is not S, after fixing this I got accepted.
Here is my source: CodeChef: Practical coding for everyone
Quick Explanation of used structures:
After building all these structures, similar to building cmmdcsum you can find the answer for each query. Please check the code for recurrence relations.
Let say that the input sequence is ordered like this:
a1 a2 … ak -1 -1 -1 -1 …
Using the structures above you can build the answer in the following way:
Is there any way to show that P(50) is indeed small enough?
I tried the same approach as the editorial. Here is my solution.
My solution is only getting partially accepted. Can someone help me?
Edit: I attached the wrong solution. This is the solution I’m talking about- CodeChef: Practical coding for everyone
I used dp,it got accepted
dp[N][S] denotes ans upto nth element such that its sum is S
dp3[N][S] denotes number of positive solution of x1+x2+…xn=S
dp2[N][element][Sum] denotes sum of gcd for all posible sequences: x1,x2…xn
Such that xi>=1,and sum(xi)=s
Like for 1 seq,it will be sum(gcd(xi,element))
Do this for all sequences and add…
complexity(50^4+T*(50^3))
How to find the permutations of numbers of which sum is S ???
In the link mentioned in editorial it’s not defined precisely. Thanks in advance.
Tester solution seems to be of some other problem?
All soln are for 1st que of div2 XD
Link clarifies the question.
I was confused that how you did the code with a for loop XDDD
now they seem to be okay
…XD
I didnt use dp lol. I used BF XD. However @taran_1407 is very good in dp. Plus, hes also the editorialist. He will help her .
Lol which one? I dont recall it XD
this one only xD