You are not logged in. Please login at www.codechef.com to post your questions!

×

pls help with this question

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

asked 07 Jan '17, 11:00

shreyasnn1's gravatar image

2★shreyasnn1
1048
accept rate: 10%

edited 07 Jan '17, 11:36

please see the code below

(07 Jan '17, 12:48) only44★

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

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

link

answered 07 Jan '17, 14:10

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

thanks a lot..

(07 Jan '17, 14:24) shreyasnn12★

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

(07 Jan '17, 14:59) nikhil_chandak5★

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;

}

link

answered 07 Jan '17, 11:15

only4's gravatar image

4★only4
1.5k212
accept rate: 17%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×399
×181

question asked: 07 Jan '17, 11:00

question was seen: 738 times

last updated: 07 Jan '17, 14:59