SANSKAR - Editorial

bit
dec14
dynamic-programming
easy
editorial

#1

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*
        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* == 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* < 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

Is there any other solution with out DP ?


#3

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.


#4

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:


#5

@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.


#6

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


#7

Good backtracking getting AC: SOLUTION


#8

Thanks @code_overlord . Really appreciate that (y)


#9

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


#10

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


#11

is this not the k-partition problem?


#12

Even this solution is giving a TLE for second subtask!!


#13

Was the trolling with omitted info (that the subsets need to be non-empty) intentional? I was able to deduce it, but I wonder how many people got WA because of this.


#14

I have got a very simple solution by simple bruteforcing, and also got AC.

here is the method:

  • first sum%k!=0 print “no”
  • then have y=sum/k (y is the sum that each subset should have)
  • now start finding (dont find all of them, just start finding) all the subsets of the set and check their sum, if their sum is y, then carefully remove those corresponding elements(of the current subset, the one which gives sum y) from the main set
  • now again start finding the subsets of the new main set and repeat the process until you find a sum y for a total of k times (a simple goto statement will do)
  • if you are able to find the sum y, k times in total then print “yes” otherwise “no”

note: in my solution the variable names “big” is “sum”, array a is the main set, and array b for subset with sum y, then all the b’s elements are removed from a

this method does not need dp, only basic knowledge is enough.

Here is the link to my answer : my code (http://www.codechef.com/viewsolution/5510448) got AC

Please upvote if u have understood, so that many others can get benefitted


#15

i am getting WA for 6 subtasks can you provide any testcase where my solution failed or any bug.
here is the link http://www.codechef.com/viewsolution/5600554


#16

I spent days trying to solve this problem, but I kept getting WA on the last test. Turns out the problem description is wrong! The problem description makes it clear that empty sets are valid:

Your task is to determine whether it
is possible to allocate all the
sanskars to followers in such a way
that the sum of intensities
of the
sanskars allocated to each follower is
equal.

The sum of [0, 0, 0] is zero and the sum of an empty set is also zero.


#17

Can’t figure out what’s wrong with my code. It passes all the test cases. Plzzzz help me! Here is the link to my code- http://www.codechef.com/viewsolution/5602314


#18

I was just wondering shouldn’t it be

“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 subsets with sum X and one subset with sum < X.”

instead of

“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.”


#19

Some solution sames not right.

For this input:

1

9 3

50 40 30 25 11 5 3 3 1

Answer: yes

The result in here and here is not same, but all passed.


#20

Simple brute forcing using recursion works.
But for some reason, I was getting WA when I was using a static variable, and later when I rather put that variable as a paramter passed in the function, I got AC.

Here is my simple solution with 0.00 time in all test cases:
http://www.codechef.com/viewsolution/5597230