Codeforces Round 1069 (Div. 1)

8 problems from Codeforces Round 1069 (Div. 1) (contest 2174), difficulty 1200-3400. 1/8 solutions verified against sample I/O.

8 items

Codeforces Round 1069 (Div. 1)

Div. 1 | 8 problems | 1/8 verified | Difficulty 1200-3400 | 19m 52s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Needle in a Haystack	1200	greedy, strings, two-pointers	14,278	2m 14s
B	Wishing Cards	1900	dp	3,963	1m 29s	✓
C1	Beautiful Patterns (Easy Version)	2400	combinatorics, math, probabilities	1,165	4m 5s
C2	Beautiful Patterns (Hard Version)	2500	combinatorics, math, probabilities	1,023	1m 44s
D	Secret Message	3400	data-structures, dp, greedy	292	2m 19s
E1	Game of Scientists (Version 1)	3100	chinese-remainder-theorem, constructive-algorithms, interactive	133	1m 52s
E2	Game of Scientists (Version 2)	3200	binary-search, chinese-remainder-theorem, dfs-and-similar	97	3m 37s
F	Mosaic Tree	2800	combinatorics, dp, fft	466	2m 32s

Practice › Codeforces Solutions › Codeforces Round 1069 (Div. 1) ›

CF 2174E2 - Game of Scientists (Version 2)

We are interacting with a hidden integer $x$ that is fixed for each game and always lies in the range $[1, c]$, where $c = 2 cdot 10^9$. Our goal is to determine this number using at most three queries. Each query chooses a base $b ge 2$.

Practice › Codeforces Solutions › Codeforces Round 1069 (Div. 1) ›

CF 2174F - Mosaic Tree

Working

Practice › Codeforces Solutions › Codeforces Round 1069 (Div. 1) ›

CF 2174E1 - Game of Scientists (Version 1)

We are asked to guess a hidden number x between 1 and c by making queries about the sum of its digits in a chosen base. Each query specifies a base b (between 2 and c) and returns either the sum of digits of x in that base, or -1 if x is smaller than b.

Practice › Codeforces Solutions › Codeforces Round 1069 (Div. 1) ›

CF 2174D - Secret Message

We are asked to analyze a weighted undirected graph with n vertices and m edges. For each graph, we need to select n - 1 edges whose total weight is minimal, but these edges must not form a tree.

Practice › Codeforces Solutions › Codeforces Round 1069 (Div. 1) ›

CF 2174C1 - Beautiful Patterns (Easy Version)

We are asked to compute the expected beauty of a linear mosaic of pebbles, where each pebble is painted in one of $m$ colors chosen independently and uniformly.

Practice › Codeforces Solutions › Codeforces Round 1069 (Div. 1) ›

CF 2174C2 - Beautiful Patterns (Hard Version)

We are asked to calculate the expected beauty of a 1×n mosaic, where each cell is painted independently with one of m colors. Beauty is defined as the square of the number of palindromic subsegments. A subsegment is palindromic if it reads the same forwards and backwards.

Practice › Codeforces Solutions › Codeforces Round 1069 (Div. 1) ›

CF 2174A - Needle in a Haystack

We are given two strings, s and t, both composed of lowercase English letters. The goal is to rearrange t in such a way that s appears at least once as a subsequence. Among all such valid rearrangements, we need to find the one that is lexicographically smallest.

Practice › Codeforces Solutions › Codeforces Round 1069 (Div. 1) ›

CF 2174B - Wishing Cards

We are building a sequence of numbers $b1, b2, ldots, bn$ representing how many wishing cards each friend will give, but each friend has an upper limit $ai$, and all $bi$ together cannot exceed a total budget $k$. Each $bi$ must stay within $0 le bi le ai$.