You are given eight pairs of numbers, x1, y1, x2, y2, ..., x8, y8. You need to find eight numbers z1, z2, ..., z8 such that (x1,y1,z1), (x2,y2,z2), ..., (x8,y8,z8) are the coordinates of the vertices of a cube with an integer side length, or to report that such numbers do not exist.
Monday, October 26, 2009
A difficult problem ten years later
Here's another Russian IOI camp problem, this time one of the most difficult problems from the 1999 summer camp. Only one contestant was able to solve it back then. I wasn't. How does it look ten years later? I have testdata in case someone wants to actually write the solution :)
Subscribe to:
Post Comments (Atom)
Well, this is quite an interesting problem. If all coordinates are less than, say 10000, then it seems not difficult to solve. Petr, can you say whether coordinates are integer or not, and what are the constraints? Thanks.
ReplyDeleteThe coordinates are floating-point. There is no constraint on their size in the original problem statement, but the testdata seems to confirm they were intended to be between -200 and 200.
ReplyDeleteWe can fix edge's length, and three points on the same side. we can assume one of there points has z = 0, ten we can calculate others z coordinates. now we have 5 points on the plain and we must place them on the 5 determined places. this is bipartite matching.
ReplyDeleteso with naive implementation it's something like O(length*binomial(8,3)*3!*5!) which seems ok now, but 10 years ago it was probably too much
You can trim some of the search knowing the that the farthest points (using only x,y coordinates) are on one of cubes diagonal.
ReplyDeletecan you send me the file with the test data please?
ReplyDelete2Anonymous: yeah, that seems like the correct approach. The devil is probably in the implementation :)
ReplyDeleteFor example, you get two choices for z coordinates even when you fix the edge length.
2KLetos: http://77.41.63.3/blog/cube/tests.zip
Здравствуй Пётр.
ReplyDeleteТебя беспокоит земляк из Москвы... Хотел бы поздравить Тебя за мировое лидерство! Keep it cool!
А также очень хотел бы, чтобы Ты дал небольшой совет.
Как окажется свободное время, напиши Мне пожалуйста на почту: letter69bunk <@> hotmail . com
Буду очень признателен, если Ты напишешь ответ!
Спасибо!
С Уважением,
- Дмитрий.
Здравствуй Пётр ещё раз...
ReplyDeleteЭто опять Дмитрий беспокоит, Я совершенно забыл написать, что совет касается freelance'а...
И совет Твой очень очень важен для Нас...
2Дмитрий:
ReplyDeleteI'm sorry, but I don't think my advice would have any value as don't have any idea about freelance programming. Please consider asking on specialized forums instead.
Well Petr, I didnt knew where to ask this. So I asked it here.
ReplyDeleteWhy is it that we see you programming in Java nowdays compared to C# ?
Is it just your preference, or is it cause you work with Java more than C# in your real life.
Hi Petr,
ReplyDeleteWe all know that you are a very good programmer. What about your achievements in maths? Have you participated in IMO and won medals? What about your performance in Russian Math Olympiads? and can you solve IMO problems within the given time? Thanks
Never participated in IMO. Biggest success was getting to the Russian MO.
ReplyDeleteI don't think I could solve IMO problems in the given time back in high school, not sure about now.
please Petr can you upload testsets(input and output) from Sao Paolo Training Camp, thank you.
ReplyDeletepetr how come you dont participate in GCJ while you are still active on topcoder
ReplyDeleteDeveloping ideas of Anonymous2 we obtain the answer:
ReplyDeletetest 1 side = 2;
test 2 side = 10;
test 3 side = 10;
test 4 side = 10;
test 5 side = 100;
test 6 side = 10;
test 7 side = 10;
test 8 side = 10;
test 9 side = 100;
test 10 side = 100.5;
test 11 side = 98.66;
P.S. Solution is strictly mathematical.
Мехмат, пожалуй, неплохое место.
How about this:
ReplyDeleteLet P_i = (x_i, y_i, 0), and loop over triples P_i, P_j, P_k. We are going to check whether P_i, P_j, P_k can correspond to the three neighbors of P_0 on the cube. For each such triple, let A = P_i - P_0, B = P_j - P_0, C = P_k - P_0. Check to see if
P_0, P_0 + A, P_0 + B, P_0 + C, P_0 + A + B, P_0 + A + C, P_0 + B + C, P_0 + A + B + C
is the same set as the P_i. If not, then P_i, P_j, P_k can't be the neighbors. Otherwise, we are left to solve the following problem: given three points (ax, ay), (bx, by), and (cx, cy), determine whether there exist az, bz, cz such that the points (ax, ay, az), (bx, by, bz), (cx, cy, cz) are mutually orthogonal and of the same (integer) length. In fact the orthogonality condition when written in terms of dot products already determines az, bz, and cz almost uniquely, so there is a little bit of checking here, but it should be straightforward...