SANSKAR problem DEC14

general
1

i don’t want you to reveal anything about the solution.

seeing the time limit on the question, i thought any naive approach would not be enough. By then, i start to think that this is the typical NP-hard problem.
So, is it that typical NP-hard problem i’m thinking about?? But how can a NP-hard problem can run in the given time limit for this question. And if you apply DP(though i have 2 WA already), how can it work for large sums for subtask #2?
P.S. If answering this reveals the solution or any algorithm applied to do this problem, then don’t answer it.

1 Like
2

As far as I know, yes It is NP-Hard Problem…
& yes It can be solved, although I’m also wondering how, but submission results have shown that It is possible…
So, keep trying…
Sleep. Code. Eat. Repeat.

1 Like
3

I think test cases for this problem weak. I think my code should have failed. I am trying to find cases where my code will fail.

2 Likes
4

As the constraints are low, it is possible to solve this NP-hard problem.But as a matter of fact, the subtask #2 is high for consideration. And yes, it is that NP-hard problem :wink:

5

what is task#2…my code is giving wrong answer for that
pls provide the test cases fr which my code is giving WA for SANSKAR

6

I have a doubt, serious doubt.

Is a sanskar allocated to only single follower ?

7

I found few boundary case in which my code is giving wrong answer but it is accepted.

8

Each follower must recieve at least one sanskari?

9

The answer should be yes , may be they are having weak test cases for such values .

10

I think they should’ve mentioned it…
A “sanskar with 0 intensity” and “no sanskar” are not the same things!

11

Does every sanskar have to be given to one follower?
Or can some sanskars remain undistributed?

eg. 1 1 1 2 are the sanskars to be distributed among 3 followers
can we give each follower sanksar of value 1, and leave the 2-sanskar undistributed?

thanks

12

I am getting WA in 2 testcase one in each subtask. Can someone please tell be any corner testcase?

13

An important point deduced from problem constraints.

A "sanskar with 0 intensity" and "no sanskar" are not the same things!

Mentioned in the Problem constraint as => ( 0 ≤ intensity of sanskar ≤ 10^5 )

14

Weak test cases for SANSKAR… We can get AC by using two different approaches for two subtasks even if one out this solution will give WA if the test cases are improved…and the other will give TLE…:slight_smile:

1 Like
15

If you find such case you can report it to feedback@codechef.com

16

think that might be true…

More i am correcting my code lesser test sets are passed…

17

after the contest is over :wink:

18

Read the problem statement, it’s written there…

19

Yes… :slight_smile: Each sanskar to a single follower :slight_smile:

20

Thanks to all…

I am fed up of solving this question, Approx to 20 submissions but WA… :frowning:

1 Like