Bjarki Ágúst

UVa Online Judge New Platform

UVa Online Judge New Platform

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. Note that MathBlog is not affiliated with UVa Online Judge in any way.

There are 6 days left of the campaign, so we encourage you to let others know, and perhaps even donate yourself.

Again, here is the campaign, and here is the main UVa OJ website.

Posted by Bjarki Ágúst in UVa Online Judge, 1 comment
UVa 102: Ecological Bin Packing

UVa 102: Ecological Bin Packing

We’re back to doing another simple UVa Online Judge problem, and this time we take on problem 102, Ecological Bin Packing. In the problem we are asked to solve a bin packing problem about recycling glass. It can be easily solved with brute force, but requires careful coding. Enough yapping, let’s take a look at the problem description.

Interpretation

We have three bins, each of which contains some number of bottles. There are three types of bottles; brown, green and clear, denoted by “B”, “G” and “C”, respectively. We are given how many  bottles of each type are in each bin. Continue reading →

Posted by Bjarki Ágúst in UVa Online Judge, 1 comment
Monday links

Monday links

Another Monday is upon us, and another batch of links is due. This week I’m going to focus on Dynamic Programming (or DP for short). The reason is that upcoming Project Euler problems are DP- and memoization heavy. Another reason is that DP problems are quite popular, so it’s definitely a good skill to have.

First up is a TopCoder Algorithm Tutorial, namely Dynamic Programming: From novice to advanced. This is a good “first look” at DP. It’s a bit heavy in the end, but that part can be skipped.

After you’ve read that, you should take a look at Bruce Merry‘s introduction to Dynamic programming. It’s got a really great step-by-step approach to solving a DP problem, which in my experience works quite well. Continue reading →

Posted by Bjarki Ágúst in Other, 5 comments
Monday links

Monday links

This Monday I have a couple of links lined up, both math related and non-math related.

First up is a Wikibook titled High School Mathematics Extensions. It contains over 140 pages covering topics like Primes, Modular Arithmetic, Logic, Discrete Probability, Mathematical Programming, and more. It also has exercises and projects for each topic. It’s directed towards 14 to 18 year olds who are interested in mathematics, but this is a good and solid introduction for anyone interested in the aforementioned topics, and can also be a good refresher for more advanced students. The Wikibook is still under construction, so if you have anything to add to it, I encourage you to do so! Continue reading →

Posted by Bjarki Ágúst in Other, 5 comments
UVa 530: Binomial Showdown

UVa 530: Binomial Showdown

Problem 530 at the UVa Online Judge, also known as Binomial Showdown, asks us to compute the number of ways one can choose elements out of elements, not taking order into account. The problem is a classical one ( choose , 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 →

Posted by Bjarki Ágúst in UVa Online Judge, 3 comments
UVa 10268: 498-bis

UVa 10268: 498-bis

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. Continue reading →

Posted by Bjarki Ágúst in UVa Online Judge, 0 comments