Problem: We have to split the number k into maximum number of elements of ai such that their sum is less than or equal to k.
Hint: To maximize the answer we have to split the number into the smallest numbers possible.
Solution: So and since the limits are small we can pick up the smallest element of the array and subtract it from k, and we keep doing this n times or until the smallest number is larger than k. Another solution is to sort the array in non-decreasing order and go on the same way.
Time complexity: or
Implementation: 9529124 .
Problem: We have a circle with radius R at position (x, y) and we want to move it to (x', y') with minimum moves possible. A move is to choose an arbitrary point on the border of the circle and rotate the circle around it with arbitrary angle.
Hint: What is the shortest path between two points? A direct line. So moving the center on that line with maximum move possible each time will guarantee minimal number of moves.
Solution: Let's draw a straight line between the two centers.
Clearly to move the center with maximum distance we need to rotate it around the intersection of the line and the circle with 180 degrees. So the maximum distance we can move the center each time is 2 * R. Let's continue moving the center with 2 * R distance each time until the two circles intersects. Now obviously we can make the center moves into its final position by rotating it around one of the intersection points of the two circles until it reaches the final destination.
Every time we make the circle moves 2 * R times except the last move it'll be ≤ 2 * R. Assume that the initial distance between the two points is d So the solution to the problem will be .
You have to be careful of precision errors. Here is a code that used only integer arithmetic operations 9529147.
Hint: Simulate the algorithm until we reach a leaf node assume that it's not the exit. Now the question is Are there some nodes that are guaranteed to be visited before trying to reach the exit again?
Solution: The first observation is that in order to return to a parent we will have to visit all nodes of the right or the left subtree of some node first. Now imagine we are in the situation below where E is the exit.
By applying the algorithm we'll reach node X. Both the E and X are in different subtrees of the root. Which means before going to the proper subtree in which the Exit exists we'll have to visit all the nodes of the left subtree (marked in red).
This means we have to get the node which the Exit and the current leaf node X are in different subtrees which will be the least common ancestor (LCA) of the two nodes. Assume the subtree height is h1. This means we visited node. By adding the nodes above the subtree which we visited during executing the string for the first time the total number of visited nodes will be . Now let's go to the other subtree. Obviously we don't need any other nodes except this subtree. So let's do the same we did to the original tree to this subtree. Execute the algorithm until we reach a leaf node, get the LCA, add to the solution where h2 is the height of the subtree of the LCA node where the leaf node exists. And so on we keep applying the rules until after executing the algorithm we will reach the exit.
Also we can do the same operations in O(h) by beginning to move from the root, if the exit is located to the left we go to the left and ans++ and then set the next command to 'R' else if it is located to the right we will visited the whole left subtree so we add the left subtree nodes to the answer and then set the next command to 'L' and so on.
Time complexity: or
Challenge: What if the pattern is given as an input (e.g. "LRRLLRRRLRLRLRR..."), How can this problem be solved?
Hint: Dynamic programming problem. To handle repetitions we have to construct the number from right to the left and calculate the answer when we reach a number equivalent to 0 modulo k.
Solution: Let's define as a recursive functions calculates the number of numbers consisting of n digits satisfying the conditions of the problem and with a specific suffix of length i Si such that .
We want to avoid repetition so by constructing the number from the right to the left when we reach a state with j = 0 with suffix ≠ 0 we return the answer immediately so any other suffix that contains this suffix won't b calculated.
So the base cases are , .
So state transitions will be (We add a digit to the left).
And we can handle j = 0 case coming from a zero suffix easily with a boolean variable we set to true when we use a digit ≠ 0 in constructing the number.
Hint: Consider we've chosen a certain path with length d where d is the length of the shortest path from 1 to n and it has x edges that are working. Assume that y is the total number of edges that are working in the whole country. So we need to make d - x changes (to make the malfunctioning edges on the path work) and y - x changes (to blow up all other edges that don't lie on the path). So we will totally make d + y - 2 * x changes where d and y are constants. So the optimal solution will depend only on number of working edges along the path. So we'll have to maximize this number!
Solution: We will use dynamic programming on all nodes that lies on some shortest path. In other words, every node x that satisfies that the shortest path from 1 to x + the shortest path from x to n equals d where d is the length of the shortest path from 1 to n. Let's define Max[x] is the maximum number of working edges along some shortest path from 1 to x. We can calculate the value Max[x] for all nodes by dynamic programming by traversing the nodes in order of increasing shortest path from node 1. So at the end we'll make d + y - 2 * Max[n] changes. We can get them easily by retrieving the chosen optimal path.