Dynamic Programming, SPbSU 2024, Training 2

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

9 items

Dynamic Programming, SPbSU 2024, Training 2

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

#	Problem	Time	✓
A	New Adventures of the Wolf of Wall Street	57s	✓
B	Choosing a Vertex To Remove	59s	✓
C	Space Expedition	52s	✓
D	A Giraffe Travels and Munches	51s	✓
E	Petya and Dice	1m 21s	✓
F	Lottery	54s	✓
G	Evolutionary Tree Weights	1m 2s	✓
H	Subsequence With Specified Differences	45s	✓
I	Sum of Path Lengths	47s	✓

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

CF 105244C - Space Expedition

A space explorer visits a fixed sequence of celestial objects. Each object offers some scientific value if studied, but also consumes two limited resources: energy and time.

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

CF 105244I - Sum of Path Lengths

The input describes a tree with vertices numbered from 1 to n. Every vertex except the first has exactly one parent given, which implicitly defines an undirected edge between each node i and its parent pi.

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

CF 105244H - Subsequence With Specified Differences

We are given a sequence of distinct integers, and we want to extract a subsequence that is strictly increasing. On top of the usual increasing constraint, there is an additional rule that restricts how consecutive elements in the subsequence can differ: if two consecutive…

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

CF 105244G - Evolutionary Tree Weights

We are given several small evolutionary scenarios, each describing a rooted tree of species and a partial mapping between some leaves and known genome strings. Every genome string has the same length and consists of four possible nucleotides.

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

CF 105244F - Lottery

We are given a starting lottery ticket of length $n$. Every position initially contains the number 1. For each position $i$, there is a required target value $bi$. If we manage to make the $i$-th position equal to $bi$, we earn $ci$ coins.

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

CF 105244E - Petya and Dice

We start with a row of n dice, each die showing a single lowercase letter. So at any moment the whole configuration is just a string of length n. The goal is to transform an initial string into a fixed target string using exactly m moves.

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

CF 105244D - A Giraffe Travels and Munches

We are given an $m times n$ grid, where each cell contains a non-negative number representing how many trees grow there. A giraffe starts at the top-left cell $(1,1)$ and wants to reach the bottom-right cell $(m,n)$. The movement rules are constrained and unusual.

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

CF 105244B - Choosing a Vertex To Remove

We are given a tree with n vertices, and every vertex carries a numeric value. If we take any connected component of this tree, its cost is defined in a slightly unusual way: we multiply the number of vertices in that component by the sum of values stored on those vertices.

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

CF 105244A - New Adventures of the Wolf of Wall Street

We are asked to fill an $N times m$ grid with two types of pieces. One is a $1 times 1$ coin tile, and the other is a $1 times 2$ dollar bill that can be placed either horizontally or vertically.