Codeforces Round 935 (Div. 3) Solution

A. Setting up Camp#

There are 3 types of people who need to stay in tents, with $a$ , $b$ , and $c$ individuals respectively. The first type, Xiaoboqi, only wants to stay alone, the second type, Xida, must stay with 2 other people, and the third type is indifferent. Each tent can accommodate a maximum of 3 people. What is the minimum number of tents needed?

Xiaoboqi stays alone, Xida forms teams internally as much as possible, and the third type fills in the gaps left by Xida, then take the ceiling of the result divided by 3.

B. Fireworks#

There are two types of fireworks that explode at times $0,a,2a,3a,\dots$ and $0,b,2b,3b,\dots$ , with each explosion lasting $m+1$ time units, meaning they explode at $[0,m],[a,a+m],[2a,2a+m],[3a,3a+m],\dots$ and $[0,m],[b,b+m],[2b,2b+m],[3b,3b+m],\dots$ respectively. For all time points, find the maximum number of fireworks that explode simultaneously.

Clearly, we can just check how many are exploding at time $m$ ; the answer is $(1 + \lfloor \frac{m}{a} \rfloor) + (1 + \lfloor \frac{m}{b}\rfloor)$ .

C. Left and Right Houses#

There is a street with $n$ households, divided into left and right sides by a road. Each household has a preference to live on the left or right side represented by $a_1, a_2, \dots, a_n$ . Now, you need to arrange the position of the road such that at least half of the households on both sides are satisfied, while minimizing the distance from the midpoint and the road's coordinate.

Although there are many conditions, you only need to enumerate where to place the road from left to right, keeping track of the prefix sums to quickly check for validity.

D. Seraphim the Owl#

There is a queue of length $n$ , and you are currently standing at the far right of the queue (position $n+1$ ). Assuming you are currently at position $i$ , you can jump left to position $j < i$ , costing $a_j + \sum_{k=j+1}^{i} b_k$ . Your goal is to jump to a position less than or equal to $m$ with the minimum cost.

The original problem is equivalent to choosing a cost $a_i$ or $b_i$ for each position, as each position will only choose one to calculate once, and the last cost is $a_i$ , allowing for a valid jump plan. Note that you need to enumerate the last landing point within $[1,m]$ , as there may be cases where $b$ is very small and $a$ is very large.

E. Binary Search#

You are given a shuffled permutation of length $n$ , and you can swap any two positions at most 2 times to ensure that binary search can find the answer for this permutation.

At first glance, it seems you need to construct a sequence of length $\lfloor \log_2n \rfloor$ to make binary search work correctly, but that's a misconception. It can be observed that although the binary search process is chaotic, it effectively narrows down the target interval to a unique one. We only need to let it run freely and place the answer in a randomly chosen target position.

During the binary search process, we mark which positions have been visited, allowing the remaining positions to be swapped freely, and finally find a position that hasn't been touched to swap. Note that during the random binary search, if the answer is found midway, an additional operation is needed to move the answer elsewhere.

That's roughly the idea; I just wrote it down randomly, added some assert, but it works.

F. Kirill and Mushrooms#

You are given $n$ mushrooms, each with a weight $a_1,a_2,a_3,\dots,a_n$ . You can select $k$ mushrooms, and the weight is the minimum weight of the selected mushrooms multiplied by $k$ . There is also a restriction: there is a permutation $p_1, p_2, p_3, \dots, p_n$ , and if you choose the $k$ mushrooms, the weights of mushrooms $a_{p_1}, a_{p_2}, \dots, a_{p_{k-1}}$ are cleared and cannot be chosen. Find the minimum number of selections under the maximum weight condition.

Enumerate how many mushrooms are selected from $1$ to $n$ (though it can only be roughly half), maintaining the top $k$ remaining mushrooms and clearing the corresponding mushrooms.

It seems like you could directly use a heap, but I didn't want to think too much and just used a binary indexed tree to maintain the $k$ largest.

G. Cook and Porridge#

There are $n$ people lined up for a meal, and there are a set of rules for sorting them in the queue. Determine if everyone can eat once within the first $D$ time units, or report that it's not possible.

I haven't written it; it seems like I need to maintain some data structure to handle it, but I don't want to write all the details.

H. GCD is Greater#

You are given an array of size $n$ , and you need to divide it into two parts, with each part containing at least 2 elements. The first part requires calculating their $\gcd$ , while the second part requires calculating their $\operatorname{bitwise AND}$ plus a parameter $x$ . Determine if there exists a partition scheme such that the weight of the first part is strictly greater than that of the second part.

Clearly, the $\gcd$ of the first part only needs 2 numbers because the more numbers there are, the smaller the $\gcd$ becomes; similarly, the $\operatorname{bitwise AND}$ also becomes smaller with more numbers, but it meets the target.

So I can directly enumerate the $\gcd$ and then figure out how to judge it, but I haven't written it down or thought it through; it should be doable.

Code#