Codeforces Round 942 (Div. 1)

Solutions for Codeforces Round 942 (Div. 1) (contest 1967). 1/8 problems verified against sample I/O. Difficulty range: 1400-3500.

8 items

Codeforces Round 942 (Div. 1)

Type: Div. 1 | Problems: 8 | Verified: 1/8 | Rating range: 1400-3500 | Time: 10m 27s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Permutation Counting	1400	binary-search, greedy, implementation	1m 16s	✗
B1	Reverse Card (Easy Version)	1400	brute-force, math, number-theory	57s	✗
B2	Reverse Card (Hard Version)	2200	brute-force, math, number-theory	1m 30s	✗
C	Fenwick Tree	2300	bitmasks, brute-force, combinatorics	1m 2s	✗
D	Long Way to be Non-decreasing	2800	binary-search, dfs-and-similar, graphs	1m 43s	✓
E1	Again Counting Arrays (Easy Version)	3100	combinatorics, dp, fft	1m 13s	✗
E2	Again Counting Arrays (Hard Version)	3500	combinatorics, dp, math	1m 26s	✗
F	Next and Prev	3200	brute-force, data-structures, implementation	1m 20s	✗

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967A - Permutation Counting

We are given a set of cards, each labeled with a number from 1 to n. For each number i, we have ai cards of that type.

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967B1 - Reverse Card (Easy Version)

We are asked to count the number of ordered pairs $(a, b)$ where $1 le a le n$ and $1 le b le m$ such that the sum $a+b$ is divisible by $b cdot gcd(a,b)$.

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967B2 - Reverse Card (Hard Version)

We are asked to count ordered pairs of integers $(a, b)$ with $1 le a le n$ and $1 le b le m$ such that $b cdot gcd(a, b)$ is divisible by $a+b$. The inputs are multiple test cases, each specifying a pair of limits $n$ and $m$.

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967C - Fenwick Tree

We are asked to reverse a Fenwick Tree construction. A Fenwick Tree is normally defined for an array a of length n such that each element sk stores the sum of a contiguous subarray of a whose length is the lowest set bit of k.

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967D - Long Way to be Non-decreasing

We are given an array where each position contains a value in the range $1$ to $m$, and a second array that defines a deterministic transformation on values: every value $x$ has a fixed replacement $bx$.

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967E1 - Again Counting Arrays (Easy Version)

We are given a fixed starting height $b0$ and we imagine building an integer path $b0, b1, ldots, bn$ where each step moves by exactly $+1$ or $-1$, but the path is never allowed to go below zero. This is a standard “walk on the non-negative integers” with unit steps.

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967E2 - Again Counting Arrays (Hard Version)

We are asked to count arrays of integers that meet a very particular set of conditions. We have a starting number, $b0$, and we want to consider sequences $b0, b1, dots, bn$ where consecutive elements differ by exactly 1.

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967F - Next and Prev

We are given a permutation, and we observe it evolving over time by revealing its prefix. After revealing the first $q$ elements, we throw away all values greater than $q$, but keep the relative order of the remaining values.