Codeforces Beta Round 85 (Div. 1 Only)

Solutions for Codeforces Beta Round 85 (Div. 1 Only) (contest 111). 3/5 problems verified against sample I/O. Difficulty range: 1400-2900.

5 items

Codeforces Beta Round 85 (Div. 1 Only)

Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1400-2900 | Time: 12m 59s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Petya and Inequiations	1400	greedy	2m 33s	✗
B	Petya and Divisors	1900	binary-search, data-structures, number-theory	2m 50s	✓
C	Petya and Spiders	2100	bitmasks, dp, dsu	2m 34s	✓
D	Petya and Coloring	2300	combinatorics, dp	2m 19s	✓
E	Petya and Rectangle	2900	-	2m 43s	✗

Practice › Codeforces Solutions › Codeforces Beta Round 85 (Div. 1 Only) ›

CF 111A - Petya and Inequiations

We need to construct an array of n positive integers. The array must satisfy two conditions at the same time. The sum of squares of all elements must be at least x, while the ordinary sum of the elements must not exceed y. The task is not to optimize anything.

Practice › Codeforces Solutions › Codeforces Beta Round 85 (Div. 1 Only) ›

CF 111B - Petya and Divisors

We are asked to process a sequence of queries, each defined by two integers, x and y. For each query, we need to count how many positive divisors of x do not divide any of the y numbers immediately preceding x in the sequence, that is, the numbers x-y, x-y+1, ..., x-1.

Practice › Codeforces Solutions › Codeforces Beta Round 85 (Div. 1 Only) ›

CF 111C - Petya and Spiders

We are given a board of size n by m, with a spider on every cell. Each spider can move to any adjacent cell or stay in place, as long as it stays inside the board. All spiders move simultaneously, and multiple spiders can occupy the same cell after moving.

Practice › Codeforces Solutions › Codeforces Beta Round 85 (Div. 1 Only) ›

CF 111D - Petya and Coloring

We have an $n times m$ grid, and every cell must be painted with one of $k$ colors. The restriction is about every vertical cut between columns.

Practice › Codeforces Solutions › Codeforces Beta Round 85 (Div. 1 Only) ›

CF 111E - Petya and Rectangle

We are given an n × m grid, and two distinct interior cells. The task is to construct the longest possible simple path between them. A simple path means we may visit each cell at most once. Consecutive cells in the path must share a side.