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
Is there editorial in Russian, or someone can help me? please)
1 Like
@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.
hello everyone
I solved this problem with a simple backtracking
if you think in the complexity , you will give me the razon
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
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.
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.
Constraint are so small, that no DP is needed, check my solution - CodeChef: Practical coding for everyone
Yes, I used graphs.
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
exactly , that would be most interesting specially for this problem ,
@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
yeah … so many solutions are incorrect and the test cases are weak.
As I said, that would be so much fun 
1 Like
Your code fails for the test case 1 1 2 0 . Point here is a sanskar with zero intensity and no sanskar are not the same things. Your gode gives yes for this test case, while the answer is no. See here: 7mjBOX - Online C++ Compiler & Debugging Tool - Ideone.com
It passes. I’m the editorialist and here is my solution which I described in the editorial: CodeChef: Practical coding for everyone
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.
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
It was difficult to stop those wrong solutions with few test cases. We will be careful next time.