The solution doesn't exist only if the mimimal way to bribe is grater than n. Otherwise we can increase the gift price to make price1 + price2 = n.
Let's find the miminal way to bribe. We should buy that gift for old lady which costs less. It means, if we have 2 guards with params a b c d, then minimum bribe price will be min(a, b) + min(c, d). Let's choose the guard with the minimal bribe price. If the minimal bribe price is greater than n, answer -1. Otherwise, the possible answer is, for example: Guard number, min(a, b), n–min(a, b).
Dima can make k–1 tasks, so Inna always tells him off for each k-th taks, beginning from the chosen place. So for the numbers with same modulo by k the answer will be the same. We should find the answer with minimal first task number so it is eniugh to calculate the sums of “tellings of” for tasks 0, 1... k–1. We can do it in such way: Determine the array int sum[k]. And put the number into appropriate bucket while reading:
sum[I mod k] + = a[i]. Now we should simply find first i with minimal sum[i].
Let's calculate dinamic: d[num][balance] where num – last looked fruit, balance — difference between sum of colories and sum of tastes. Let's multiply each b by k. The answer will be d[n].
d[num][balance] = maximal possible sum of tastes under conditions.
Step: from d[num][balance] we can relax answers:
d[num + 1][balance] = max(d[num + 1][balance], d[num][balance]) – if we don't choose a fruit
d[num + 1][balance + a[i] - b[i]·k] = max(d[num + 1][balance + a[i] - b[i]·k], d[num][balance] + a[i]) – if we choose a fruit.
Balance can be negative, so in programming languages which don't support negative indexation, indexes should be shifted by the biggest negative number for balance. If we determine the balance as sum(b·k) - sum(a) it will be the sum of all tastes.
The answer for some path is a range under which we can go all the way, and this range is the intersection of all the ranges on the path. We can conclude it because the number is valid for path if it is valid for all ranges in the path. We will iterate all ribs. Let the left board of range on a rib is the left board of our intersection. It means we can't use ribs whith left board greater than ours. Lets iterate all right boards, determining the answer as the range from fixed left board to the chosen right. This answer exists if we have any path from the first node to the last. Let's check if the graph is connected if we leave only ribs with left board not greater than our and right board not less than our. If the graph is connected — let's update the answer. Right board can be found by binary search so the complexity is O(M2·logM).
There are many solutions for this task. I will describe my, you can deal with other by looking participants code. To find the answer we should calculate maxDis[k][k], where maxDis[i][j] – maximal complexity from note i to note j.
Now we should only iterate the song updating answer for each pair of adjacent notes. Let's think how we can calculate the matrix.
For each place (x1, y1) on the guitar let's iterate pairs (x2, y2) with y2 ≤ y1.
If (x2 ≤ x1) distance will be x1–x2 + y1–y2. So we should find minimal x2 + y2 in submatrix from (0, 0) to (x, y).
If (x2 ≥ x1) distance will be x2–x1 + y1–y2. So we should find maximal x2–y2 in submatrix from (n–1, 0) до (x, y).
We will calculate this values for each note. We need too much memory so we should memorize only one previous row for each note. For each place we will update dinamics for both variants according to already calculated and for our own note (which is in this cell) we will also compare (i + j) or (i–j) with current value in the cell.