11498: Division of Nlogonia

Thought about reviving this blog. I visited UVa Online Judge today and they have a lot of new problems since I last visited it. I tried looking for an easy problem and this is what I found. Here is a sample C++ code solution that got accepted:

#include <stdio.h>

int main() {
  char line[100];
  int num_tests, n, m, x, y;
  char h, v;

  while (1) {
    fgets(line, 100, stdin);
    sscanf(line, "%d", &num_tests);

    if (num_tests == 0) {
      return 0;
    }

    fgets(line, 100, stdin);
    sscanf(line, "%d %d", &n, &m);

    for (int i = 0; i < num_tests; ++i) {
      fgets(line, 100, stdin);
      sscanf(line, "%d %d", &x, &y);

      if (x == n || y == m) {
        printf("divisa\n");
        continue;
      }

      if (x > n) {
        h = 'E';
      }
      else {
        h = 'O';
      }

      if (y > m) {
        v = 'N';
      }
      else {
        v = 'S';
      }

      printf("%c%c\n", v, h);
    }
  }

  return 0;
}

UVa problem 11417: sample algorithm

To solve problem 11417 (GCD), it would be beneficial if one knows about the Euclidean algorithm and division algorithm. One could search up "greatest common divisor" in Google and browse through the corresponding Wikipedia article.

The algorithm to get the greatest common divisor between two numbers i and j can be best explained through an example. Consider i = 18 and j = 84, to get the GCD:

84 / 18 = 4 R 12
18 / 12 = 1 R 6
12 / 6 = 2 R 0

GCD for 18 and 84 is then 6.

Another example: i = 16 and j = 56:

56 / 16 = 3 R 8
16 / 8 = 2 R 0

GCD for 16 and 56 is then 8.

In the process illustrated above, the divisor that caused the remainder to be 0 is the greatest common divisor.

UVa problem 11417: sample code

001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005 
006   int   n
007       , g
008       , i
009       , j
010       , k
011       , i0
012       , j0
013       ;
014 
015   while (fgets(line, 100, stdin)) {
016     sscanf(line, "%d", &n);
017 
018     if (n == 0) {
019       break;
020     }
021 
022     for(i = 1, g = 0; i < n; i++) {
023       for(j = i + 1; j <= n; j++) {
024         i0 = i;
025         j0 = j;
026 
027         for (; 1; ) {
028           k = j % i;
029 
030           if (k == 0) {
031             break;
032           }
033 
034           j = i;
035           i = k;
036         }
037         g += i;
038 
039         j = j0;
040         i = i0;
041       }    
042     }
043 
044     printf("%d\n", g);
045   }
046 
047   return 0;
048 }

UVa problem 10865: sample algorithm

To solve problem 10865 (Brownie Points), one can imagine the plane divided into 4 quadrants like in Figure 1.


Figure 1. Plane divided into 4 quadrants.

In Figure 1, Stan draws his vertical line while Ollie draws his horizontal line so that the two lines intersect to form the center point with coordinates (x0, y0).

The center point corresponds to the middle of the input sequence provided by the user. Please refer to Figure 2 for an illustration.


Figure 2. The middle point corresponds to the center point.

In Figure 2, x0 is equal to 1 and y0 is equal to -3.

In Figure 1, the plane is divided into 4 quadrants: pp, pn, np and nn. The quadrant pp corresponds to that portion of the plain that is above and to the right of the center point. The quadrant pn corresponds to that which is below and to the right. The quadrant np corresponds to that which is above and to the left. The quadrant nn corresponds to that which is below and to the left.

So given a random point (x, y), we check to which quadrant it belongs to by comparing x against x0 and y against y0. For example, for the first point in Figure2 (3, 2), x > x0 since 3 > 1, and y > y0 since 2 > -3. As such the point (3, 2) is to the right and above the center point (1, -3). Hence it belongs to the quadrant pp.

For each point then, we determine the quadrant to which it belongs. Then we sum up the number of points belonging to each quadrant. Stan’s score is simply the number of points within pp and nn, while Ollie score is the number of points within pn and np.

Note also that if x is equal to x0, or if y is equal to y0, we do not accumulate the point into the total of any quadrant, as the problem states that crossed brownies do not count.

