Algorithm Share

11044: Searching for Nessy

2009-11-01T19:22:00.000-08:00


000 #include <stdio.h>
001 
002 int main() {
003   char line[100];
004   int i, t, n, m, nq, mq, nr, mr, s;
005 
006   fgets(line, 100, stdin);
007   sscanf(line, "%d", &t);
008 
009   for (i = 0; i < t; i += 1) {
010     fgets(line, 100, stdin);
011     sscanf(line, "%d %d", &n, &m);
012 
013     n -= 2;
014     nq = n / 3;
015     nr = n % 3;
016     if (nr) {
017       nq += 1;
018     }
019 
020     m -= 2;
021     mq = m / 3;
022     mr = m % 3;
023     if (mr) {
024       mq += 1;
025     }
026 
027     s = nq * mq;
028     printf("%d\n", s);
029   }
030 
031   return 0;
032 }

10420: List of Conquests

2009-11-01T16:35:00.000-08:00

For this problem, a C++ standard map could be used where the country is used as the key and the number of women Don Giovanni loved in the corresponding country is used as the value. The C++ standard library map automatically sorts its key and value pairs in ascending order according to the keys. In effect, a straightforward iteration on the map yields an alphabetical traversal on the countries accumulated.

Here's a sample implementation:


000 #include <stdio.h>
001 #include <map>
002 #include <iostream>
003 #include <string>
004 
005 using namespace std;
006 
007 int main() {
008   char line[100], ctmp[100];
009   int n, i, j;
010   map<string, int> countries;
011   map<string, int>::iterator iter;
012   
013   fgets(line, 100, stdin);
014   sscanf(line, "%d", &n);
015   
016   for (i = 0; i < n; i += 1) { 
017     fgets(line, 100, stdin);
018     
019     for (j = 0; 1; j += 1) {
020       if (line[j] == ' ') {
021         break;
022       }
023       ctmp[j] = line[j];
024     }
025     ctmp[j] = 0;
026     
027     countries[ctmp] += 1;
028   }
029   
030   for (iter = countries.begin(); iter != countries.end(); ++iter) {
031     cout << iter->first << " " << iter->second << endl;
032   }
033 
034   return 0;
035 }

10361: Automatic Poetry

2009-11-01T01:25:00.000-07:00


#include "stdio.h"

int main() {
  char line[100], s1[100], s2[100], s3[100], s4[100], s5[100];
  char l1[100], l2[100];
  int i, j, k, n, q;
  
  fgets(line, 100, stdin);
  sscanf(line, "%d", &n);
  
  for (i = 0; i < n; i += 1) {
    s1[0] = 0;
    s2[0] = 0;
    s3[0] = 0;
    s4[0] = 0;
    s5[0] = 0; 

    fgets(line, 100, stdin);
    
    for (j = 0, k = 0, q = 0; 1; j += 1, k += 1, q += 1) {
      if (line[j] == '<') {
        break;
      }
      s1[k] = line[j];
      l1[q] = line[j];      
    }
    s1[k] = 0;
    j += 1;
    
    for (k = 0; 1; j += 1, k += 1, q += 1) {
      if (line[j] == '>') {
        break;
      }
      s2[k] = line[j];
      l1[q] = line[j];      
    }
    s2[k] = 0;
    j += 1;

    for (k = 0; 1; j += 1, k += 1, q += 1) {
      if (line[j] == '<') {
        break;
      }
      s3[k] = line[j];
      l1[q] = line[j];      
    }
    s3[k] = 0;
    j += 1;
    
    for (k = 0; 1; j += 1, k += 1, q += 1) {
      if (line[j] == '>') {
        break;
      }
      s4[k] = line[j];
      l1[q] = line[j];      
    }
    s4[k] = 0;
    j += 1;
    
    for (k = 0; 1; j += 1, k += 1, q += 1) {
      if (line[j] == '0' || line[j] == '\n') {
        break;
      }
      s5[k] = line[j];
      l1[q] = line[j];      
    }
    s5[k] = 0;
    l1[q] = 0;
    
    fgets(line, 100, stdin);
    
    for (j = 0; 1; j += 1) {
      if (line[j] == '.') {
        break;
      }
      l2[j] = line[j];
    }
    l2[j] = 0;
    
    printf("%s\n", l1);
    printf("%s%s%s%s%s\n", l2, s4, s3, s2, s5);   
  }

  return 0;
}

UVa problem 10260: sample algorithm sample code

2009-01-30T11:55:00.000-08:00

To solve UVa problem 10260 (Soundex), one could use a map to map characters to their integer values.


