#constructive-algorithms
CF 2222D - Permutation Construction
CF 2222D - Permutation Construction Rating: - Tags: constructive algorithms, data structures, sortings Solve time: 4m 9s Verified: no Solution Problem Understanding We are given an array $a$ of length $n$. We must construct a permutation $p$ of indices $1$ to $n$. For any pair of positions $i<j$, the pair contributes to the score only if it is an inversion in $p$, meaning $p_i>p_j$. Each such inversion contributes the interval...
CF 2222E - Seek the Truth
CF 2222E - Seek the Truth Rating: - Tags: binary search, bitmasks, constructive algorithms, interactive Solve time: 1m 59s Verified: no Solution Problem Understanding The original problem is interactive, but the version used for judging after the contest is the hacked format. Instead of interacting with a judge, each test case directly gives us the hidden values n , k , and c . The interactive story is useful because...
CF 1949K - Make Triangle
CF 1949K - Make Triangle Rating: 2800 Tags: constructive algorithms, math Solve time: 2m 29s Verified: yes Solution Problem Understanding We are given a multiset of positive integers and three required group sizes. Every number must belong to exactly one of the three groups, and each group must contain exactly the requested number of elements. After splitting the numbers, we look only at the three group sums. If those sums...
CF 1949D - Funny or Scary?
CF 1949D - Funny or Scary? Rating: 2600 Tags: constructive algorithms Solve time: 1m 10s Verified: no Solution Problem Understanding We are given a set of $n$ game scenarios, each of which must be played exactly once by the player. Between any two different scenarios $i$ and $j$, the game has a transition video that can be either funny (F) or scary (S). This transition is symmetric, meaning the video...
CF 241G - Challenging Balloons
CF 241G - Challenging Balloons Rating: 1900 Tags: constructive algorithms Solve time: 1m 6s Verified: yes Solution Problem Understanding We have a row of balloons placed at increasing positions on a line. Each balloon has a pressure endurance, which limits how large its radius can grow. We inflate balloons sequentially from left to right. Each balloon expands until either it reaches its maximum radius, dictated by its pressure endurance, or...
CF 48H - Black and White
CF 48H - Black and White Rating: 2800 Tags: constructive algorithms Solve time: 1m 46s Verified: no Solution Problem Understanding We are asked to tile an $n \times m$ rectangular floor with three types of 2x2 square tiles: black, white, and mixed tiles that have a black and a white section in a diagonal pattern. The counts of black-only tiles, white-only tiles, and mixed tiles are given as $a$, $b$,...