PROBLEM LINK:
Author-
Tester- Multiple
Editorialist- Abhishek Pandey
DIFFICULTY:
CAKEWALK
PRE-REQUISITES:
Array, Looping (and Prefix-Sum)
PROBLEM:
The question simply says that, there are N villages, with villages i and i+1 being adjacent. Each village has a toll both where you have to pay tax only once, or both times of going and coming back. Now, each village has some amount of coal which you can sell to gain profit. Your goal is to maximize the profit.
QUICK EXPLANATION:
Clearly, it makes no sense to collect profit from village i+1 without collecting profit from village i, since you will have to pay tax for both- to reach village i and i+1. Due to this property, we can claim that, if we want to collect profit from village i+1, then we must collect profit from all villages from 1,2....i as well, as we have to pay tax to reach all these villages from village 1.
Hence, we simply make an array profit and use prefix-sum technique, where profit[i] denotes profit earned by taking coal from village i.
(Note that- Since we compulsorily have to return to village 1, we can simply account for policy 2 by including tax twice. Refer to editorialist’s solution for details).
EXPLANATION:
The heart of the problem is dealt in Quick Explanation section itself.
Now, have a re-look at the question to observe the following-
- We can go from village 1 to village 2. From village 2 to village 3 (forward direction) or back to village 1 (backward direction).
- We cannot visit village i without visiting village i-1 for all i in range [2,N]
- Lets say village i is included in list of villages to visit to maximize profit. Since our goal is to maximize profit, and that we are already paying tax to reach village i-1 (else we cannot reach village i !!), it really makes no sense to ignore coal at village i-1. In other words, if you are paying tax to reach a village, it makes no sense to not collect profit from it.
From point 3, we can claim that-
If village ‘i’ is included in the list of villages to collect profit from, then all villages in range [1,i] (i.e. the villages coming before village ‘i’) are also included in the list
One direct impact of above claim is that, we can observe the prefix-sum nature of problem. With view of maximizing profit, if we decide to take profit from village i, then we also take profit from all villages from 1,2,3....(i-1).
Now, we make an array profit[n] , where profit[i] denotes profit gained by visiting till village i. (Recall that you need to visit and collect profit from all villages before i as well, hence “till i”.)
Its easy to visualize the exact formula/recurrence relation to calculate profit[i]. Let coal[i] denote “coal at village i” and policy[i] denote “policy at tollbooth to reach village i” and tax[i] denote **"tax to come at village i from village i-1). We can formulate profit[i] as-
profit[i]=profit[i-1]+ coal[i]-policy[i]*tax[i]
(Here we used the fact that, policy[i] is 2 if tax is to be paid twice- for going and returning- else 1. You can use alternatives, like if else statements, and deduct tax twice if policy[i] is 2 and likewise. All such solutions are acceptable.)
Now all we have to do is to find the maximum element in profit[n] and print the answer!
SOLUTION:
TimeComplexity=O(N)
SpaceComplexity=O(N)
CHEF VIJJU’S CORNER:
1.I think its fair to include a brief explanation of how we can visualize the recurrence formula. Lets say, we decide to go till village i in the list. This means all villages before i must be factored in as well. This is denoted by profit[i-1], i.e. profit obtained by visiting all villages upto village i-1. Now, all we need is how much profit is earned by coming to village i. Its simply, money obtained from coal - money lost on tax. Money obtained from coal is coal[i] , and I already mentioned various ways of deducting taxes (via if else, or by the recurrance relation I used).
2.Prefix sum is a extremely handy trick, especially useful to convert O(N) operations to O(1). One of the good/tougher problems purely on prefix sum is Total Diamonds. You will find the concept of prefix sum generously used in problems of codechef LONG challenges- although the exact use may not be this simple!