001 #include "stdio.h"
002 #include "map"
003 
004 using namespace std;
005 
006 int main() {
007   char line[100], ctmp[100], dtmp[100];
008 
009   int i, j, prev, len, arr[20];
010 
011   map m;
012   map::iterator mi;
013 
014   m['B'] = 1;
015   m['F'] = 1;
016   m['P'] = 1;
017   m['V'] = 1;
018 
019   m['C'] = 2;
020   m['G'] = 2;
021   m['J'] = 2;
022   m['K'] = 2;
023   m['Q'] = 2;
024   m['S'] = 2;
025   m['X'] = 2;
026   m['Z'] = 2;
027 
028   m['D'] = 3;
029   m['T'] = 3;
030 
031   m['L'] = 4;
032 
033   m['M'] = 5;
034   m['N'] = 5;
035 
036   m['R'] = 6;
037 
038   while (fgets(line, 100, stdin)) {
039     for (i = 0, j = 0, prev = 0, len = 0; line[i] != 0; i++) {
040       mi = m.find(line[i]);
041       
042       if (mi != m.end()) {
043         j = (*mi).second;
044 
045         if (j == prev) {
046           continue;
047         }
048 
049         arr[len] = j;
050         len++;
051         prev = j;
052       }
053       else {
054         prev = 0;
055       }
056     }
057 
058     for (i = 0; i < len; i++) {
059       printf("%d", arr[i]);
060     }
061     printf("\n", ctmp);
062   }
063 
064   return 0;
065 }

An easier way to find easy problems

2009-01-30T04:24:00.001-08:00

An easier way to find easy problems in the UVa Online Judge is to use Steven Halim's World of Seven website. His website can be easily searched through Google. Figure 1 shows an excerpt from his website.

Figure 1. Illustration from World of Seven website for finding easy problems.

From Figure 1, we see that some problems are rated 7.0, 8.0, 2.0, 5.5, 2.5, etc. Generally, the lower the rating the easier the problem is. So if you want to find an easy problem, choose a rating number that is as close to 0 as possible.

UVa problem 10469: sample algorithm, sample code

2009-01-30T04:15:00.000-08:00

To solve 10469 (To carry or not to carry), one needs to be able to discover that in order to get the sum without the carry-bits, one simply has to perform a bitwise xor operation on the two numbers.

XOR is simply the following formulat:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 1

For example, for 4 XOR 6, we have to represent them in binary as follows:
4: 100
6: 110
______
2: 010


001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005 
006   int i, j;
007 
008   while (fgets(line, 100, stdin)) {
009     sscanf(line, "%d %d", &i, &j);
010     printf("%d\n", i ^ j);
011   }
012 
013   return 0;
014 }

UVa problem 100: sample code, sample algorithm

2009-01-30T03:49:00.000-08:00

UVa problem 100 (3n + 1) is a pretty straightforward problem. There is one tricky part though. That i is not necessarily always less than j. So one needs to watch out for the case when i is greater than or equal to j.

Also one, can speed things a little bit by using the bit-shift operator for division or multiplication. A division by 2 is similar to a right bit-shift by 1 bit. A multiplication by 2 is equivalent to a left bit-shift by 1 bit.

That is, x / 2 is equivalent to x >> 1; x * 2 is equivalent to x << 1.


001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005 
006   int   i
007       , j
008       , n
009       , n0
010       , m
011       , cycle
012       , max
013       ;
014 
015   while (fgets(line, 100, stdin)) {
016     sscanf(line, "%d %d", &i, &j);
017 
018     if (i <= j) {
019       for (n0 = i, max = 1; n0 <= j; n0++) {
020         n = n0;
021         for (cycle = 1; n != 1; cycle++) {
022           m = n & 1;
023           if (m) {
024             m = n << 1;
025             n = m + n + 1;
026           }
027           else {
028             n >>= 1;
029           } 
030         }
031         if (cycle > max) {
032           max = cycle;
033         }
034       }
035     }
036     else {
037       for (n0 = j, max = 1; n0 <= i; n0++) {
038         n = n0;
039         for (cycle = 1; n != 1; cycle++) {
040           m = n & 1;
041           if (m) {
042             m = n << 1;
043             n = m + n + 1;
044           }
045           else {
046             n >>= 1;
047           } 
048         }
049         if (cycle > max) {
050           max = cycle;
051         }
052       }
053     }
054 
055     printf("%d %d %d\n", i, j, max);
056   }
057 
058   return 0;
059 }

UVa problem 10696: sample code, sample algorithm

2009-01-18T02:18:00.000-08:00

To solve this problem, one needs to be able to discover the observation that:
if N is greater than 100, the output is N - 10; otherwise it is always 91.

One can discover this observation by running a simple simulation of the recursive F91 function:


001 #include "stdio.h"
002 
003 int f91(int n) {
004   if (n <= 100) {
005     return f91(f91(n + 11));
006   }
007   else {
008     return n - 10;
009   }
010 }
011 
012 int main() {
013   char line[100];
014 
015   int n;
016 
017   while (fgets(line, 100, stdin)) {
018     sscanf(line, "%d", &n);
019  
020     if (n == 0) {
021       break;
022     }
023 
024     printf("%d\n", f91(n));
025   }
026 
027   return 0;
028 }

After discovering the pattern, one can then simplify his code like as follows:


001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005   int   n
006       , n1;
007 
008   while(fgets(line, 100, stdin)) {
009     sscanf(line, "%d", &n);
010 
011     if (n == 0) {
012       break;
013     }
014 
015     if (n > 100) {
016       n1 = n - 10;
017     }
018     else {
019       n1 = 91;
020     }
021 
022     printf("f91(%d) = %d\n", n, n1); 
023   }
024 
025   return 0;
026 }

UVa problem 10783: sample algorithm

2009-01-17T22:22:00.000-08:00

For UVa problem 10783 (Odd Sum), one just has to sum up all the odd numbers between two numbers, a and b. Things can get slow if for each number between a and b, one checked if that number were odd or even, like in the following code:

