Codeforces Global Round 4

Solutions for Codeforces Global Round 4 (contest 1178). 4/9 problems verified against sample I/O. Difficulty range: 800-3500.

9 items

Codeforces Global Round 4

Type: Global | Problems: 9 | Verified: 4/9 | Rating range: 800-3500 | Time: 55m 42s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Prime Minister	800	greedy	1m 46s	✓
B	WOW Factor	1300	dp, strings	1m 21s	✓
C	Tiles	1300	combinatorics, greedy, math	10m 25s	✓
D	Prime Graph	1500	constructive-algorithms, greedy, math	7m 44s	✗
E	Archaeology	1900	brute-force, constructive-algorithms, greedy	5m 22s	✗
F1	Short Colorful Strip	2200	combinatorics, dfs-and-similar, dp	3m 59s	✓
F2	Long Colorful Strip	2600	dp	6m 44s	✗
G	The Awesomest Vertex	3000	data-structures, dfs-and-similar	8m 35s	✗
H	Stock Exchange	3500	binary-search, flows, graphs	9m 46s	✗

Practice › Codeforces Solutions › Codeforces Global Round 4 ›

CF 1178H - Stock Exchange

We are given a collection of $2n$ stocks. Each stock $i$ has a price that evolves over time in a very simple deterministic way: at integer time $t$, its price is $ai cdot t + bi$. Time starts at $t = 0$, and prices only change at integer moments.

Practice › Codeforces Solutions › Codeforces Global Round 4 ›

CF 1178G - The Awesomest Vertex

We are working with a rooted tree where every node contributes two values, ai and bi. For any node v, consider the path from the root down to v. Along this path we accumulate the sums of a values and b values separately.

Practice › Codeforces Solutions › Codeforces Global Round 4 ›

CF 1178F2 - Long Colorful Strip

We are given a long strip of length $m$, initially all painted with color $0$. Then colors $1$ through $n$ are applied one by one. Each color $i$ is applied by choosing a segment $[ai, bi)$ that is currently monochromatic, and repainting it with color $i$.

Practice › Codeforces Solutions › Codeforces Global Round 4 ›

CF 1178C - Tiles

We are tiling a rectangular grid of size $w times h$, where each cell must contain one square tile. Each tile is a square split along a diagonal into a black and a white triangular half.

Practice › Codeforces Solutions › Codeforces Global Round 4 ›

CF 1178D - Prime Graph

We are asked to construct a simple undirected graph on exactly $n$ vertices. We are free to choose any edges as long as we avoid self-loops and duplicate edges. The graph must satisfy two number-theoretic constraints at the same time.

Practice › Codeforces Solutions › Codeforces Global Round 4 ›

CF 1178E - Archaeology

We are given a long string formed only from the letters a, b, and c, with the restriction that no two adjacent characters are equal.

Practice › Codeforces Solutions › Codeforces Global Round 4 ›

CF 1178F1 - Short Colorful Strip

The final strip consists of n unit segments, and because n = m in this subtask, every colour from 1 to n appears exactly once. The input array is simply a permutation describing the visible colour on each unit segment after all repainting operations have finished.

Practice › Codeforces Solutions › Codeforces Global Round 4 ›

CF 1178B - WOW Factor

We are given a string made only of two characters, v and o. We need to count how many subsequences of this string form the pattern "wow". A subsequence means we pick indices in increasing order, not necessarily contiguous, and read the characters at those positions.

Practice › Codeforces Solutions › Codeforces Global Round 4 ›

CF 1178A - Prime Minister

There are several political parties, and the first party belongs to Alice. She wants to form a coalition that always contains her own party and may contain some additional parties. The coalition must control more than half of all seats in parliament.