Couldn't understand Sanskar....Help!!

[snow3]

Please if anyone could help me to understand the Sanskar problem in December Challenge 2014.I will be really grateful to you .I have read the tutorials but am not able to understand the solution.Please Help!!.If explanation could be an elaborate one like for a beginner, that would be great!!

[rishabhprsd7]

okay…

consider sample test case

5 3

1 2 4 5 6

problem says that can you distribute these values present in array to 3 followers equally.

Considering above test case,
you may assume that lets check whether sum of all elements mod number of followers(which in this case is 3) is equal to 0 or not so

You may check:
arraySum%followers==0

so it passes this case as

1+2+4+5+6=18 and 18 %3 ==0

so this can be accepted that there is a chance that all numbers can evenly be distributed to k followers(i.e. 3)

Now you may ask what do i mean by even distribution?

So answer is that without changing the values of element in array can i distribute those value to followers or not…

Okay to make it simple,

Consider you have 3 friends and 5 chocolates of different weights and you have to distribute those chocolates to your 3 friends but since they are your best friends you cannot give uneven weight chocolates to them (assuming you dont like chocolates, or you like your friends more than anything else).

Now,
weights of chocolates are

[ 1unit 2unit 4units 5units 6units ]

Now you cannot cut those chocolates to make it equal so Can you evenly distribute chocolates to your friends?

This is the question…!!

Now Approach is

First calculate what is the amount of chocolate you need to distribute… so it can be calculated as total weight divided by number of friends

i.e. 18/3=6

SO you got an idea that you have to distribute 6units of chocolate to each

Now how to do that

Call your first friend and give him a chocolate that weigh 6units… remember that you hav chocolates of( 1, 2, 4, 5, 6) units.

As you gave a chocolate of 6units to your first friend now you have chocolates with weights(1,2,4,5)and two more friends are waiting.

Call second friend and offer him chocolate with weigh(2 and 4) as 2+4 makes 6… now chocolates left with you are(1,5)…

So finally call your third friend and give him chocolates which weigh (1 and 5) as 1+5=6…and so there are no left chocolate with you and you successfully distributed chocolates to your k (3) friends…

So answer is YES for test case

5 3
1 2 4 5 6

…

Now here assume a case that you have two friends but you have only one chocolate which weigh 0units(remember you can still distribute that chocolate to you friend,hypothetical case)

so you can give a chocolate to your first friend which weigh 0units but you dont have any chocolates left to give to your second friend… So sad… SO answer is No for test case…

1 2

0

---

Also consider a case you have two chocolates which weighs(1unit ans 3units) an you have two friends

Calculate total which which has to be distributed to each friend, 4/2 is 2.

Now check your pocket, you’ll find there is no chocolate which can be added up to make a sum of 2 and there is no chocolate which weigh 2 so you cannot distribute chocolates evenly to your friends… SAD isn’t it?

So answer is NO for test case…

2 2
1 3

---

EDIT:
These are some of the test cases, check them to get a better understanding…!

Just check whether exist subarrays in the given array which could sum up to the number which you have to distribute,

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 still have any doubts regarding problem or any test case you may ask here…

Hope you understood!!

[gvaibhav21]

There are a number of approaches for this problem, since the constraints are small. What the problem demands is that given an array of non-negative integers, is it possible to divide the array into ‘k’ non-empty sub-sets with equal sum.

My approach: Firstly check if the sum of all sanskars is divisible by the number of followers. If yes, then sort the sanskars according to their intensities, and then start trying to create ‘k’ subsets with equal sum x (where x= (sum of all elements)/(no. of followers) ). In order to do this, i used recursion.

In the start, allot the largest sanskar to a subset. Then, taking largest sanskar unalloted till now, temporarily allot that sanskar to the “current” subset, seeing if the sum of the subset exceeds x or not. If yes, do not assign this sanskar and proceed to the next largest sanskar. Proceeding in this way, if no possible further selection of sanskars is possible which can provide a sum of exactly ‘x’, discard the previously ‘temporarily’ allotted sanskar and similarly proceed the above procedure for the next largest sanskar.
Now, at the end of recursion, if we have been able to assign ‘k’ subsets, then answer is “yes” otherwise the answer is “no”…

Try to understand it using my code: ideone.com/9jEkzn

I am sorry if the explanation got a little messy, it’s quite difficult to explain backtracking without the example of code.Try to understand using the code in the link

[snow3]

Thanks @rishabhprsd7 for your time and effort to explain it such elaborately.
Thank you so much!!

[snow3]

I will definitely try out that approach…Thanks:)

[rishabhprsd7]

bro one gain knowledge by sharing…

you’re most welcome…

and if you still have any doubts you may ask it without hesitation…!