SPC 2019

12 problems from SPC 2019 (contest 102419), difficulty -. 6/12 solutions verified against sample I/O.

12 items

SPC 2019

Special | 12 problems | 6/12 verified | Difficulty - | 1h 38m

#	Problem	Rating	Tags	Accepted	Time	✓
A	Two Strings				10m 29s	✓
B	Super Jaber				19m 25s	✓
C	Two operations				4m 55s
D	Xor the graph				4m 22s
E	Geometry Problem				1m 18s
F	xor-sum				12m 25s	✓
G	Large array				4m 4s	✓
H	In-degree				4m 47s
I	Another Query Problem				7m 54s	✓
J	Jaber The policeman				9m 6s
K	The Dragon and the Kingdom of Trees				6m 40s
L	Cheating detection.				12m 49s	✓

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419K - The Dragon and the Kingdom of Trees

Think about the last time each tree was attacked. If a tree is reset after year t, then it grows for exactly m - t years afterward, so its final height is m - t. Equivalently, define [ ti = m-hi. ] The value ti is the last reset time of tree i.

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419J - Jaber The policeman

Think of every row and every column as a vertex of a bipartite graph. A cell containing 1 is an edge between its row vertex and its column vertex. The value ai tells us exactly how many edges must be incident to row i. The column degrees are completely under our control.

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419H - In-degree

We have an undirected graph, and every edge must eventually point toward exactly one of its two endpoints. For a vertex whose value is specified as (ai), exactly (ai) incident edges must point into that vertex. A vertex with (ai=-1) has no restriction on its final in-degree.

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419C - Two operations

We start with two values, x = 0 and a = 1, and want to make x equal to the given target n using as few operations as possible. The first operation adds the current a to x.

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419B - Super Jaber

The city is a one dimensional array of buildings. Building i has floors from 0 through h[i]. Jaber starts at (i1, f1) and must reach (i2, f2). Inside a building, moving between consecutive floors costs one move.

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419G - Large array

The array a is not given explicitly. It is an infinite-looking repetition of the shorter array b, truncated after n elements. If b = [b0, b1, ..., b(m-1)], then every block of m consecutive elements of a is another copy of b.

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419E - Geometry Problem

I can write the complete editorial, but the geometry figure is essential to deriving the formula. The statement only says “find the area of the grey area, in the figure,” and the figure is not included in the material you provided.

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419D - Xor the graph

We have an undirected graph, and every vertex already carries an integer smaller than (2^{20}). We may choose a subset of vertices and one XOR value (x), then replace every chosen value (ai) by (ai oplus x). The goal is to make the two endpoint values different on every edge.

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419L - Cheating detection.

We have two programs written in a tiny language with three kinds of statements: defining a variable, reading a variable, printing a variable, and assigning the sum of two variables to another variable.

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419I - Another Query Problem

We maintain an integer array (A) of length (n), initially filled with zeroes. A type 2 operation adds an arithmetic progression to one contiguous interval. For an operation ((l,r,a,b)), position (i) receives [ a+b(i-l).

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419F - xor-sum

For each test case, we need to print an array of exactly (n) integers. Every value must lie in the interval ([0,m]), the ordinary sum of all values must be (s), and their bitwise XOR must be (x). If no such array exists, we print (-1).

Practice › Codeforces Solutions › SPC 2019 ›

CF 102419A - Two Strings

We have two strings a and b of the same length. We must choose two different positions and swap those positions in both strings simultaneously. The goal is to make the resulting a lexicographically larger than the resulting b.