Mid Week Practice: 2007 Greater New York Regionals - solutions

Post date: Aug 1, 2013 5:59:57 AM

Here I will attempt to explain how to solve the problems in today's practice, which are mostly from the 2007 Greater New York Regionals. Note, here Problem G is actually from the 2004 Greater New York contest and was misplaced in the 2007 Greater New York Regionals during this week's practice by accident.

I will assume my target audience are neophytes so this blog post will sometimes delve into implementation details that are obvious for veterans. However, as I expect the neophytes to improve throughout the course of reading this blog post, and because I get progressively more tired while writing this, and because the later problems are harder in general, the amount of minute implementation detail will diminish as the writing progresses.

Problem A: Mispelling

Notice that the problem title is ironically misspelt, as it appeared on the HUST site where we practiced. The idea is that, given a string, we want to remove the Mth character. For those who are new to programming contests, this is a good warm up for getting familiar with how to perform basic input and output routines. In c++, this is easily solved by simply outputting the substring at 0 with a length of M-1 and the subtring at M to the end.

int m; string s; cin >> m >> s; cout << s.substr(0,m-1) << s.substr(m) << endl;

There are many ways to do it. For example, you can read the string character by character, while echoing each character except for the Mth one. Or, you could read the string as a char array. Then you can set the Mth character to the NULL character signifying end of string, print that, and use pointer arithmetic to print the other half.

Problem B: Conversions

Mathematically this problem is trivial. Once you know which units you are converting between, simply multiply the quantity by a fixed constant. The slightly harder part is the implementation. This is made trivial by use of the map STL template in c++ as well as their equivalents in other languages. I highly recommend c++ programmers to know how to use map. You can read about it on c++ reference. In any case, in this problem you can even hard code the thing with a switch or some if statements, since there are only four kinds of units to deal with.

Notice this question expects precisely four decimal places. You can use #include<iomanip> and cout << fixed << setprecision(4) or printf("%.4lf",x).

Problem C: Encoding

This problem is divided into two parts. First, you must be able to convert a number (in this case, a character) into a binary string. Second, you must be able to traverse a 2D area in a spiral.

Ones and zeroes

As you are traversing the array in a spiral, the Qth square you come across will be the (Q%5)th bit in the (Q/5)th character of the input string. This requires you to be familiar with bitwise operators. Here we will be using the bitwise left shift operator (<<) and the bitwise AND operator (&). A bitwise left shift (wikipedia)simply moves a number left, e.g. 0001 << 1 = 0010. The bitwise AND (wikipedia) of two numbers simply computes, for every bit, whether both numbers have that bit set to 1.

int z = ((s[Q/5] - 'A' + 1) & (1 << (4 - Q%5))) == 0?0:1;

Spirals

There are several ways to traverse an 2D lattice in a spiral. We start out with x=y=0. While traversing, we must keep track of our current direction (you can use an int for this, or an enum for better style) that can be one of four possibilities: 1. east (x++), 2. south (y++), 3. west (x--) and 4. north (y--). Whenever you hit the edge, or an already visited cell, increment your direction modulo 4. For example, if you were travelling east, go south instead; and if you were travelling north, go east instead. You can keep track of your already visited cells by using an additional array of bools. Be sure not to read or write to arrays out of bounds! At the same time remember to increment the Q for use in the bitwise part earlier.

To move in the given direction, you can either do a switch statement, some if-else statements, or you can use arrays, like this:

dx[] = {1, 0, -1, 0};

dy[] = {0, 1, 0, -1};

so that when choosing the next cell to go into, given some direction d, you can do this:

x += dx[d]; y += dy[d];

If you are pro like ultimusmaximus, you can simply use one array. Here is the complete source code which solves the problem in 342 bytes:

n,i,r,c,d[4]={1,0,-1},x,j,z,_[999];char s[999],q[999];main(a){for(scanf("%d",&n);z++<n;){scanf("%d%d",&r,&c);d[1]=c;d[3]=-c;gets(s);for(a=r*c;a--;)q[a]=48,_[a]=0;q[r*c]=0;for(a=x=0,i=1;s[i];i++)for(j=5;j--;){q[a]=_[a]=s[i]==32?48:(s[i]-64>>j&1)+48;a+=d[x];x=a==c-1||a==r*c-1||a==r*c-c||_[a+d[x]]?(x+1)%4:x;}printf("%d ",z);puts(q);}return 0;}

