NICARRAY - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Praveen Dhinwa
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Backtracking, Combinatorics, and Modular Arithmetic.

PROBLEM:

Given an array A of length N with some elements missing and a value S, consider all ways of filling missing elements and for every resulting array, find the sum of gcd of every unordered pair. Print the sum modulo 10^9+7.

SUPER QUICK EXPLANATION

  • Order of elements does not matter. If C is the number of missing elements in the array and Si is the sum of non-missing elements, We need to fill C values so that their sum is S-Si.
  • We can calculate all such ways by forming all ways, say in the array B of length C, such that B[i] \leq B[i+1] and counting all different ordering using combinatorics.

EXPLANATION

Considering the slow solution first.

We can make a backtracking solution where we try to fix the first x elements, and filling missing elements with all possible choices such that the total sum does not exceed S. Then iterating over every pair of values and calculate pairwise gcd-sum and print the answer. Time complexity, in this case, is Exponential, thus, will pass only the first subtask.

For the second subtask, we need to work harder than that.

First of all, Notice that the order of elements does not matter at all since the position of an element is irrelevant to our problem.

Second thing, If Si is sum of visible elements, Missing elements can have sum S-Si. Now, Suppose we have a parititon B_1, B_2, B_3 \dots B_k such that \sum B[i] = S-Si.

If we can get all partitions of S-Si into C elements, we can simply calculate the answer in O(N^2) by iterating over every pair and taking gcd.

But, Number of partitions of S is also very high if we consider them ordered. Like, If we consider 1+2 different than 2+1 as a partition of 3, Number of the partition of 50 is very high.

But, We can notice, that pairwise gcd-sum do not change, when just the ordering of elements of partition changes. Like, Suppose we have example N = 3, S = 4 and array 1 -1 -1. We can notice that pairwise gcd-sum of 1 1 2 is same as pairwise gcd-sum of 1 2 1. Hence, if we can calculate the pairwise gcd-sum for all distinct partitions of S-Si with non-missing elements, we can solve this problem fast enough.

Now, we can once again use backtracking solution, this time with another constraint, that current element cannot be smaller than the previous element. This way, we can get a partition and we calculate pairwise gcd-sum.

But, the problem is, how do we know how many times a partition will appear. Fortunately, we can rush to Combinatorics :stuck_out_tongue: for answers. We can see, It is just the number of Distinct permutations of the given sequence.

Fortunately, If any element occurs x times, the Same permutation will be counted x times. This way, We can just Find the number of distinct permutations of the given sequence, and thus, find the required answer.

Hence, we can just find every unordered partition of S-Si into C elements, Find pairwise gcd-sum with each partition and also the number of times the same partition may appear and calculate the answer.

For reference, the method of computing distinct permutations of a sequence can be found here.

Time Complexity

The time complexity of this solution is O(P(S)*N^2) where P(S) is the number of unordered partitions of S. There is no closed form for Number of unordered partitions of a number, but for S = 50, it is small enough for our solution to pass comfortably.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

1 Like

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

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:

…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

Hi,
Is it possible for you to suggest test cases for which my solution is failing.

Link: https://www.codechef.com/viewsolution/21245633

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: https://www.codechef.com/viewsolution/21272024

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?

Well, you can read more about partition function at http://www.mathpages.com/home/kmath556/kmath556.htm as well as https://math.stackexchange.com/questions/1908701/integer-partition-of-n-into-k-parts-recurrence .

Also, there might be other pages which you may find on google.

I am also on the same boat as you. Exact same verdict with same approach. Hope someone finds out the problem in this approach.

I tried testing it with 50 test cases but it returns everything correct. Saw one thing tho, for input-

1
2 50
50 1

I got output of-

0
1

from your code. Can this be it?