The 2022 SDUT Summer Trials

12 problems from The 2022 SDUT Summer Trials (contest 103800), difficulty -. 11/12 solutions verified against sample I/O.

12 items

The 2022 SDUT Summer Trials

Special | 12 problems | 11/12 verified | Difficulty - | 10m 56s

#	Problem	Time	✓
A	Ginger's number	53s	✓
B	Ginger's game	1m 2s	✓
C	Ginger's sequence	58s	✓
D	Ginger's line	51s	✓
E	Ginger's coloring	49s	✓
F	Ginger's treasure	1m 5s	✓
G	Ginger's password	49s	✓
H	Ginger's clone	49s	✓
I	Ginger's balance	45s	✓
J	Ginger's cow	1m 22s
K	Ginger's palindrome	48s	✓
L	Ginger's function	45s	✓

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800L - Ginger's function

We are given a polynomial built as a product of independent factors. Each factor contributes a small set of possible powers of $x$, and when we multiply all factors together we obtain a final expanded polynomial.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800J - Ginger's cow

Let $f(x1,dots,xn)$ be represented by an ordered reduced BDD with root node $r$. For each node $k$ in the BDD, write $V(k)$ for its variable index, and write $mathrm{LO}(k)$ and $mathrm{HI}(k)$ for its two successors. The sinks are $bot$ and $top$.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800I - Ginger's balance

We are given a two-pan balance where each side can hold at most n identical items at once. There are m items in total, and exactly one of them is “bad”, meaning it differs in weight from all others, though we do not know whether it is heavier or lighter.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800K - Ginger's palindrome

We are given a collection of items, where each item has two values: a label and a cost. The label is treated as a string or number that can be concatenated with others. We are allowed to pick any multiset of these items, meaning we may reuse the same item multiple times.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800H - Ginger's clone

We are given an $n times n$ grid where each cell contains a distinct integer. Two agents move on this grid simultaneously. Ginger starts at the top-left cell and initially faces downward. His clone starts at the bottom-right cell and initially faces upward.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800G - Ginger's password

We are asked to reconstruct a full password of length $k$ over lowercase English letters. The password is not arbitrary: it must be non-decreasing in lexicographic order, meaning each character is at least as large as the previous one in the alphabet order.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800F - Ginger's treasure

The input is essentially a long encoded list of integers, where each integer is wrapped by vertical bars and appears in order. If we strip the formatting, we obtain an array of weapon attack values, each associated with its position in the original string.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800E - Ginger's coloring

We are given a permutation of the numbers from 1 to n. You can think of it as a directed graph where every node points to exactly one other node, and because it is a permutation, every node also has exactly one incoming edge. This structure breaks into disjoint directed cycles.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800D - Ginger's line

We are given a collection of straight lines in the plane, each described by an equation of the form $y = ai x + bi$. The task is to count how many unordered pairs of distinct lines intersect at exactly one point. Geometrically, two lines intersect if they are not parallel.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800B - Ginger's game

We are given an array of monster health values. Before anything starts, we are allowed to reduce each value independently, but we can never increase it beyond its original value. After that preparation, we choose a starting position $i$.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800C - Ginger's sequence

We are given an array of integers and a modulus value k. From the array, we can choose any non-empty subsequence, meaning we pick some indices while preserving order, but order itself does not affect the sum so effectively we only care about which elements are selected.

Practice › Codeforces Solutions › The 2022 SDUT Summer Trials ›

CF 103800A - Ginger's number

We are given two positive integers for each test case, call them $x$ and $y$. In one move, we are allowed to pick two divisors $a$ of $x$ and $b$ of $y$, with an extra constraint that $a$ and $b$ share no common prime factors.