Problem D: Decoding

Here, the spiral traverse is the same. Now you read in from binary instead. Given some binary array you can again use bitwise arithmetic to get your character. Consider the kth bit to be a one left shifted by k, and add that to your desired outcome.

int z; for(int k = 0; k < 5; k++) { if(bits[k] == 1) z += (1 << (4 - k)); }

char c = ' '; if(z > 0) c = z + 'A' - 1;

Problem E: Flipping Burned Pancakes

Solving this problem optimally is NP-Hard, but fortunately the problem statement only requires at most 3M-2 flips for M pancakes. The basic algorithm is to insert the largest pancake to the bottom of the stack each time:

1. Determine the position of the largest pancake in the stack.
2. Flip all the pancakes above and including the largest pancake, so that the largest pancake ends up on top.
3. If necessary, flip the pancake at the top such that the burned side is facing up.
4. Flip all pancakes, so that the largest pancake is now at the bottom with the burned side at the bottom.
5. Repeat for the remaining pancakes excluding the bottom pancake.

We see that the problem size reduces by one each time we go through with this. Each time, there is at most 3 flips, on steps 2, 3, and 4. We only need to go through M-1 iterations since once the largest M-1 pancakes are in place, the remaining smallest pancake is automatically at the top (+1 if it is reversed). Hence this will take 3M-2 flips at most, exactly fitting into the problem statement requirement.

To actually implement this, the ideal data structure is a splay tree, which can flip pancakes and reverse their directions in logarithmic time. Also good is some sort of doubly linked list so that you can reverse it in O(1) time (although flipping the burned side would still take O(M)). In any case M cannot exceed 30, so the array or vector are more than sufficient.

Problem F: Monkey Vines

This looks like a problem involving binary trees and data structures but is in fact trivial. Observe that the answer is simply two to the power of the height of the tree. (Proof left as an exercise for the reader)

To find the height of the tree, simply count the brackets. Start with a count of zero. Opening brackets ([) add one, and closing ones (]) subtract one. The height is the maximum count. Notice that there is an efficient way to compute powers of two: bitwise left shift! So just output 1<<maxdepth.

Problem G: Model Rocket Height

This is a geometry and algebra problem.

The set of all points with a fixed azimuthal angle from the observer is a cone. (Clearly, if you are looking up at a fixed angle to the ground, you can rotate around on the spot without changing this angle, thereby sweeping out a cone area). Here we have three observers, each reporting a different angle. The observers are standing on a straight line, equally spaced D units apart. The line is H units above the ground. Notice that the rocket being observed is not necessarily collinear with this line, so the full 3D space must be considered. Let us consider our coordinate system to be centered on observer B, with the z-axis being the vertical axis, such that:

(x-D)^2 + y^2 = z^2 / tan(alpha)^2

x^2 + y^2 = z^2 / tan(beta)^2

(x+D)^2 + y^2 = z^2 / tan(gamma)^2

For simplicity, let us define the following variables:

a = 1/tan(alpha)

b = 1/tan(beta)

c = 1/tan(gamma)

The math way

Rearranging, we obtain:

3x^2 + 3y^2 = z^2 (a^2 + b^2 + c^2) - 2D^2

Observe that tan(beta)^2 = z^2 / (x^2 + y^2). The rest of the algebra is left as an exercise for the reader. Credit to Paul for the algebraic solution

The hard way

We can iteratively find the optimal z by a variety of searches, including multiprobe search and ternary search. Here we will use binary search on the derivative of area of the triangle formed from the three points that is the intersection of the three cones with a horizontal plane at height z. Given a z, we can compute the three intersection points of the three circles by basic algebra:

xab = (rb*rb-ra*ra+d*d)/(2*d);

xac = (rc*rc-ra*ra)/(4*d);

xbc = -(rb*rb-rc*rc+d*d)/(2*d);

yab = sqrt(rb*rb-xab*xab);

