Help the DJ

Problem code: JX

All Submissions

All submissions for this problem are available.

DJ N3xt0r could hardly sleep last night. He thought he was doing his job so well, but it seems like the dancers at the disco are looking for a whole different kind of music these days and the place has become nearly empty. Being the best DJ ever, he would not let that happen again. So he pulled some strings and gathered valuable information regarding the musical preferences of the dancers expected to attend the disco tonight. By 8.00PM, DJ N3xt0r has a file with the following info:

The number of dancers (D) expected to attend tonight.
The number of songs (S) on his laptop media library.
The boredom factor (B) of the dancers: the number of songs disliked by a dancer that will play before he gets bored and leaves the disco.
The musical preferences of the dancers represented by a D-row S-column matrix (M). If M_ij = 1 then dancer i likes song j. If M_ij = 0 he does not like the song.

He wants to build a playlist such that the number of dancers present when the party ends is maximized. Desperate, DJ N3xt0r seeks for your help. He will make you a VIP member of the disco if you write a program that performs the task. Notice that, as the playlist will be projected on a screen, dancers who don't see any song they like will leave immediately.

Input

Input starts with two integers (1 <= D, S <= 500) separated by a single space. The next line contains the boredom factors of the dancers (1 <= B₁, B₂…, BD <= S) separated by single spaces. The next D lines describe the M matrix. Each line represents the musical preferences of a dancer, and will consist of S binary integers (0, 1) separated by single spaces.

Output

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.

Scoring

Points scored for a single test will equal the number of dancers present when the party ends according to your playlist. The total score of the program is the sum of points scored in all tests.

Example

Input:
4 5
2 3 3 4
1 0 0 0 0
0 0 1 0 0
1 1 1 0 1
0 1 0 0 0
Output:
3
0
4
1
Scoring:
2

Date:	2009-10-15
Time limit:	15s
Source limit:	50000
Languages:	C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK CAML CLPS PRLG WSPC BF ICK TEXT JS

Submit

Comments

Login or Register to post a comment.

In the example mentioned, if

Abhinava Srivastava - 1st Nov,2009 15:39:54.

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

Eisenberger András - 1st Nov,2009 16:58:13.

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

Dejan - 1st Nov,2009 17:53:07.

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

Admin - 1st Nov,2009 18:05:04.

@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

Abhinava Srivastava - 1st Nov,2009 18:37:30.

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

Admin - 1st Nov,2009 18:41:24.

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

sir i don't understand what u

sumit - 2nd Nov,2009 02:48:39.

sir i don't understand what u want to say so please be clear

As discussed after the last

Stephen Merriman - 2nd Nov,2009 10:00:17.

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

In the example, the scoring

toxboi - 2nd Nov,2009 10:59:55.

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

Admin - 2nd Nov,2009 13:56:22.

@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

Stephen Merriman - 3rd Nov,2009 03:03:10.

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

Sandeep Pathak - 3rd Nov,2009 06:42:52.

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

Stephen Merriman - 3rd Nov,2009 07:23:24.

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

Sandeep Pathak - 3rd Nov,2009 07:46:51.

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

Well, that immediately

Stephen Merriman - 3rd Nov,2009 09:28:10.

Well, that immediately implies what you said is wrong.

When does a dancer leave? In

Prashanth K S - 3rd Nov,2009 09:31:25.

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

sriram - 3rd Nov,2009 12:01:39.

@ 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

kschetan - 3rd Nov,2009 20:54:37.

not able to understand the output please help me

@sriram: dont confuse the two

Prashanth K S - 3rd Nov,2009 21:14:02.

@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

Gunjan Sharma - 3rd Nov,2009 22:45:36.

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

Piotr Mikulski - 4th Nov,2009 03:13:30.

Does length of solution matter?

@ Prashanth The score will be

Stephen Merriman - 4th Nov,2009 12:08:01.

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

In the example mentioned, if

vasudev karthik - 4th Nov,2009 18:47:25.

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

what is the length of the

vasudev karthik - 4th Nov,2009 18:50:49.

what is the length of the playlist for a solution?

It would be really nice to

Josh Metzler - 5th Nov,2009 06:57:48.

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

Admin - 5th Nov,2009 16:49:30.

@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

Abhinava Srivastava - 5th Nov,2009 17:00:38.

please post the testcases...

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

@Stephen, How do you see

Ajay Somani - 6th Nov,2009 02:58:51.

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

Stephen Merriman - 6th Nov,2009 12:28:59.

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

Triguna M S - 7th Nov,2009 00:38:07.

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

Nadeem Moidu - 7th Nov,2009 17:31:52.

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

Stephen Merriman - 8th Nov,2009 08:17:43.

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

Josh Metzler - 9th Nov,2009 08:17:09.

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.

Ajay Somani - 9th Nov,2009 12:00:23.

It happened with me too.

why does it give runtime

anuj jamwal - 9th Nov,2009 16:08:16.

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

Time limit is 2-15 seconds.

Admin - 9th Nov,2009 19:32:22.

Time limit is 2-15 seconds.

What does that mean? We need

Stephen Merriman - 10th Nov,2009 02:06:30.

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

Admin - 10th Nov,2009 03:46:37.

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

but how many songs should I

German Gonzalez - 10th Nov,2009 19:29:19.

but how many songs should I put in the list ?

Hi, Can anyone tell me where

Satyendra Mishra - 10th Nov,2009 23:37:27.

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

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