for (i = a, sum = 0; i <= b; i += 1) {
__j = i mod 2;
__if (j == 1) {
____sum += i;
__}
}

To hasten the computation, we can start at an odd number in the for-loop and add 2 to the iterator index for each iteration.

First we check if a is odd or even. If it is even, we increment it to make it odd. Then we go to the for-loop:

for (j = a, sum = 0; j <= b; j += 2) {
__sum += j;
}

UVa problem 10783: sample code

2009-01-17T22:16:00.000-08:00


001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005 
006   int   num_cases
007       , i
008       , j
009       , k
010       , a
011       , b
012       , sum
013       ;
014 
015   fgets(line, 100, stdin);
016   sscanf(line, "%d", &num_cases);
017 
018   for (i = 1; i <= num_cases; i += 1) {
019     fgets(line, 100, stdin);
020     sscanf(line, "%d", &a);
021 
022     fgets(line, 100, stdin);
023     sscanf(line, "%d", &b);
024 
025     k = a & 1;
026     if (k == 0) {
027       a += 1;
028     }
029 
030     for (j = a, sum = 0; j <= b; j += 2) {
031       sum += j;
032     }
033 
034     printf("Case %d: %d\n", i, sum);
035   }
036 
037   return 0;
038 }

UVa problem 11231: sample algorithm

2009-01-17T03:48:00.000-08:00

To solve UVa problem 11231 (Black and white painting), one has to distinguish between two cases: when the top left corner (first_box) is white, or black. After some analyses, one is able to find a way to determine if the first_box is white or black based on the given n, m and c. Figure 1 summarizes this.

Figure 1. Summary for determining if the top left corner is white or black given n, m and c.

In Figure 1, if n and m are of the same type, for example, both even or both odd, then the color of the bottom right corner (last_box) will be the same as the first_box. Otherwise, they will have opposite colors.

First, we tackle the case when the first_box is white (case_white). For case_white, there are two cases. Let us name them case_white1 and case_white2.

For case_white1, we take a look at the chess boards embedded within the painting. This is shown in Figure 2.

Figure 2. Chess boards embedded in the painting for case_white_1.

In Figure 2, passing lanes, both horizontal and vertical are shown. Only 4 passing lanes are shown to avoid clutter. A chess board is defined for each intersection between a horizontal passing lane and a vertical passing lane.

We define a chess board as having four coordinates: h1, h2, v1, v2. h1 stands for the lower-numbered row of the board, h2 stands for the higher-numbered row, v1 stands for the lower-numbered column and v2 stands for the higher-numbered column. A chess board will be designated (h1, h2, v1, v2) for brevity.

In Figure 2, then, there are 4 embedded chess boards as identified when a horizontal lane intersects a vertical lane:

(1, 8, 1, 8)

(1, 8, 3, 10)

(3, 10, 1, 8)

(3, 10, 3, 10)

To compute the number of embedded chess boards in case_white1, we need to obtain the total number of boards in each vertical passing lane. Let us call this number x. We also need to obtain the total number of boards in each horizontal passing lane, calling this number y. The product of x and y will give us the total number of boards for case_white1. Let us call this product, z.

By observing the patterns in case_white1, we arrive at a formula given by Equation 1.

[Equation 1]

x = (n - 6) / 2

y = (m - 6) / 2

z = x * y

Next, we tackle case_white2. Figure 3 shows the embedded boards for case_white2.

Figure 3. Chess boards embedded in the painting for case_white_2.

In Figure 3, the embedded boards have the following coordinates:

(2, 9, 2, 9)

(2, 9, 4, 11)

(4, 11, 2, 9)

(4, 11, 4, 11)

Taking the numbers of boards in the vertical lanes to be q, and the number of boards in the horizontal lanes to be r, we arrive at Equation 2, where s is the total number of boards for case_white2

[Equation 2]

q = (n - 7) / 2

r = (m - 7) / 2

s = q * r

Next, we take on case_black. case_black like case_white offers two cases: case_black1 and case_black2. Figure 4 shows some of the boards in case_black1.

Figure 4. Chess boards embedded in case_black_1.

In Figure 4, the boards have the following coordinates:

(2, 9, 1, 8)

(2, 9, 3, 10)

(4, 11, 1, 8)

(4, 11, 3, 10)

We also arrive at Equation 3, using the same analogy for the variable names as in Equation 1.

[Equation 3]

x = (n - 7) / 2

y = (m - 6) / 2

z = x * y

Figure 5 shows case_black_2.

Figure 5, chess boards embedded in case_black2.

In Figure 5, the following boards are defined:

(1, 8, 2, 9)

(1, 8, 4, 11)

(3, 10, 2, 9)

(3, 10, 4, 11)

Equation 4 is also derived using the same terminologies as used in Equation 2.

[Equation 4]

q = (n - 6) / 2

r = (m - 7) / 2

s = q * r

The total number of embedded chess boards for either case, case_white or case_black, is the sum of z and s.

UVa problem 11231: sample code

2009-01-17T02:53:00.000-08:00


