SANSKAR - Editorial

Good backtracking getting AC: SOLUTION

Thanks @code_overlord . Really appreciate that (y)

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

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

is this not the k-partition problem?

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

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

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

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

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

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

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

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.

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

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.

Very weak test cases. I am disappointed.

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

bruteforce (backtracking ) is acceped here!!!
CodeChef: Practical coding for everyone (my solution)

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

Hi,
Can any one please provide test cases for my [SOLUTION][1]. It gives WA for test cases 2,3,5.

Thanks and Regards
Prasad
[1]: CodeChef: Practical coding for everyone