Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
November Dwite Question 2 Problem
Author Message
Hypernon

Posted: 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.

A.J

Posted: 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
Hypernon

Posted: 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

Posted: 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

Posted: 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

Posted: 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: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 6 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: