We are playing basketball. There are two hoops. We have N turns. Our Aim is to maximize score, as per following rules.
- If we get through hoop 1, we get A points.
- If we get through hoop 2, we get B points.
- If we get through same hoop at ith turn as well as (i-1)th turn, we lose C points.
In such problems where we are required to calculate maximum score/minimum cost/maximum profit, and score at ith turn depends upon previous results (previously computed), We use dynamic programming.
Let us ignore K fixed actions initially.
In this problem, first of all we need to define DP state. Score at ith turn depend directly upon scores at (i-1)th turn.
DP state for this problem will be defined as mapping (count, last) => score.
This means that after making “count” turns, with “last” being the last action, we have best possible answer “ans”.
Now, we need to define a recurrence relation.
let score means 0, score means A and score means B.
dp[count][last] = j \in [0,2] max(dp[count-1][j] - ((j>0 && j==last )?C:0)) + score[l];
Above recurrence means, that, for every turn i, we calculate best answer for 3 states of each turn, (3 states being no basket at ith turn, 1st hoop at ith turn and 2nd hoop at ith turn.).
Condition (j == last) check if last turn was same as current turn and reduce score by C accordingly. Since state j means no basket, It does not reduce score by C, when there are consecutively, So j>0 is necessary.
For every state, we check all three states of previous turn, as stated in above relation.
Now, final answer will be max(dp[N], dp[N], dp[N]).
Now, What if K actions are pre-decided.
Now, we also need to take care that we do abide with pre-defined actions as given in input.
Suppose we are given 1 fixed turn, 2 2. For this, we will set (other two states of ith turn) dp = -1 ans dp = -1. Now, whenever we encounter value -1, we will know that this is invalid, therefore, we will skip it, by using continue statement appropriately.
We are given the map of a town with N regions and R uni-directional roads, first M regions having supermarkets. We are required to find all Posh regions, Posh regions being defined below:
- Posh region is that region which is an upmarket and all the regions from which this region can be reached are all upmarkets.
- Upmarket means a region, which either contain a shopping center, or it is possible to reach shopping center though given network of roads.
Quick Solution: First hint: Reverse all edges and try to reformulate this problem
First of all, we will reverse all the edges. i.e. Source becomes destination and destination becomes source. (U’ll understand why).
Now, Upmarket can be defined (in this new road map) as:
Regions having supermarket, or region reachable from a region having supermarket.
This reduces all the complication in finding out all upmarkets. All we need to do is a dfs on first M nodes, marking all nodes connected to current supermarket as upmarket.
So now, we have a list of upmarkets (preferably as a boolean array), we need to find posh areas.
In this new road map, we will define Posh regions as those regions which are not non-posh regions (because in this new structure, defining non-posh structure is a lot easier.)
Non-posh region is those region, which can be reached from a non-upmarket.
See!!, by reversing road directions, finding all posh regions became a lot easier.
Now, create a new boolean array posh and set all regions as posh, which were upmarkets.
Now, run dfs from each non-upmarket, and set posh[r] = false for every region r reachable from non-upmarket.
The remaining regions are posh regions.
Editorials for remaining problems will be posted soon.
That’s all. Cheers!!