I haven't read your code, but I guess I can provide a counter-test for your solution. Consider the following test 11 3 6 5. First you get GGGBGGG. After that, you insert remaining four G's in the beginning. But you can do that, because K equals to 3.

Let me attempt a proof at the solution for Problem D:

Let the predicate be that the greedy algorithm will find the solution iff it exists.

Now, how do we know if a solution exists in the first place?

Now, there are 2 cases:

1. Two teas are of same quantity.
2. Two teas are of different quantity.

For the first case, it is obvious that the solution exists since we can just take one at a time.

The second case is more tricky. Let us recognise that we need to find a mapping between blocks of tea A and blocks of tea B.

Let tea A be the tea of lesser quantity. Now, in every mapping, we must map at least 1 of A to at most k of B. Hence, |B| can be at most (|A|+1)*k since we can place combine pairs of k Bs and 1 A together. Now, we can place at most k Bs at the right of the last A.

Now that we know how to tell when a valid solution exists, we need to prove our original predicate.

Let's assume that the solution exists based on our above conditions (i.e. there is a valid quantity of B and, we can always find mapping from at least 1 of A to at most n (<=k) of B).

Case 1 is trivial as the greedy algorithm will pick one of each tea in alternating steps.

For case 2,

Let tea A be the tea of lesser quantity, and tea B be the tea of greater quantity.

For case 2, the algorithm will pick at most n (<=k) from tea B (n is maximised). Now, we will pick 1 from tea A since |B| >= |A| at all times. Hence, we have a block mapping from A to B. This choice will repeat until all of A and B have been used up. Note that the choice for A is minimal. Hence, even for a minimum quantity for A, the greedy algorithm will always find the solution.

Now we must prove in the other direction: if the greedy algorithm finds a solution, then the solution exists (is valid).

If the greedy solution finds a solution, then all of the A and B must have been used up since we run the algorithm while |A| > 0 and |B| > 0 and there exists a one to one mapping from each block of A to each block of B.

Hence, the greedy algorithm will find the solution iff it exists.

Do correct me if I am wrong.

Thanks a lot I got accepted now.

how did you gauge that time should only be integers, I planned to simulate but couldn't figure out way to deal with decimal timings

Понятие скорости просто разнится. Эти скорости в обычном понимании (единицы дистанции / время) будут выглядеть как и . Подразумевается, что эти величины сравниваются (т.е. условие верно при t₁ > t₂).

Woah! the checker isn't checking if the answer is minimum or not. This is highly surprising.

Let's say we have some pointers for odd number and even number. This pointer is used for which odd/even number we can use next.

First, check each number which has duplicate in original array. If the number has duplicate Change that number in this way : 1.) If the number is odd and the number of odd numbers is more than even numbers, then change that number with next possible even number 2.) If the number is odd and the number of odd numbers is less than or equal to even number, then change that number with next possible odd number (Vice versa if the number is even number)

Then, after change every duplicates, we can have a condition when number of even numbers is different than number of odd numbers. So for every "new array" elements, we check whether if it's odd or even. If it is odd and the number of odd numbers is more than the number of even numbers, we should change it with next possible even number (vice versa with even number in the "new array")

To calculate the number of cards exchange, simply we compare each element in our "newest array" (the one we have after the second "change") with the original array from input.

What case makes it impossible? For every case of changing cards, we check whether our current available odd/even number is more than M.

Idea: Use two pointers to keep track of the maximum amount of the tracks you can listen if you start from [left for left in range(n)] (find the corresponding right [left, right]).

Say if we have [left, right] already found, it is easy to maintain the sum of decentness while traversing the two pointers, the problem left is how to find the corresponding (right) for each (left). We will use greedy to minimise the listening time, that is to partially listen for the wth longest tracks.

In order to maintain the listening time in a decent time, we should use heaps to keep track of the tracks that are being partially listened and those who are not, and maintain the sum. We should also use two pointers for keeping track of the total listening time — manipulate the heaps and the sum of listening time whenever a track is included / excluded to the current segment.

My solution

I can, if u stiil need it. And give u even more: another cool solution. But my english is pretty bad :)

First, let's consider the min and max of the amount of "dead-ends".

Note that the amount of dead-ends on each layer is layer-independent — Having more "dead-ends" on the layer above or below doesn't affect the min nor the max of the "dead-ends" that could exist.

Minimum: As we try to avoid "dead-ends" being created, on each node on layer i (1 <= i <= k), we try to allocate at least one node from layer (i+1) as its' child. If layer (i+1) has greater or equal amount of nodes than layer i, then there will be no "dead-ends" as every node gets at least one child. If else, there will be a[i+1] -a[i] "dead-ends" created (where a[x] is the amount of nodes on layer x). The sum of this for each layer will be the min of total "dead-ends"

Maximum: As we try to create as many "dead-ends" as possible, we will allocate all the nodes on layer (i+1) as the child of one single node on layer i, layer i will have a[i] -1 "dead-ends" created. The sum of this for each layer will be the max of total "dead-ends".

Any amount out of this range is impossible to achieve, so we print -1 for those cases.

For any amount x where (min <= x < max), there exist a node u and v such that:

u -> subtree(u)

v -> subtree(v)

where u and v are on the same layer.

To increase the amount of "dead-ends" by one, we can redirect the edges in the following way:

u -> subtree(u), subtree(v)

v is a dead end now.

Therefore we could first construct the tree in the way that creates the least dead-ends, then gradually increase the amount of dead-ends by one until we reach the answer.

My code

So obviously when a == b, there exists an answer "GBGBGB...". To achieve this state, we will try to reduce abs(a-b). For example, if a > b, then we will first print "GGGGG...B", for each "B", we will print "A" for min(a-b, k) times. If we can reach a == b before b becomes negative, then we have found the answer. Otherwise, since we have tried the best scenario that spams the "G" the most, it is obvious that there does not exist a valid answer for the case.

Claim: min time igor reaches x2 is T=min(igor walk time, tram bypass igor and arrive at x2 time)

Proof: say that igor reaches x2 at time S (S < T). than this means that igor neither walks nor using tram. contradiction! so the claim is right.