001 #include "stdio.h"
002 
003 int main() {
004   char   line[100]
005        , first_box
006        , black
007        , white
008        ;
009 
010   int   n
011       , m
012       , c
013       , ne
014       , me
015       , code
016       , x
017       , y
018       , z
019       , q
020       , r
021       , s
022       , v
023       ;
024 
025   black = 'b';
026   white = 'w';
027 
028   while (fgets(line, 100, stdin)) {
029     sscanf(line, "%d %d %d", &n, &m, &c);
030 
031     if (n == 0 && m == 0 && c== 0) {
032       break;
033     }
034 
035     ne = n & 1;
036     me = m & 1;
037 
038     ne <<= 2;
039     me <<= 1;
040 
041     code = 0;
042     code = ne | me | c;
043 
044     if (code == 0) {
045       first_box = black;
046     }
047     else if (code == 1) {
048       first_box = white;
049     }
050     else if (code == 2) {
051       first_box = white;
052     }
053     else if (code == 3) {
054       first_box = black;
055     }
056     else if (code == 4) {
057       first_box = white;
058     }
059     else if (code == 5) {
060       first_box = black;
061     }
062     else if (code == 6) {
063       first_box = black;
064     }
065     else {
066       first_box = white;
067     }
068 
069     if (first_box == white) {
070       x = n - 6;
071       x >>= 1;
072 
073       y = m - 6;
074       y >>= 1;
075 
076       q = n - 7;
077       q >>= 1;
078 
079       r = m - 7;
080       r >>= 1;
081     }
082     else {
083       x = n - 7;
084       x >>= 1;
085 
086       y = m - 6;
087       y >>= 1;
088 
089       q = n - 6;
090       q >>= 1;
091 
092       r = m - 7;
093       r >>= 1;
094     }
095 
096     z = x * y;
097     s = q * r;
098 
099     v = z + s;
100 
101     printf("%d\n", v);
102   }
103 
104   return 0;
105 }

UVa problem 11417: sample algorithm

2009-01-16T20:42:00.000-08:00

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

2009-01-16T20:39:00.000-08:00


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 10300: sample algorithm

2009-01-16T01:12:00.000-08:00

For problem 10300, Ecological Premium, for each farmer case, one is given three parameters: land area (land_area), number of animals (num_animals), and degree of environmental friendliness (degree_friendliness). The problem describes that the premium due to the farmer is calculated as Equation 1.

[Equation 1]
premium = (land_area / num_animals) * degree_friendliness * num_animals

But notice from Equation 1 that num_animals can be cancelled out to simplify the formula to Equation 2.

[Equation 2]
premium = land_area * degree_friendliness

In this case, the num_animals parameter is not needed and is used to confused the solver.

So, for a given test case, we calculate the premium for each farmer. Then we sum them up to obtain the burden due by the government.

UVa problem 10300: Sample code

2009-01-16T01:00:00.000-08:00


001 #include "stdio.h"
002 
003 int main() {
004   char   line[100]
005        ;
006 
007   int   num_cases
008       , num_farmers
009       , i
010       , j
011       , area
012       , num_animals
013       , factor
014       , burden
015       ;
016 
017   fgets(line, 100, stdin);
018   sscanf(line, "%d", &num_cases);
019 
020   for (i = 0; i < num_cases; i += 1) {
021     fgets(line, 100, stdin);
022     sscanf(line, "%d", &num_farmers);
023 
024     for (j = 0, burden = 0; j < num_farmers; j += 1) {
025       fgets(line, 100, stdin);
026       sscanf(line, "%d %d %d", &area, &num_animals, &factor);
027 
028       burden += area * factor;
029     }
030 
031     printf("%d\n", burden);
032   }
033 
034   return 0;
035 }

UVA problem 10633: sample algorithm

2009-01-10T18:54:00.000-08:00

Problem 10633 may be entitled "Rare Easy Problem" but I do not think it is that easy. It is tricky as well as a little technical as well as tricky. So one has to be very careful with this before submitting.

We define the difference between N and M in Equation 1.

Y = N - M. [Equation 1]

Since M is formed by chopping off the last digit from N, we have Equation 2.

M = N / 10 [Equation 2]

Using Equation 2, Equation 1 can be expressed as Equation 3.

Y = N - (N / 10) [Equation 3]

Using a little algebra, Equation 3 can be transformed to get N as a function of Y.

N = (10 / 9) * Y [Equation 4]

Equation 4 then provides us a way of calculating N given the input Y.

But then we seem to have another problem. Equation 4 will only lead to one value of N given Y. That does not make sense because for example, given Y = 18, N can be 19 or 20, which gives us two possible answers for N, whereas Equation 4 only provides us one answer.

To solve this mystery, we have to analyze the pattern of some answers. Table 1 provides a listing of Y values followed by the corresponding N values.

Table 1. Listing of Y and corresponding N values.
Y, N
10, 11
11, 12
12, 13
13, 14
14, 15
15, 16
16, 17
17, 18
18, 19 20
19, 21
20, 22
21, 23
22, 24
23, 25
24, 26
25, 27
26, 28
27, 29 30
28, 31
29, 32
30, 33
31, 34
32, 35
33, 36
34, 37
35, 38
36, 39 40
37, 41
38, 42
106, 117
107, 118
108, 119, 120
109, 121
110, 122

