Friday, January 30, 2009

UVa problem 10260: sample algorithm sample code

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

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

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

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 }

Sunday, January 18, 2009

UVa problem 10696: sample code, sample algorithm

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 }

Saturday, January 17, 2009

UVa problem 10783: sample algorithm

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


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

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.