This course has already ended.

Homework before week 4

This week our theme is the divide-and-conquer paradigm for algorithm design. In our homework we will cover the following topics:

  • segment tree data structures for answering range queries

  • union–find data structures for storing a collection of disjoint sets

  • square-root tricks that can lead to very simple algorithms that are sometimes fast enough.

Homework reading

We will follow Competitive Programmer’s Handbook by Antti Laaksonen. Please read (at least) the following part to prepare for week 4:

  • Chapter 9: Range queries

  • Section 15.2: Union-find structure

  • Chapter 27: Square root algorithms

Homework problems

You will find here a mini-contest with one task: Please ask in Zulip if you need help!

To complete the homework, solve the task before the contest closes. Please use your own personal CSES account. Once you have completed the homework contest, please submit the following form:

A+ presents the exercise submission form here.

Posting submission...