Problem 102 at the UVa online judge deals with a special kind of bin packing problem, where we are asked to recycle glass in the most efficient way possible.We solve the problem by simple brute force. It may though be harder to implement than might seem at first sight. In any case, this is yet another easy problem from the UVa online judge.

Continue reading...Thursday, July 5, 2012

In problem 10055 at the UVa online judge, we are asked to help Hashmat, the brave warrior, to decide whether he should fight against his opponents. We do that be calculating the difference between the number of Hashmat's soldiers and the number of his opponent's soldiers.The problem is an easy one, but has still eluded many. After little work we end up with an almost one-line solution.

Continue reading...Wednesday, June 13, 2012

Problem 10783 at the UVa Online Judge, also known as Odd Sum, asks us to compute the sum of odd numbers in a given range. The problem is easy, but fun, and can be solved in a similar way to the first Project Euler problem. We start off by creating a straight-forward solution which unfortunately works due to small test cases. We do one minor optimization and then finally finish with a neat closed-form solution.

Continue reading...Wednesday, June 6, 2012

Problem 530 at the UVa Online Judge, also known as Binomial Showdown, asks us to compute the number of ways one can choose k elements out of n elements, not taking order into account. The problem is a classical one (n choose k, anyone?), but with a twist. The input numbers are big, and we need to be really careful not to overflow integers in our intermediate computations. We discover a formula that has smaller intermediate values than the direct formula, and with one more small observation, we're done.

Continue reading...Thursday, May 24, 2012

Problem 10268 at the UVa Online Judge, 498', asks us to evaluate the derivative of a polynomial. It is, like the name suggests, a version of problem 498, which we've already covered here. We solved problem 498 with code reuse in mind. We created a Polynomial class which we can extend to solve this problem, but all we need is to know a formula and then its just a matter of plugging the correct values in.

Continue reading...Tuesday, May 22, 2012

In Problem 498 at UVa Online Judge, Polly the Polynomial, we are asked to evaluate a polynomial. The problem is easier that usual, but its designed to help engineers remember the basic algebra skills, which they supposedly forget as they progress further in their studies. We focus on code reuse and put a little extra work into this problem, but that extra work might save us some work the next time we need to work with polynomials. We also did some manual input parsing, but that can be a handy skill to have.

Continue reading...Wednesday, May 16, 2012

Problem 10127 at UVa Online Judge, Ones, is a neat little problem. We are given an integer and are asked to find its smallest multiple that consists only of ones.We start off by coming up with a simple brute-force solution which, unfortunately, doesn't even work. With some clever observations and some thinking in reverse-mode, we manage create a good solution that works. We also see the interesting results of an attempt I made to make an even faster solution, which unfortunately turned out to be slower.

Continue reading...Wednesday, May 9, 2012

In problem 10229 at UVa Online Judge, Modular Fibonacci, our task is to calculate huge Fibonacci numbers, modulo some given integer.We analyse different methods of computing Fibonacci numbers, but they are either too slow or aren't applicable in our situation. We end up developing a fast solution that makes use of Fibonacci numbers in matrix form and exponentiation by squaring.

Continue reading...Wednesday, April 25, 2012

In UVa 294, Divisors, we are asked to find the number with the maximum number of divisors in a given range. Counting number of divisors is a classic problem, and there exists a fast and simple way to do it. We start off with a straight-forward, but slow, implementation and progressively optimize it until it's fast enough. We don't stop there, though, but we end with a much faster implementation by noticing that divisor count is related to prime factorization.

Continue reading...Wednesday, April 18, 2012

The 3n + 1 problem (or UVa 100) is the first problem at UVa's online judge. It's not the easiest problem there, but also very far from being the hardest.We are dealing with Collatz sequences (also known as Hailstone numbers), and are asked to find the length of the longest Collatz sequence in a given range. We solve the problem by using brute force, but that solution strategy alone might not be fast enough. We realize that we do some computations over and over, so we crank up the speed by doing some caching.

Continue reading...
Wednesday, January 2, 2013

1 Comment