Editorials

Problem: CHEFFB

Problem Description:

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.

Solution:

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[0] means 0, score[1] means A and score[2] 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][0], dp[N][1], dp[N][2]).

**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[2][0] = -1 ans dp[2][1] = -1. Now, whenever we encounter value -1, we will know that this is invalid, therefore, we will skip it, by using continue statement appropriately.

Problem: POSH

Problem Description:

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**

Detailed Solution:

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!!