11335 - Discrete Pursuit

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

11335 - Discrete Pursuit

Post by shakil » Sun Nov 04, 2007 3:34 am

Sorry.......
Last edited by shakil on Mon Nov 05, 2007 7:36 pm, edited 1 time in total.
SHAKIL

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Nov 04, 2007 3:52 am

Read the problem carefully. At time t=0, the only possible position of cop is (0,0) and velocity is (0,0). At time t=1, the possible velocity of the cop is (u,v) where -1<=u,v<=1 and the possible position is (x,y)=(0,0)+(u,v) where -1<=x,y<=1. For this problem it is sufficient to only know the maximum bounds on x,y,u,v.
Let x[t]=maximum bound of x at time t, then
x[t]=x[t-1]+t

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

need sample i/o

Post by deena sultana » Sun Nov 04, 2007 5:58 pm

Can anyone give some sample i/o for 11335, plzzz? i am getting WA
:cry:

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: need sample i/o

Post by sclo » Mon Nov 05, 2007 12:48 am

deena sultana wrote:Can anyone give some sample i/o for 11335, plzzz? i am getting WA
:cry:
It might give the problem away if I give any more input/output. You could easily write a bruteforce bfs program to check your results.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: need sample i/o

Post by sohel » Mon Nov 05, 2007 12:27 pm

deena sultana wrote:Can anyone give some sample i/o for 11335, plzzz? i am getting WA
:cry:
and also it would be more helpful if you describe your algorithm first!!

Hint: consider x and y component separately.

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

Post by deena sultana » Mon Nov 05, 2007 12:58 pm

well, my algorithm is like this...
1. for t=0, the object's position is (0,0) and u=0, v=0 and the thief's position is (a,0), as the problem states.
2. then for t=1 the object will move at the position from where the distance of the thief's current position (at t=1) is minimum;
3. repeat this process until the distance is 0.

wont it work?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Nov 05, 2007 1:04 pm

ds wrote:the object will move at the position from where the distance of the thief's current position (at t=1) is minimum
By distance, do you mean the Manhattan distance or the Euclidean distance?

And don't you take the current speed in consideration?
What if you have two places with the same minimum distance, which point do you consider then?

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

Post by deena sultana » Mon Nov 05, 2007 1:19 pm

ops sorry for my incomplete description :P
i've calculated the Manhattan distance, and also considered the current speed. but, in case of tie i 've chosen the 1st one :-S (may be this is the fault, no?)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Nov 05, 2007 9:38 pm

deena sultana wrote:ops sorry for my incomplete description :P
i've calculated the Manhattan distance, and also considered the current speed. but, in case of tie i 've chosen the 1st one :-S (may be this is the fault, no?)
Your algorithm is wrong. In any optimal solution, the direction of the cop doesn't change much. But in your algorithm, the cop can change direction.

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

Post by deena sultana » Tue Nov 06, 2007 12:01 pm

yes, i understand :(
it was a stupid algorithm :roll:
sorry :(

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

Post by deena sultana » Tue Nov 06, 2007 5:12 pm

Hint: consider x and y component separately.
Wow! this hint is simply great! who r trying to solve 11335, plz think about it and have a pretty solution :-)
thanks to sohel. thanks to sclo too.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Wed Jan 16, 2008 9:12 pm

Is this problem solvable using Dynamic Programming? :oops:
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Thu Jan 17, 2008 4:15 am

I don't think DP is suitable for this problem.

-----
Rio

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

Re: 11335 - Discrete Pursuit

Post by slxst » Fri Sep 05, 2008 8:12 pm

I honestly don't know where to begin to attack this problem but it seems that this problem is really easy.

Could anyone give me a little hints about where to start?

By the way: I don't know what the other posters are meaning about x component and y component.

Thanks a lot.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11335 - Discrete Pursuit

Post by andmej » Sun Sep 07, 2008 2:04 am

Imagine you had to solve a simpler problem: The thief and the cop can only move along one axis. In that case, how would you calculate the minimum time needed for the cop to catch the thief in only that direction?

For example, imagine that the cop can't move along the y-axis (he can only move along the x-axis) and same for the thief. If thief is at position (0, a) and cop is at position (0, 0), how would the cop move to catch him?

Now, imagine the opposite thing along the y-axis (that is, neither the cop nor the thief can move along the x-axis), and compute the time.

The final answer will be the maximum of these two values, because the cop can advance in both directions simultaneously and he can "work" on the two solutions at the same time.

Hope this helps. If I'm not clear enough please tell me so I can explain better.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Post Reply

Return to “Volume 113 (11300-11399)”