Analyzing Table 1 reveals that for any given Y, there can be one or two values of N. Also notice that N has two values only when Y is divisible by 9. When Y is divisible by 9, N has two values N1 and N2 given by Equation 5.

[Equation 5]
N1 = (10 / 9) * Y
N2 = N1 - 1

So the algorithm is given by Equation 5. There's one more issue though. The problem requires that the solution be able to accept inputs as large as 10^18. That's a big input number.

If we used an ordinary integer to represent Y, the integer would most likely be able to accommodate up to 2 billion only assuming a 32-bit signed integer. 10^18 is the following number:

1,000,000,000,000,000,000
___6___5___4___3___2___1

2^31 is the following number:

2,147,483,648
___3___2___1

Obviously, the ordinary integer will not be able to hold 10^18.

If we use an unsigned long long int (assuming that the C language is used), the maximum integer value would be increased to 2^64 (subtract 1 from that to be more accurate):

18,446,744,073,709,551,616
____6___5___4___3___2___1

Well 2^64 seems quite certainly to be greater than 10^18 by a magnitude of about 18.

Alternatively, Equation 5 can be expressed as Equation 6 for N1 which is what I did in the sample code.

N1 = Y + (Y / 9) [Equation 6]

UVA problem 10633: sample code

2009-01-10T18:46:00.000-08:00


001 #include "stdio.h"
002 #include "iostream"
003 
004 using namespace std;
005 
006 int main() {
007   char line[100];
008   unsigned long long
009         x
010       , y
011       , z
012       , m
013       , n
014       ;
015 
016   while (1) {
017     cin >> y;
018 
019     if (y == 0) {
020       break;
021     }
022 
023     x = y / 9;
024     n = y + x;
025 
026     z = x * 9;
027     if (z == y) {
028       m = n - 1;
029       cout << m << " ";
030     }
031 
032     cout << n << endl;
033   }
034 
035   return 0;
036 }

UVa problem 11173: sample algorithm

2009-01-01T23:14:00.001-08:00

To solve UVa problem 11173 (Grey codes), one needs to know a trivia. I know it's quite unfair but that's the way it really is.

I actually spent hours trying to code this thing, trying to accurately simulate the reflection algorithm so vividly and exquisitely described by the problem. Then when I submitted, the online judge said I maxed out the time limit. Then I spent a few more hours figuring out how in the world to speed up this program.

Turned out the vivid description was a trick, a deception into leading me that that was the way to solve the problem. It was to divert my attention into thinking that there was no other way to solve it but to manually do the instruction on reflection step by step.

Then after surrendering, after some while, I thought that maybe there's some clue out there in Google. So I looked up "gray codes" in Google, and guess what? You guessed right. There was a trivia I had to know. To convert from binary to gray code, one only needed a bit shift and an xor bit-wise operation. Try googling it up.

The formula is disappointingly just a single statement to solve this problem:

g = b ^ (b >> 1);

where g stands for the gray code and b stands for the binary number.

That simple and it took me about 4 hours to figure this out. When I learned of this trivia, it took me less than 5 minutes to solve the problem. It's crazy.

UVa problem 11173: sample code

2009-01-01T23:08:00.000-08:00


001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005   int   num_tests
006       , i
007       , j
008       , k
009       , g
010       ;
011 
012   fgets(line, 100, stdin);
013   sscanf(line, "%d", &num_tests);
014 
015   for (i = 0; i < num_tests; i += 1) {
016     fgets(line, 100, stdin);
017     sscanf(line, "%d %d", &j, &k);
018     
019     g = k ^ (k >> 1);
020 
021     printf ("%d\n", g);
022   }
023 }

Parsing words

2009-01-01T04:47:00.000-08:00

Suppose, a user inputs the line in Code 1 (without the quotations).

Code 1. Sample input by user.

“  My name           is   Earl ”

And you need to parse the words “My”, “name”, “is” and “Earl”. How do you do that? Note that the spaces and/or tabs between words, or before or after each word may be zero or more spaces and/or tabs. This just makes parsing more complicated, doesn’t it?

People have different ways of doing things. Let me present my way in Code 2.

Code 2. Sample code for parsing words.
001 #include "stdio.h"
002
003 int main() {
004 __char line[100], ctmp[100];
005 __int i, j;
006
007 __fgets(line, 100, stdin);
008
009 __for (i = 0; 1; i += 1) {
010 ____if (line[i] == '\n' line[i] == 0) {
011 ______break;
012 ____}
013
014 ____if (line[i] == ' ' line[i] == '\t') {
015 ______continue;
016 ____}
017
018 ____for (j = 0; 1 ; i += 1, j += 1) {
019 ______if ( line[i] == ' '
020 _________ line[i] == '\t'
021 _________ line[i] == '\n'
022 _________ line[i] == 0
023 ______) {
024 ________break;
025 ______}
026 ______ctmp[j] = line[i];
027 ____}
028 ____ctmp[j] = 0;
029
030 ____printf("B%sE\n", ctmp);
031 __}
032 }

Of course, there are easier ways like I could use strtok or other more sophisticated methods available. But somehow, I never learned how to use them, had a hard time trying to configure them, and eventually, I ended up just using the code in Code 2 after tiring frustrations one after the other.

The code in Code 2 uses the fgets function in line 007 to get an input line from the user. The for loop in line 009 is then used to process the input character by character.

