Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Grouping
Author Message
klopyrev

Posted: Tue Mar 13, 2007 1:40 am   Post subject: Grouping

Suppose you are given a group of people who need to be seated at tables during an event for several rounds. There is a limit to the maximum number of people at a table. Each round consists of people introducting themselves to each other. At the end of a round, the people get up and move to their next assigned table. If two people who have already met end up at the same table, that is a collision. Also, you are told that some of the people met before the event. These people are given in pairs. The input is as follows.

1) The number of people. (1 < N < 100)
2) The maximum number of people per table (1 < P < 10)
3) The number of rounds (0 < R < 10)
4) Several pairs of numbers, A and B, which mean that A and B have already met and them being at the same table would be a collision.

Note: At the conclussion of the round, if A and B were at the same table, they are considered to have met for the next round.

The task is to provide a list of table assignments for each of the people attending the event. Tables are labelled by letters and people by numbers. This list of assignments should maximize the number of people who have met and minimize the number of collisions.

KL

klopyrev

Posted: Wed Mar 14, 2007 5:18 pm   Post subject: Re: Grouping

Is anyone going to reply and help me out...
Cervantes

Posted: Wed Mar 14, 2007 7:08 pm   Post subject: RE:Grouping

It's a tough problem; you might have to give it time. Also, your post never suggested you needed help. I interpreted it as, "hey everyone, look at this cool problem I've found. Can you solve it?", not, "Can someone help me solve this?"
klopyrev

Posted: Wed Mar 14, 2007 7:11 pm   Post subject: Re: Grouping

Sorry, forgot to mention that I can't solve it myself. If anyone can think of a solution, please tell me.

KL
Fevian

Posted: Wed Mar 14, 2007 10:10 pm   Post subject: RE:Grouping

Well, are you making a program for this or is just a math problem. If it's just math, make a few linear equations, with an x and y. You'll also for a couple of them have to use R and P so you can get that. Other than that, it's just points, graphing, blah blah. Algebra.
klopyrev

Posted: Wed Mar 14, 2007 11:31 pm   Post subject: Re: Grouping

I have no idea how to make linear equations from the question above. Please explain.

KL
ericfourfour

Posted: Thu Mar 15, 2007 4:32 pm   Post subject: Re: Grouping

klopyrev wrote:
maximize the number of people who have met and minimize the number of collisions.

Those two words make me think quadratics. Although, I really have no clue how to solve this problem.
klopyrev

Posted: Sun Mar 25, 2007 5:52 pm   Post subject: Re: Grouping

Hello? Anyone there???

abcdefghijklmnopqrstuvwxy

Posted: Sun Mar 25, 2007 6:18 pm   Post subject: RE:Grouping

Quote:

This list of assignments should maximize the number of people who have met and minimize the number of collisions.

I'll give you a tip, once you've determined all possible different combinations for a given number, all of the future combinations will ALWAYS be collisions. So all you have to do is develop one equation or algorithm that finds all possible combinations, by doing this you have succeeding in achiefing the minimal amount of collisions.

Does that help?
klopyrev

Posted: Sun Mar 25, 2007 6:26 pm   Post subject: Re: Grouping

I don't get what you mean by all possible combinations for a given number.
abcdefghijklmnopqrstuvwxy

Posted: Sun Mar 25, 2007 6:37 pm   Post subject: RE:Grouping

The number of people would be the "given number".

Now this would depend on T for number of tables.

Normally N^2 would give you the possible combinations, but since you wan't to minimize collisions you have to weed out the combinations which consist of the same numbers being reversed or reused in a combination. I.E. all the 1-1's, 2-2's.

I guess I mine as well just do it for you...

EDIT: hold on, i'll give you an equation, the one i posted previous didn't work.

((N^T - N)/2) = TotalCombosWithoutCollisions. Don't ask me to do the boring tedious part of printing out all different combos, i'll leave that to you, hopefully you know how to do a for loop and print to the standard output.

Do you get it now klopyrev?

Rounds R would fit in to figure out if there will be any collisions and if so how many.

So if ((N^T - N)/2) > R*T then you won't have an collisions. If you do have collisions than you will have R*T - ((N^T - N)/2) collisions.

Freakman Edit: Triple post combined into one, there's an edit button for a reason.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 11 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: