10064 - Traveling in another Dimension

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

Moderator: Board moderators

Post Reply
blue cat
New poster
Posts: 3
Joined: Tue Apr 09, 2002 6:03 am

10064 - Traveling in another Dimension

Post by blue cat » Tue Apr 09, 2002 6:21 am

I got WA for scores of times!If anyone who got accepted,can you tell me how to do it by emailing me.My email is "flyingbluecat@hotmail.com".

hburch
New poster
Posts: 3
Joined: Wed Apr 10, 2002 7:33 am

Re: P10064

Post by hburch » Wed Apr 10, 2002 7:39 am

I do not understand the problem statement for #10064. In particular, what is meant by "his voyage is continuous"? "Never stops anywhere" does not really make sense to me.

Of course, only 8 logins have submitted accepted solutions, so my hopes on hitting on someone is not high. :)

bester
New poster
Posts: 1
Joined: Fri Apr 23, 2004 10:09 am

10064-Help!!

Post by bester » Fri Apr 23, 2004 12:38 pm

Hi!!

I have some "problems" with this "problem" :wink: (Traveling in another dimension).

for this inputs what do you answer

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10064 travelling in another dimension

Post by little joey » Mon Sep 27, 2004 11:20 am

This problem is getting on my nerves.

For the first number I use the same routine as for problem 10647 for which I got AC.
For the second number I use an obvious formula.
I only print "-1" if Arnold has no friends.

I tried versions using ints, long longs and doubles (the input format is not specified to be ints only), but all got WA.

Can somebody give me a hint?

Input:

Code: Select all

6 0 47 84 55 -3 -33
6 5 -93 -47 72 34 -15
7 0 98 -73 -9 -18 -44 67
5 -94 -77 -59 82 -90
3 -21 61 29
10 -43 -38 -16 54 30 63 -42 -13 -85 80
1 -50
10 -29 -53 -50 62 -20 6 -21 -35 13 2
6 -56 12 66 23 -28 -5
3 -20 7 36
0
1 0
2 -10 10
3 -10 0 10
4 -30 -10 10 30
5 -20 -10 0 10 20
Output:

Code: Select all

23.50 25.00
-25.67 -7.33
19.14 3.00
-30.80 -47.60
12.33 23.00
4.20 -1.00
-50.00 -50.00
-11.20 -12.50
3.50 2.00
16.67 7.67
-1
0.00 0.00
0.00 0.00
-3.33 0.00
0.00 0.00
-4.00 0.00

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Sep 27, 2004 1:07 pm

The problem statement is very confusing indeed.

The first number should not be as in 10647, for when going from house i to house j, Arnold should not stop in houses between them. This seems to be how you interpreted the second column, but in this scenario, Arnold never stops at all - he just traces the route he would take but never stops at any friend.

I think the source of this confusion is the sentence "Another important thing here is that Arnold stops in every house. If he had not done that he would have required more energy." which is definitely a bit misleading.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Sep 27, 2004 2:02 pm

So what you are saying is:

The first number is the x for which E(x) is minimum, where E(x) = sigma_i(2 * (x_i - x)^2), which was my second number.

The second number is the x for which E(x) is minimum, where E(x) = (sigma_i(2 * abs(x_i - x))^2.

x is the location of Arnolds house, E(x) is the energy of a trip as a function of x, and x_i are the locations of his friends.

Well, I thought this four dimensional story was insane, but now I think the whole problem statement is insane... why is Arnold looping back and forth to all of his friends houses without ever stopping, as in the second case?

Thanks anyway. Got AC with the above.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Sep 27, 2004 4:13 pm

I think you can guess where I got the idea for problem 10647.
After I got WA with my understanding of problem 10064, I thought that would be another interesting problem.

jasiu--
New poster
Posts: 3
Joined: Tue May 31, 2005 8:49 pm

Post by jasiu-- » Sun Jun 05, 2005 11:11 pm

i am also trying to solve this problem and i guess i have misunderstood the specification. so i have few questions:

let's denote friends' locations as a_k, 1 <= k <= n. also, let's denote arnold's house coordinates as x. then we have:

total effort in the first case is:
2*(x-a_1)^2 + 2*(x-a_2)^2 + ... + 2*(x-a_n)^2
is that right?

total effort in the second case is:
( 2*|x-a_1| + 2*|x-a_2| + ... + 2*|x-a_n| )^2
is that also right?

i know how to calculate the x values to make these two formulas have their minimal values (or at least i think i know). but is that, what they want me to do?

one more question: when should i print -1? i print -1 only if n = 0. if n > 0, then first formula always have one minimal value, in the second formula there are infinitely many answers, if n is even. what should i do then?

am i at least a bit right or got it totally wrong? please, someone help me. regards,

jasiu

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Jun 06, 2005 7:53 am

You are totally right.
If there are more than one such places (in the first case or in the second case) print the smallest coordinate.
This should resolve the cases where n is even.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Sun Aug 27, 2006 7:14 pm

Just posting AC I/O for those who are still confused (as I was after reading above posts):
input

Code: Select all

6 0 47 84 55 -3 -33
6 5 -93 -47 72 34 -15
7 0 98 -73 -9 -18 -44 67
5 -94 -77 -59 82 -90
3 -21 61 29
10 -43 -38 -16 54 30 63 -42 -13 -85 80
1 -50
10 -29 -53 -50 62 -20 6 -21 -35 13 2
6 -56 12 66 23 -28 -5
3 -20 7 36
0
1 0
2 -10 10
3 -10 0 10
4 -30 -10 10 30
5 -20 -10 0 10 20 
output

Code: Select all

25.00 0.00
-7.33 -15.00
3.00 -9.00
-47.60 -77.00
23.00 29.00
-1.00 -16.00
-50.00 -50.00
-12.50 -21.00
2.00 -5.00
7.67 7.00
-1
0.00 0.00
0.00 -10.00
0.00 0.00
0.00 -10.00
0.00 0.00
PS: In my opinion, the problem is asking to guess what author was thinking when he wrote it. The worst problem description EVER!!!!

Post Reply

Return to “Volume 100 (10000-10099)”