Buying Fruits
Question Link: https://www.codechef.com/COTY2018/problems/CCSFRUIT
Since the question demands n ≤ 105, you have to use n log n or a better algorithm in order to pass test cases in expected time . Since Tom has limited money and he has to buy maximum fruits with that money, he will want to start buying fruits with lowest price and then move to buy fruits with higher prices.
Since price of each fruits is given , he can sort the pries using a sorting algorithm .
Eg ) suppose you have 8 rupees
toy prices are – 2, 3, 5, 8.
then you will start will 2 (8-2=6 left), then 3 (6-3=3 left) but after that you will not have enough money left to buy any more fruits.
So maximum fruits you can buy = 2
Cartesian Coordinate System
Question Link: https://www.codechef.com/COTY2018/problems/CTY1
The given condition fails if there is more than
one point on both sides of the y axis. We can detect
this by counting the number of points on each side
while getting the input.
The Legendry Coin Change Problem
Question Link: https://www.codechef.com/COTY2018/problems/CTY2
For the approach we are going to take to solve this problem, knowledge of concepts of recursion and dynamic programming are required.
We shall first declare a function solve(i, make). This is supposed to find out the number of ways to make make using coins from i to numCoins.
Our recursive function will work as follows:
We take coin i making the next call solve(i, make – c[i]).
Choose the next denomination coin by calling solve(i+1, make).
This way we have split our original problem into two sub problems. Our final answer will be the sum of the solution of these two sub problems.
Also note that if and when make becomes zero, our function returns 1 because only one way exists to make a change for 0 units, i.e. to not have any coins. (Similar to how zero factorial is one.)
Another important thing to note is that we must make sure not to have overlapping sub problems or else the solution will time out!
Save The Day
Question Link: https://www.codechef.com/COTY2018/problems/CTY3
The key observation of this problem is that this is a maximum bipartite matching problem.
The nodes in position will be destroyed; others nodes will be safe.
In the problem statement, we know, in each turn we can move each token at most once. During the turns each node may temporarily contain arbitrarily many tokens. At the very end, each node must again contain at most one token.
Manipulative Strings
Question Link: https://www.codechef.com/COTY2018/problems/CTY4
In this problem, we have a string where each letter appears exactly twice, and we want to remove the duplicate letters in such a way that the first letter is alphabatically smallest.
A native approach is to generate all possible ways of removing the duplicate letters and check which of those ways has the smallest beginning letter. But that’s not necessary.
Notice that, for our string, we’re only interested in the characters that can appear in beginning of the string. For a character to appear in the beginning of a string, it must appear before every other character and its duplicate both appear. For example:
abcddeeabc
When we consider the above string, a, b, c, and d can all be characters that appear at the beginning of the string after we remove duplicates. The reason that ‘e’ can’t be chosen is because ‘d’ shows up twice before ‘e’ does. That means no matter which ‘d’ is removed, it will appear before any ‘e’s can show up.
So now we know that to solve our problem, we just need to find which characters appear in the string before any other character has its duplicate show up. Then, we can choose the smallest character from that set as our answer.
To solve this problem, we’re going to make use of a frequency array. We create an array where each index represents a character. For example, index 0 represents ‘a’, index 1 represents ‘b’, and index 25 represents ‘z’. Inside of each of these indices will be a number that represents the number of times we see a particular character.
For this problem, we’ll look at each character in the string, from left to right, updating our frequency array as we go, and once we find a frequency of 2 for any character, we know that we can only choose a letter from the letters we’ve visited before. We then check our frequency array for the letters we’ve seen to find which letter was the smallest, and return that as our answer.
The time complexity for this solution is O(N) (specifically O(N/2 + 1) ), since at worst we have to check half of the letters in our string until we find the duplicate. The space complexity is O(1), since the only extra space we use is a frequency array to represent the count of 26 characters.
So, every node in position corresponds to some safe node. We can precalculate the matching graph, then find the maximum bipartite matching.