Sunday, December 28, 2014

591: box of bricks

This problem is pretty straightforward except for one very bad trick. The problem requires outputting a blank line for every set processed. I got caught here and got a wrong answer in my first try.

The algorithm first calculates the total number of bricks and divides the sum by the number of stacks. the resulting number is the number of bricks for each stack so that all stacks have the same height. i call this height the fair height which is the height whereby all stacks should be equal to.

the algorithm then goes through each stack. if the height of a stack is greater than the fair height, then get the difference. sum all the differences for all stacks taller than the fair height. this sum of differences would then be equal to the minimum number of brick moves.

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

int main() {
    char line[1000];
    char *pch;
    int n, i, fair, x, moves, k;
    int h[1000];

    for (k = 1; 1; k += 1) {
        gets(line);
        sscanf(line, "%d", &n);

        if(!n)
            break;

        gets(line);
        pch = strtok(line, " \t\n");
        i = 0;
        while (pch) {
            h[i] = atoi(pch);
            pch = strtok(NULL, " \t\n");
            i += 1;
        }

        fair = 0;
        for (i = 0; i < n; i += 1) {
            fair += h[i];
        }
        fair /= n;

        moves = 0;
        for (i = 0; i < n; i += 1) {
            x = h[i];
            if (x > fair) {
                moves += (x - fair);
            }
        }

        printf("Set #%d\n", k);
        printf("The minimum number of moves is %d.\n\n", moves);
    }

    return 0;
}
 



Wednesday, December 10, 2014

136: ugly numbers

This is a brute force approach. If the current number is divisible by 2, 3 or 5, then divide it by the number it is divisible by. Keep dividing until you reach 1 as long as it is divisible by 2, 3 or 5. If the current dividend is not yet 1, and it is not divisible by 2, 3 or 5, then it means that your current number is not an ugly number. This approach took 26 seconds on an i5 machine. uVA problem specs requires at most 3 seconds. Other blogs discuss using dynamic programming.

#include "stdio.h"

int main() {
    int i, x, r, is_ugly, count;

    count = 0;
    for(i = 1; 1; i += 1) {
        x = i;
        is_ugly = 1;
        while (x > 1) {
            r = x % 2;
            if (r) {
                r = x % 3;
                if (r) {
                    r = x % 5;
                    if (r) {
                        is_ugly = 0;
                        break;
                    }
                    else {
                        x /= 5;
                    }
                }
                else {
                    x /= 3;
                }
            }
            else {
                x /= 2;
            }
        }
        if (is_ugly) {
            count += 1;
            //printf("%d ", i);
            if (count >= 1500) {
                break;
            }
        }
    }
    printf("The 1500'th ugly number is %d.\n", i);

    return 0;
}

10082: WERTYU

For this problem, I created a character array, containing the keyboard characters in their original sequence. To translate a letter, i searched for the letter in the array and printed the letter that is one index before the index where the letter is located in. I had to detect spaces in the input as well. If the current letter is a space, print a space in the output as well.

#include "stdio.h"

int main() {
    char line[1000];
    int i, j;
    char orig[] = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";

    while(gets(line)) {
        for(i = 0; line[i]; i += 1) {
            if(line[i] == ' ') {
                printf(" ");
                continue;
            }
            for(j = 0; orig[j]; j += 1) {
                if(line[i] == orig[j]) {
                    printf("%c", orig[j-1]);
                    break;
                }
            }
        }
        printf("\n");
    }

    return 0;
}

Friday, October 17, 2014

10018 - Reverse and Add

This problem is pretty straight forward except for one thing. The unsigned int restriction. The problem says that the palindrome cannot be greater than 2^32 = 4,294,967,295, but somehow, just using unsigned int does not work. Unsigned int is 32-bit, and when I use this, I get wrong answer. When I tried using unsigned long long int which is equivalent to 64-bit, the code got accepted.

To read or write an unsigned long long int, I used %llu instead of the usual %d in printf() or scanf().

To get the digits of an integer, I get the remainder when the number is divided by 10. Get the remainder when the quotient is divided by 10 again. Repeat and repeat until the quotient equals 0. The series of remainders obtained correspond to the digits of the integer.

Here's an implementation that got accepted:

#include "stdio.h"

