Solving UVa 11402 with Segment Trees

Pirate

UVa 11402: Ahoy, Pirates! is one of the most challenging of the uHunt starred problems I have come across so far, for a few reasons:

  • The problem is designed to be solved using a segment tree. This is a data structure that comes up in competitive programming, but isn’t covered in the standard algorithms textbooks (e.g., Sedgewick or CLRS). So I studied it for the first time in preparation for solving this problem.
  • A static segment tree like the one described in Wikipedia, is not sufficient. Solving this problem requires a segment tree that implements lazy propagation so that updates can be made efficiently.
  • As an extra challenge, the problem author added the requirement for an “invert” operation. This adds some implementation complexity and means a generic segment tree implementation won’t work.
  • Java solutions seem to run very close to the time limit, which is a generous five seconds for this problem. Even an efficient solution that addresses the previous points may nevertheless need some additional performance tweaking to run fast enough.

Read on for solutions to these issues, and an explanation of how to go about coding a solution.

« Continue »

Cal and Scott’s Top Performer Course

Bubble

In an earlier post, I mentioned a pilot course I took a couple of years ago on applying deliberate practice to various types of jobs. Well that original pilot, and a subsequent pilot in 2014, has resulted in a course called Top Performer (not an affiliate link). As part of the homework for the second pilot, I came up with the idea for Project 462 and this blog. So as people are considering the course this week, I thought I would add my thoughts to the mix.

« Continue »

Software Methodologies for Very Small Teams

Bootstrap DNA

When I was working on my undergraduate degree in Computing and Software Systems, I took a class in software engineering. The purpose of this class was to introduce us to the range of real-world processes that professionals use to develop software, processes that didn’t often come up in our academic work. That goal turned out to be a tall order for a three-month class, given the scope it tried to cover. It might have been more effective to pick one process and use it for a group project. Nevertheless, one exercise I remember from the class is matching software development processes to types of projects.

Here’s the type of question I’m talking about, from a University of New Brunswick class assignment:

Giving reasons for your answer based on the type of system being developed, suggest the most appropriate generic software process model that might be used as a basis for managing the development of the following systems:

a) A system to control anti-lock braking in a car

b) A virtual reality system to support software maintenance

c) A university accounting system that replaces an existing system

d) An interactive travel planning system that helps users plan a journey with the lowest environment impact

« Continue »