×

# pls help with this question

 0 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 104●8 accept rate: 10% please see the code below (07 Jan '17, 12:48) only44★

 2 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 answered 07 Jan '17, 14:10 371●2 accept rate: 23% thanks a lot.. (07 Jan '17, 14:24) Glad to know that. If you feel the question has been answered, then please the accept the answer :) (07 Jan '17, 14:59)
 0 I have provided a code in c. Feel free to ask if you have any problem in the following code. #include #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; imax) max = x; } while (min<=max) { if (a[min]==1) { min += k; count++; } else min++; } printf("%d", count); return 0;  } answered 07 Jan '17, 11:15 4★only4 1.5k●2●12 accept rate: 17%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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