Codeforces Round 717 (Div. 2)

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

5 items

Codeforces Round 717 (Div. 2)

Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2500 | Time: 12m 36s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Tit for Tat	800	greedy	2m 22s	✓
B	AGAGA XOOORRR	1500	bitmasks, brute-force, dp	2m 27s	✗
C	Baby Ehab Partitions Again	1700	bitmasks, constructive-algorithms, dp	2m 51s	✗
D	Cut	2100	binary-search, data-structures, dp	2m 25s	✓
E	Baby Ehab Plays with Permutations	2500	combinatorics, dp, math	2m 31s	✓

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

CF 1516E - Baby Ehab Plays with Permutations

We start with the identity permutation of numbers from 1 to n arranged in a row. In one operation, we are allowed to pick any two positions and swap their values. After performing exactly j such swaps, the array becomes some permutation of 1 to n.

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

CF 1516D - Cut

We are given an array of up to $10^5$ integers. For each query $[l,r]$, we must split that subarray into the minimum possible number of contiguous pieces such that, inside every piece, the product of all elements equals the least common multiple of those elements.

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

CF 1516C - Baby Ehab Partitions Again

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 717 (Div. 2) ›

CF 1516B - AGAGA XOOORRR

We are given an array and allowed to repeatedly compress it by taking two adjacent elements, removing them, and replacing them with their XOR.

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

CF 1516A - Tit for Tat

We are given an array of non-negative integers, and we can perform a number of “transfer” operations. In one operation, we choose two different elements, subtract one from the first, and add one to the second, provided that the first element does not go below zero.