You are not logged in. Please login at www.codechef.com to post your questions!

×

SANSKAR - Editorial

2
2

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.

This question is marked "community wiki".

asked 15 Dec '14, 19:36

pkacprzak's gravatar image

5★pkacprzak ♦♦
75485097
accept rate: 12%

edited 24 Aug '18, 17:53

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 15 Dec '14, 21:59

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

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

(15 Dec '14, 22:01) acodebreaker21★

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

(15 Dec '14, 22:03) code_overlord3★

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.

link

answered 16 Dec '14, 05:00

xellos0's gravatar image

7★xellos0
5.9k54394
accept rate: 10%

2

Agreed, I think that if intensity is > 0 it won't make the problem easier, only easier to understand...

(16 Dec '14, 15:19) betlista ♦♦3★
4

It would also save me (and most likely many others) a few hours of trying to find the bug that doesn't exist.

(16 Dec '14, 17:40) xellos07★

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.

link

answered 16 Dec '14, 14:21

luc4sdreyer's gravatar image

4★luc4sdreyer
1427
accept rate: 10%

You need to think of one thing here : assigning SANSKAR with 0 intensities is different than assigning nothing at all.
So you can try this test case:
2
5 2
0 0 0 0 0
2 5
0 0
answers :
yes
no
and do check my submissions for problem. www.codechef.com/DEC14/status/SANSKAR,abcdexter24

(17 Dec '14, 19:27) abcdexter242★

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

link

answered 16 Dec '14, 17:02

codebreaker123's gravatar image

4★codebreaker123
1765
accept rate: 10%

1

@pkacprzak Please look at this.

(20 Dec '14, 02:00) codebreaker1234★

Is there editorial in Russian, or someone can help me? please)

link

answered 20 Dec '14, 12:37

wyvern's gravatar image

2★wyvern
11
accept rate: 0%

2

I am sorry i cannot translate it in Russian, but i can mention the cases for which your code is failing.. I checked your code and found that out of 25 test cases your code failed in 9 test cases.. Cases are..

6 3
1 2 1 2 1 2
yes
6 3
1 1 1 2 2 2
yes
1 2
0
no
5 2
1 1 0 2 2
yes
5 2
3 1 3 5 6
yes
10 2
4 5 1 5 5 0 5 1 4 8
yes
9 2
3 2 1 1 1 1 1 1 1
yes
6 2
3 2 2 3 2 2
yes
8 3
7 3 3 1 1 4 1 1
yes
Your code fails on above mentioned test cases..

(21 Dec '14, 10:12) rishabhprsd72★

Is there any other solution with out DP ?

link

answered 15 Dec '14, 19:38

achaitanyasai's gravatar image

5★achaitanyasai
2.2k61748
accept rate: 10%

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

(15 Dec '14, 19:58) betlista ♦♦3★

Yes, I used graphs.

(15 Dec '14, 20:18) thezodiac19946★
2

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

(15 Dec '14, 22:01) code_overlord3★
1

As I said, that would be so much fun :-D

(15 Dec '14, 22:08) betlista ♦♦3★
(15 Dec '14, 23:45) damn_me3★

It was difficult to stop those wrong solutions with few test cases. We will be careful next time.

(16 Dec '14, 12:23) shiplu2★
1

@damn_me
your solution is wrong!
fails for the following case:
1
6 3
9 9 2 8 1 1



ur just lucky! :P

(17 Dec '14, 15:44) shivam15115★
showing 5 of 7 show all

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.

link

answered 15 Dec '14, 19:44

chaitan94's gravatar image

4★chaitan94
2526
accept rate: 0%

edited 16 Dec '14, 16:04

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 :)

link

answered 15 Dec '14, 20:07

ab13123002's gravatar image

5★ab13123002
4126
accept rate: 8%

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

link

answered 15 Dec '14, 20:17

bovas's gravatar image

2★bovas
1
accept rate: 0%

edited 15 Dec '14, 20:37

2

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

(15 Dec '14, 21:54) code_overlord3★

Good backtracking getting AC: SOLUTION

link

answered 15 Dec '14, 22:11

znirzejskwarka's gravatar image

5★znirzejskwarka
1
accept rate: 0%

Thanks @code_overlord . Really appreciate that (y)

link

answered 15 Dec '14, 22:14

bovas's gravatar image

2★bovas
1
accept rate: 0%

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

link

answered 15 Dec '14, 23:04

asvcracker007's gravatar image

5★asvcracker007
-13159
accept rate: 0%

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

(15 Dec '14, 23:43) damn_me3★

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

link

answered 16 Dec '14, 00:01

sherwin21990's gravatar image

2★sherwin21990
11
accept rate: 0%

that would be a greedy approach.... It shouldn't work. But unfortunately it did work due to weak test cases. I've checked,these greedy solutions do fail on some test cases.

(16 Dec '14, 09:41) fauzdar652★

is this not the k-partition problem?

link

answered 16 Dec '14, 00:38

jporcelli11's gravatar image

3★jporcelli11
1
accept rate: 0%

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

link

answered 16 Dec '14, 02:49

mansigupta19's gravatar image

1★mansigupta19
431419
accept rate: 0%

It passes. I'm the editorialist and here is my solution which I described in the editorial: http://www.codechef.com/status/SANSKAR,pkacprzak

(16 Dec '14, 04:43) pkacprzak ♦♦5★

@pkacprzak , check this http://ideone.com/EtDTSI this is your solution with Max constraints, giving TLE

Even my own DP solution gives TLE for this case though.

(16 Dec '14, 14:55) fauzdar652★

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

link

answered 16 Dec '14, 10:11

king_of_hacker's gravatar image

3★king_of_hacker
204312
accept rate: 7%

This is a wrong solution ! You can't greedily choose a subset with valid sum and remove those elements. Such a solution would most probably fail the following test case: 1 8 3 4 4 5 6 8 3 3 6

(16 Dec '14, 11:52) fauzdar652★

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

link

answered 16 Dec '14, 11:15

rohan_30193's gravatar image

1★rohan_30193
1
accept rate: 0%

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

link

answered 16 Dec '14, 15:20

ar56's gravatar image

3★ar56
-32
accept rate: 0%

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.

link

answered 16 Dec '14, 18:29

zhupeijun's gravatar image

4★zhupeijun
11
accept rate: 0%

edited 16 Dec '14, 18:37

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

link

answered 16 Dec '14, 21:15

thunderclash's gravatar image

5★thunderclash
183
accept rate: 0%

I have one query. My friend made this solution wherein he found all the masks whose sum was (total/k) and pushed them in a vector. After that he did this method of checking.

bool flag = false;
for(int i=0; i<test.size(); i++) { int cur = test[i]; int cnt = 1; for(int j=0; j<test.size(); j++) { if((cur & test[j]) == 0) { cur |= test[j]; cnt++; } }

        if(cur == ((1<<n) - 1) && cnt == k)
        {
            flag = true;
            break;
        }
    }

Link: http://www.codechef.com/viewsolution/5513412 Can anyone explain me how does this method covers all the subsets of choosing 'k' masks? I know that a recursive method of finding 'k' masks will surely give the correct answer but how does this method do that? Any help is appreciated.

link

answered 17 Dec '14, 12:52

ishaangupta's gravatar image

4★ishaangupta
11
accept rate: 0%

edited 17 Dec '14, 12:56

Very weak test cases. I am disappointed.

link

answered 17 Dec '14, 14:37

shinjiikari's gravatar image

5★shinjiikari
15117
accept rate: 0%

It is really really disappointing to see solutions implementing bruteforce being accepted. Not just that, even wrong solutions are accepted which fail in simple test cases.

eg- This solution- http://www.codechef.com/viewsolution/5573665
This fails for the simple test case-
1
6 3
8 1 1 9 9 2
Clearly the correct answer is yes but this solution gives no.

Am sure there are many more cases like these.

@admin
Please look into the matter and ensure stronger test cases!!

link

answered 17 Dec '14, 15:26

shivam1511's gravatar image

5★shivam1511
4382414
accept rate: 22%

edited 17 Dec '14, 15:26

bruteforce (backtracking ) is acceped here!!! http://www.codechef.com/viewsolution/5591154 (my solution)

link

answered 17 Dec '14, 18:20

no__load's gravatar image

3★no__load
1
accept rate: 0%

I made an array of all bits configurations with sum S/k(of course,if S%k==0) and used recursive function to choose the configuration for my k-th follower,than for the (k-1)-th.Also to boost my time ,I made some improvements such as taking individually the configurations of 1 and 2 elements(because those pairs are unique). I think I submitted around 30 code sources,before I got 100 points.My question is how cand you say that O(k * (2^n) * n) for EACH TESTCASE can get AC?That complexity takes around 1s for each test case... From now on please give a solution that really fits in the worst testcases or make the constraints lower.It's not nice to see that some stupid optimizations give you 100 points. I'll let my source code here,if someone is interested in it. http://www.codechef.com/viewsolution/5560280

link

answered 18 Dec '14, 21:28

archazey's gravatar image

6★archazey
572
accept rate: 0%

Hi, Can any one please provide test cases for my SOLUTION. It gives WA for test cases 2,3,5.
Thanks and Regards
Prasad

link

answered 19 Dec '14, 00:33

prasadram126's gravatar image

2★prasadram126
121
accept rate: 0%

@ prasadram126
Your code fails at cases where

(sum_of_intensities%follower == 0) but ((sum_of_intensities/follower) < max_value_in_list)
Check this test case:
9 4
0 0 4 1 5 4 2 0 8
Answer should be no but your code output yes.

link

answered 19 Dec '14, 00:58

rishabhprsd7's gravatar image

2★rishabhprsd7
1.9k11243
accept rate: 14%

You may use these test cases to check your code:

5 3
0 0 0 0 0
yes

6 3 1 2 1 2 1 2 yes

6 3 1 1 1 2 2 2 yes

6 2 0 5 1 3 1 4 yes

7 1 4 3 3 4 1 4 3 yes

8 3 2 2 0 0 1 3 2 6 no

9 4 0 0 4 1 5 4 2 0 8 no

1 2 0 no

3 2 0 0 0 yes

5 3 3 0 2 4 6 no

3 3 2 4 7 no

5 2 4 5 3 2 6 yes

5 2 1 3 4 4 6 yes

5 2 1 1 0 2 2 yes

5 2 3 1 3 5 6 yes

10 2 4 5 1 5 5 0 5 1 4 8 yes

7 1 4 3 3 4 1 4 3 yes

9 2 3 2 1 1 1 1 1 1 1 yes

6 2 0 5 1 3 1 4 yes

2 2 0 0 yes

6 2 3 2 2 3 2 2 yes

8 3 7 3 3 1 1 4 1 1 yes

5 2 1 3 3 3 4 yes

6 3 3 7 3 1 4 3 yes

3 3 3 0 0 no

link

answered 19 Dec '14, 01:03

rishabhprsd7's gravatar image

2★rishabhprsd7
1.9k11243
accept rate: 14%

First i checked if dividing in subsets of appropriate sum is possible or not.... then I arranged the array in decreasing order, and took the first and searched for possible partners in its subgroup through the array... if i dont get it i jumped to the next in array and checked the whole array again for partners... If i would find a subset... i will mark all its elements as taken and count++... in the check if count is equal to k... Now the problem is I got 80 points for it.. WA for only 1 testcase in 4 of 20 point.. Any help of any kind would be appreciated... Thanks

link

answered 19 Dec '14, 16:25

atulkv's gravatar image

3★atulkv
1
accept rate: 0%

Try these cases:

5 3
0 0 0 0 0
yes

6 3 1 2 1 2 1 2 yes

6 3 1 1 1 2 2 2 yes

6 2 0 5 1 3 1 4 yes

7 1 4 3 3 4 1 4 3 yes

8 3 2 2 0 0 1 3 2 6 no

9 4 0 0 4 1 5 4 2 0 8 no

1 2 0 no

3 2 0 0 0 yes

5 3 3 0 2 4 6 no

3 3 2 4 7 no

5 2 4 5 3 2 6 yes

5 2 1 3 4 4 6 yes

5 2 1 1 0 2 2 yes

5 2 3 1 3 5 6 yes

10 2 4 5 1 5 5 0 5 1 4 8 yes

7 1 4 3 3 4 1 4 3 yes

9 2 3 2 1 1 1 1 1 1 1 yes

6 2 0 5 1 3 1 4 yes

2 2 0 0 yes

6 2 3 2 2 3 2 2 yes

8 3 7 3 3 1 1 4 1 1 yes

5 2 1 3 3 3 4 yes

6 3 3 7 3 1 4 3 yes

3 3 3 0 0 no

If you get AC above test cases then add link to your code here.. :)

(19 Dec '14, 18:56) rishabhprsd72★

@ishaangupta it actually isn't trying to choose all the possibilities, it just tries to find whether the required subset is present.

The entire thing would be like this: You have a vector with all the masks. Any 2 masks can be used together only when both have no element common, since one Sanskar can be given to only one follower. This is checked using the bitwise &.

Further, the condition for having found a successful subset is that- all the sanskars have been chosen, and K values are present in the subset selected, this is checked in the if using the 1<<n - 1 and other expression.

The flow would be of this sort, First the outer for loop selects a starting element. The inner loop selects the values which are 'compatible' with the current selection, I.e. which do not use sanskars already is use, and after finding these values, updates the cur variable to make notice of this addition of a value.

And then basically it goes through all values, doing the same thing. If there are n sanskars, then the number ((1<<n)-1) simply is a series of 1s, it is the number corresponding to the case when each and every Sanskar has been used.

Eg if n is 4, then it would be 1111, which corresponds to the selection of all 4 sanskars.

Using this method, if at any point the required condition is reached, we break after setting a flag.

link

answered 20 Dec '14, 19:45

thunderclash's gravatar image

5★thunderclash
183
accept rate: 0%

hello everyone I solved this problem with a simple backtracking if you think in the complexity , you will give me the razon

link

answered 21 Dec '14, 02:04

chaous's gravatar image

6★chaous
1
accept rate: 0%

Hi,
can any one please share the solution, which is implemented of editorial . Because i have some doubts in that like what is the size of "dp" and how to initialize it?
Thanks

link

answered 21 Dec '14, 17:14

prasadram126's gravatar image

2★prasadram126
121
accept rate: 0%

can anyone tell me why don't we do sum of all n intensity and if sum%by k followers == 0 then ans is YES otherwise NO. I only passed starting 2 test cases why this logic is not correct according the statement given into problem.

link

answered 02 Oct '18, 16:56

anju98's gravatar image

2★anju98
233
accept rate: 0%

can anyone tell me why don't we do sum of all n intensity and if sum%by k followers == 0 then ans is YES otherwise NO. I only passed starting 2 test cases why this logic is not correct according the statement given into problem.

link

answered 02 Oct '18, 17:01

anju98's gravatar image

2★anju98
233
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,875
×3,828
×2,220
×371
×228

question asked: 15 Dec '14, 19:36

question was seen: 16,109 times

last updated: 02 Oct '18, 17:01