The for loop starts by checking if the current character it is processing is an end character which can either be a carriage return or a null character (line 010). If the current character is an end character, the loop breaks and processing of the input line is finished.

If the loop determines that the current character is not an end character, it does a another check to see if the current character being processed is a white space which could be a literal space character or a tab character (line 014). If it is a white space character, the loop restarts with the next character.

So, what checks 010 and 014 do is to find a character that is not an end character and at the same time, not a white space also. If a character passes these two initial checks, then we know that we have come across a character that is the beginning of a word because the character is neither an end character or a white space.

The loop then enters into a second for loop (line 018). The second for loop first checks if the character is an end character or a white space (line 019). If it is, it means that we have reached the end of a word and so we break out of the second for loop to break further processing of the current word being parsed out.

In the second for loop, if the current character passes the check of line 019, meaning that the current character is a valid character for a word – valid meaning that it could be alphanumeric or any other character as long as it is not an end character or a white space, then the current character is added into the current word being formed (ctmp).

So the second for loop keeps looping, concatenating one character after another until the end of the word is detected through a character that is either an end character or a white space. A null character is then added to the end of the word to signify the end of the character string (line 028).

After we have formed a word, we can pretty much do anything we want to do with the word parsed out from the input line. In Code 2, we simply print it (line 030).

So we go back to the first for loop and repeat the process all over again until all characters in the input line are processed.

Figure 1 shows a sample output of Code 2 when it is ran with the input of Code 1.

Figure 1. Output when Code 2 is inputted with the input of Code 1.

UVa problem 10865: sample algorithm

2009-01-01T03:57:00.000-08:00

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 10865: sample code

2009-01-01T03:22:00.000-08:00


001 #include "stdio.h"
002 
003 int main() {
004   char   line[100]
005        ;
006   int   i
007       , x
008       , y
009       , x0
010       , y0
011       , num_points
012       , grid[200000][2]
013       , middle
014       , pp
015       , pn
016       , np
017       , nn
018       , stan
019       , ollie
020       ;
021 
022   while (fgets(line, 100, stdin)) {
023     sscanf(line, "%d", &num_points);
024 
025     if (num_points == 0) {
026       break;
027     }
028 
029     for (i = 0; i < num_points; i += 1) {
030       fgets(line, 100, stdin);
031       sscanf(line, "%d %d", &x, &y);
032 
033       grid[i][0] = x;
034       grid[i][1] = y;
035     }
036 
037     middle = num_points >> 1;
038     x0 = grid[middle][0];
039     y0 = grid[middle][1];
040 
041     pp = 0;
042     pn = 0;
043     np = 0;
044     nn = 0;
045 
046     for (i = 0; i < num_points; i += 1) {
047       x = grid[i][0];
048       y = grid[i][1];
049 
050       if (x == x0 || y == y0) {
051         continue;
052       }
053       else if (x > x0 && y > y0) {
054         pp += 1;
055       }
056       else if (x > x0 && y < y0) {
057         pn += 1;
058       }
059       else if (x < x0 && y > y0) {
060         np += 1;
061       }
062       else {
063         nn += 1;
064       }
065     }
066 
067     stan = pp + nn;
068     ollie = np + pn;
069 
070     printf("%d %d\n", stan, ollie);
071   }
072 
073   return 0;
074 }

Finding the easy problems

2008-12-30T01:15:00.000-08:00

For starters, it would be best to try to solve the easier problems first. If one tried solving the hard problems first, then he might get frustrated immediately from getting rejected submissions one after the other. It could also happen that he would get stuck in a single problem for several days and end up extremely disappointed in programming and swearing never to do programming again.

For competitors in a contest, it is also best to find, solve and submit the easier problems first given a set of problems. Otherwise, one might spend so much time in a single hard problem that he losses time that could have been more productively used to submit much easier problems. So instead of submitting 3 easy problems at the end of the contest, he only submits 1 hard problem. But the weight of the easy problem is just the same weight as a hard problem in a programming competition.

So, when one starts a contest, before solving any problem, he should scan and sort out which problems are easier to solve first. Then he should solve the easier problems first. If he wishes to win, then he should resist the temptation of solving the hard problem first for whatever reason. The easy problem and the hard problem would earn one the same amount of money if the contest awarded cash prizes. So why should one consume all his time in solving a hard problem, unless he is not after winning the contest and just simply after programming insight enlightenment?

In this post, I discuss about finding easy problems in the UVa problem archive. Easy problems are only relative in the sense that they are easy compared to the other problems also existing within the archive. So how do we define relativity? Through statistics.

Figure 1 shows a screenshot of the problem archive where statistics are shown for each problem.

Figure 1. Screenshot of the problem archive.

Two ratio statistics are shown for each problem. The first one is the ratio of accepted submissions to total submissions. Let’s call this the BR ratio. For example, for problem 10800, the BR ratio is 19.73%. The second ratio is the ratio of number of users who actually solved the problem to the total number of users who attempted to solve the problem regardless of whether they solved it or not. Let’s call this the UR ratio. For problem 10800, the UR ratio is 67.51%.

