Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 November Dwite Question 2 Problem
Index -> CompSci.ca, Contests -> DWITE
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Hypernon




PostPosted: Wed Nov 24, 2010 10:21 pm   Post subject: November Dwite Question 2 Problem

Hello, I'm a member of the team Happy Bunny. Keep in mind the code that I submitted for Question 2 does have an error in it, so don't look at that version of my code. I've since fixed my error, and I have what I believe to be a correct solution to Question 2, however when I run my program using the supplied Test Case, I don't get 5/5 cases correct. The test data supplied is:
134 54
1000 1
1000 666
645 32
68 2

And my program gives me these results:
73 (Correct answer is 85)
1 (Correct answer is 1)
316 (Correct answer is 346)
544 (Correct answer is 584)
68 (Correct answer is 68)

As you can see, I only get 2 out of 5 correct, however I am starting to think that the expected results are wrong. For example, it took me a while, but I did the first case manually on paper, and found out that the 54th person to walk into a theater of 134 seats would sit in the 73rd seat, not the 85th. This is keeping in mind that they will always sit in the largest open set of seats that is closest to the entrance, and within that set they will sit in the middle (If the set has an even number of seats they will sit at the lower of the two seats in the middle, because it is closest to the entrance). Am I just doing something wrong, or are the test results actually incorrect? I think I may be going a little insane here.

Just for clarification, I will depict my process of doing this problem for a set of 24 seats (seats are separated by commas):
Step 1: 1,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x
Step 1: 1,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,2
Step 1: 1,x,x,x,x,x,x,x,x,x,x,3,x,x,x,x,x,x,x,x,x,x,x,2
Step 1: 1,x,x,x,x,x,x,x,x,x,x,3,x,x,x,x,x,4,x,x,x,x,x,2
Step 1: 1,x,x,x,x,5,x,x,x,x,x,3,x,x,x,x,x,4,x,x,x,x,x,2
Step 1: 1,x,x,x,x,5,x,x,6,x,x,3,x,x,x,x,x,4,x,x,x,x,x,2
Step 1: 1,x,x,x,x,5,x,x,6,x,x,3,x,x,7,x,x,4,x,x,x,x,x,2
Step 1: 1,x,x,x,x,5,x,x,6,x,x,3,x,x,7,x,x,4,x,x,8,x,x,2
Step 1: 1,x,9,x,x,5,x,x,6,x,x,3,x,x,7,x,x,4,x,x,8,x,x,2
Step 1: 1,x,9,10,x,5,x,x,6,x,x,3,x,x,7,x,x,4,x,x,8,x,x,2
Step 1: 1,x,9,10,x,5,11,x,6,x,x,3,x,x,7,x,x,4,x,x,8,x,x,2
Step 1: 1,x,9,10,x,5,11,x,6,12,x,3,x,x,7,x,x,4,x,x,8,x,x,2
Step 1: 1,x,9,10,x,5,11,x,6,12,x,3,13,x,7,x,x,4,x,x,8,x,x,2
Step 1: 1,x,9,10,x,5,11,x,6,12,x,3,13,x,7,14,x,4,x,x,8,x,x,2
Step 1: 1,x,9,10,x,5,11,x,6,12,x,3,13,x,7,14,x,4,15,x,8,x,x,2
Step 1: 1,x,9,10,x,5,11,x,6,12,x,3,13,x,7,14,x,4,15,x,8,16,x,2

And then the remaining seats are filled in left to right order, meaning the 24th person would sit in seat 23.

I am sure that my program does this process because I manually printed out the array I am using to store the set of seats at each step (this was for the first test case), and it filled the seats in this exact manner. Is this not the correct way to fill the seats? I'd appreciate any help with my problem.
Sponsor
Sponsor
Sponsor
sponsor
A.J




PostPosted: Wed Nov 24, 2010 10:35 pm   Post subject: RE:November Dwite Question 2 Problem

Your working out was wrong. '4' should actually go where '5' is, and that changes things. Basically, I think you forget to read the part where I said:
"If multiple seats are equally far, then the person will sit closer to the entrance of the room."

I apologize if that part wasn't clear enough Sad
Hypernon




PostPosted: Wed Nov 24, 2010 10:42 pm   Post subject: RE:November Dwite Question 2 Problem

But multiple seats aren't equally as far. The right set of seats contains 11 seats while the left set contains only 10. If he sat on the left side, he'd be closer to other people than he would be if he sat on the right side. Is this not true? If he sat in the left set, he'd be 4 away from a person on his left side and 5 away from a person on his right side. That means the closest person to him is 4 away. But in the right set the closest person to him is 5 away. He wants to sit as far away from people as possible, and 5 is greater than 4.
A.J




PostPosted: Thu Nov 25, 2010 12:14 am   Post subject: RE:November Dwite Question 2 Problem

Ah, my mistake. I miscounted the number of 'x's. However, if you wanted the reasoning for the output of the official testcase, I could send you the output diagram (much like a siagram you have) for each of the testcase. I'll PM them to you.
A.J




PostPosted: Thu Nov 25, 2010 12:22 am   Post subject: RE:November Dwite Question 2 Problem

Oh, also, in the example you gave, the '10' is in the wrong place. It should be right beside the '1' (as that's the position closest to the entrance, and all other positions for the 10 is is the same distance to its closest person).
Hypernon




PostPosted: Thu Nov 25, 2010 6:37 am   Post subject: Re: RE:November Dwite Question 2 Problem

A.J @ Thu Nov 25, 2010 12:22 am wrote:
Oh, also, in the example you gave, the '10' is in the wrong place. It should be right beside the '1' (as that's the position closest to the entrance, and all other positions for the 10 is is the same distance to its closest person).


Ok, there's the problem. Thanks for pointing it out. I just assumed a person would rather have only 1 person directly next to them than 2 people. If anything, it was that part that wasn't clear enough in the question. I'm glad we've figured this out though.
Display posts from previous:   
   Index -> CompSci.ca, Contests -> DWITE
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 6 Posts ]
Jump to:   


Style:  
Search: