|
04-12-2008, 05:06 AM
| #1 |
| Banned Join Date: Nov 2007
Posts: 678
| how do i solve this problem? [ Problem B | 1999 ACM Finals problem set | My ACM problem archive | my home page] The 23rd Annual ACM International Collegiate Programming Contest WORLD FINALS sponsored by http://www.karrels.org/Ed/ACM/99/bigblue.gif Problem A Bee Breeding Professor B. Heif is conducting experiments with a species of South American bees that he found during an expedition to the Brazilian rain forest. The honey produced by these bees is of superior quality compared to the honey from European and North American honey bees. Unfortunately, the bees do not breed well in captivity. Professor Heif thinks the reason is that the placement of the different maggots (for workers, queens, etc.) within the honeycomb depends on environmental conditions, which are different in his laboratory and the rain forest. As a first step to validate his theory, Professor Heif wants to quantify the difference in maggot placement. For this he measures the distance between the cells of the comb into which the maggots are placed. To this end, the professor has labeled the cells by marking an arbitrary cell as number 1, and then labeling the remaining cells in a clockwise fashion, as shown in the following figure. Code:
__ __ __ __
__/ \__/ \__/ \__/ \__
__/ \__/ \__/53\__/ \__/ \__
/ \__/ \__/52\__/54\__/ \__/ \
\__/ \__/51\__/31\__/55\__/ \__/
/ \__/50\__/30\__/32\__/56\__/ \
\__/49\__/29\__/15\__/33\__/57\__/
/ \__/28\__/14\__/16\__/34\__/ \
\__/48\__/13\__/ 5\__/17\__/58\__/
/..\__/27\__/ 4\__/ 6\__/35\__/ \
\__/47\__/12\__/ 1\__/18\__/59\__/
/..\__/26\__/ 3\__/ 7\__/36\__/ \
\__/46\__/11\__/ 2\__/19\__/60\__/
/..\__/25\__/10\__/ 8\__/37\__/ \
\__/45\__/24\__/ 9\__/20\__/61\__/
/..\__/44\__/23\__/21\__/38\__/ \
\__/70\__/43\__/22\__/39\__/62\__/
/ \__/69\__/42\__/40\__/63\__/ \
\__/ \__/68\__/41\__/64\__/ \__/
/ \__/ \__/67\__/65\__/ \__/ \
\__/ \__/ \__/66\__/ \__/ \__/
\__/ \__/ \__/ \__/ \__/
\__/ \__/ \__/ \__/
Input The input consists of several lines, each containing two integers a and b (a,b <= 10000), denoting numbers of cells. The integers are always positive, except in the last line where a=b=0 holds. This last line terminates the input and should not be processed. Output For each pair of numbers (a,b) in the input file, output the distance between the cells labeled a and b. The distance is the minimum number of moves to get from a to b. Sample Input 19 30 0 0 Output for the Sample Input The distance between cells 19 and 30 is 5. This page maintained by Ed Karrels. Last updated December 7, 1999 i was just looking for some programing problems, when i got this site, which contains several archived programing contest problems. this problem is from 1999. i just have no idea what needs to be known to solve this problem. although i suspect that it has to with graph or network theory. but i am not a CS major. can someone help me? EDIT: Oops! I copy-pasted the page here, and it is distorting the thread layout, you can see the page here: http://www.karrels.org/Ed/ACM/99/prob_a.html EDIT2: Fixed! Thanks Todd!  EDIT3: Duh! Now the hive gets distorted! Adding code tags again!  EDIT4: Finally! Last edited by manav; 04-12-2008 at 05:54 AM. |
| manav is offline |  |
|
04-12-2008, 05:47 AM
| #2 |
| Jack of many languages  Join Date: Nov 2007 Location: Katy, Texas
Posts: 2,072
| Don't put the text within code tags and it will auto wrap.
__________________ Mac and Windows cross platform programmer. Ruby lover. |
| Dino is offline | |
|
04-12-2008, 05:47 AM
| #3 |
| Registered User  Join Date: Nov 2004 Location: india
Posts: 493
| First approach that i can think of : Create the honeycomb layout by simple simulation. Store what cells are reachable from each cell in an adjacency list as from one cell, maximum 6 others could be reachable. Then do a bfs from cell1 to cell2. Maximum number of cells visited is 10000. There could be a faster mathematical way of generating the honeycomb other than simple simulation but i'm too tired to think it out right now. |
| PING is offline | |
|
04-12-2008, 06:03 AM
| #4 |
| Banned Join Date: Nov 2007
Posts: 678
| I also searched for "shortest path" and found "Dijkstra's algorithm" but the explanation is not so simple, as, i could understand it! |
| manav is offline | |
|
04-12-2008, 06:52 AM
| #5 | |
| Registered User Join Date: Nov 2004 Location: india
Posts: 493
| Quote:
Last edited by PING; 04-12-2008 at 03:22 PM. Reason: typo | |
| PING is offline | |
|
04-12-2008, 07:00 AM
| #6 |
| Banned Join Date: Nov 2007
Posts: 678
| thanks PING! can you suggest any similar site where i can find simpler programming problems? |
| manav is offline | |
|
04-12-2008, 07:18 AM
| #7 |
| Registered User Join Date: Nov 2004 Location: india
Posts: 493
| |
| PING is offline | |
|
04-12-2008, 08:29 AM
| #8 |
| Senior software engineer  Join Date: Mar 2007 Location: Portland, OR
Posts: 5,768
| Wow people. You don't need Dijkstra's algorithm for this. You are making it waaaay too complicated. The real problem here is figuring out how to deal with the spiral coordinate system. And it's not that hard a problem. It would be nice not to discourage somebody attempting a perfectly good problem.. EDIT: The ACM programming problems are like elementary school world problems. There is stuff in there which is meant to throw you off what is actually a very simple solution. Clearly, that stuff worked! Last edited by brewbuck; 04-12-2008 at 08:32 AM. |
| brewbuck is offline | |
|
04-12-2008, 08:58 AM
| #9 |
| l'Anziano  Join Date: Aug 2001
Posts: 2,630
| My first thought was to do Dijkstra's algorithm as well. I don't know of another way right off of the top of my head. |
| DavidP is offline | |
|
04-12-2008, 09:39 AM
| #10 |
| l'Anziano Join Date: Aug 2001
Posts: 2,630
| Well I just figured out how to tell the distance from any node on a certain level of the honeycomb and the last node of that level. Although it does not solve the problem completely, it is a step in the right direction. The distances of all nodes in a specific ring to the last node of that ring can be found as follows: - Find the level of the ring. (Ex. node 15 is in level 3, node 5 is in level 2) - The distances of each node in the ring to the last node of the ring (Ex. distances of all nodes on level 3 (nodes 15-30) to the last node on level 3 (node 30)) are: Code: int n = level; int d = 1; int i = 0; for ( int k = 0; k < (n * 2 - 1); k++, i++, d++ ) node[i].distance = d; for ( int k = 0; k < n; k++, i++ ) node[i].distance = d; d--; for ( int k = 0; k < n; k++, i++ ) node[i].distance = d; d--; for ( int k = 0; k < (n * 2 - 2); k++, i++, d-- ) node[i].distance = d; |
| DavidP is offline | |
|
04-12-2008, 09:46 AM
| #11 |
| (?<!re)tired  Join Date: May 2006 Location: Portugal
Posts: 5,656
| if you look at any coordinate system, they are simply patterns where each node can be easily predicted or its position evaluated. You just need to find the pattern on this one, in order to compute solutions to the problem.
__________________ Originally Posted by brewbuck: Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster. |
| Mario F. is offline | |
|
04-12-2008, 12:09 PM
| #12 |
| Cat without Hat  Join Date: Apr 2003
Posts: 8,492
| The pattern is simple. The core (ring 0) is node 1. The ring around it (ring 1) is 2 through 7, 6 cells. Every subsequent ring consists of 6 cells more than its inner ring. Ring 2 has 12 cells, ring 3 18, ring 4 24, which brings us to cell 62 and the last partial ring in the example.
__________________ All the buzzt!  CornedBee"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code." - Flon's Law |
| CornedBee is offline | |
|
04-12-2008, 05:56 PM
| #13 | |
| Registered User Join Date: Nov 2004 Location: india
Posts: 493
| Quote:
| |
| PING is offline | |
|
04-13-2008, 11:25 AM
| #14 |
| Dr Dipshi++  Join Date: Oct 2006 Location: On me hyperplane
Posts: 1,219
| I have been playing around with this for the last couple of hours. I'm nearly there but got myself stuck at one last point, and I cant be bothered to think about it any more. Basically the program converts the number to 2d co-ords, then moves in a direction according to difference in x, y positions from location to target. My problem is finding a simple way of getting the number of the adjacent tile to the current location. Anyone got any ideas? Code: #include <stdio.h>
#include <math.h>
#define MAX_RING 6
#define DEG_TO_RAD 0.0174532925
enum {DOWN, DOWN_LEFT, UP_LEFT, UP, UP_RIGHT, DOWN_RIGHT} adjacent;
// Gets the current ring
int GetRing(int pos)
{
static const int rings[MAX_RING] = { 1, 7, 19, 37, 61, 91 };
for(int i=0; i<MAX_RING; i++)
if(pos <= rings[i])
return i;
return -1;
}
void SpiralTo2D(int pos, int *x, int *y)
{
static const int ring_offset[MAX_RING+1]= { 0, 1, 7, 19, 37, 61, 91 };
static const int ring_size[MAX_RING] = { 1, 6, 12, 18, 24, 30 };
int ring = GetRing(pos);
int step = pos - ring_offset[ring];
int sector_size = 360 / ring_size[ring];
int deg = (sector_size * step) - 240;
*x = (int)(sin(deg*DEG_TO_RAD) * ring *10);
*y = (int)(cos(deg*DEG_TO_RAD) * ring *10);
//printf("%2d> x:%lf y:%lf", pos, x, y);
//printf(" ring:%d, step:%d, sector:%d deg:%d\n", ring, step ,sector_size, deg);
}
int GetTile(int pos, const int move)
{
int ring = GetRing(pos);
switch(move)
{
case UP: break;
case DOWN: break;
case DOWN_LEFT: break;
case DOWN_RIGHT: break;
case UP_LEFT: break;
case UP_RIGHT: break;
}
return 1;
}
// Gets next step
int GetNextTile(int location, int target)
{
int l_x, l_y, t_x, t_y; // Location and target co-ords
SpiralTo2D(location, &l_x, &l_y);
SpiralTo2D(target, &t_x, &t_y);
printf("Loaction: %d %d\n", l_x, l_y);
printf("Target: %d %d\n", t_x, t_y);
if(l_x == t_x) // Move up or down only
if(l_y == t_y)
return -1; // Target found!
else if(l_y < t_y)
return GetTile(location, UP); // Tile above
else
return GetTile(location, DOWN); // Tile below
else if(l_x > t_x)// Move left
if(l_y > t_y)
return GetTile(location, DOWN_LEFT);
else
return GetTile(location, UP_LEFT);
else //Move Right
if(l_y > t_y)
return GetTile(location, DOWN_RIGHT);
else
return GetTile(location, UP_RIGHT);
}
int main()
{
int pos = 34;
int target = 2;
GetNextTile(pos, target);
getchar();
return 0;
}
|
| mike_g is offline | |
|
04-13-2008, 03:45 PM
| #15 |
| (?<!re)tired Join Date: May 2006 Location: Portugal
Posts: 5,656
| The solution, I'm pretty sure, must not be obtained by defeating the original coordinates system. By mapping the cells to the cartesian system, you will be obtaining distances according to that coordinates system. The problem however asks you to do it with the proposed spiral coordinates. In fact, the problem solves itself rather easily if you stick to that coordinate system. Much more easily than with the Cartesian coordinates. And the text even gives you an hint as to how you should solve it. As I mentioned before you should first try to determine the pattern behind those coordinates. For this effect, take CornedBee earlier observation and then read the problem carefully again. At one point you read "For example, two maggots in cells 19 and 30 are 5 cells apart." Can you see a general formula to calculate all distances regardless of the start and end cells as being the most obvious answer to the problem? Naturally you can, because even if the coordinate system was different, that is a characteristic of every 2d system you can come up with in which distances between two consecutive points is fixed. You just have to find the formula for this one. I'm not going to try and solve it myself. Too lazy for that and math challenged enough for it to take me more than it should. But you guys enjoying the fine school years should have no trouble. Just don't complicate what is simple.
__________________ Originally Posted by brewbuck: Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster. Last edited by Mario F.; 04-13-2008 at 03:47 PM. |
| Mario F. is offline | |
 |
| Thread Tools | |
| Display Modes | |
|
Similar Threads | ||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Solve This Problem Within 3 Hr Urgent Need | annum | C Programming | 12 | 10-04-2009 09:56 AM |
| problem solve | coolnarugodas | C Programming | 7 | 04-26-2005 12:31 PM |
| Help. I don't know how to solve my problem in a program I wrote. | Hapster | C Programming | 2 | 04-25-2005 11:59 AM |
| Bubble Sort / selection problem | Drew | C++ Programming | 7 | 08-26-2003 03:23 PM |
| problem cant solve please help. | sarah | C Programming | 6 | 09-03-2001 01:32 PM |
Linear Mode
