11116 - Babel Towers

[rammestain]

does this problem have any critical input?
I got a lot WA for it.

[arsalan_mousavian]

EDIT : i got AC
use EPS=0.000001 for double comparison , i did this and got AC

[lost]

I'm also repeatedly getting WA, and since this seems to be very simple problem, I'm starting to suspect that i missed something ;p

Basic math assumptions that i made:
1) coordinates for center of mass for multiple objects are independent of each other (ie, Xcm does not depend on Y coordinates of objects)
2) resulting center of mass for several objects is: Xcm= sum(Xi*Mi)/sum(Mi) , where Xi is X coordinate of i-th object, and Mi is that objects mass
3) same goes for Ycm, and Zcm is not even needed here
4) Xi*Mi is in 1E10 range, sum(Xi*Mi) is in 1E13 range
5) mass of each block 'equals' square of radius R (3rd param in input line)
6) check if center of mass (Xcm,Ycm) lies on block (Xi,Yi,Ri) is: if (sqr(Xcm-Xi)+sqr(Ycm-Yi)>= sqr(Ri)-EPS then 'unfeasible'

Basic assumptions about problem:
1) when each new k-th block is added, we need to check if every substack (i) starting from top has center of mass that lies on top of block (i-1) under it
2) So if we add k=4th block, we need to check if 4 lies on 3, if 3+4 lies on 2, if 2+3+4 lies on 1 etc


With above asumptions i made fairly simple program that keeps getting WA. After that i made 3 versions of solution, original one that used real extended type, and two integer ones, one that used int64 for sums and BigInt for square/radius check, and other who use BigInt for all calculations.

Since I'm still getting WA, I wonder if some of my assumptions are wrong, or if there is some special input case that i'm not covering

[navid_a2b]

can anyone help me ? why i'm getting WA ?

Code: Select all

code removed

[elif]

Try the following testcase:
2
0 0 10
9 9 10

Shoud output:
Unfeasible 1

[navid_a2b]

center of mass of block 1 is ( x=9 , y=9 ) which is on the surface of
block 0 , Could you tell me why is it unfeasible ?

[stubbscroll]

The point (9,9) is not inside a circle of radius 10, which means the top block's centre of mass does not rest on the bottom block.

[navid_a2b]

Thanks elif and stubbscroll !
I got AC

[andmej]

Hello. My algorithm is as following:

Code: Select all

for every block i starting from the second block do
    for every block j strictly under block i do
      if euclidean distance between center of block i and center of block j is greater than or equal to radius of block j then
        print Unfeasable i

if not unfeasable then
    print Feasable

I'm getting wrong answer. What's wrong with this algorithm?

Is this output correct?
Input

Code: Select all

57
10000 10000 3
9999 10000 5
9998 10000 7
9997 10000 9
9996 10000 11
9995 10000 13
9994 10000 15
0

Output (This output is wrong)

Code: Select all

Unfeasible 3

Edit: Corrected the input, as Jan said.

Thanks.

[Jan]

Your case is wrong. However, try the case...

Input:

Code: Select all

5
10000 10000 3
9999 10000 5
9998 10000 7
9997 10000 9
9996 10000 11
0

Output:

Code: Select all

Unfeasible 4

Hope it helps.

[andmej]

Hello Jan. Thanks for your answer.

Can you clarify me why is the correct output 4?

Here's my reasoning:

(I only consider x,y coordinates)

Block 0 is placed in the ground at point (10000, 10000).

Block 1 is placed over block 0 at point (9999, 10000), 1 unit away from block 0's center.

Block 2 is placed over block 1 at point (9998, 10000), 2 units away from block 0's center and 1 unit away from block 1's center.

Block 3 is placed over block 2 at point (9997, 10000), but it is exactly 3 units away from block 0's center, which makes the tower unstable and "Unfeasible 3".

What's wrong with this approach?

Thanks a lot!

[Jan]

I don't understand how did you take your decision. I am describing the basic theory...

If some objects(say y1, y2, ..., yn) are placed over another object (say X) then the center of masses of y1, y2, ..., yn must be inside the body of X. Otherwise the objects (y1, y2, ..., yn) will fall.

Now if we generalize the theory a bit..

Say y1, y2, y3, ..., yn are placed. Now if we want to place ym (m=n+1), then the following decisions can be made..

1) The center of mass of ym must be inside of yn.
2) The center of masses of ym, yn must be inside of y(n-1).
3) The center of masses of ym, yn, y(n-1) must be inside of y(n-2).
...
n) The center of masses of ym, yn, ..., y2 must be inside of y1.

This way we can find whether a design is feasible. Hope it helps.

[andmej]

Thanks Jan.

My algorithm was wrong, I was not considering the center of mass of all the discs above a given disc but only the disc immediately on it.

Thanks to your clarification I could get accepted after some wrong answer due to a precision error. I used const double EPS = 10E-9 for the comparisons and it worked.

Any way, here's some extra input/output:

Input

Code: Select all

3
0 10 5
0 6 10
0 16 5
8
10000 -10000 5
9999 -10000 7
9998 -10000 9
9997 -10000 11
9996 -10000 13
9995 -10000 15
9994 -10000 17
0 0 100
4
10 10 5
8 7 6
9 8 10
0 8 7
0

Output:

Code: Select all

Unfeasible 2
Unfeasible 7
Feasible

Thanks Jan!