int main() {
  char line[100];
  unsigned long long int num, q, r, l, mid, ispal, rnum, pow, sum;
  int i, j, k, num_input, count;
  unsigned int array[100];

  scanf("%d", &num_input);

  for (k = 0; k < num_input; k += 1) {
    scanf("%llu", &num);

    q = num;
    l = 0;
    while (q > 0) {
      r = q % 10;
      q /= 10;
      array[l] = r;
      l += 1;
    }

    sum = num;
    count = 0;
    do {
      count += 1;
      rnum = 0;
      pow = 1;
      for (i = l - 1; i >= 0; i -= 1) {
        rnum = rnum + (array[i] * pow);
        pow = pow * 10;
      }

      sum = sum + rnum;
//      printf("sum=%d\n", sum);

      q = sum;
      l = 0;
      while (q > 0) {
        r = q % 10;
        q /= 10;
        array[l] = r;
        l += 1;
      }

      mid = l / 2;
      ispal = 1;
      for (i = 0, j = l - 1; i < mid; i += 1, j -= 1) {
        if (array[i] != array[j]) {
          ispal = 0;
          break;
        }
      }
    } while (ispal == 0);

    printf("%d %llu\n", count, sum);
  }

  return 0;
}

Tuesday, October 14, 2014

299 - Train Swapping