yac = sqrt(ra*ra-(xac-d)*(xac-d));

ybc = sqrt(rb*rb-xbc*xbc);

where ra = z*a, rb = z*b, and rc = z*c for the above defined a, b, c. If the circles do not intersect, the y values will be NaN and you can check if a double is NaN by checking equality against itself (yab != yab). A NaN always returns false when compared with anything, including itself, according to some ISO standard. Anyway, having found the intersection points, you can compute the area by using my triangle area function:

double tri_area(double ax, double ay, double bx, double by, double cx, double cy) {

  return abs(ax*(by-cy)+bx*(cy-ay)+cx*(ay-by))/2.0;

}

We wish to minimize the tri_area. You can easily perform binary search by evaluating the numerical derivative of tri_area, by evaluating it for some z+dz/2 and z-dz/2 for some arbitrarily small dz and taking the difference.

When tri_area is zero, this means that the three points have converged to a single point, i.e. the unique (other than the other side with -y) point of intersection of the three cones has been found. At that point you can return z+H.

What is binary search

I expect most good programmers to be able to implement binary search but apparently many can't. Don't worry, here's how you do it:

const double EPS = 1e-9;

double lo = 0, hi = 2e9;

while(hi-lo > EPS) {

  double mid = (hi+lo)/2;

  if(eval(mid)<0) lo = z;

  else hi = z;

}

The eval function here will compute the difference of the tri_area for z-values of mid-dz/2 and mid+dz/2.

Problem H: Tiling a Grid with Dominoes

This is the archetypal dynamic programming problem. The solution is an integer sequence that appears on OEIS: sequence A005178. The recurrence relationship is:

a(n) = a(n-1)+5*a(n-2)+a(n-3)-a(n-4);

Assume you already know all the ways to tile widths of n-1, n-2, etc. There is only one way to go from n-1 to n, namely by adding a single layer of two vertical dominoes. There are five ways to go from n-2 to n, by adding the five kinds of patterns exemplified in the problem statement for the n=2 case. But we might be over counting things! Think carefully about what the a(n-3) and -a(n-4) terms do.

Problem I: Spatial Concepts Test

This is an implementation problem where you essentially hardcode how the faces look like from the eight vertices. Notice that for each of the vertices, all three rotations are just rearrangements of their description strings. For example, if you can see C2D2F2, you can also see D2F2C2 and F2C2D2. A rotation by N quarter turns is equivalent to adding N to the orientation number of that face, modulo 4. For example, rotating A1 anticlockwise by 90 degrees yields A2; rotating it again by 90 degrees yields A3; then A4; then A1 again. To save you the trouble of thinking (I spent quite some time drawing it out and thinking about it), here are the eight vertices:

• Vertex 143,431,314: Face 1 rotated 2 times; Face 4 rotated 0 times; Face 3 rotated 3 times.
• Vertex 346,463,634: Face 3 rotated 2 times; Face 4 rotated 1 times; Face 6 rotated 3 times.
• Vertex 362,623,236: Face 3 rotated 1 times; Face 6 rotated 0 times; Face 2 rotated 2 times.
• Vertex 132,321,213: Face 1 rotated 1 times; Face 3 rotated 0 times; Face 2 rotated 3 times.
• Vertex 154,541,415: Face 1 rotated 3 times; Face 5 rotated 0 times; Face 4 rotated 3 times.
• Vertex 125,251,512: Face 1 rotated 0 times; Face 2 rotated 0 times; Face 5 rotated 3 times.
• Vertex 265,652,526: Face 2 rotated 1 times; Face 6 rotated 1 times; Face 5 rotated 2 times.
• Vertex 564,645,456: Face 5 rotated 1 times; Face 6 rotated 2 times; Face 4 rotated 2 times.

In total, 24 vertices. It is useful to actually draw out all eight corners and mark which way the symbol on each face is pointing, to determine how much to rotate. Having computed these, for each of the five tests given, you can check if that string is equal to one of the 24 you just computed. If yes, output "Y"; otherwise, "N".

Appendix: Source codes

1. A: source
2. B: source
3. C: source
4. D: source
5. E: source
6. F: source
7. G: source
8. H: source
9. I: source