Folks, any ideas on how to approach the following questions:

Q1. Given coins and minCoins both of size n < 10^5 and k < 10^5. coins[i] represents the cost of crossing the i-th toll and is subtracted from the number of coins you have after crossing the toll. If after crossing the i-th toll, you have atleast minCoins[i] remaining you get a star. Return an array of size n where arr[i] represents the number of stars which can be collected if you start to cross tolls from the i-th toll with k initial coins. Note that it is possible to have enough coins to continue even with remaining coins < minCoins[i] at a particular toll i. Ex: coins = [5, 7, 2, 1], minCoins = [4, 3, 2, 2], k = 10, ans = [1, 1, 2, 1]

I think a sliding window/two pointers on the coins array might work here but not 100% sure.

Q2. Given n < 10^5 numbers and k < 10^9, can the numbers be sorted just by swapping two number a[i], a[j] such that abs(a[i]-a[j]) <= k any number of times? Return boolean true/false. Ex: arr = [6, 5, 1, 2], k = 2, ans = false, arr = [2, 1, 6, 5], k = 2, ans = true For this problem, I think a set needs to be created starting from index i till the rightmost j possible. Then the set needs to be sorted in place. This process can be repeated till the end of the array and then it can be checked if the array is sorted. The set can be created by binary searching arr[i]-k or arr[i]+k in the existing set to see if arr[i] can be inserted into the set. If not, then this is the end of the current set.

Is there a better way to do this?

Q3. Given a graph with n < 10^5 nodes and m < 2*10^5 edges. Both nodes and edges have values. The pleasant value of a path in graph is the sum of node values minus the sum of edge values on that path. Return the maximum pleasant value of a path of length 4 starting from any node. All nodes and edges visited in a path must be unique. Ex: G = [[1, 2], [2, 3], [3, 4], [4, 5]], has paths 1-2-3-4 and 2-3-4-5

Any ideas for this?

I am trying to solve this question:

There are n nodes in a tree numbered 1 to n. Each node has a value v. There are two players A and B. A and B take turns choosing nodes of the tree with A starting first. Each player can only choose a node which is directly connected to one of the node they have already chosen. A and B are assigned different nodes initially and then they start choosing nodes. The game continues until no player can choose a node. If any player is unable to choose a node, they skip their turn.

There are q queries where each query gives x and y which are the initial nodes assigned to A and B. For each query, what is the maximum value A and B can collect by choosing nodes as described above given both play optimally?

Given n,q < 10^5

This is what I have come with so far: For each query, consider only the shortest path between x and y. Both A and B are going to move towards each other on this path. Eventually they will meet in the middle on this path. Consider the edge between A and B. Then the maximum number of points A can collect is sum of all the nodes to the left of the edge and B can collect the sum of all the nodes to the right of the edge.

But this solution is O(q*n). Can this be solved in a more optimal way or is there any other approach for this?

I was solving this question: http://codeforces.net/contest/479/problem/B

The output specification states that: "Note that in the process of performing operations the heights of some towers can become equal to zero."

Consider the second test case:

3 4

2 2 4

We can arrive at a better solution than the one given by doing the following operations:

1 2

1 2

Now the towers are: 4 4 with instability 0 (as tower 1 no longer exists). But the answer states minimum as 1.

Can somebody please help me understand what I am misunderstanding here?

EDIT: So I understood that I should not have assumed that a tower with no blocks will not exist. I am now interested in this variant:

Suppose a tower with no blocks ceases to exist. How would one solve this problem now? I tried but could not come on with a working solution. Example: There are 3 towers initially: 2 5 7. Suppose we can only move two blocks. Then we can achieve zero instability. Any help is appreciated.