Hello Guys, I’m back with another set of editorials in hope you would like them.
I had performed badly in February Cook Off and wasn’t in a good mood, that’s the reason of no editorials for Cook Off this time.
Without wasting much time, Here are the editorials.
Given the heights of hills and U and D (and one parachute too), determine how far we can move, if we cannot climb more than U units in a single jump, nor fall more than D units (unless using a parachute).
Simplest solution is to simulate the whole process.
- If next hill has height same as current hill, Just jump.
- If next hill has height greater than current hill height+U, terminate, else jump.
- If next hill has height smaller than current hill, but is within D units, jump.
- If next hill has height smaller than current hill-D, jump using parachute if available, else terminate.
That’s all guys. Just keep updating index and print the answer.
Link to my
. #[Game with numbers] #### Difficulty:Easy-Medium ### Problem: We are to simulate the game between Chef and his brother, game is as follows. Staring with a number of cards A[i] occuring D[i] times, chef and his brother takes turns to remove B[i] cards. Aim of Chef is to maximize sum of remaining cards while that of his brother is to minimize sum. We have to answer final sum after K turns. ### Solution: Firstly,Sort all tuple(Ai, Di) with on basis of Ai. Now, we need to determine, **given a set of cards**, which cards will be **removed by chef** and which cards will be **removed by his brother**. To maximize sum of remaining cards, Chef will remove cards with minimum value, while his brother, to minimize sum of remaining cards, will remove cards with maximum value. This way, we can even handle chef's turns and his brother's turns separately. Suppose **Chef** denote number of cards Chef removes, while **Bro** denote number of cards that chef's brother remove. The answer to this problem is **Sum of all cards - sum of Chef smallest cards - Sum of Bro largest cards**. **Proof**: Chef will remove smallest cards available while brother will remove largest cards only. This way, turn of one doesn't affect the choice of other. We can simply remove **Chef** cards from front and **Bro** cards from the end. Here's a simple [implementation]. This problem can also be a good problem for understanding [two pointers technique]. I have solved this using two pointers technique too, which can be referred [here]. #[Prefix Borders] (Only 40 points solution) #### Difficulty: Easy-medium ### Problem Given a String, we need to answer queries of the form p, k. Consider prefix of length p of given string, find length of kth smallest border of this prefix. Border here is defined as the string which is both prefix and suffix of a string. ### Solution; Since this is a simple solution for 40 points solution only, Constraints for this editorials are $N \le 100$ and editorial will be very short and too the point. Define ArrayList[N+1] for string border lengths of ith prefix. **For every prefix 1 to p, Find all the border of this prefix, push it into adj[p] the length of border found.** This part can be done using brute force in $O(N^3)$ as $N<=100$. After adding all the borders, sort all the ArrayLists. Now we can answer queries in O(1) time. If pth prefix doesn't have k borders, print -1, else print adj[p][k-1]. So simple to get 40 points. Here's the link to my
Hope you all like my editorials.
As always i ask you all, to feel free to ask questions, share your approach for all problems.