rahulkhairwar's blog

Help with Codenation contest questions
By rahulkhairwar, history, 8 years ago, In English

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.

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    long long ANS = 1LL;
int val=0;
for(int i=n;i>=1;i--){
     if(cnt[i] <= val){
         ANS = 0;
         break;
     }
     else{
         ANS *= (cnt[i]-val);
         ANS %= 1000000007;
         val++;
     }
}
return ANS;
    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply