SANSKAR - Editorial

editorial
, , , ,
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.

23

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

24

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

25

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

26

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

27

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

28

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
29

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

30

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

1 Like
31

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

32

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

33

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

34

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.

35

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.

36

Constraint are so small, that no DP is needed, check my solution - CodeChef: Practical coding for everyone

37

Yes, I used graphs.

38

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ā€.

2 Likes
39

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

40

@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ā€.

2 Likes