We at MathBlog have written about a couple of problems from the UVa Online Judge. The current UVa OJ platform is almost 7 years old, and so the UVa OJ team thinks it's time for an upgrade. They intend to build the platform up from scratch, but to do that, they need funding. Therefore, they've set up a campaign, located here, where you can donate and help fund the project.There are 6 days left of the campaign, so we encourage you to let others know, and perhaps even donate yourself.

Continue reading...2 January 2013

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...5 July 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...13 June 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...6 June 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...24 May 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...22 May 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...16 May 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...9 May 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...2 May 2012

UVa Online Judge is a website hosted by the University of Valladolid, Spain.It has two main roles. First, it's a problem archive with over 3500 programming problems. Second, you can upload your solution to one of the problems in the archive, and the online judge will determine whether it's correct or not.We cover the basic steps on how to submit your first solution and list a couple of tools to help you solve problems.

Continue reading...
17 April 2013

1 Comment