Codeforces Round 1069 (Div. 2)

Solutions for Codeforces Round 1069 (Div. 2) (contest 2175). 2/7 problems verified against sample I/O. Difficulty range: 800-3400.

7 items

Codeforces Round 1069 (Div. 2)

Type: Div. 2 | Problems: 7 | Verified: 2/7 | Rating range: 800-3400 | Time: 12m 28s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Little Fairy's Painting	800	implementation	1m 22s	✓
B	XOR Array	1300	constructive-algorithms, math	1m 37s	✗
C	Needle in a Haystack	1200	greedy, strings	1m 37s	✗
D	Wishing Cards	1900	dp, greedy	1m 41s	✓
E1	Beautiful Patterns (Easy Version)	2400	combinatorics, math, probabilities	1m 53s	✗
E2	Beautiful Patterns (Hard Version)	2500	combinatorics, math, probabilities	2m 1s	✗
F	Secret Message	3400	data-structures, implementation, trees	2m 17s	✗

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

CF 2175F - Secret Message

We are given a weighted undirected graph. We must choose exactly $n-1$ edges. If those $n-1$ edges form a spanning tree, the choice is forbidden. We want the minimum possible total weight among all choices of $n-1$ edges that do not form a tree.

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

CF 2175E2 - Beautiful Patterns (Hard Version)

We are asked to compute the expected beauty of a one-dimensional mosaic of length $n$, where each position is independently colored using one of $m$ colors. The beauty is defined as the square of the number of palindromic subsegments of the mosaic.

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

CF 2175E1 - Beautiful Patterns (Easy Version)

We are looking at a random string of length $n$, where each position independently receives one of $m$ colors with equal probability.

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

CF 2175D - Wishing Cards

We are tasked with distributing a limited number of wishing cards among $n$ friends so that the cumulative happiness of Little A is maximized. Each friend $i$ can carry at most $ai$ cards, and the sum of all cards cannot exceed $k$.

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

CF 2175B - XOR Array

We are asked to construct an array of positive integers of length n such that the XOR of a single contiguous subarray from index l to r is zero, while the XOR of every other non-empty subarray is non-zero.

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

CF 2175C - Needle in a Haystack

We are given two strings, s and t. The goal is to rearrange the letters of t such that s appears as a subsequence in the resulting string, while making the final string lexicographically as small as possible.

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

CF 2175A - Little Fairy's Painting

We are given a very long ribbon with $10^{18}$ cells, but only the first $n$ cells are already painted with specific colors. Each color is represented as an integer.