Binary Search the Answer for UVa 11413 and UVa 12032

Ladder

In the Divide and Conquer section of uHunt Chapter 3, one of the subsections is called Binary Search the Answer. Here’s how that technique works.

For a binary search problem like UVa 12192, the data to search is the input data. For that problem, you are given a rectangular grid of integers, and your goal is to find a square region that satisfies a particular property. One step in the process of finding that region efficiently is to run binary search on the data in a row.

Binary search problems like UVa 11413 and UVa 12032 require a different approach. Instead of binary searching the input data, you must search potential output values. The result of the search is the answer.

Competitive programming problem statements often specify the range of inputs that you are required to handle in your solution. For example, the description for UVa 12192 specifies that the grid cannot be larger than 500×500.

The input range is there for a few reasons. It lets you estimate the runtime of your solution before you submit, to avoid a Time Limit error. It also lets you choose an appropriate algorithm. If you determine that an $O(n^2)$ algorithm will run fast enough given the input size, then there’s no need to use an $O(n \log n)$ algorithm, which may take more time to implement. Finally, for search problems, the range tells you which values you have to search.

For binary search the input problems, you can directly plug the input range from the problem statement into the low and high values in your binary search function. For binary search the output problems, you may have to process the input first. Let’s look at a couple of examples.

« Continue »

A Career Skill: Organizing Information

Information

Another session of Top Performer is underway, and one of the goals of the early lessons is finding a skill that is important for success in your career. That has me thinking about skills for programmers. Today I’m going to focus on one particular skill that is critical for programmers working on a team, and becomes more critical as you work on larger projects.

I wrote about a few different skill categories in Skills for Programmers. If you’re a new college graduate starting a full-time job, you might have strong algorithmic problem-solving skills, knowledge of Computer Science fundamentals, expertise in a few specific technologies, and good work habits. Depending on your background, you may even have some of the soft skills required for success at a software company. But what new graduates generally don’t have is experience working on a large codebase that a team of programmers has built up over several years.

When you’re building a small project from scratch, technical questions can be answered through a Stack Overflow search. You still have to think about timeless software engineering questions like good design and whether you’re building the right product for your target audience. But you can rely on others who are working with the same technology to get you unstuck.

When you’re maintaining or enhancing a large software system as part of a team, it’s not enough just to know the technology you’re working with. You also have to know the details of the specific system you’re working on. As I wrote a few weeks ago, that means you have to figure out how to learn from local experts.

If you have a general programming question, find the answer on Stack Overflow, and later forget the answer, you can always find it again. I do that all the time. But if you forget an answer that you got from a local expert, you have to go back to that expert to get it again. That’s an inefficient use of a scarce resource, and it might make your expert grumpy. You want to make the best use of your local experts or, if you’re the expert, ensure that others make the best of your time. You can do that using the skill I’ll be exploring today.

« Continue »

A Summer Learning Plan

Surfers

We have arrived at that time of the year when students leave behind their regular academic schedules and take up summer activities like bike riding, taking long walks on the beach, and learning competitive programming. Last week, a reader sent me an email asking for advice on the best way to spend two months practicing algorithmic problem solving. Here are some ideas for others who may be interested in pursuing that as well.

« Continue »

Learning How to Learn Competitive Programming

Learn

Last week, Quora hosted a session with Barbara Oakley, one of the two instructors for Learning How to Learn, “the world’s largest online course.” During the Quora session, people asked her questions about learning techniques, public speaking, online courses, and other topics. I took the Learning How to Learn class when it was first offered on Coursera, and found it to be a good survey of current learning research, combined with plenty of advice on how to apply it. So when Oakley’s session popped up on Quora, it caught my eye.

It’s worth taking the whole course on Coursera, but the Quora session offers a concentrated summary of a few key ideas. I thought it would be interesting to apply some of Oakley’s advice from the session to the type of learning that goes on here at Red-Green-Code.

« Continue »

Learning From Local Experts

Experts

There’s a certain kind of programming problem that you won’t find the solution to on Stack Overflow, programming blogs, or even an old-fashioned paper book. It’s the kind of problem that is, to use an old Stack Overflow term, too localized. Imagine you’re working on a software team and you encounter one of the following situations:

  • You run a local build (without changing any local files), and it fails.
  • You’re working on a feature, and you need to know how to simulate a credit card payment for your product, without actually submitting a credit card.
  • You’re about to submit a database schema change, and you want to test the database upgrade process the way it will actually work in the shared test environment and on the live system.

There are a few ways you could potentially solve these problems. You can always use the old standby technique of Googling keywords and seeing if you can match the general results with the specific needs of your project. That may get you some interesting options, but it’s likely to require a lot of work.

If your team has good internal documentation with a search function that works, then you may be in luck. If you can find documentation about the exact scenario you’re looking for, then you’re even luckier. Keeping internal documentation is a good practice for any software team, but it does require discipline. Stack Overflow is even trying to encourage team documentation (as long as the team is willing to publish it to the world) with their teams feature.

When Google and internal documentation fail, there’s still one more thing you can try: ask a local expert. Here are a few tips on doing that effectively.

« Continue »