SANSKAR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Jay Pandya
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

DIFFICULTY:

EASY

PREREQUISITES:

DP, bits

PROBLEM:

Given a set S of N integers the task is decide if it is possible to divide them into K non-empty subsets such that the sum of elements in every of the K subsets is equal.

QUICK EXPLANATION:

We use dynamic programming to solve it. If the solution exists, each subsets has to have a sum of its elements equal to the sum of all elements in S divided by K. Let X be that value. Let dp[k][bitmask] = 1 if and only if it is possible to divide a subset A of S denoted by the bitmask into k subsets each with sum X or to divide A into k - 1 subsets of sum X and one subset of sum < X. For a single dp[k][bitmask] entry, we will iterate over all elements of S which are not in A and try to extend current solution. The answer is “yes” if and only if dp[K][bitmask denoting the whole set S] = 1, and because we try to extend dp states only for k < K, we are sure than dp[K][bitmask] denotes if it is possible to divide a subset denoted by bitmask into K subsets with equal sums (see explanation below).

EXPLANATION:

Let SUM be the sum of all elements in S. If SUM % K != 0, then the answer is “no” because there is no way to divide elements equally.

Let X = SUM / K.

Let dp[k][bitmask] = 1 if and only if it is possible to divide a subset A of S denoted by the bitmask into k subsets each with sum X or to divide A into k - 1 subsets with sum X and one subset with sum < X.

Initially all entries in dp are set to 0.

At the beginning, we set dp[0][0] = 1 because it is possible to create 0 subsets with equal sums using no elements.

In the main loop, we iterate over all values k = 0, 1, …, K - 1 denoting the number of subsets for which we try to extend our solution and over all subsets of S denoted by a bitmask. Let A be a subset denoted by a bitmask. For a given dp[k][bitmask] we compute how much we have to add to the k+1th subset in order to get k+1 subsets, each with a sum X. We do that by subtracting k * X from the sum of elements in A. Then we iterate over all elements of S which are not in A and we try to extend our solution (see the code below):

Let a be an array denoting the set S. I omit the case when SUM % K != 0.

for k = 0 to K - 1:
    for bitmask = 0 to 2^n - 1:
        if not dp[k][bitmask]: 
            continue
        sum = 0
        for i = 0 to n - 1:
            if (bitmask & (1LL << i)):
                sum += a[i]
        sum -= k * x
        for i = 0 to n - 1:
            if (bitmask & (1LL << i)):
                continue //there is nothing to extend
            new_mask = bitmask | (1LL << i) //bitmask denoting a set with i-th element added
            if sum + a[i] == x: //we can fill the k+1 th subset with elements of sum X using a set of elements denoted by new_mask
                dp[k + 1][new_mask] = 1
            else if sum + a[i] < x: //we can fill k subsets with elements of sum X and one subsets with sum < X using a set of elements denoted by new_mask
                dp[k][new_mask] = 1

if dp[K][2^n - 1] == 1:
    print "yes"
else:
    print "no"               

Time Complexity:

The time complexity per one testcase is O(K * 2^N * N)

SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.

RELATED PROBLEMS:

To be uploaded soon.

2 Likes

Is there any other solution with out DP ?

I tried brute-forcing all possibilities, and managed to get it within the time limit, but am getting WA. I’ve tried all sorts of test cases, but could’nt find any case where my code fails… can anyone help me? This is my code: http://www.codechef.com/viewsolution/5593901

Finally I got it accepted here: http://www.codechef.com/viewsolution/5605439 Though it was not clearly mentioned in the problem, in the editorial each of the subsets is assumed to be non-empty.

Constraint are so small, that no DP is needed, check my solution - http://www.codechef.com/viewsolution/5540066

My solution contains Bitmask DP for 1st task and General DP(subset sum) for the 2nd subtask.
You can already see the Bitmask DP above. I will discuss my approach of subset sum.
For subtask 2 :
I took special care for intensity 0 and duplicate intensities.
You can see my solution :Sanskar Solution

Sorry for my style of writing code for this problem as I was in a hurry to get 100 pts.
Happy Coding :slight_smile:

@chaitan, since the limit is small , we can solve it using brute-force.
here is my solution http://www.codechef.com/viewsolution/5587907
it gets tricky when sanskar’s intensity is 0.
suppose there are 3 sanskars and 2 followers and let the intensity be 0{for all 3 sanskars}.But we can give
a “yes”,since the total sum adds up to 0.But consider 2 sanskars and 3 followers,and intensity with 0.
Here the o/p is “no”.Though the intensity is 0 , its greater than having no sankars.
This might be the problem.This occured to me.

Yes, I used graphs.

Unfortunately, your solution is incorrect and the test cases are weak.
It fails for this test:

1

8 3

4 4 6 5 8 3 3 6

The correct answer is “yes”. Your code produces “no”.

2 Likes

This time it would be such fun if there are hacks/challenges in the contest :smiley:

9 Likes

exactly , that would be most interesting specially for this problem ,

@betlista your solution is incorrect and the test cases are weak. It fails for the following test

1

8 3

4 4 5 6 8 3 3 6

Your code produces “no”. The correct answer is “yes”.

2 Likes

yeah … so many solutions are incorrect and the test cases are weak.

As I said, that would be so much fun :smiley:

1 Like

Good backtracking getting AC: SOLUTION

Thanks @code_overlord . Really appreciate that (y)

I am getting WA in last test case of SANSKAR…

Here is my algo…

I have used simple back tracking and recursion along with dp(by the means of map itachi) to find whether a number is not found previously or not in the same derivation tree…

I am getting WA only in the last test case

Can anyone tell me where my code is wrong

Or provide the test cases for which my code gives WA

Thnx for the help

http://www.codechef.com/submit/complete/446994-8759--548f1837882bb

Your code fails for the test case 1 1 2 0 . Point here is a sanskar with zero intensity and no sanskar are not the same things. Your gode gives yes for this test case, while the answer is no. See here: http://ideone.com/7mjBOX

Recursion: http://www.codechef.com/viewsolution/5552989

Can’t a first fit algorithm be used for this problem? we know how much each follower should have and we know the number of followers…Please explain

is this not the k-partition problem?

//