SANSKAR - Editorial

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:

1 Like
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: 7mjBOX - Online C++ Compiler & Debugging Tool - Ideone.com

44

Recursion: CodeChef: Practical coding for everyone

45

It passes. I’m the editorialist and here is my solution which I described in the editorial: CodeChef: Practical coding for everyone

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 EtDTSI - Online C++0x Compiler & Debugging Tool - Ideone.com
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…

1 Like
51

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

4 Likes
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:

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

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.

1 Like
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…

2 Likes
58

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

should be yes

59

Can be done on O(2^n * n)