Description

Contest Description

Welcome to the Competitive Programming 4 - Chapter 3.5 Contest! This contest focuses on dynamic programming techniques, featuring problems from Book 1, Chapter 3.5 of "Competitive Programming 4" by Steven Halim, Felix Halim, and Suhendry Effendy. The problems are categorized into different sections based on the type of dynamic programming they emphasize.

Problem Categories

1. Max 1D/2D Range Sum
   Problems A → I
   This section includes 9 problems focused on finding maximum sums in 1D and 2D arrays. These problems will test your ability to apply dynamic programming techniques to efficiently compute maximum subarray sums, whether in a single dimension or within a 2D grid.

2. Longest Increasing Subsequences
   Problems J → P
   A set of 7 problems where you need to find the longest increasing subsequences in a sequence of numbers. These problems are classic examples of dynamic programming, where you must carefully construct solutions by considering previous elements in the sequence.

3. 0-1 Knapsack
   Problems Q → U
   This section consists of 5 problems revolving around the 0-1 knapsack problem, a fundamental dynamic programming challenge. You'll be required to maximize the value of items that can be carried in a knapsack without exceeding its weight capacity, choosing whether to include or exclude each item.

4. Coin Change
   Problems V → X
   These 3 problems will test your ability to determine the number of ways to make change for a given amount using a set of coin denominations. The coin change problem is another staple in dynamic programming, often requiring you to compute the minimum number of coins needed or the total number of ways to achieve the target sum.

5. Traveling Salesperson Problem (TSP)
   Problems Y → AD
   Covering 6 problems, this section deals with the Traveling Salesperson Problem, where you must find the shortest possible route that visits a set of cities and returns to the origin city. Dynamic programming offers an efficient way to tackle this NP-hard problem using bit masking and memoization.

6. DP Level 1
   Problems AE → AL
   A collection of 8 introductory dynamic programming problems designed to solidify your understanding of basic DP concepts. These problems are a great starting point if you're new to dynamic programming or looking to review the fundamental techniques.

7. DP Level 2
   Problems AM → AS
   This final section contains 7 problems that delve into more advanced dynamic programming topics. These problems will challenge your ability to apply dynamic programming in more complex scenarios, requiring a deeper understanding and more sophisticated approaches.

This contest provides a comprehensive review of dynamic programming techniques, from basic principles to more advanced applications. Good luck, and happy coding!

Start & End Times

Problems

The contest has not yet started. The problems will become available when the contest starts.

Scoring

Pass/Fail — Ranked

Standings

• Standings are shown without limitation.

Languages

Ada Algol 68 APL Bash C C# C++ COBOL Common Lisp Crystal D Dart Elixir Erlang F# Forth Fortran Go Haskell Java JavaScript (Node.js) JavaScript (SpiderMonkey) Julia Kotlin Lua Modula-2 Nim Objective-C OCaml Octave Odin Pascal Perl PHP Prolog Python 3 Racket Ruby Rust Simula 67 Smalltalk SNOBOL Swift TypeScript Visual Basic Zig