I think this problem is an implementation of the insertion sort algorithm (http://en.wikipedia.org/wiki/Insertion_sort). Given a sequence 4 3 2 1, you can perform swaps on the numbers as follows:

4 3 2 1
3 4 2 1
3 2 4 1
2 3 4 1
2 3 1 4
2 1 3 4
1 2 3 4

This gives a total of 6 swaps. Here's another sequence and the sequence of swaps performed to sort the numbers:

4 3 5 1 2
3 4 5 1 2
3 4 1 5 2
3 1 4 5 2
1 3 4 5 2
1 3 4 2 5
1 3 2 4 5
1 2 3 4 5

This gives a total of 7 swaps.

So, one can simply implement the sequence of swaps and count the swaps.

Here's the code. By the way, I used scanf("%d\n", &n) in this code. I noticed that if I don't put \n in the scanf() function, the code does not accept input properly. The scanf() has to be used with the \n character.

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

int main() {
  char line[1000];
  int n, i, l, j, k, p, swaps, temp;
  int c[100];
  char *pch;

  scanf("%d\n", &n);

  for (i = 0; i < n; i += 1) {
    scanf("%d\n", &l);

    gets(line);

    pch = strtok(line, " \t\n");
    for (j = 0; j < l; j += 1) {
      c[j] = atoi(pch);
      pch = strtok(NULL, " \t\n");
    }

    for (k = 1, swaps = 0; k < l; k += 1) {
      for (p = k - 1; p >= 0; p--) {
        if (c[p] < c[p+1]) {
          break;
        }
        temp = c[p];
        c[p] = c[p+1];
        c[p+1] = temp;
        swaps += 1;
      }
    }

//    printf("B");
//    for (j = 0; j < l; j += 1) {
//      printf("%d ", c[j]);
//    }
//    printf("E\n");
    printf("Optimal train swapping takes %d swaps.\n", swaps);
  }

  return 0;
}

Monday, October 13, 2014

10035 - Primary Arithmetic

I get a wrong answer here. and then when i reviewed my code, i realized the error.

what i did was to extract each digit one by one from each number. to extract the first digit, get the remainder by dividing the number by 10. the remainder is the first digit. to extract the second digit, divide the quotient from the first division by 10. the remainder is the second digit. to obtain the third digit, divide quotient from the second division by 10. the remainder is the third digit, etc., etc. until you reach the 9th digit.

sum the first digit from the first number with the first digit from the second number. if the sum is greater than 9, then there is a carry of 1 in the next operation. sum the second digit from the first number and the second digit from the second number and the carry from the first operation. if the sum of the second digits with the carry is greater than 9, then there is a carry in the next operation. sum the third digit from the first number and the third digit from the second number and the carry from the previous operation. if the sum is greater than 9, then there is a carry in the next operation. Repeat the cycle until you reach the 9th digits. During the process, count the number of carries.

The error i had was I forgot to reset the carry when the sum was less than or equal to 9. This led to a wrong answer which was made me upset and depressed. After a few minutes, i reviewed my code and realized the resetting error. Overconfidence kills.

#include "stdio.h"

int main() {
  unsigned int x, y, i, rx, ry, num_carry, sum;
  bool carry;

  while (1) {
    scanf("%d %d", &x, &y);

    if (x == 0 && y == 0) {
      break;
    }

    carry = 0;
    num_carry = 0;

    for (i = 0; i < 9; i += 1) {
      rx = x % 10;
      x = x / 10;

      ry = y % 10;
      y = y / 10;

      sum = rx + ry + carry;

      if (sum > 9) {
        carry = 1;
        num_carry += 1;
      }
      else {
        carry = 0;
      }
    }

    if (num_carry > 1) {
      printf("%d carry operations.\n", num_carry);
    }
    else if (num_carry == 1) {
      printf("1 carry operation.\n");
    }
    else {
      printf("No carry operation.\n");
    }
  }

  return 0;
}

11172 - Relational Operator

This is probably the easiest problem I ever solved in UVA.

I thought that there must be some kind of trick here. Some technicality that would make the problem extra tricky and deceiving. But it looks like there's no trick or deception here. It looks like just a really easy problem.

I also discovered that gets() can be used for these types of problems, instead of my usual fgets() style.

Here's the code:

#include "stdio.h"

int main() {
  char line[100];
  int n, i, a, b;

  gets(line);
  sscanf(line, "%d", &n);

  for (i = 0; i < n; i += 1) {
    gets(line);
    sscanf(line, "%d %d", &a, &b);
//   printf("A=%d, B=%d\n", a, b);

    if (a < b) {
      printf("<\n");
    }
    else if (a > b) {
      printf(">\n");
    }
    else {
      printf("=\n");
    }
  }
}

Sunday, October 12, 2014

10038 - Jolly Jumpers

This is another crazy problem.

It's supposed to be straight forward, but I kept getting run time errors.

My algorithm was to create a list of checks. Whenever a difference was calculated, the checks array element with index equal to the difference was set to 1. Then once all the differences were calculated, and all the checks were marked, I verified if all check elements with indices from 1 up to n-1 were marked with 1. If all were marked with 1, then the sequence is jolly.

I thought the run time error was because I was marking a checks element that is out of bounds. So I tried increasing my checks array from 3000 to 4000. But still the run time error existed. Then I realized that if the private key was n = 3000, then the input line would be more than 3000 characters long. This meant that my usual way of getting the line from the input would not longer work.

Usually, I use this code to get input from the user:
fgets(line, 100, stdin)

But since the input line can be more than 3000 characters long, I changed the code to:
fgets(line, 1000000, stdin)

When I did this, the run time error disappeared.

Here's the code:

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

int main() {
  char line[1000000];
  int n, i, x, j, diff, is_jolly;
  int arr[4000];
  int checks[4000];
  char *pch;

  while (fgets(line, 1000000, stdin)) {
    pch = strtok(line, " \t\n");
    n = atoi(pch);

    if (n == 1) {
      printf("Jolly\n");
      continue;
    }

    for (i = 0; i < n; i += 1) {
      pch = strtok(NULL, " \t\n");
      x = atoi(pch);
      arr[i] = x;
    }

//    printf("arr: ");
//    for (i = 0; i < n; i += 1) {
//      printf("%d ", arr[i]);
//    }
//    printf("\n");

    j = n - 1;
    for (i = 1; i <= j; i += 1) {
      checks[i] = 0;
    }

//    printf("checks: ");
//    for (i = 1; i <= j; i += 1) {
//      printf("%d ", checks[i]);
//    }
//    printf("\n");

    for (i = 1; i <= j; i += 1) {
      diff = arr[i] - arr[i - 1];
      
      if (diff < 0) {
        diff = -1 * diff;
      }

//      printf("diff = %d\n", diff);

      if (diff <= 3000) {
        checks[diff] = 1;
      }
    }

//    printf("diff: ");
//    for (i = 1; i <= j; i += 1) {
//      printf("%d ", checks[i]);
//    }
//    printf("\n");

    is_jolly = 1;
    for (i = 1; i <= j; i += 1) {
      if (checks[i] != 1) {
        is_jolly = 0;
        break;
      }
    }

    if (is_jolly) {
      printf("Jolly\n");
    }
    else {
      printf("Not jolly\n");
    }
  }
}

Friday, October 10, 2014

UVA 494 Kindergarten Counting Game

I couldn't succeed in this problem. Here's my code that could not get accepted. It's quite frustrating. Wish I knew what the private key was. I think I have to let go though, as this will drive me insane if I force myself to get my code accepted. Letting go in life is quite essential to healthy and peaceful living.

What I did here was to go through a line character by character. If the current character is a letter, then turn on the switch to 1. If it is not a letter turn off the switch to 0. When the switch switches from 0 to 1, then I increment the word count. After a line is processed, the code prints the word count. Doesn't work though. huhu.

#include "stdio.h"
#include "string.h"

int main() {
char line[100];
  int word_count, i;
  bool word_found;

while (fgets(line, 100, stdin)) {
    for (i = 0, word_found = 0, word_count = 0; line[i]; i += 1)
      if ((line[i] >= 65 && line[i] <= 90) || (line[i] >= 97 && line[i] <= 122)) {
        if (word_found == 0) {
          word_count += 1;
          word_found = 1;
        }
      }
      else {
        word_found = 0;
      }

      printf("%d\n", word_count);
}

return 0;
}

Parsing words through strtok

Here's how to parse words through strtok().

#include "stdio.h"
#include "string.h"

int main() {
  char line[100];
  char *pch;

  while (fgets(line, 100, stdin)) {
    pch = strtok(line, " \t\n");
    while (pch) {
      printf("B%sE\n", pch);
      pch = strtok(NULL, " \t\n");
    }
  }

  return 0;
}


272: TEX quotes

What I did here was to use a switch.

Process the line character by character. if the current character is an unoriented double quote, check the switch. if the switch is 0, convert to ``, then switch the switch to 1. If the switch is 1, convert to '', then switch the switch to 0.

Here's a code:

#include

int main() {
  char line[100];
  int i;
  bool x = 0;

  while (fgets(line, 100, stdin)) {
    for (i = 0; line[i]; i += 1) {
      if (line[i] != '\n') {
        if (line[i] == '"') {
          if (x == 0) {
            printf("``");
            x = 1;
          }
          else {
            printf("''");
            x = 0;
          }
        }
        else {
          printf("%c", line[i]);
        }
      }
    }
    printf("\n");
  }

  return 0;
}

Thursday, October 9, 2014

458: Decoder

It's been a while since I tried out UVA. am currently applying for a programming job, and the recruiter said that I need to demonstrate skills in C/C++. And so I thought I may need to try out a few programming problems before the recruiter's technical exam.

uHunt recommends that I solve 458 (Decoder). The clue for this problem is the ASCII table:

http://www.asciitable.com/

For the input:
1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5

Notice that the first character is '1'. The ascii character '1' has a decimal equivalent of 49 based on asciitable.com

The output for the input above is

 *CDC is the trademark of the Control Data Corporation.

Therefore the input to output conversion is from '1' to '*'. The ascii character '1' has a decimal equivalent of 49. The ascii character '*' has a decimal equivalent of 42. 49-42 = 7. Therefore 7 is the decimal equivalence between input ascii character and output ascii character.

Just be careful with the the endline character at the end of each input line. What I did was to check each character in the input line. If the character is not equal to the endline, then convert it.

Here's the code:

#include

int main() {
  char line[100];
  char c;
  int i;

  while(fgets(line, 100, stdin)) {
    for (i = 0; c = line[i]; i += 1) {
      if (c != '\n') {
        c -= 7;
        printf("%c", c);
      }
    }
    printf("\n");
  }

  return 0;
}

Saturday, January 4, 2014

My uVA ranking

My current ranking in uVA is around 22000+. It is very far from top coders such as Steven Halim and Felix Halim. Am not sure if these guys are brothers. Steven Halim teaches in some university, I think, in Singapore. These guys are very popular names in uVA and uHunt and I think they have authored programming books catered for programming competitions.

There's this guy Josh Bao who ranks number 1 in the list: http://uhunt.felix-halim.net/id/1133  I did some searching on him and he happens to be a google software chief engineer. He also happens to have a PhD. Did not know that Google was into hiring PhDs. Anyway, Josh Bao has over 4000+ solved problems. Me, on the other hand, only have 20+. He also studied in the Caltech. He must be born genius. Wish I were as gifted as him, but if I were as gifted as him, I would probably be super duper proud. If now that I don't have half his brain, I am already super proud, how much more if I were as intelligently gifted as he is. God has his reasons.

102: Ecological bin packing

This problem was suggested to me by uHunt. It was supposed to be again another easy problem. But upon first reading the problem, it is very intimidating. The problem starts off with an introduction about NP-problems. Big words that make the problem intimidating. I was thinking about dynamic programming algorithms or graph theory algorithms to solve the problem. I was indeed intimidated. In addition, the problem was quite lengthy.

Then I decided to search Google about the problem. Then upon first search, I saw the key words "Brute force". I thought about it a little and I thought that brute force may not be a bad idea after all. I counted the total number of brute force cases and there were only 6. So I decided to hard code them all since there were only 6 cases. For each case, compute for the number of movements. Then choose the case that has the minimum number of cases.

But there's a problem in choosing the case with the minimum number of movements. The problem constrains that the case chosen should be the one that comes out first in alphabetical sorting. Thus, I had to arrange the cases in such a way that the first case was the first in alphabetical order, and the last case was the last in alphabetical sorting. Here's my sample code:

#include

int main() {
  char line[100];
  int b0[3], b1[3], b2[3], x[6], i, j, min;
  
  while (fgets(line, 100, stdin)) {
    sscanf(line, "%d %d %d %d %d %d %d %d %d"
 , &b0[0], &b0[1], &b0[2]
 , &b1[0], &b1[1], &b1[2]
 , &b2[0], &b2[1], &b2[2]
    );
    
    // B = 0; G = 1; C = 2
    
    // 021 BCG
    x[0] = (b1[0] + b2[0]) + (b0[2] + b2[2]) + (b0[1] + b1[1]);

    // 012 BGC
    x[1] = (b1[0] + b2[0]) + (b0[1] + b2[1]) + (b0[2] + b1[2]);
    
    // 201 CBG
    x[2] = (b1[2] + b2[2]) + (b0[0] + b2[0]) + (b0[1] + b1[1]);

    // 210 CGB
    x[3] = (b1[2] + b2[2]) + (b0[1] + b2[1]) + (b0[0] + b1[0]);
    
    // 102 GBC
    x[4] = (b1[1] + b2[1]) + (b0[0] + b2[0]) + (b0[2] + b1[2]);

    // 120 GCB
    x[5] = (b1[1] + b2[1]) + (b0[2] + b2[2]) + (b0[0] + b1[0]);    
    
    for (i = 4, j = 5, min = x[5]; i >= 0; i -= 1) {
      if (x[i] <= min) {
      min = x[i];
      j = i;
      }
    }

//    for (i = 0; i < 6; i += 1) {
//      printf("%d: %d\n", i, x[i]);
//    }

    switch(j) {
      case 0: printf("BCG %d\n", x[j]);
              break;
      case 1: printf("BGC %d\n", x[j]);
              break;
      case 2: printf("CBG %d\n", x[j]);
              break;
      case 3: printf("CGB %d\n", x[j]);
              break;
      case 4: printf("GBC %d\n", x[j]);
              break;
      case 5: printf("GCB %d\n", x[j]);
              break;      
    }
  }
  
  return 0;
}

10071: Back to High School Physics (Java)

I was able to solve this problem previously using C++. I tried to rewrite my code using Java. I have very little experience with Java and am somewhat learning slowly. So I tried to rewrite my previous code using the language Java that is steadily gaining popularity.

It took me a while to get the syntax right. First I realized that the class has to be named "Main"; otherwise, uVA will not accept the code and report compile error. I also somewhat learned how to get lines from standard input using Java. All of this is very technical in nature. All syntax concerns and not really algorithmic concerns. Here is my code after suffering with the syntax. Pain is associated with learning something new.

I noticed that Java somewhat runs slower than C++ for the same problem. Or maybe because I don't know how to optimize my Java code. I noticed that this code runs for about 1++ seconds, whereas my previous C++ code runs in few milliseconds.

import java.util.Scanner; 

public class Main {
  public static void main(String args[]) {
    int v, t, r;
    Scanner sc = new Scanner(System.in);
      while(sc.hasNext()){
         v = sc.nextInt();
         t = sc.nextInt();
         r = v * t;
         r = r << 1;
         System.out.println(r);
      }
  }
}

10071: Back to High School Physics

I tried another uHunt "easy" problem. 10071: Back to High School Physics. It does not sound easy at all nor does it look like high school physics. The problem is about getting the distance an object travels given an initial time and initial velocity, and assuming that the particle travels at constant acceleration.

I really could not remember my physics anymore, so I tried to look at the net for the formulas. I attempted to derive the formulas using my super rusty calculus, but then I opted to look at the Internet for more accurate formulas. I found this formula:

v = at + v0

I then assumed that v0 = 0. Meaning, that the particle had zero velocity at time 0. I then computed for the acceleration at time t:

a = v / t

Then I also found another formula. It was something like:

r = 0.5 * a * (t^2) + (v0 * t) + r0

I then assumed that r0 = 0 and v0 is also 0. Substituting a = v / t, I ended up with the formula r = 2 * v * t
The problem asks the distance after twice the time needed to reach the velocity given in the problem, so:

r = 0.5 * a * (t^2)
r = 0.5 * (v / t)  * ((2t)^2)  // Problem asks the displacement after twice the time given in the problem.
r = 0.5 * (v / t) * (4 * t^2)
r = 2 * v * t

Later on, I realized that I did not really have to go through all these painful derivations. One can simply use the uVA toolkit to put some test inputs, and the take a look at the outputs. Based on the inputs and outputs, one can figure at the formula relating the input to the output. For instance the input 3,6 yields 36, while the input 5, 12 yields 120. So the output must be twice the product of the inputs. uVA toolkit can be found at http://uvatoolkit.com/  Again it is one of those more popular sites regarding uVA. It is also advertised in the wikipedia entry for uVA online judge along with uHunt.

Here's my sample code:

#include

int main() {
  char line[100];
  int v, t, r;

  while (fgets(line, 100, stdin)) {
    sscanf(line, "%d %d", &v, &t);

    r = (v * t);
    r = r << 1;
    
    printf("%d\n", r);
  }
  
  return 0;
}

10055: Hashmat the brave warrior

It's been awhile since I last tried to code for uVA online judge. Probably more than a year. But for some reason, I finally mustered the courage to try to code again. This time I tried using online resources to learn from them. One of the more popular resources is uHunt which enables users to find problems that are easy. In this way, by solving easy problems, one can solve more, and not get that frustrated. I know the feeling of being unable to get an accepted answer. Everytime you submit, you get "Wrong answer" response. It is just so painful. So I tried using uHunt to see if indeed it does suggest easier problems to solve. uHunt, by the way, has an address of: http://uhunt.felix-halim.net

The first problem uHunt suggested to me was 10055 Hashmat the brave warrior. It looks very easy, because all you have to do is subtract two numbers and get the absolute value of the difference. But ironically, it is very deceptive. I had several wrong answer submissions and I could not decipher what was wrong. It happens that this problem is a play on technicality. The problem states "The input numbers are not greater than 2^32." This probably means that plain integer data types won't be able to handle the integer storage. I used unsigned int, but I got wrong answer. Then I tried unsigned long int, still wrong. I also tried unsigned long long int, and still I got wrong answer. It was crazy and definitely a play on technicality. Then I checked the forums and noticed that I had to use %lld instead of %d in my sscanf() and printf() functions. It was a terrible experience because I felt that it was supposed to be a very easy problem. I ended up having more wrong answer submissions for this problem than probably any other problems in the past. And this problem was supposed to be one of the easier ones. Tsk, tsk.


Anyway, here's my code:

#include

int main() {
  char line[100];
  unsigned long long int a, b, c;

  while (fgets(line, 100, stdin)) {
    sscanf(line, "%lld %lld", &a, &b);

    if (a > b) {
      c = a - b;
    }
    else {
      c = b - a;
    }

    printf("%lld\n", c);
  }
  
  return 0;
}