OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2

12 problems from OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 (contest 105698), difficulty -. 12/12 solutions verified against sample I/O.

12 items

OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2

Special | 12 problems | 12/12 verified | Difficulty - | 11m 24s

#	Problem	Time	✓
A	actGenshinImp	1m 5s	✓
B	Bracket Problem Yet Again	54s	✓
C	Candidate Elimination	53s	✓
D	Depth of Cartesian Tree	48s	✓
E	Extra Character	1m 2s	✓
F	Five Steiner	51s	✓
G	Get Mex Range Add Linear	44s	✓
H	Hell of Optimizing Geometric Construction	1m 10s	✓
I	Inequality Satisfying Subsequences	53s	✓
J	Jenga Tower	1m 8s	✓
K	Kaz's Party	47s	✓
L	LIS on Tree	1m 9s	✓

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698L - LIS on Tree

We are given a tree where every vertex carries a numeric label. From this tree, we consider any simple path between two vertices. Once a path is fixed, it forms a linear sequence of node values in the order they appear along that path.

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698K - Kaz's Party

We are given a set of n friends sitting at a party, each of whom has a uniquely preferred drink. Kaz assigns each friend exactly one drink, forming a permutation of size n. Some friends may immediately receive their correct drink, while others do not.

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698J - Jenga Tower

We are given a vertical stack of rectangular blocks. Each block has a fixed weight proportional to its width and a fixed horizontal position interval $[li, ri]$. The blocks are placed one above another in order, and each block must support everything above it without tipping.

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698H - Hell of Optimizing Geometric Construction

We need to construct a set of $n$ distinct lattice points in a bounded square so that a very specific geometric rule induces a permutation-like behavior. Each point $Xi$ looks at all other points and selects its nearest neighbor.

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698I - Inequality Satisfying Subsequences

We are given a sequence of positive integers and we want to count how many non-empty subsequences are “safe” in the sense that they never contain a triple of elements that can form a triangle.

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698G - Get Mex Range Add Linear

We are maintaining a family of n sets indexed from 1 to n. Every set starts identical and contains only the number 0. Over time, we apply range updates.

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698E - Extra Character

We are given a string whose full structure is indirectly encoded through its Z-function. The Z-array at position i tells us how far the prefix of the string matches the substring starting at i, so it captures all prefix overlap information in a compressed form.

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698F - Five Steiner

We are given five fixed points on the plane, each with integer coordinates, and we are allowed to connect them with straight line segments.

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698D - Depth of Cartesian Tree

We are given a permutation of the numbers from 1 to n. For any segment of this permutation, we can build its Cartesian tree, where the root is always the maximum element of that segment, and the left and right children are defined recursively by splitting the segment around…

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698A - actGenshinImp

We are given a rectangular grid where each cell contains a lowercase letter. A valid object to count is a simple path of exactly 13 distinct cells connected by edges in the grid, moving only up, down, left, or right.

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698B - Bracket Problem Yet Again

We are given an array of positions, each position must eventually be assigned either an opening bracket or a closing bracket. Each choice has its own cost per position: placing an opening bracket at index i costs a[i], while placing a closing bracket costs b[i].

Practice › Codeforces Solutions › OCPC 2024 Summer, Day 5: OCPC Potluck Contest 2 ›

CF 105698C - Candidate Elimination

We are given a single “group” of $n$ cells, similar to one row, column, or box in Sudoku. Each cell contains a set of candidate numbers, and we are guaranteed that there exists a valid way to assign exactly one number per cell such that all chosen numbers are distinct.