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)
Full Editorial: https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-round-1-solutions/1599716033377625
Auto comment: topic has been updated by cegprakash (previous revision, new revision, compare).
Problem 2:
You can solve this in O(N^4) per case.
You know an optimal square's sides will be bounded by an existing point. So we check N^2 squares and form a long long bitmask of all included squares.
Then for each pair of squares we can OR the bitmasks giving N^4 total per case.
Wow this is a very good optimisation.. Thank you.
Do you have any simple editorial for problem 4?
Loose notes:
Say we have to put umbrellas in a fixed order. How many ways are there? We can see there are P(M — ((r1+r2) + (r2+r3) + ... + (r{n-1}+rn)), N+1) ways to do so, where P(N,K) is the number of ways to write x_1 + ... + x_k = N with integer x_i >= 0. Now P(N,K) = N-1 choose K-1.
Also, that expression simplifies to M — 2S + r1 + rn where S is the sum of r_i. So when we add up, for each ordering r1, r2,.., how many ways are there? There are n! ways, and each way on average is sum{ri != rj} F(ri,rj) / (n*(n-1)), where F is the expression we calculated above.
To get it fast, we'll need to compute modular inverse quickly. We may also need to precompute "X to K factors", ie. X*(X-1)*(X-2)*...(X-K+1) quickly using dp.
This solution is missing a corner case, that the cycle drawn around the first square could have touched a point in the final square before start moving, which will make this point out of the final square after moving !!!
I don't know how people missed that case ! that will make the problem the hardest in the contest!!
and if that was the answer, why the problem setter made the first shape is cycle and not a simple square ?!
Can you provide a test case that fails a solution that find two squares covering the most number of points in union?
after reading the editorial, it seems there is a theorem says that
"It can be shown that, given any such pair of squares, it’s always possible to construct a circle which will encompass some or all of the zombies in M, such that after the Move function-spell, all of the zombies initially within either of the squares will end up inside D. This is based on the idea that a very large circle, with its center very far away from the squares, can effectively be used as a line to divide the points as needed."
that was from the editorial !
so I think this case https://postimg.org/image/xan5potox/
will never happen
sorry! :D
Edit: This solution can actually be broken, as pointed out by Zlobober below. It does however pass the complete test set given in the editorial on Facebook. How unfortunate.
Problem two can be solved in O(n^3) per test case with a very simple algorithm. Instead of searching for two squares to destroy simultaneously, just search for one square with the greatest number of points, destroy it and then do it again, with the first set of destroyed points now removed.
Solution: http://ideone.com/3DHQdS
Wait, that is a wrong solution.
If you first choose the most profitable square, then you will surround the group in the middle, and after that you won't be able to deal with two points on a large distance.
Did this solution pass the system test?
Oh you're right! It did indeed pass all of the tests (the complete set, not just the subset given to me during the contest.) There have been quite a few reports of wrong solutions that the test data didn't catch for this problem, which is rather unfortunate.