pls help with this question

general
,
1

here’s the question… it was asked in inoi 2010 http://www.iarcs.org.in/inoi/2010/inoi2010/inoi2010-qpaper.pdf

can somebody provide the algorithm to solve this question and if possible the code too.

PS: i did not understand malavika’s code on github

EDIT: I FORGOT TO MENTION THE QUESTION: QUESTION 2: TWIN ROBOTS

2

I have provided a code in c.

Feel free to ask if you have any problem in the following code.

#include <stdio.h>

#define inchar getchar_unlocked

inline int inPos() 
{
int n = 0;
register char ch = inchar();
while (ch < '0' || ch > '9') ch = inchar();
while (ch >= '0' && ch <= '9') 
{
	n = (n << 3) + (n << 1) + (ch - '0');
	ch = inchar();
}
return n;
}

int a[10000005];

int main()
{
    int n, k, x, min, max, i, count=0;
    n = inPos();
    k = inPos();
    min = 10000001;
    max = 0;
    for (i=0; i<n; i++)
    {
       x = inPos();
       a[x] = 1;
       if (x<min)
           min = x;
       if (x>max)
           max = x;
    }
    while (min<=max)
    {
       if (a[min]==1)
       {
          min += k;
          count++;
        }
       else
          min++;
     }
   printf("%d", count);
return 0;

}

3

please see the code below

4

Initially I had also struggled with this problem and you’re right that Malvika’s code is really complex for this problem.

Let me give you a big hint which just then boils down to the solution.

The key for this problem relies on the fact that if the position of R2D2 robot is a[i][j] then the position of the other robot C3PO is a[j][n-i-1] since whenever R2D2 takes a step to the right or down then C3PO has to take a step down or left respectively.

Here is the problem on CodeChef for you to practice : https://www.codechef.com/problems/TWINRO

Let me explain further. As usual, DP comes into the play.

Let DP[i][j] denote the maximum score that the two robots have achieved if R2D2’s position is i, j. From the above key I told you, now you also know the position of the other robot. Now you just take max(DP[i-1][j], DP[i][j-1]) for reaching the position i, j (as these are only positions from which R2D2 would have come to i, j) and add the current score of of the two robots. Then the final answer awaits for you at DP[n-1][n-1] since that is the final position of R2D2.

That key hint will take care of adding C3PO’s scores as well :wink:

Hope this helps. Here’s my code : https://www.codechef.com/viewsolution/12432523

1 Like
5

thanks a lot…

6

Glad to know that. If you feel the question has been answered, then please the accept the answer :slight_smile: