The 2003 27th Annual acm International Collegiate Programming Contest World Finals sponsored by IBM Problem C
The latest research in reconfigurable multiprocessor chips focuses on the use of a single bus that winds around the chip. Processor components, which can be anywhere on the chip, are attached to connecting points on the bus so that they can communicate with each other.
Some research involves bus layout that uses recursively-defined "SZ" curves, also known as "S-shaped Peano curves." Two examples of these curves are shown below. Each curve is drawn on the unit square. The order-1 curve, shown on the left, approximates the letter "S" and consists of line segments connecting the points (0,0), (1,0), (1,0.5), (0,0.5), (0,1), and (1,1) in order. Each horizontal line in an "S" or "Z" curve is twice as long as each vertical line. For the order-1 curve, the length of a vertical line, len, is 0.5.
The order-2 curve, shown on the right, contains 9 smaller copies of the order-1 curve (4 of which are reversed left to right to yield “Z” curves). These copies are connected by line segments of length len, shown as dotted lines. Since the width and height of the order-2 curve is 8 × len, and the curve is drawn on the unit square, len = 0.125 for the order-2 curve.
The order-3 curve contains 9 smaller copies of the order-2 curve (with 4 reversed left to right), connected by line segments, as described for the order-2 curve. Higher order curves are drawn in a similar manner.
The connecting points to which processor components attach are evenly spaced every len units along the bus. The first connecting point is at (0,0) and the last is at (1,1). There are 9k connecting points along the order-k curve, and the total bus length is (9k –1) × len units.
You must write a program to determine the total distance that signals must travel between two processor components. Each component’s coordinates are given as an x, y pair, 0 ≤x ≤1 and 0 ≤y ≤1, where x is the distance from the left side of the chip, and y is the distance from the lower edge of the chip. Each component is attached to the closest connecting point by a straight line. If multiple connecting points are equidistant from a component, the one with the smallest x coordinate and smallest y coordinate is used. The total distance a signal must travel between two components is the sum of the length of the lines connecting the components to the bus, and the length of the bus between the two connecting points. For example, the distance between components located at (0.5, 0.25) and (1.0, 0.875) on a chip using the order-1 curve is 3.8750 units.
The input contains several cases. For each case, the input consists of an integer that gives the order of the SZ curve used as the bus (no larger than 8), and then four real numbers x1, y1, x2, y2 that give the coordinates of the processor components to be connected. While each processor component should actually be in a unique location not on the bus, your program must correctly handle all possible locations. The last case in the input is followed by a single zero.
For each case, display the case number (starting with 1 for the first case) and the distance between the processor components when they are connected as described. Display the distance with 4 digits to the right of the decimal point.
Use the same format as that shown in the sample output shown below. Leave a blank line between the output lines for consecutive cases.
Sample Input 1 0.5 .25 1 .875 1 0 0 1 1 2 .3 .3 .7 .7 2 0 0 1 1 0 Output for the Sample Input Case 1. Distance is 3.8750 Case 2. Distance is 4.0000 Case 3. Distance is 8.1414 Case 4. Distance is 10.0000
I give a solution below, probably the fastest possible, with each case, time complexity O(k)+C1, and space complexity O(k)+C2. k is the order of the curve, C1, C2 are constants. We use recursion, the depth is k, and on each level the cost is constant. Surprisingly efficient. (Definitely, there may be some more elegant solution using iteration through the whole bus to calculate the number of links between any two connection points. However, this could compromise some efficiency.)
The program has been tested with MS VC 2005 Express. I don't have much time to give more explanation. However, if you have spent some time trying to solve this problem by yourself, then you can understand it right away.
//Author: Victor Zeng 1/3/2007 /* The key idea of our solution is to view Order-K curve as 3x3 block. For Order-1 curve, each sub-block is a connection point. For Order-2 or higher curve, each sub-block represents an order-(k-1) curve. We use a flag "reverse" to identify shape of the block. If a block is S shape we call it reverse==false. For Z shape, we call it reverse==true. We use a flag "topdown" to identify the direction we want to travel through the block. If enter into this block from bottom then we say topdown==false. If enter into this block from top then we say topdown==true There are four cases: S shape curve, enter from bottom S shape curve, enter from top reverse=false, topdown=false reverse=false, topdown=true (0,2)->(1,2)->(2,2)-> (0,2)<-(1,2)<-(2,2)<- | | (0,1)<-(1,1)<-(2,1) (0,1)->(1,1)->(2,1) | | ->(0,0)->(1,0)->(2,0) <-(0,0)<-(1,0)<-(2,0) entry sub-block (0,0) entry sub-block (2,2) Z shape curve, enter from top Z shape curve, enter from bottom reverse=true, topdown=true reverse=true, topdown=false ->(0,2)->(1,2)->(2,2) <-(0,2)<-(1,2)<-(2,2) | | (0,1)<-(1,1)<-(2,1) (0,1)->(1,1)->(2,1) | | (0,0)->(1,0)->(2,0)-> (0,0)<-(1,0)<-(2,0)<- entry sub-block (0,2) entry sub-block (2,0) Consider sub-block at(1,2), we want to decide the number of links to reach it: with S shape, entry sub-block (0,0), the number of links from (0,0) to (1,2) is 7 If (1,2) represents a sub-block, then the sub-block is both reverse and topdown i.e. entry sub-block (0,2). with S shape, entry sub-block (2,2), the links from (2,2) to (1,2) is 1 If (1,2) represents a sub-block, then the sub-block is reverse but not topdown i.e. entry sub-block (2,0). with Z shape, entry sub-block (0,2), the links from (0,2) to (1,2) is 1 If (1,2) represents a sub-block, then the sub-block is both not reverse (S) and not topdown i.e. entry sub-block (0,0). with Z shape, entry sub-block (2,0), the links from (0,2) to (1,2) is 7 If (1,2) represents a sub-block, then the sub-block is not reverse (S) but topdown i.e. entry sub-block (2,2). For any Order-K curve K>0: All connection points are assigned with a location # (i,j) i,j=0,1,2,...,3k-1: (0,3k-1) (1,3k-1) .... (3k-1,3k-1) (0,3k-2) (1,3k-2) .... (3k-1,3k-2) ... (0,1) (1,1) .... (3k-1,1) (0,0) (1,0) .... (3k-1,0) We set for this block (Order-K curve, K>0), reverse=false and topdown=false. To calculate d, the length of path from (0,0) to (i,j): We view the Order-K curve as 3x3 block with order-(k-1) curve as sub-block. The sub-block where location# (i,j) belongs to is: (i/3k-1,j/3k-1) Within the sub-block (i/3k-1,j/3k-1) of order-(k-1), the location# for (i,j) is (i%3k-1,j%3k-1). We can calculate the number of links dm (m=k,k-1,...,1), 0≤dm≤8 from the entry sub-block to the sub-block where (i,j) belongs to. Repeat this process until sub-block is simply a connection point. Then d = dk9k-1+...+d3*92+d2*91+d1. For any connection point, we can pass it when travlling from (0,0) to (1,1). Let the length of path from connection point (0,0) to connection point (i,j) be d(i,j) Let the length of path from connection point (0,0) to connection point (k,m) be d(k,m) Then the length of path from (i,j) to (k,m) will be max(d(i,j),d(k,m))-min(d(i,j),d(k,m)). */ #include "stdafx.h" #include <iostream> #include <string> #include <math.h> #include <vector> using namespace std; // // To avoid repeating calculating power(3,k): // power3 function calculates base 3 raised to power p. // we cache the data, so that it is calculated only once // int power3(int p) { //make sure it is calculated only once static vector<int> pow3; if (p<=0) throw string("Power parameter has to be positive integer"); //base 3 if(p<=(int)pow3.size()) return pow3[p-1]; else { int pow = (pow3.size()==0)?1:pow3[pow3.size()-1]; for (size_t t=pow3.size(); t!=p; t++) { pow = pow*3; pow3.push_back(pow); } return pow; } } // // base9links function: // Input: // int i,j -- location#(i,j) in a 3x3 block, zero based index // bool reverse, topdown -- describe the shape property and direction property. // // Return: // the number of links BETWEEN sub-blocks starting from the entry sub-block to // to the sub-block (i,j). // // If current block is of order-k (k>1), then (i,j) represents a sub-block of // order-(k-1). The reverse and topdown properties of this sub-block can be // derived from those of current block. Therefore, base9links will also change // those properties of current block to that of the (i,j) sub-block. // // Sample Input: // There are four cases: // S shape curve, enter from bottom // reverse=false, topdown=false // (0,2)->(1,2)->(2,2)-> // | // (0,1)<-(1,1)<-(2,1) // | // ->(0,0)->(1,0)->(2,0) // entry sub-block (0,0) // // S shape curve, enter from top // reverse=false, topdown=true // (0,2)<-(1,2)<-(2,2)<- // | // (0,1)->(1,1)->(2,1) // | // <-(0,0)<-(1,0)<-(2,0) // entry sub-block (2,2) // // Z shape curve, enter from top // reverse=true, topdown=true // ->(0,2)->(1,2)->(2,2) // | // (0,1)<-(1,1)<-(2,1) // | // (0,0)->(1,0)->(2,0)-> // entry sub-block (0,2) // // Z shape curve, enter from bottom // reverse=true, topdown=false // <-(0,2)<-(1,2)<-(2,2) // | // (0,1)->(1,1)->(2,1) // | // (0,0)<-(1,0)<-(2,0)<- // entry sub-block (2,0) // // Consider sample sub-block (1,2) i.e. i=1, j=2, // with S shape, entry sub-block (0,0), the links from (0,0) to (1,2) is 7 // If (1,2) represents a sub-block, then the sub-block is // both reverse and topdown i.e. entry sub-block (0,2). // with S shape, entry sub-block (2,2), the links from (2,2) to (1,2) is 1 // If (1,2) represents a sub-block, then the sub-block is // reverse but not topdown i.e. entry sub-block (2,0). // with Z shape, entry sub-block (0,2), the links from (0,2) to (1,2) is 1 // If (1,2) represents a sub-block, then the sub-block is // both not reverse (S) and not topdown i.e. entry point (0,0). // with Z shape, entry point (2,0), the links from (0,2) to (1,2) is 7 // If (1,2) represents a sub-block, then the sub-block is // not reverse (S) but topdown i.e. entry point (2,2). // int base9links(int i, int j, bool &reverse, bool &topdown) { int d = 0; //0...8 if (reverse==false&&topdown==false) { if (j==0) d = i; else if (j==1) d = 5-i; else d = 6+i; } else if (reverse==false&&topdown==true) { if (j==2) d = 2-i; else if (j==1) d = 3+i; else d = 8-i; } else if (reverse==true&&topdown==false) { if (j==0) d = 2-i; else if (j==1) d = 3+i; else d = 8-i; } else if (reverse==true&&topdown==true) { if (j==2) d = i; else if (j==1) d = 5-i; else d = 6+i; } if (d==4) topdown = !topdown; else if (d==1) { reverse = !reverse; topdown = !topdown; } else if(d==3) reverse = !reverse; else if(d==5) reverse = !reverse; else if(d==7) { reverse = !reverse; topdown = !topdown; } return d; } // // buslinks function calculates the length of path, i.e. total number of links from the // entry point of order-k curve travelling to connection point at location // (i, j). the curve is a s curve if reverse==false, otherwise it is a z curve. // if the entry point is at the top level, then topdown==true. // if the entry point is at the bottom level, then topdown==false. // buslinks function may recursively call itself. // void buslinks(int &d, int k, int i, int j, bool &reverse, bool &topdown) { //i,j in [0, pow(3,k)-1] if (k==1) //0<=i<=2, 0<=j<=2 d = d*9+base9links(i,j,reverse,topdown); else { //order-k curve can be divided into 9 sub-block of size order-(k-1) //i, j is in the sub-block (i/power(3,k-1), j/power(3,k-1)) //i/power(3,k-1) among 0,1,2 //j/power(3,k-1) among 0,1,2 int r = base9links(i/power3(k-1), j/power3(k-1), reverse, topdown); d = d*9+r; //reduce to a lower order case buslinks(d, k-1, i%power3(k-1),j%power3(k-1), reverse, topdown); } return; } // // Given input coordinate x, y for a processor component, find out the connection point // it should attach to, and the actual distance between (x,y) to the connection point. // pair<pair<int, int>,double> calc(int k, double x, double y) { //------------------------// double len = 1.0/(power3(k)-1); //k=1,2,...,8, 0<=x<=1.0, 0<=y<=1.0 double xi = x*(power3(k)-1); double yi = y*(power3(k)-1); //location# double i = floor(xi); double j = floor(yi); double m = ceil(xi); double n = ceil(yi); double d1=sqrt((x-i*len)*(x-i*len)+(y-j*len)*(y-j*len)); double d2=sqrt((x-i*len)*(x-i*len)+(y-n*len)*(y-n*len)); double d3=sqrt((x-m*len)*(x-m*len)+(y-j*len)*(y-j*len)); double d4=sqrt((x-m*len)*(x-n*len)+(y-n*len)*(y-n*len)); if (d2<d1) j = n; if (d3<min(d1,d2)) i = m; if (d4<min(min(d1,d2),d3)) { i = m; j = n; } return make_pair(make_pair((int)i,(int)j),min(min(d1,d2),min(d3,d4))); } // // ridebus_solver calculates the distance between x1,y1 and x2,y2 in // an Order-K curve // double ridebus_solver(int k, double x1, double y1, double x2, double y2) { //handle point x1,y1 pair<pair<int, int>,double> p1=calc(k, x1, y1); int i1 = p1.first.first, j1=p1.first.second; bool reverse = false; bool topdown = false; int d1 = 0; //store the links from (0,0) to (i1,j1) buslinks(d1, k, i1, j1, reverse, topdown); //handle point x2,y2 reverse = false; topdown = false; pair<pair<int, int>,double> p2=calc(k, x2, y2); int i2 = p2.first.first, j2=p2.first.second; int d2 = 0; //store the links from (0,0) to (i2,j2) buslinks(d2, k, i2, j2, reverse, topdown); //calculate the links from (i1,j1) to (i2,j2) int d = max(d1,d2)-min(d1,d2); //calculate the distance (x1,y1) to (x2,y2) double td = p1.second+p2.second+1.0*d/(power3(k)-1); //total actual distance return td; } // store input case data struct testcase { int caseno; //case no int k; //order of curve double x1, y1,x2,y2; //coordinates of two points under test }; // entry function of acm-2003-world-final-c void ridebus() { vector<testcase> testcases; //store all test cases int caseno=0; int k; //order of curve double x1, y1,x2,y2; do { //input one case per loop cin>>k; if (k==0) //no more input break; cin>>x1>>y1>>x2>>y2; if (k<0||k>8) { k=1; cout<<"Illegal input of order number, assume 1"<<endl; } if (x1<0||x1>1) { cout<<"Illegal input of horizontal position, assume 0.0"<<endl; x1=0.0; } if (y1<0||y1>1) { cout<<"Illegal input of vertical position, assume 0.0"<<endl; y1=0.0; } if (x2<0||x2>1) { cout<<"Illegal input of horizontal position, assume 1.0"<<endl; x2=1.0; } if (y2<0||y2>1) { cout<<"Illegal input of vertical position, assume 1.0"<<endl; y2=1.0; } testcase tc; tc.caseno = ++caseno; tc.k = k; tc.x1 = x1; tc.y1 = y1; tc.x2 = x2; tc.y2 = y2; testcases.push_back(tc); } while (1); cout<<fixed; cout.precision(4); for(size_t t=0; t<testcases.size(); t++) { double d = ridebus_solver(testcases[t].k, testcases[t].x1, testcases[t].y1, testcases[t].x2, testcases[t].y2); cout<<endl<<"Case "<<testcases[t].caseno<<". "<<"Distance is "<<d<<endl; } }