There was a contest by Codenation today (13th Nov, 2016) and there were 3 questions to be solved in 1.5 hours.
Q1) Given a string s, 2 players can remove a single character turn by turn where player 1 starts first. But the condition to remove is that each player can remove a character which is at an index >= the index which was removed previously, and the string gets re indexed after each turn. In the 1st turn player 1 can remove any character. If the final string is lexicographically greater than the original string s, player 1 wins, else player 2 wins. We had to tell who will be the winner.
Constraints :
number of tests cases <= 10
length of string <= 100
I couldn't come up with a complete logic during the contest. How can we solve this question?
Q3) We are given n points on a straight line : a0, a1, ...., a(n — 1) (a[i] > 0). Also, there is a starting point, s = 0, and an ending point t (> a[n]). Out of the n + 2 points, we have to choose K + 2 points such that the minimum distance between any 2 consecutive points from the chosen ones is maximum. Also, s and t are always chosen, so essentially we have to choose K out of the n points a[0....n — 1].
For this, I thought of a dp solution :
First I added 0(the starting point) at a0, and shifted the rest by 1 place. Then,
Let dp(i, j, k) = min. dist. b/w any 2 consecutive points by using up to the ith point, with jth point being the previous one, and choosing k points so far.
And the base condition will be that to choose exactly 1 point when i >= 1 and j >= 0, dp[i][j][1] = a[1]. I calculated this dp in iterative manner.
Then, I keep track of answer as :
ans = INFINITY;
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
ans = min(ans, dp[i][j][K]);Constraints :
1 <= n <= 600 1 <= k <= 100 1 <= t <= 11000 1 <= a[i] < t
But this could clear only 2 out of 3 sample cases. Can someone tell me what's wrong with this logic?
Thank You.
There was also a third question (or maybe we got different problem sets).
Q. You are given two integer arrays each of size n numbered from 1 to n. First array is compromise limit for Male(M) and the second array is compromise limit for Female(F). You need to form n pairs, where a person can only be part of one pair. Only rule is that the product of compromise limit for the male and female in the pair shouldn't exceed a given limit L. Find different number of ways in which the pairs can be formed.
Constrains:
1 <= n <= 100
1 <= M[i] <= 100
1 <= F[i] <= 100
1 <= L <= 10000
Kindly suggest a method to solve this. Also if possible, link the code as well. Thanks.
First of all there was a typo in the question they have written that the product should not exceed L but for the second sample case the answer was 2 which comes when you take the condition that the product is less than L not even equal to L.
This can be solved using sorting. First sort both the given array. Then you need to build a count array that will store the number of the values in female array that a particular value in male array can take such that product of both the values is less than L.
For Example:-
Sample Case Third
6 500
20 21 23 24 24 25
20 20 20 23 25 25
The count array for the above test case will be
4 4 3 3 3 0
Now start from right and take the answer as 1 initially.
For Q3, Binary Search with greedy should work.You can binary search over distance and choose the nearest point from the current point such that the distance is >= some d(parameter for binary search) and accommodate your 'hi' and 'lo' of binary search based on whether you are able to go from s to t (with distance parameter d) by using k or more points(if you were able to accommodate more than k points you can certainly accommodate k points).
For Third Question here is a link to a very similar problem. As brighterstill said it can be solved using Binary Search And Greedy.
Aggressive cows
Q1 You didn't tell us if a player has to remove a character if he can, or he can choose to not remove a character if he's reached an optimal string. So, first I'm assuming he can choose not to remove if he wishes.
Thus, A will remove an index such that the next two consecutive indices have higher value.
eg: xxxxcdea => xxxxea
In case he has to choose if he can, then we'll just make sure that the original string has at least 2 arrangements like I said above, or , if there's only one such arrangement, then there's at least one more character after the arrangement. This is because if a player has already reached the optimal string, but there's still possible characters to remove, he can remove the last character and end the game.
eg: xxxxcdeapqra , xxxxcdea lets player 1 win. xxxxcde lets player 2 win.