#sortings
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 2222B - Artistic Balance Tree
CF 2222B - Artistic Balance Tree Rating: - Tags: greedy, sortings Solve time: 3m 53s Verified: no Solution Problem Understanding We have an array, and before each marking operation we are allowed to reverse any odd-length segment centered at some position. After that reversal, the element currently sitting at index x_i becomes marked. The subtle detail is that marks belong to elements, not positions. If an element gets marked and...
CF 1949F - Dating
CF 1949F - Dating Rating: 2200 Tags: greedy, sortings, trees Solve time: 1m 57s Verified: no Solution Problem Understanding Each user can be viewed as a set of activities. We need to find two users whose sets satisfy three conditions simultaneously: They share at least one activity. The first user has at least one activity that the second user does not have. The second user has at least one activity...
CF 1949B - Charming Meals
CF 1949B - Charming Meals Rating: 1500 Tags: binary search, brute force, greedy, sortings Solve time: 1m 44s Verified: yes Solution Problem Understanding We have two arrays of size n . The array a contains the spiciness values of the appetizers, and the array b contains the spiciness values of the main dishes. Every appetizer must be paired with exactly one main dish, and every main dish must be used...
CF 48F - Snow sellers
CF 48F - Snow sellers Rating: 2800 Tags: greedy, sortings Solve time: 1m 27s Verified: yes Solution Problem Understanding We are asked to plan snow purchases over n days from m companies, ensuring we buy exactly W cubic meters each day. Each company produces a fixed daily amount w[i] , but the cost of all snow from that company decreases linearly: c[i] on day 1, c[i] - a[i] on day...
CF 38E - Let's Go Rolling!
CF 38E - Let's Go Rolling! Rating: 1800 Tags: dp, sortings Solve time: 1m 24s Verified: yes Solution Problem Understanding We are given n marbles on a one-dimensional axis, each with a position x[i] and a pin cost c[i] . You can stick a pin in some marbles, paying the associated cost, and unpinned marbles will roll left until they hit the nearest pinned marble. If a marble has no...