Codeforces Round 729 (Div. 2)

6 problems from Codeforces Round 729 (Div. 2) (contest 1542), difficulty 800-2700. 2/6 solutions verified against sample I/O.

6 items

Codeforces Round 729 (Div. 2)

Div. 2 | 6 problems | 2/6 verified | Difficulty 800-2700 | 33m 36s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Odd Set	800	math	51,621	5m 9s	✓
B	Plus and Multiply	1500	constructive-algorithms, math, number-theory	26,531	16m 20s	✓
C	Strange Function	1600	math, number-theory	16,178	2m 39s
D	Priority Queue	2200	combinatorics, dp, implementation	2,921	6m 14s
E1	Abnormal Permutation Pairs (easy version)	2400	combinatorics, dp, fft	1,437	2m 1s
E2	Abnormal Permutation Pairs (hard version)	2700	combinatorics, dp, fft	1,015	1m 13s

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

CF 1542E1 - Abnormal Permutation Pairs (easy version)

We are asked to count ordered pairs of permutations of size n. For each pair (p, q), we require two conditions at the same time: in lexicographic order p comes before q, and the inversion count of p is strictly larger than that of q.

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

CF 1542D - Priority Queue

We are given a sequence of operations that can either insert a value into a multiset or delete the smallest value currently present.

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

CF 1542A - Odd Set

We are given a collection of numbers with even size, specifically 2n integers per test case. The task is to decide whether it is possible to partition these numbers into n disjoint pairs such that every pair consists of two numbers whose sum is odd.

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

CF 1542C - Strange Function

We are given many queries. Each query provides a very large integer $n$, and we consider every integer $i$ from 1 to $n$. For each $i$, we define a function $f(i)$ as the smallest positive integer that fails to divide $i$.

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

CF 1542B - Plus and Multiply

We start from the number $1$. From any number already in the set, we may perform either of two operations: multiply by $a$, or add $b$. After applying these operations any number of times in any order, we obtain an infinite set of reachable values.

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

CF 1542E2 - Abnormal Permutation Pairs (hard version)

The solution does not answer the stated problem correctly. The expression to be bounded is $$leftlfloor frac{b}{2} rightrfloor le leftlfloor frac{b}{v+1} rightrfloor cdot frac{b}{v+1} le b,$$ but the argument does not correctly establish the lower bound.