SPOOKY - Editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Aakash Jain
Tester: Aakash Jain
Editorialist: Aakash Jain

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic programming

PROBLEM:

Find if a given number N is a weird number. That is, it must satisfy the following two conditions:

  • Its proper divisors (divisors including 1 but not N) must all add up to a value greater than N.
  • No subset of its proper divisors must add up to exactly N.

QUICK EXPLANATION:

Find and store the divisors of N. Then perform the subset sum algorithm with N as the target sum and the list of divisors as the set.

EXPLANATION:

Firstly, we need to find the divisors of N. Start with an empty set D. For each number i in the closed interval [1, sqrt(N)], we check if N is exactly divisible by it. If i is a divisor then clearly N/i must also be a divisor. So, i and N/i are added to D. The pseudo-code would be:

D[0] = 1
nD = 1
for i = 2 to sqrt(N)
if N%i == 0
	D[nD++] = i
	D[nD++] = N/i
After finding all the divisors, we find **S**, the sum of all elements in **D**. If **S <= N** then the first condition is violated and **N** is not weird.

Next, using the values in D, we must find if there exists any subset that adds to N. If we find that there is no such subset, then N is weird. Otherwise, it is not weird. In other words, we must solve the standard subset sum problem. To optimize for speed, we use the dynamic programming approach to the problem. This approach is well explained with code here.

AUTHOR’S SOLUTION:

Author’s solution can be found here.