Java Lessons from uHunt Chapter 2

Reference2

This post is part of a series on Java syntax and libraries for solving the problems in each chapter of uHunt, a tool for competitive programming practice. You can find the rest of the posts in the series by visiting my uHunt Java post category.

In the previous post in this series, a review of Java for uHunt Chapter 1 problems, I covered Java basics. This time around, I’ll be discussing the additional Java features required to solve the Chapter 2 problems. The problems in this chaper focus on data structures, so we’ll be looking at data structures supported by the Java Class Library.

As before, I have put full examples of all of these topics in my Reference.java reference class. You can look there to find sample code to try out.

« Continue »

Lessons from Competitive Programming 3, Chapter Two

CP3Chapter2

This post is part of a series of commentaries covering each chapter of Competitive Programming 3 by Steven and Felix Halim. You can find the rest of the posts in the series by visiting my CP3 post category.

Competitive Programming 3 (CP3) Chapter 2 covers a selection of data structures that are useful for solving competitive programming problems. These data structures are used in the Chapter 2 uHunt problems, and in subsequent chapters in the book. In some cases, Chapter 2 just provides a brief introduction to topics that are covered extensively elsewhere. For example, Section 2.4.1 covers some basic information about representing a graph, while Chapter 4 contains the book’s full treatment of graph algorithms. And Section 2.2 devotes a paragraph each to common data structures like arrays, stacks and queues, which readers are expected to know about already. In other cases, Chapter 2 goes into more depth. For example, it’s harder to find information about the Segment Tree data structure in other sources, so it is covered in more detail in this chapter.

As in the rest of the book, each section in this chapter ends with a list of recommended UVa Online Judge problems. The same list can be found on uHunt, where you can also track your progress.

In addition to UVa OJ problems, each section also has written problems. For example, a question in the section on stacks and arrays asks the reader how to implement a stack using an array. Answers are supplied for some of these problems at the end of the chapter. I have just been skimming these written problems. The appeal for me of the CP3/uHunt approach is that problems are “graded” automatically by a computer. Solving problems and then looking up answers at the end of the chapter is the traditional textbook self-study approach. While that can be useful, especially you have a peer or instructor to review your written answers, my goal in using this book is learning through coding. I found plenty of opportunities to learn about the Chapter 2 data structures while I was solving the corresponding uHunt problems.

« Continue »

Lessons from uHunt Chapter Two

uHunt Chapter 2

This post is part of a series that considers what can be learned from the problems in each chapter of uHunt, a tool for competitive programming practice. You can find the rest of the posts in the series by visiting my uHunt post category.

I recently finished the last of the 37 starred problems in uHunt Chapter 2. I’m solving these problems as part of a learning project that I’m calling Project 462, after the 462 uHunt starred problems.

Chapter 2 highlights problems that require more specific data structures than the ad-hoc problems in Chapter 1. The chapter starts out with arrays, covers familiar data structures like stacks and queues, and ends with problems that use Segment Trees and Fenwick Trees, data structures that you may not have heard about in college.

The uHunt approach is to categorize problems by the algorithm, data structure or technique that the authors recommend using to solve them. In addition to the category, each problem has a level — generally 1 through 4 — indicating its difficulty level. The Chapter 2 problems mostly use the same range of levels as the Chapter 1 problems. But for each Chapter 2 problem, there is an extra step of learning or reviewing the appropriate data structure. Although they start with a data structure recommendation, most Chapter 2 problems still require problem-solving techniques and creative thinking.

In many competitive programming situations, you won’t know which data structure to use in advance. The goal of the uHunt style of practice is to get familiar with the range of problems that you’ll come across, so that you know which data structure, algorithm, or technique to use when you see a similar problem in the future.

« Continue »