UVa problem 11364: sample algorithm

To solve UVa problem 11364 (Parking), it would be beneficial to know that the minimal distance Michael has to walk is simply twice the distance from the farthest store to the nearest store. For example, consider the following setup:
A________B______________C_____D
X______________________________

A, B, C and D are the stores while X is Michael’s car. To get to all the stores and return to his car, Michael would have to walk:

A to B
B to C
C to D
D to C
C to B
B to A

In essense, the total distance he would have traveled would be just twice the distance from A to D.

Consider now the following setup:

A________B______________C_____D
__________________X____________

For Michael to get to all stores and return to his car, he would need to walk:

X to B
B to A
A to B
B to X
X to C
C to D
D to C
C to X

Again, analyzing this series of walks, it is simply twice the distance from A to D.

Hence to compute the minimal distance given a series of stores to walk to, simply find the nearest store and the farthest store, get their difference and then multiply the difference by 2.

UVa problem 10851: sample algorithm

In UVa problem 10851 (2D Hieroglyphs decoder), one could explore the advantage of using right bit-shifts instead of long-cut division for division by powers of 2. For example, to divide a number by 128 (which is 2 raised to the power of 7), one could simply shift the number 7 bits to the right.Definitely, this fact could give one an advantage as a bit-shift operation is so much simpler and faster than traditional division.

Moreover, the mod operation may be quite computationally expensive as well. Since a mod by 2 operation is only needed, one could simply check whether the last binary bit of a number is 0 or 1 in order to tell if the number is divisible by 2 or not.

For example, the number 15 when represented in binary is 1111. Since its last bit (the right-most) is 1, then it is not divisible by 2. The number 12 when represented in binary is 1100. Since the last bit is 0, then it is divisible by 2. Bitwise-ANDing the number with 1 will enable one to get the last bit of the number.

For this problem, one could build a lookup table for each of the 256 ASCII characters. One could explore the use of a C++ standard map, where the key is the encrypted character and the value is the actual ASCII character. For example, we could build a map like the following:

Key, Value
//\\//\/, L
\/////\/, A
…

And so when our program sees an encryption of //\\//\/, it can simply lookup the map and find that the encryption stands for the ASCII character L.

UVa problem 10851: sample code

001 #include "stdio.h"
002 #include "string"
003 #include "map"
004 #include "iostream"
005 
006 using namespace std;
007 
008 int main() {
009   char   line[100]
010        , ctmp[100]
011        , dtmp[100]
012        , input[10][100]
013        ;
014   int   num_msg
015       , i
016       , ii
017       , j
018       , k
019       , b
020       , c
021       , m
022       , n
023       , p
024       , msg_len;
025       ;
026 
027   map imap;
028   map::iterator iter;
029 
030   for (c = 0; c < 256; c += 1) {
031     ctmp[0] = '/';
032     ctmp[9] = '/';
033 
034     for (i = 1; i < 9; i += 1) {
035       ii = i - 1;
036 
037       b = c >> ii;
038       b &= 1;
039 
040       ctmp[i] = b == 0 ? '/' : '\\';
041     }
042 
043     ctmp[10] = 0;
044 
045     imap.insert(pair(ctmp, c));
046   }
047 
048   fgets(line, 100, stdin);
049   sscanf(line, "%d\n", &num_msg);
050 
051   for (i = 0; i < num_msg; ++i) {
052     for (j = 0; j < 10; ++j) {
053       fgets(line, 100, stdin);
054       sscanf(line, "%s\n", &input[j]);
055     }
056 
057     fgets(line, 100, stdin);
058 
059     msg_len = strlen(input[0]) - 2;
060 
061     for (m = 1, p = 0; m <= msg_len; m += 1, p += 1) {
062       for (n = 0; n < 10; n += 1) {
063         ctmp[n] = input[n][m];
064       }
065       ctmp[n] = 0;
066 
067       iter = imap.find(ctmp);
068       dtmp[p] = iter->second;
069     }
070     dtmp[p] = 0;
071 
072     printf("%s\n", dtmp);
073   }
074 
075   return 0;
076 }