The other day someone asked a problem: where we are mining x amount of gold at the end of each day, and the collected gold can be used to buy some extra machines which in turn helps us dig more gold, the machines cost some amount of money each, but their production rate is same (= z). We want maximum gold at the end of the $$$K^{th}$$$ day This problem was pretty simple because the production rate was the same for all the machines.

My question is, if the production rate was different, then which machine would have been the optimal choice at the start of each day? This question can be reduced to the following: Consider an array: $$$a_1(K - i) - b_1, a_2(K - i) - b_2, \ldots, a_n(K - i) - b_n$$$, where $$$a_k$$$ is the production rate of the $$$k^{th}$$$ machine, $$$b_k$$$ is the cost of the $$$k^{th}$$$ machine, and $$$i$$$ is the $$$0-indexed$$$ day, changing which I want to observe the order of the elements. Here, each element of the array represent how much each machine will contribute to the total gold if it's bought at the start of the $$$i^{th}$$$ day. Now, slightly deviating from the original problem and ignoring that one machine can be bought only once, is there a way to find the maximum element for each $$$i$$$, from $$$0$$$ to $$$K - 1$$$ with $$$K \leq 10^5$$$?

I am new to graph theory and need some help. I have an undirected tree with a few coloured nodes. My task is to calculate the minimum distance from each node to any of the coloured nodes in $$$O(N)$$$. N is the number of nodes. The number of coloured nodes may be up to N.

My solution: Initialise an array of size N with infinity as the elements, this will represent my min distance array, say $$$A$$$. Change $$$A[i] = 0$$$, if $$$i$$$ is a coloured node. Run a dfs from each coloured node and each recursive call of the dfs ends if it either reaches a leaf or a node with $$$A[i]$$$ less than or equal to that of the parent. Store the distances on A along the way.

But I suspect that the complexity of this approach is $$$O(N^2)$$$, consider a tree with a root and many children, and let these children have many more single child each, and let the leaves be coloured, kind of like a flower. Since I don't know of a problem that is based on this, I cannot verify anything.

If anyone can prove if it's $$$O(N)$$$ or $$$O(N^2)$$$ then please help me. If it has bad complexity or downright wrong then please help me with a solution.

Another approach I though of was to simultaneously run a dfs from all the coloured nodes and end a recursive call of each node if it's reached a previously reached node, kind of like a radiation from the coloured nodes. But I don't even know if that's possible for me to implement.

help pls

This problem has been bugging me since morning today. I have a number K, and an array A with N elements. I can merge any amount of numbers in the array such that each element in the end is at least K. I want to merge minimum number of elements to achieve this, or in other words the final array should have maximum size.

Let's say $$$K = 6$$$ and $$$A = [4, 4, 5, 5, 6, 7, 9]$$$ (here size = $$$N = 7$$$) I have this proposed solution which I have not been able to prove/disprove with several random outputs.

The solution is: consider the subset of A containing all the elements which are less than K, which for this A is $$$A' = [4, 4, 5, 5]$$$, (size = $$$N' = 4$$$), my solution is:

For the given example, max length = 3 + min(2, 3) = 5, which corresponds to 9, 9, 6, 7, 9 after merging the 4s and 5s.

If anyone can help me give a counterexample or help me prove the solution, please do so.

How do I calculate the length of longest subarray ending at index $$$i$$$ $$$(1 \leq i \leq N)$$$ with elements smaller than or equal to $$$A[i]$$$ in an array A of length N for each $$$i$$$? $$$(1 \leq N \leq 10^6).$$$

I have tried a few different approaches with two pointers, tried using the merge sort algorithm to find the lesser than or equal to elements before each element but every approach I tried have obvious flaws.

Can anyone please help me with this? I would appreciate a solution without the use of data structures like segment trees or BIT and such, as I am yet to learn about these.