Good Sets

ACM ICPC India Regionals Online Preliminary round got over last week. Our team ‘Dashwood’ (named after the password used by Harold Finch in the TV series Person of Interest ), we were able to solve 5 questions out of the 7 questions.

The 5 questions which we could solve were all relatively easy compared to the other two.

Link to the contest here.

Out of the 5 questions which we solved one was very interesting to solve, so here’s a blog explaining how I did it.

It was basically a Dynamic Programming problem.

Read the question here.

Here is the code in C++

	#include <stdio.h>
	#include <string.h>
	#define M 750000
	#define MOD 1000000007
	int inp[M+1], dp[M+1];
	int main() {
	int t,n,sum;
	scanf("%d", &t);
	while(t–) {
	sum = 0;
	memset(inp, 0, sizeof(inp));
	memset(dp, 0, sizeof(dp));
	scanf("%d", &n);
	for(int i = 0, j; i < n; ++i) {
	scanf("%d", &j);
	inp[j] = 1;
	}
	for(int i = 1; i <= M; ++i) {
	if(inp[i]) {
	dp[i] = (dp[i] + 1) % MOD;
	sum = (sum + 1) % MOD;
	for(int j = 2 * i; j <= M; j += i) {
	if(inp[j]) {
	dp[j] = (dp[j] + dp[i]) % MOD;
	sum = (sum + dp[i]) % MOD;
	}
	}
	}
	}
	printf("%d\n", sum);
	}
	return 0;
	}

view raw

good_sets.cpp

hosted with ❤ by GitHub

The inp[] will contain 1 at the indices corresponding to the input numbers.

Now we iterate through the array inp and if an index i has 1.

We update dp[i] by

dp[i] = (dp[i] + 1) % MOD;

Then we update the dp array at all the indices which are the multiples of i .

dp[j] = (dp[j] + (dp[i] + 1)) % MOD;

where j loops over all the multiples of i.

and with each update of the dp array we increment the variable sum by the same amount.

Now after all the updates sum will contain the final answer.

Why this works?

For example let the given array be {2, 3, 6, 12}.

Now we take {12} and we have to find the number of ways we can append new arrays to it such that 12 is near to its factor.

So we can append 6 or 3 or 2 with {12} or not append anything. We can append not just the individual numbers but also the arrays which can be formed with those numbers.

So for {6} we can append 2 or 3 or not append anything.

{2, 6}, {3, 6}, {6}

So dp[6] contains 3

For 2 and 3 we cannot append any numbers.

{2}, {3}

So dp[2] = dp[3] = 1

So we can append {2, 6}, {3, 6}, {6}, {2}, {3} to {12}

So the number of ways we can form subarrays with 12 is

dp[6] + dp[3] + dp[2]

which is 5.

The final answer is the sum of number of ways you can make arrays ending with {2}, {3}, {6} and {12}.

The variable sum has the total sum of the dp[] array and hence the final answer.