Dynamic Programming, SPbSU 2024, Training 1

9 problems from Dynamic Programming, SPbSU 2024, Training 1 (contest 105239), difficulty -. 9/9 solutions verified against sample I/O.

9 items

Dynamic Programming, SPbSU 2024, Training 1

Special | 9 problems | 9/9 verified | Difficulty - | 8m

#	Problem	Time	✓
A	1-Stable Sequence by Number	1m	✓
B	Let Us Assemble a Portfolio Together	44s	✓
C	Colored Tree	1m	✓
D	Da Hong Pao	53s	✓
E	Rain	1m 2s	✓
F	Large Tiling With Dominoes	49s	✓
G	Butterball on a Diet	49s	✓
H	These Piles of Stones Again!	44s	✓
I	Path And k Vertices	59s	✓

Practice › Codeforces Solutions › Dynamic Programming, SPbSU 2024, Training 1 ›

CF 105239A - 1-Stable Sequence by Number

We are asked to enumerate sequences of length n where every element is a positive integer and neighboring elements differ by at most one.

Practice › Codeforces Solutions › Dynamic Programming, SPbSU 2024, Training 1 ›

CF 105239C - Colored Tree

We are given a tree where each node carries two attributes: a weight and a color. From this tree we want to select a subset of vertices with two simultaneous restrictions. First, no two chosen vertices may be adjacent in the tree, so the chosen set must be an independent set.

Practice › Codeforces Solutions › Dynamic Programming, SPbSU 2024, Training 1 ›

CF 105239D - Da Hong Pao

We are given a sequence of cups arranged in a line. Each cup has a value that represents how relaxing it is to drink. Evgeny repeatedly removes cups until none remain, but each time he is only allowed to take either the leftmost or the rightmost remaining cup.

Practice › Codeforces Solutions › Dynamic Programming, SPbSU 2024, Training 1 ›

CF 105239I - Path And k Vertices

We are given a rooted tree where every edge is directed from a child up to its parent, so from any node you can follow a unique chain of parents until you reach the root. Each vertex has a distinct integer value attached to it.

Practice › Codeforces Solutions › Dynamic Programming, SPbSU 2024, Training 1 ›

CF 105239H - These Piles of Stones Again!

We are given a small combinatorial game played on three independent piles of stones. Each move consists of selecting exactly one pile and removing a number of stones from it. The number of stones removed must belong to a fixed allowed set given in the input.

Practice › Codeforces Solutions › Dynamic Programming, SPbSU 2024, Training 1 ›

CF 105239G - Butterball on a Diet

Each store trip gives Butterball two independent supplies: some rice and some chicken breast. Across all trips, he wants to assemble meals of fixed size $k$ grams, but the rules restrict how ingredients can be combined.

Practice › Codeforces Solutions › Dynamic Programming, SPbSU 2024, Training 1 ›

CF 105239F - Large Tiling With Dominoes

We are asked to count how many ways we can completely cover a rectangular grid of height m and extremely large width n using 1×2 dominoes. Each domino covers exactly two adjacent cells either horizontally or vertically, and every cell of the grid must be covered exactly once.

Practice › Codeforces Solutions › Dynamic Programming, SPbSU 2024, Training 1 ›

CF 105239E - Rain

We are given a rectangular grid representing flooded terrain, where each cell has a water depth value. A traveler starts in the top-left cell and wants to reach the bottom-right cell.

Practice › Codeforces Solutions › Dynamic Programming, SPbSU 2024, Training 1 ›

CF 105239B - Let Us Assemble a Portfolio Together

We are given a collection of projects, and for each project there are several mutually exclusive ways to execute it. Each way has a cost and a revenue. For every project we must either pick exactly one of its available ways or skip the project entirely.