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 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.