Two other statistics exist which are the total submissions for a problem (B value) and the total number of users who attempted to solve a problem (U value). For problem 10800, B is 5039 meaning there were 5039 submissions for this problem whether the submissions were accepted or rejected. For the same problem, U is 1265, meaning there were 1265 users who submitted solutions whether their solutions were accepted or not.

So given this statistics, how do we interpret them? Generally, to find an easy problem, we would want to look for one which has a relatively high BR ratio. This means that an easy problem would be a problem for which most submissions were accepted because it was easy to solve so most people solved it in their first attempt or submission.

Figure 2 shows an example were an easy problem is visually spotted out.

Figure 2. Problem 10865 is likely to be an easy problem.

In Figure 2, one can easily point out that problem 10865 can likely be an easy problem because of the high BR ratio relative to its surrounding neighbor problems. The BR ratio stands out at 71%. Its closest rival has a BR ratio of 55.81%. The 71% BR ratio means that for about every 10 submissions, 7 of those were accepted. With a higher statistical historical ratio, one’s likelihood of solving the problem becomes higher. So it would be better if one start with such easy problems when starting his career in programming in order not to get frustrated at the start of his career immediately.

There is a watch out though. Figure 3 shows an example.

Figure 3. Problem 717 appears to be an easy one but could be actually a real hard one.

In Figure 3, problem 717 stands out easily with a BR ratio of 83.33%. This ratio is very high compared to other problems’ ratios. But looking at its B value of only 18, something looks fishy. The B value is very low which means that out of the tens of thousands of coders, only 18 solutions were submitted. Looking at the U value reveals something even more dismal: only 12 users attempted to solve this problem.

So why did most users avoid this problem as only 12 out of the tens of thousands of coders attempted to try this problem? Most probably this problem is a difficult one which most coders have no idea on how to solve. And those who attempted to solve it were most likely the genius type of users. Remember in high school or college when there would always be someone in class who stands out because of his extreme intelligence. Well, this is perhaps the type of person who solves the problem like problem 717.

So one feel that he is confident to take on really challenging problems, and that most problems have become too easy already, and that he has had enough programming experience already so that he is no longer vulnerable to becoming frustrated whenever he is unable to solve difficult problems, then one must at all cost avoid this type of problems with high BR ratios but extremely low B values.

Notice also that for problem 717, out of the 12 users who attempted it (U = 12), all of them were able to solve it (UR = 100%), confirming that these few people must indeed be geniuses.

UVa problem 11364: sample algorithm

2008-12-29T21:14:00.000-08:00

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 11364: sample code

2008-12-29T20:58:00.000-08:00


001 #include "stdio.h"
002 #include "stdlib.h"
003 
004 int main() {
005   char  line[100]
006       , ctmp[100]
007   ;
008   int   num_tests
009       , num_stores
010       , stores[100]
011       , itmp
012       , max
013       , min
014       , diff
015       , i
016       , j
017       , k
018       , m
019   ;
020 
021   fgets(line, 100, stdin);
022   sscanf(line, "%d\n", &num_tests);
023 
024   for (i = 0; i < num_tests; i += 1) {
025     fgets(line, 100, stdin);
026     sscanf(line, "%d\n", &num_stores);
027 
028     fgets(line, 100, stdin);
029     for (j = 0, m = 0; 1; j += 1) {
030       if (line[j] == '\n' || line[j] == 0) {
031         break;
032       }
033 
034       if (line[j] == ' ' || line[j] == '\t') {
035         continue;
036       }
037 
038       for (k = 0; 1 ; j += 1, k += 1) {
039         if (line[j] == ' ' || line[j] == '\t' || line[j] == '\n' || line[j] == 0) {
040           break;
041         }
042         ctmp[k] = line[j];
043       }
044       ctmp[k] = 0;
045 
046       stores[m] = atoi(ctmp);
047       m += 1;
048     }
049     
050     max = 0;
051     min = 99;
052     for (j = 0; j < num_stores; j += 1) {
053       if (stores[j] > max) {
054         max = stores[j];
055       }
056 
057       if (stores[j] < min) {
058         min = stores[j];
059       }
060     }
061     diff = max - min;
062     diff *= 2;
063 
064     printf("%d\n", diff);
065   }
066 
067   return 0;
068 }

UVa problem 10851: sample algorithm

2008-12-29T19:57:00.000-08:00

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

2008-12-29T19:14:00.000-08:00


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 }

Getting input

2008-12-29T03:36:00.001-08:00

For programming competitions, input will usually come from standard input; that is, input is taken from the user manually typing the input, or input is directed into the program from a file.

When input is manually typed by the user, it will be like Figure 1.

Figure 1. Input manually typed by the user.

In Figure 1, the user manually types the input “User is typing this line now.”

When input is directed into the program from a file, it would appear like Figure 2.

Figure 2. Input directed from a file.

In Figure 2, the contents of the file i.txt are inputted into the program.

Reading a line from standard input can be done using Code 1.

Code 1. Reading a line from standard input.

#include "stdio.h"


int main() {
__char line[100];


__fgets(line, 100, stdin);


__return 0;
}

In Code 1, the fgets statement is configured to read from standard input using the stdin parameter. The line read is then placed into the character array line. The parameter 100 is used to indicate the maximum number of characters to be read. We use 100 since we declared the line variable to be a character array of 100 slots.

