SANSKAR - Editorial

bit
dec14
dynamic-programming
easy
editorial

#41

yeah … so many solutions are incorrect and the test cases are weak.


#42

As I said, that would be so much fun :smiley:


#43

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: http://ideone.com/7mjBOX


#44

Recursion: http://www.codechef.com/viewsolution/5552989


#45

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


#46

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.


#47

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


#48

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


#49

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


#50

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


#51

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


#52

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


#53

@damn_me

your solution is wrong!
fails for the following case:

1

6 3

9 9 2 8 1 1



ur just lucky! :stuck_out_tongue:


#54

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


#55

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… :slight_smile:


#56

@pkacprzak Please look at this.


#57

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…


#58

if getting wa for subtask 2 last test case:
check
1
4 2
0 0 0 0

should be yes