SANSKAR - Editorial

shivam1511 · December 17, 2014, 3:44pm

@damn_me

your solution is wrong!
fails for the following case:

1

6 3

9 9 2 8 1 1

ur just lucky!

no_load_1 · December 17, 2014, 6:20pm

bruteforce (backtracking ) is acceped here!!!
http://www.codechef.com/viewsolution/5591154 (my solution)

abcdexter24 · December 17, 2014, 7:27pm

You need to think of one thing here : assigning SANSKAR with 0 intensities is different than assigning nothing at all.

So you can try this test case:

2

5 2

0 0 0 0 0

2 5

0 0

answers :

yes

no

and do check my submissions for problem. www.codechef.com/DEC14/status/SANSKAR,abcdexter24

archazey · December 18, 2014, 9:28pm

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. http://www.codechef.com/viewsolution/5560280

prasadram126 · December 19, 2014, 12:33am

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]: http://www.codechef.com/viewsolution/5615560

rishabhprsd7 · December 19, 2014, 12:58am

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

rishabhprsd7 · December 19, 2014, 1:03am

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

atulkv · December 19, 2014, 4:25pm

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

rishabhprsd7 · December 19, 2014, 6:56pm

Try these cases:

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

If you get AC above test cases then add link to your code here…

codebreaker123 · December 20, 2014, 2:00am

@pkacprzak Please look at this.

wyvern · December 20, 2014, 12:37pm

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

thunderclash · December 20, 2014, 7:45pm

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

chaous · December 21, 2014, 2:04am

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

rishabhprsd7 · December 21, 2014, 10:12am

I am sorry i cannot translate it in Russian, but i can mention the cases for which your code is failing… I checked your code and found that out of 25 test cases your code failed in 9 test cases… Cases are…

6 3
1 2 1 2 1 2
yes
6 3
1 1 1 2 2 2
yes
1 2
0
no
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
9 2
3 2 1 1 1 1 1 1 1
yes
6 2
3 2 2 3 2 2
yes
8 3
7 3 3 1 1 4 1 1
yes

Your code fails on above mentioned test cases…

prasadram126 · December 21, 2014, 5:14pm

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

anju98 · October 2, 2018, 4:56pm

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.

anju98 · October 2, 2018, 5:01pm

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.