Let's consider that $$$l_1$$$, $$$l_2$$$, and $$$l_3$$$ are sorted working segments. Can we explicitly say something about one of them?
$$$l_1$$$ must be equal to $$$1$$$.
Let's consider that $$$l_1$$$, $$$l_2$$$, and $$$l_3$$$ are sorted working segments.
If $$$l_1$$$ is not equal to $$$1$$$ then we can decrease $$$l_1$$$ by $$$1$$$ and increase $$$l_3$$$ by $$$1$$$. So we'll increase the answer.
We've got that $$$l_1 = 1$$$ and we have to work just with $$$l_2$$$ and $$$l_3$$$.
Now, our problem can be rewritten as:
$$$l_2 + l_3 = n - 4$$$, maximize $$$min(l_2 - 1, l_3 - l_2)$$$.
And as we know that $$$l_3 = n - 4 - l_2$$$, just:
maximize $$$min(l_2 - 1, n - 4 - 2 \cdot l_2)$$$.
If we increase both values under the minimum scope by one, solutions don't change:
maximize $$$min(l_2, (n - 3) - 2 \cdot l_2)$$$.
If we choose $$$l_2 = \left\lfloor\frac{n-3}{3}\right\rfloor$$$, then $$$min(l_2, (n - 3) - 2 \cdot l_2) = \left\lfloor\frac{n-3}{3}\right\rfloor$$$.
If the answer is greater, then $$$l_2 > \frac{n - 3}{3}$$$ and $$$(n - 3) - 2 \cdot l_2 > \frac{n - 3}{3}$$$, and it means that $$$2 \cdot (l_2) + ((n - 3) - 2 \cdot l_2) > n - 3$$$ but $$$2 \cdot (l_2) + ((n - 3) - 2 \cdot l_2) = n - 3$$$.
The only thing is left to do is to calculate final answer. And it is $$$\left\lfloor\frac{n-3}{3}\right\rfloor - 1$$$ or just $$$\left\lfloor\frac{n}{3}\right\rfloor - 2$$$.
It was a mathematician way of solving. As it's pretty obvious that $$$l_2$$$ is approximately $$$\frac{n}{3}$$$, you could check $$$l_2 = \frac{n}{3} \pm 5$$$ and choose the best among them.
Is there a way to cut pieces to save the minimum value and satisfy required conditions?
What is the minimum possible number of operations to perform it?
Is there any better solution?
Let's start with a simple solution.
Let's choose the minimum piece from $$$a$$$ and assume that it will remain the minimum until the end.
As the array is sorted, let's define the minimum piece as $$$a_1$$$.
It means that in the end, all pieces must be smaller or equal to $$$2 \cdot a_1 - 1$$$.
The lower bound of the answer for this solution is $$$\displaystyle{\sum\limits_{i=1}^{n}\left\lceil\frac{a_i}{2 \cdot a_1 - 1}\right\rceil}$$$.
Let's show that this is achievable.
For each piece, while its size greater than $$$2 \cdot a_1 - 1$$$, let's cut off a piece of size $$$2 \cdot a_1 - 1$$$.
The only problem is that we could get a piece smaller than $$$a_1$$$ in the end.
But it means that before the last cut we had a piece in the range $$$[2 \cdot a_1, 3 \cdot a_1 - 2]$$$. All pieces in this range can be easily cut into pieces of the right size in one move.
The only left question is why the minimum piece in the end should have size $$$a_1$$$. Actually, it shouldn't, but it gives the best answer anyway.
As was described above, the lower bound of the solution with the minimal piece of size $$$x$$$ in the end is $$$\displaystyle{\sum\limits_{i=1}^{n}\left\lceil\frac{a_i}{2 \cdot x - 1}\right\rceil}$$$.
Having a minimal piece with a smaller size, we can't get anything better, because the lower bound will be equal or greater for all $$$x < a_1$$$.
What is the first letter in the answer?
$$$a$$$ if $$$t$$$ doesn't start with $$$a$$$ and $$$b$$$ otherwise.
Ask the same question as Hint1 for each position.
When we can't choose the minimum unused letter?
If we form a circle of size less then $$$26$$$.
Maintain any structure to check it.
First of all, the encryption process is reversible. If we obtained $$$t$$$ from $$$s$$$ using the circle $$$c$$$, we can obtain $$$s$$$ from $$$t$$$ using the same cycle $$$c$$$, but reversed.
So, let's think in terms of encryption of $$$t$$$.
Lexicographical order itself is a greedy thing. So, we can create a greedy algorithm.
Let's go from left to right and generate the result letter by letter. We have to choose the best possible option at each step. Let's describe the options we have.
- If the current letter was used earlier, we already know the replacement we need to choose.
- Otherwise, we would like to choose the minimum possible option. We need to maintain some structure to know what is acceptable.
Let's keep the circle that is already generated(it's a graph). For each letter we have one incoming edge and one outgoing edge in the end. Let's keep them for every letter: arrays $$$in[26]$$$, $$$out[26]$$$.
When we want to generate an outgoing edge at some step(let's define the letter on this step as $$$x$$$), we have to choose the minimum letter that doesn't have an incoming edge yet. With one exception: if creating the edge using this rule creates a circle of size less than $$$26$$$. It would mean that we wouldn't have a full circle in the end. It's easy to see that there is no more than one such letter, as this letter is just the end of a chain starting in $$$x$$$.
To check that a small circle wasn't generated, we can go along an outgoing edge $$$26$$$ times, starting at $$$x$$$. If we end up in $$$x$$$ or there was no edge at some step then everything is ok, we can create this edge.
Complexity is $$$\mathcal{O}(26 \cdot 26 + n)$$$, that is, $$$\mathcal{O}(n)$$$.
How many sets can fit in $$$5$$$ cards?
At most two.
If there are two sets among $$$5$$$ cards, there will be a central card.
Consider each card as a central card.
For every two cards, there is always a single card that forms a set with them.
[1] That means that two sets can share at most one card.
Let's prove that there are no more than $$$2$$$ sets in a meta-set.
Let's define $$$5$$$ cards as $$$c_1, c_2, c_3, c_4, c_5$$$. Let's guess that $$$(c_1, c_2, c_3)$$$ is a set.
All other sets can have at most one card among $$$(c_1, c_2, c_3)$$$ (according to [1]), so they must include $$$c_4$$$ and $$$c_5$$$. So we have at most one other set, otherwise they would have two same cards, which is prohibited according to [1].
So, every meta-set looks like $$$2$$$ sets with one common card. Let's call this card a central card.
Now there is just a simple combinatorics. For each card, we want to know the number of sets that include it. If this number is $$$s$$$, then we should add $$$\frac{s(s-1)}{2}$$$ to the answer — it is the number of meta-sets with this card as a central card.
To get the number of sets for each card, we can iterate over all pairs of cards $$$(i, j)$$$, generate the complement to the set, and add $$$1$$$ to that card in a map/hashmap.
Complexity is $$$\mathcal{O}(kn^2\log(n))$$$ or $$$\mathcal{O}(kn^2)$$$.
How many possible options are there for the distance between $$$p_1$$$ and $$$p_2$$$.
We can limit it with $$$2 \cdot n$$$ options.
Consider options $$$d_1[1] + d_2[i]$$$, $$$|d_1[1] - d_2[i]|$$$. Solve each one in linear(almost) time.
Consider the biggest distance among $$$d_1$$$ and $$$d_2$$$.
Can we match it with something?
Remove them one by one while they exceed the distance between $$$p_1$$$ and $$$p_2$$$. Then the problem is trivial.
Let's assume that considered point $$$p_1$$$ was to the left of considered point $$$p_2$$$.
Let's assume that we know the distance $$$l$$$ between considered points $$$p_1$$$ and $$$p_2$$$. Let's show how to solve this problem in linear time(almost linear).
As long as there is a value greater than $$$l$$$, let's get the largest among them(let's call it $$$x$$$). Let's assume that this value is from $$$d_1$$$.
It's easy to see that this point is to the right of the considered point $$$p_2$$$ (because the largest distances is to the point $$$p_1$$$). It means that we can match distance $$$x$$$ from $$$d_1$$$ to the distance $$$x - l$$$ from $$$d_2$$$.
When there is no value greater than $$$l$$$, all other houses are located between considered points. We can match them by sorting.
That is the $$$\mathcal{O}(n log(n))$$$ solution.
Let's limit possible options of $$$l$$$ with $$$\mathcal{O}(n)$$$ options.
If we know that some house has distances $$$x$$$ and $$$y$$$ to considered options, then there are $$$2$$$ options of $$$l$$$: $$$x + y$$$ and $$$|x - y|$$$.
Let's consider $$$2 \cdot n$$$ options $$$d_1[1] + d_2[i]$$$, $$$|d_1[1] - d_2[i]|$$$.
Complexity is $$$\mathcal{O}(n^2 log(n))$$$.
Draw currencies on 2D plane.
Assume that you can throw out any amount of money at any moment.
What will an area of possible points look like?
It will look like a convex polygon in the upper-right quarter.
Keep its edges.
How does the structure change when a new day comes?
A new segment is added. A prefix of old segments is shifted by vector, the remaining suffix of old segments is shifted by opposite vector,
Let's draw currencies on 2D plane. Having $$$x$$$ pebbles and $$$y$$$ beads is described as point $$$(x, y)$$$.
Let's assume that we can throw out any amount of money at any moment. In this case, an area of possible points can be described as a convex polygon in the upper-right quarter. Initially it is the rectangle $$$[(0, 0), (0, b), (a, b), (a, 0)]$$$.
At any moment, this polygon can be described as a list of segments starting at point $$$(0, y_0)$$$ and finishing at point $$$(x_k, 0)$$$. In the rectangle described above, there are $$$2$$$ segments.
Let's keep those segments sorted by angle.
When a new day comes, each point can be shifted by the vector $$$c\cdot(p_i, -q_i)\ \forall c \in [-1, 1]$$$ if the new point has non-negative coordinates.
If we forget about new points to be non-negative, how new segments look like?
We just have to add new segment $$$(2 \cdot p_i, -2 \cdot q_i)$$$ and shift a prefix of old segments by $$$(-p_i, q_i)$$$ and remaining suffix of segments by $$$(p_i, -q_i)$$$.
Then the only thing left to do is to cut segments to keep our polygon non-negative.
Sounds great, but sounds like $$$\mathcal{O}(n^2)$$$.
Do we need to maintain segments explicitly?
No!
Let's just keep the set of their lengths and angles. Knowledge of extreme points $$$(0, y_0)$$$ and $$$(x_k, 0)$$$ is enough.
So we need to:
- Insert a new segment to the set. (You need just length and angle).
- Shift extreme points $$$(0, y_0)$$$ and $$$(x_k, 0)$$$ by $$$(-p_i, q_i)$$$ and $$$(p_i, -q_i)$$$ correspondingly.
- Delete or cut the last and first segments while they are out of the non-negative area.
Complexity $$$\mathcal{O}(nlog(n))$$$.
There is another simple $$$\mathcal{O}(n^2log(n))$$$ approach:
We can keep the area as a polygon. At each step, create two copies shifted by corresponding vectors. Build a convex hull of them. Cut this convex hull to be in the non-negative area.
It won't fit. Mentioned just for fun.
