Hello, everyone. I would like to invite you to the fifth contest of the ICO prep series.
**Problem Setters: ** Udit Sanghi
**Problem Tester: ** Soham Mukerjee
It will be held on 15th December from 8:00 pm to 11:00 pm IST. Link - Contest
The contest will be unrated. Hope you like the problems. There would be 4 problems and 3 hours to them.
Please ask your doubts below.
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.
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:
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!!
Problem: ZORG
Problem Description:
Given N D-dimensional points, find the pair with largest manhattan distance.
If two or more pairs have same largest manhattan distance, print the pair having points with least indices. Now, print points in sorted order.
That is… if selected pair has first x co-ordinate same and (x+1)th different, print first the point with smaller (x+1)th co-ordinate.
Solution:
Now, Distance between two points is given as abs(x1-x2)+abs(y1-y2) … D dimensions.
Abs(a-b) means a-b if a>=b and b-a if b>a.
So, we see that to find the correct manhatten distance between two points, we need to consider many cases.
Take example: Consider points (2,4) and (5,3).
Abs(a) can also be written as max(a, -a).
So, Manhattan distance between two points (x1,y1) and (x2,y2) can also be written as max(x1-x2+y1-y2, x1-x2-y1+y2, x2-x1+y1-y2, x2-x1+y2-y1)
For every dimension x, we need to consider two cases, (x1-x2 and x2-x1).
So, we will use bitmasking to consider every possible sign combination, of all dimensions.
For every mask, we will take ith dimension positive if ith bit is on. otherwise negative.
Now, run a loop for each point and calculate special value of this point with respect to this mask.
Special value here defined for sign combination can be illustrated using following example.
mask = 1001, point (4,2,3,5)
special value = 1*4 - 1*2 - 1*3+1*5
For calculating special value, take positive sign when bit is on and vice versa.
Now, find the points with minimum and maximum special value for current mask and compare it with current best found distance. If max-min > current_max, points = min_point, max_point.
Special case to be taken where max-min == current_max, selection of points is on basis of index of points.
Doing this for every mask will give us the pair with maximum manhattan distance.
Output them as explained above in Problem part.
Cheers!!