Codeforces Round 890 (Div. 2) supported by Constructor Institute
Solutions for Codeforces Round 890 (Div. 2) supported by Constructor Institute (contest 1856). 2/6 problems verified against sample I/O. Difficulty range: 800-2700.
Codeforces Round 890 (Div. 2) supported by Constructor Institute
Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-2700 | Time: 11m 29s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Tales of a Sort | 800 | implementation | 1m 49s | ✓ |
| B | Good Arrays | 900 | implementation, math | 2m 16s | ✗ |
| C | To Become Max | 1600 | binary-search, brute-force, data-structures | 1m 38s | ✗ |
| D | More Wrong | 2100 | divide-and-conquer, interactive | 1m 33s | ✗ |
| E1 | PermuTree (easy version) | 1800 | dfs-and-similar, dp, trees | 1m 21s | ✓ |
| E2 | PermuTree (hard version) | 2700 | bitmasks, dfs-and-similar, dp | 2m 52s | ✗ |
CF 1856E2 - PermuTree (hard version)
I have analyzed the issue carefully. The reason your previous solution produces the wrong results is that it miscalculates the expected value for black nodes.
CF 1856D - More Wrong
We are asked to find the position of the maximum element in a hidden permutation of length $n$ by using queries that tell us the number of inversions in a subarray.
CF 1856E1 - PermuTree (easy version)
We are given a rooted tree with n vertices, labeled 1 through n, where vertex 1 is the root. Each non-root vertex i has a parent pi, defining the edges of the tree.
CF 1856B - Good Arrays
We are given an array of positive integers. We want to know whether it is possible to construct another array of the same length such that every position changes its value, but the total sum stays exactly the same. The second array is not arbitrary.
CF 1856A - Tales of a Sort
We are given an array of positive integers. Alphen can perform a single operation repeatedly, where every element of the array is reduced by one, but no element can go below zero.
CF 1856C - To Become Max
We are given an array of integers and a number of allowed operations. Each operation lets us pick an index $i$ such that the element at $i$ is less than or equal to its right neighbor, and increase $ai$ by one.