SANSKAR - Editorial

editorial
, , , ,
21

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

22

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

23

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.

4 Likes
24

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.

25

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

26

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

27

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

28

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

29

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
30

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

31

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

1 Like
32

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

33

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
34

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

4 Likes
35

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.

36

http://www.codechef.com/submit/complete/587873-8759--549044e4867a4 I m getting TLE

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

38

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.

39

Very weak test cases. I am disappointed.

40

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!!