NICARRAY - EDITORIAL

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 :frowning: . Did anyone solve it by dp?

Thanks for your nice editorials as always taran!! :wink:

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

1 Like

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:

  1. First you build cnt[i][j] = number of ways to write i as sum of j terms.
  2. Second you can use cnt[i][j] to compute dp[i][j][k] = considering all different ways to write i as sum of j terms how many times term k will be used.
  3. Next you can use dp to compute cmmdcsum[i][j] = solution of the problem if you have S=i and j of -1s.

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:

  1. Find gcd sum for a1 a2 … ak, let denote it by fixedSum. You know that this sum will be added to the final answer for every different way of replacing the -1 sequence. If we have n1 of -1 then we can set the answer for now to be sol = fixedSum * cnt[S’][n1] where S’ = S - a1 - a2 … - ak.
  2. Next we should add to the answer the gcd sum of all possible replacement of -1’s if we consider only the sequence formed of -1’s. We have calculated this already in cmmdcsum, so we can set sol += cmmdcsum[S’][n1].
  3. Finally we should add the gcd sum of all pairs (ai, x) where x is a possible replacement of -1. We already now how many times each number x appears in all possible replacements of -1s, so for each ai and each x<=S’ we set sol += gcd(ai,x) * dp[S’][n1][x].

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))

https://www.codechef.com/viewsolution/21238180

2 Likes

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.

@taran_1407 Could you please explain how to solve this problem using Backtracking ?

Thanks

Tester solution seems to be of some other problem?

1 Like

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

HERE is my solution

1 Like

…XD

ask @vijju123 he used DP but got tle… 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 :wink: .

1 Like

Oh god, will this ever end? @vijju123 xD

Nopes, I aint banning any account just like that @taran_1407 XD

hahahhah XD I just saw word DP in your soln @vijju123

Lol which one? I dont recall it XD

this one only xD