10064 - Traveling in another Dimension

[blue cat]

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]

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]

Hi!!

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

for this inputs what do you answer

[little joey]

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]

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.

[little joey]

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]

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--]

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

[little joey]

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]

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!!!!