Problem 1:
1) You need to buy exactly n pies where n is no. of days
2) You must have bought at least i pies after ith day
3) If you buy x pies on a day, you'll have to spend sum of cost of pies + x*x
Within a day, you can greedily pick the smallest pies.
Putting them into a DP of two states where DP[i][j] means optimal cost of buying j pies starting from day i will give an AC.
Complexity : O(days * days * days)
Problem 2:
We can move the points inside a random circle of any radius into the resultant square. (but each point gets translated by dx,dy)
The final answer is the number of points inside a square of given side length which we need to maximize.
One of the optimal ways is that the circle is chosen such that it is bigger than the resultant square.
Suppose if we have two squares of same side length, we can move all the points from one square to another square. We can always draw a circle outside one of these squares and move to other square and it'll not affect the result.
Two loops from 0 to n-1 to find a square from any two points.
Another two loops from 0 to n-1 to find a square from any two points.
Final loop to count the number of points inside these two squares.
This is an O(n^5) solution and is not optimal one. Feel free to comment optimal methods if any.
Problem 3
We need the shortest distance between any two nodes before we can proceed. This can be found using Floyd Warshall in O(n^3).
Lets assume we are currently at node currNode and the truck is loaded with L items and already delivered to D families.
This 3 variables currNode, L, D forms a state
DP[currNode][L][D] denotes the optimal way from currentNode when the truck is already loaded with L family items and D families are yet to be served.
When L = 0, we cannot deliver anything. i.e. we must load from next family.
When L = 2, we cannot load anything. i.e. we must deliver the first loaded family.
When L = 1, we can either deliver or load.
Overall complexity : O(n^3 + n * families)
