Codeforces Round 270

Solutions for Codeforces Round 270 (contest 472). 5/7 problems verified against sample I/O. Difficulty range: 800-2800.

7 items

Codeforces Round 270

Type: Special | Problems: 7 | Verified: 5/7 | Rating range: 800-2800 | Time: 12m 18s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Design Tutorial: Learn from Math	800	math, number-theory	1m 22s	✓
B	Design Tutorial: Learn from Life	1300	-	1m 44s	✓
C	Design Tutorial: Make It Nondeterministic	1400	greedy	1m 16s	✓
D	Design Tutorial: Inverse the Problem	1900	dfs-and-similar, dsu, shortest-paths	1m 6s	✓
E	Design Tutorial: Learn from a Game	2800	constructive-algorithms, implementation	3m 25s	✗
F	Design Tutorial: Change the Goal	2700	constructive-algorithms, math, matrices	1m 27s	✗
G	Design Tutorial: Increase the Constraints	2800	bitmasks, data-structures, fft	1m 58s	✓

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472A - Design Tutorial: Learn from Math

We are given a single integer n, where n ≥ 12. The task is to find any two composite numbers whose sum is exactly n. A composite number is an integer greater than 1 that has at least one divisor other than 1 and itself.

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472B - Design Tutorial: Learn from Life

We have an elevator starting on the first floor. Every person is waiting on that floor and wants to reach a specific destination floor. The elevator can carry at most k people at once. Moving between floors costs time equal to the floor difference.

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472C - Design Tutorial: Make It Nondeterministic

We are given a list of people, each with a first name and a last name. For each person, we have the freedom to choose either their first or last name as a handle.

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472D - Design Tutorial: Inverse the Problem

We are given an $n times n$ matrix where each entry $d[i][j]$ represents the distance between nodes $i$ and $j$. The question asks whether there exists a weighted tree with $n$ nodes such that the distance along the tree between any two nodes exactly matches the corresponding…

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472E - Design Tutorial: Learn from a Game

We have two boards of the same size. A move starts by choosing one cell and placing a finger on it. After that, the finger walks through adjacent cells. Every time the finger moves from one cell to another, the two orbs in those cells are swapped.

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472F - Design Tutorial: Change the Goal

We are given two arrays of integers, x and y, each of length n. The array x is the starting state, and y is the desired target state. The only operation allowed is x[i] ^= x[j], which replaces x[i] with the bitwise XOR of x[i] and x[j].

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472G - Design Tutorial: Increase the Constraints

We are given two long binary strings, a and b. Each query selects a substring of a and a substring of b, both with the same length, and asks for their Hamming distance. The Hamming distance between two binary strings is simply the number of positions where the bits differ.