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;
}