Codeforces Round 716 (Div. 2)

Solutions for Codeforces Round 716 (Div. 2) (contest 1514). 3/5 problems verified against sample I/O. Difficulty range: 800-2700.

5 items

Codeforces Round 716 (Div. 2)

Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2700 | Time: 11m 40s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Perfectly Imperfect Array	800	math, number-theory	2m 51s	✗
B	AND 0, Sum Big	1200	bitmasks, combinatorics, math	2m 30s	✗
C	Product 1 Modulo N	1600	greedy, number-theory	2m 6s	✓
D	Cut and Stick	2000	binary-search, data-structures, greedy	2m 52s	✓
E	Baby Ehab's Hyper Apartment	2700	binary-search, graphs, interactive	1m 21s	✓

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

CF 1514D - Cut and Stick

We are given an array of integers and multiple queries, each asking about a subarray. For each query, we need to divide the subarray into subsequences, possibly of different lengths, so that no number appears more than half the length of any subsequence, rounded up.

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

CF 1514E - Baby Ehab's Hyper Apartment

We are given a single apartment floor modeled as a number line, with n rooms located at integer coordinates from 1 to n. Each room has an initial height assigned to it, and we are allowed to modify the heights in a constrained way.

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

CF 1514A - Perfectly Imperfect Array

Method 1b already provides the key idea. If $(umldots u1u0)3$ is a ternary integer, its decimal value is obtained from the nested form $$(cdots((umcdot3+u{m-1})cdot3+u{m-2})cdots)cdot3+u0.$$ For pencil-and-paper work this means: Start with the leading digit.

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

CF 1514B - AND 0, Sum Big

We are asked to count arrays of length n where each element lies between 0 and 2^k - 1, such that the bitwise AND of all elements is zero and the sum of elements is as large as possible. The result should be returned modulo 10^9 + 7.

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

CF 1514C - Product 1 Modulo N

We are given the numbers from $1$ to $n-1$, and we must select as many of them as possible while keeping a very specific multiplicative condition: if we multiply all selected numbers together, the result must leave remainder $1$ when divided by $n$.