In Code 1, once the fgets statement is executed, the user can pretty much do anything with the line variable which contains the line read from standard input. For example, the user can print the contents into standard output such as the code in Code 2.

Code 2. Printing what was read from standard input.

#include "stdio.h"

int main() {

__char line[100];

__fgets(line, 100, stdin);

__printf("User typed the following: %s\n" , line);

__return 0;

}

When Code 2 is executed, it behaves like Figure 3.

Figure 3. Sample execution of Code 2.

Dev-C++

2008-12-28T21:56:00.001-08:00

Most of the algorithms I will be discussing will be based on how I will implement them in the C/C++ language. Although algorithms should be purely independent of the programming language used, I often think of the algorithms in terms of the underlying language I would be using to implement them.

In this post, I will be discussing the tool used for compiling the C/C++ codes I create to test my algorithms. Although everyone has his own way of compiling – like others may use g++ or Visual C++ – others may have no idea on how to compile. This post is dedicated to those others who have no idea or are confused on how to compile their codes. I present my way of compiling.

To compile my C/C++ codes, I use the tool Dev-C++. You can use Google to search for it. It’s a tool my college instructor, Noel Patron from the Ateneo de Manila University, taught me. I thought I would only use it in college, but when I started working as an employee, I was also using it in the company’s regular programming competitions.

My company back then was Canon Information Technologies Philippines, Inc. The company would host quarterly programming competitions. Cash rewards were awarded to winners. I won a couple of contests but I do not consider myself to be a top programmer. The contests in Canon were almost always created by a certain Edward Bernardo, the chief software architect.

So I thought that after college, that would be the end of my using the Dev-C++ tool. But joining the programming competitions in Canon (also called ci-tech (pronounced as “see-I-tek”)) forced me to use the tool again. It was actually the software architect Edward Bernardo who coerced all programming contest participants to use the tool, so I had no choice but to use it again.

Interestingly, several years since I last used the tool in college, the tool had not changed much. Somehow, someway or another, people just stopped developing the tool, and so no new updates or versions of the tool were released since I last used it in college. And that was several years ago.

Somehow also, it is the only Windows C++ compiler I know how to use until this date. In college, I used to use Borland C++ or Microsoft Visual C++. But somehow, these other tools lost popularity. Borland C++ definitely lost popularity as I don’t hear anybody using it anymore, at least in my neighborhood. Microsoft Visual C++ definitely is ultra popular, but how in the world do you get the software for free. Microsoft keeps collecting money from us, until we third world developers have nothing left to use to develop our ideas and algorithms.

So, I was left with Dev-C++, until now, and who knows, maybe until I’m real old and shriveled like a rotten tomato, still aspiring to be a decent programmer.

Now, going back to the real topic. The Dev-C++ website is kind of confusing. I always got lost in it back in college when I had to download the binary and install it into a workstation. In my days, we had no personal laptops and so we had to hop from one computer to another, and install the bloody tool every time we saw that the workstation we hopped into did not have the tool installed into it.

To download the tool, go to the following website:
http://www.bloodshed.net/devcpp.html

Figure 1 shows a screenshot of the site.

Figure 1. Screenshot of the Dev-C++ website.

Click onto the download page, download the binary and install it. By the way, Dev-C++ is for Windows.

Once installed, you can immediately use it. Figure 2 shows a screenshot of the Dev-C++ tool.

Figure 2. Screenshot of the Dev-C++ tool.

Through the tool, you type in your code, save it and then compile (CTRL-F9). Should there be no compile errors, you can close the dialog box shown in Figure 2. Open a command prompt and run the executable as shown in Figure 3.

Figure 3. Executing the executable.

In Figure 3, go to the directory where you saved your code. More often than not, the executable will be the same name as the file name of your code except for the suffix extension. For example, if you named your code a.cpp, then most likely, an executable named a.exe will be created if your compilation yielded no errors. Simply type the name of the executable to execute.

UVa Online Judge

2008-12-28T20:31:00.000-08:00

The UVa Online Judge (http://icpcres.ecs.baylor.edu/onlinejudge/) is a website that archives thousands of problems used for computer programming competitions. It also provides a facility for validating code submissions to the problems published. Hence, it offers an excellent venue for testing algorithms.

Each problem in the archive is tagged with an ID number for easy identification. Refer to Figure 1.

Figure 1. Problems listing in the archive.

In Figure 1, the problem “Moscow time” has an ID number of 505.

Codes can be submitted for online validation can be written in C, Java, C++ or Pascal. Figure 2 shows the form for online submission.

Figure 2. Form for online code submission.

To search for a problem, one can opt to use the Google search bar as shown in Figure 3.

Figure 3. Google bar for searching problems.

Simply type in the problem ID in the Google bar. Be sure to tick the icpcres.ecs.baylor.edu button.

Welcome!

2008-12-28T19:21:00.000-08:00

Welcome to Algorithm Share!

This blog is about sharing algorithms with others.

As for now, most of the problems to which algorithms will be discussed will come from the UVa Online Judge: http://icpcres.ecs.baylor.edu/onlinejudge/

I encourage you to post comments if you have algorithms to share as well. Most of the algorithms I will share will be my own ideas, but I believe that there are a thousand more algorithms out there that are more optimized than my own for a given problem. So, please do share your algorithms for me to learn as well.