CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

Solutions for CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) (contest 1896). 3/9 problems verified against sample I/O. Difficulty range: 800-3500.

9 items

CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

Type: Div. 1+2 | Problems: 9 | Verified: 3/9 | Rating range: 800-3500 | Time: 19m 44s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Jagged Swaps	800	sortings	1m 49s	✓
B	AB Flipping	900	greedy, strings, two-pointers	1m 49s	✗
C	Matching Arrays	1400	binary-search, constructive-algorithms, greedy	2m 38s	✗
D	Ones and Twos	1700	binary-search, data-structures, divide-and-conquer	3m 8s	✓
E	Permutation Sorting	2100	data-structures, sortings	2m 59s	✗
F	Bracket Xoring	2600	constructive-algorithms, greedy, implementation	2m 35s	✗
G	Pepe Racing	3200	constructive-algorithms, implementation, interactive	2m 6s	✗
H1	Cyclic Hamming (Easy Version)	3400	brute-force, divide-and-conquer, dp	1m 36s	✓
H2	Cyclic Hamming (Hard Version)	3500	brute-force, dp, fft	1m 4s	✗

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896G - Pepe Racing

There are $n^2$ racers with distinct speeds. A race may contain exactly $n$ racers, and the only information returned is the winner of that race.

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896H1 - Cyclic Hamming (Easy Version)

We are given two binary strings, both of length $2^{k+1}$. Some positions are fixed as 0 or 1, while others are unknown and marked with a question mark.

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896H2 - Cyclic Hamming (Hard Version)

Let $n = 2^{k+1}$. We must fill the question marks in two binary strings $s$ and $t$, each of length $n$, so that both strings contain exactly $n/2$ zeros and $n/2$ ones. The second condition is much more interesting.

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896F - Bracket Xoring

Working

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896D - Ones and Twos

We are given an array consisting only of 1s and 2s, and the array changes over time. Between changes, we are repeatedly asked a yes/no question: whether there exists a contiguous subarray whose sum is exactly some target value. The key difficulty is that the array is not static.

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896E - Permutation Sorting

We are given a permutation of 1...n. Some positions are already correct, meaning a[i] = i. These positions are called good. Every second, we look only at the positions that are still not good. Their values are cyclically shifted one step to the right among those positions.

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896C - Matching Arrays

We have two arrays of equal length. Array a is fixed, while array b may be rearranged arbitrarily. After choosing a permutation of b, we compare the arrays position by position. The beauty of the resulting pair of arrays is the number of indices where a[i] b[i].

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896A - Jagged Swaps

We are given a permutation and a very specific swap operation. A swap is allowed only at a position i where the element is a local maximum. In other words, a[i] must be larger than both of its neighbors.

Practice › Codeforces Solutions › CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1896B - AB Flipping

We are given a string consisting only of two characters, A and B, which can be thought of as a line of adjacent tiles. The only allowed move is to pick a position where an A is immediately followed by a B, and swap them so that the A moves one step to the right.