If the string has odd length, you can't split it into equally sized parts.
Otherwise, the parts are $$$s[:\frac{n}{2}]$$$ and $$$s[\frac{n}{2}:]$$$ and we check they are equal.
Say a number is special if its a square or a cube.
Precalculate all special numbers $$$\leq 10^9$$$. There are only approximately $$$10^{4.5} + 10^3$$$ of them, or about 32000.
To query whether a number is special, we can either do a binary search or linear scan. Alternatively, we could order the queries.
Greedy from right to left. Notice that in each step of the addition, to get a two digit number, the result has to be atleast 10 higher. So there is at most one choice in each addition: either you can make a 1 digit or 2 digit number, but not both.
So in the implementation, check if you can complete the addition for the result being 1 digit, or 2 digits if that fails.
Let's binary search for the answer, reducing the question to the decision problem of if a certain value of alpha can be achieved.
In this context, each shop's item is either valuable (value >= alpha) or not valuable. Because we can only go to n-1 shops, 2 or more friends must have a valuable item at some shop. Also every friend must have a valuable item at some shop. We can check both of these conditions quickly.
There are two conditions for the MEX to be R: * All the values at R have to be incremented by 1 (call this count(R)) * All the values <= R-1 have to be filled (call this low(R-1))
count(R) is easy to find. Note low(R)'s can be found additively with a greedy method: we always pull the largest "free" value towards R, so that low(R) = low(R-1) + (distance from largest unused value). We can keep track of these "largest unused values" using a maxheap.
All this is window dressing for a simple round robin algorithm. Say for example, there are three tables of 5 and more tables of 4. In the first seating, seat people normally (1-5, 6-10, 11-15, 16-19, 20-23, ...). The first 15 people get to sit at the "big" tables. In the second seating, seat the next 15 people (16-30) into the big tables, by seating them (16-20, 21-25, 26-30, 31-34, ...) (circle back to 1 if you get to the last person). It's clear that the use-frequency of the big tables is kept together with this approach.
Consider a graph where bombs are connected by an edge iff blowing up one would cause the other to blow up. Using DSU or otherwise, we can find all connected components, and also the time where all the bombs in that component would all blow up without intervention.
Now what follows is a simple array problem: if the answer is X, it means we've blown up (X+1) components and the remaining components blow up at time <= X. We can scan linearly to find the first X that satisfies the conditions.
(Thanks @neal)
Sqrt decomposition. Let $$$r = \lfloor \sqrt{n} \rfloor + 1$$$ The idea is that jumping $$$k = Ar + B$$$ steps can be done with $$$A$$$ big steps of distance $$$r$$$, and $$$B$$$ small steps of distance $$$1$$$.
Let $$$P(x)$$$ be the permutation, and $$$Q = P^{-1}$$$, $$$\text{jump} = P^r$$$. We maintain these throughout the operations.
The query is easy, so let's focus on the swap, say swapping $$$x, y$$$. We need to update $$$P, Q, \text{jump}$$$. We can update $$$\text{jump}$$$ by maintaining $$$x, y, jx = \text{jump}(x), jy = \text{jump}(y)$$$ as all four pointers walk backwards one step at a time.
Comments (0)
