SANSKAR - Editorial

editorial
, , , ,
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: CodeChef: Practical coding for everyone

Finally I got it accepted here: CodeChef: Practical coding for everyone 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:

1 Like
5

@chaitan, since the limit is small , we can solve it using brute-force.
here is my solution CodeChef: Practical coding for everyone
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.

1 Like
6

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

10 Likes
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.

5 Likes
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 (CodeChef: Practical coding for everyone) got AC

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

2 Likes
15

i am getting WA for 6 subtasks can you provide any testcase where my solution failed or any bug.
here is the link CodeChef: Practical coding for everyone

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.

3 Likes
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- CodeChef: Practical coding for everyone

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

2 Likes
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

21

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: CodeChef: Practical coding for everyone
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.

22

Very weak test cases. I am disappointed.