Help the DJ

In the example mentioned, if the DJ shows only one song in the playlist either  0,1 or 2, the score would be 2.

So do we need to maximize the number of songs as well...?

Should I take the last sentence:

"Notice that, as the playlist will be projected on a screen, dancers who don't see any song they like will leave immediately."

to mean that if a dancer has a boredom factor of, say, 100, and we only play 90 songs, but he likes none of those songs, he still leaves (even though we played less "boring" songs to him then his boredom factor)? So in other words does that mean that for every dancer we should play at least one song he/she likes?

Wouldn't it be more optimal if we choose only the first two songs? That way 3 people will stay all the time, the score will be 3. If we choose the first two songs the first dancer we like the first song, but not the second, but his boredom factor is hign enough for him to stay.There will be no songs for  the second dancer so he would be the only one to leave. The third dancer will like the first two , but he won't hear the third and the fifth that he likes, but his boredom factor is hign enough for him to stay at the party. And last, the fourth dancer, he will like the second song, but not the first, and that is enough for him to stay

@Abhinava The scoring for the problem doesn't include the number of songs being played, it depends on the number of dancers left at the end of the party.

@Eisenberger Yes, what is mentioned in the problem statement is correct.

If number of songs being played is not considered, there would be more than one slutions as I mentioned in my previous post...

The solution which has the most number of people left at the end would be most optimal.

As discussed after the last contest, will the input be generated uniformly randomly within the constraints?

In the example, the scoring is 2 but if we select songs 0 2 1, this will not let dancer 1 to leave the floor, so thats an better answer than the one in current example.

If we go for songs 0 4 1, then dancer 1 will leave the floor immediately, otherwise taking songs 0 2 1, he wouldn't leave considering the boredom factor (B) = 3. So, the party will end up with 3 dancers scoring better than whats given in the example.

Please correct me if I've mistaken anything :)

@Sumit Re-read the problem statement.

@stephen Yes, we have tried our best to keep it random

@Vipul The example is just that - an example. This is a challenge problem. The better your score, the higher your rank.

Something is wrong with the display of scores in the submissions section. I accidentally submitted the same solution twice, the first one said 2040 [0.99 points], and the second 2040 [1.185 points]. Doesn't seem to affect the scoreboard though.

Dear Admin,

I am slightly confused. You said that the scoring does not depend on the number of songs played. I can always chose 1 song so that no one leaves. What is wrong with that? If I do that then my score is extremely low. Can you specify how is scoring done?

Sandeep

Read the problem statement:

Notice that, as the playlist will be projected on a screen, dancers who don't see any song they like will leave immediately.

Thanks Stephen! I noticed that but I am still missing something!

Well, that immediately implies what you said is wrong.

When does a dancer leave?

In the above example, say, I play songs in the order 2 1 0, with dancer 1 liking the 0th song and having boredom of 2. Will he stay on to hear song #0, which is the 3rd song of the night. Or will he leave after hearing song #1, which is the 2nd song of the night, as his boredom factor would have gone on to zero?

@ Prashanth

Read this carefully : -

Notice that, as the playlist will be projected on a screen, dancers who don't see any song they like will leave immediately.

So a person with boredom factor b will leave if there occurs a sequence of b  consecutive songs in the play list, none of which he likes.

Correct me if wrong.

Print the number of songs selected (P) for the playlist on a single line. Then print P integers, each one on a single line, indicating the songs selected, in any order. Notice that selecting a song more than once is not something a self-respecting DJ would ever do, so this will lead to Wrong Answer. The song numbers start from 0, i.e., print 0 when selecting the first song and S-1 when selecting the last.

not able to understand the output please help me

@sriram: dont confuse the two statements. If there is no song that a dancer likes, he will leave immediately without listening to even one. period.

My confusion is, say there are two songs - S0 and S1. Dancer is A, who likes S1. Boredom factor of Dancer A = 1.

If my playlist is S0, my score is 0. If my playlist is S1, my score is 1. This is understood. But if my playlist is S0 S1, then what will my score be? Simple.

Mods, could you please answer this? Its not a test case, it is just that I am trying to understand the problem statement. I want to know at which point the boredom factor make a dance leave the disco. Sorry if am missing something or unable to understand the problem statement.

I have given correct solution for Help The DJ then why have I not got the points for it? My score is still 0

Does length of solution matter?

@ Prashanth

The score will be 0, as Dancer A will leave after hearing the 1 song he doesn't like.

@ sriram

The order of the playlist is completely irrelevant, a dancer will leave after hearing B songs they don't like regardless of whether they are consecutive or not.

@ Piotr

That has been answered already; the score solely depends on the number of dancers remaining.

what is the length of the playlist for a solution?

It would be really nice to know the random distributions used for the B's (is every B uniformly and randomly chosen from [1,S]?) and the M's (does every person have a 50% chance of liking each song, or are there some people that like 90% of the songs and others who like 10%?).

@Josh we will include distribution of test data for all future contest challenge problems.  if you have any other feedback please let us know ~amit

please post the testcases...

You are telling runtime error but have no clue why...

@Stephen,

How do you see the order to be relevant, as in Prashanth's question.

If the playlist is S0 S1, then the score is 0, and if the playlist is S1 S0, then the score is 1. Isnt it ?

By my understanding, regardless of the order, dancer one will leave after hearing the song he doesn't like. Ie the order isn't important, only the number of songs on the list that each person doesn't like.

How would the program take inputs? As command line arguments or through some text file input? I will be writing C# file so generating an exe would be fine for submission? Or I need to generate a dll?

There is something wrong with the scoring. I am not getting any score for some of my submissions. It just says correct. Not even 0.

The time limit says 15s. If I submit a program which does nothing for 5 seconds then quits, I get time limit exceeded. What is the correct time limit? (If there are different time limits for different inputs, we need to know precisely which time limits apply to which inputs).

Thanks - I thought I was going crazy, as my time limit checking code was working fine locally, but I kept getting TLE on submit, even when I reduced the limit to 5s.

It is a major frustration to have one time limit in the problem statement and another for submissions.

+1

It happened with me too.

why does it give runtime error for the code when its running on my pc?

Time limit is 2-15 seconds.

What does that mean? We need to know which cases have a time limit of what otherwise the whole point of a time limit is kind of ruined.. and that is the most important part of a challenge problem.

We will try including this information from the next contest along with the distribution of data.

but how many songs should I put in the list ?

Hi,

Can anyone tell me where to find details about Tie Breaker problems?

The questions i have are like

1. Will my solution be accpedted if it solves all the test cases correctly or it will accept the solution anywyas but scoring will be = no of test cases passed?

2. IS scoring based on correct soluton*rel performance?

I guess it will be better if i can get some link where these kind of info regarding tie breaker probs are present?

Thanks

It was mentioned by Aniruddha(Codechef) that time limit is 2-15sec in comments but in problem statement, it clearly says that its 15 sec?

And how to know what score I received? In problem page in recent activity, it just shows whether accepted or not for me but fr others it shows scores?

Wow, 2157!  I'm impressed.  Josh, I think you can go to bed. :)  (I concede, in any case.)

I was surprised, too.  Of course, I was surprised when you got 2155, and then again when I got 2156.  I'm done now, though.

1. Will my solution be accpedted if it solves all the test cases correctly or it will accept the solution anywyas but scoring will be = no of test cases passed?

You need to pass all test cases, else you will get a WA.

2. IS scoring based on correct soluton*rel performance?

I don't quite get what you mean by the *, but yes, the performance is relative to the best score on the problem.