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 :)

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.
at

16 comments:

  1. Unknown26 October, 2009 22:35

    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.

    ReplyDelete
  2. Petr Mitrichev27 October, 2009 08:10

    The 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.

    ReplyDelete
  3. Anonymous27 October, 2009 11:44

    We 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.

    so 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

    ReplyDelete
  4. Anonymous28 October, 2009 00:31

    You can trim some of the search knowing the that the farthest points (using only x,y coordinates) are on one of cubes diagonal.

    ReplyDelete
  5. Kletos28 October, 2009 04:17

    can you send me the file with the test data please?

    ReplyDelete
  6. Petr Mitrichev28 October, 2009 09:28

    2Anonymous: yeah, that seems like the correct approach. The devil is probably in the implementation :)

    For 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
  7. Anonymous09 November, 2009 13:30

    Здравствуй Пётр.
    Тебя беспокоит земляк из Москвы... Хотел бы поздравить Тебя за мировое лидерство! Keep it cool!
    А также очень хотел бы, чтобы Ты дал небольшой совет.
    Как окажется свободное время, напиши Мне пожалуйста на почту: letter69bunk <@> hotmail . com
    Буду очень признателен, если Ты напишешь ответ!
    Спасибо!
    С Уважением,
    - Дмитрий.

    ReplyDelete
  8. Anonymous10 November, 2009 08:25

    Здравствуй Пётр ещё раз...
    Это опять Дмитрий беспокоит, Я совершенно забыл написать, что совет касается freelance'а...
    И совет Твой очень очень важен для Нас...

    ReplyDelete
  9. Petr Mitrichev10 November, 2009 09:38

    2Дмитрий:
    I'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.

    ReplyDelete
  10. Unknown26 November, 2009 05:05

    Well Petr, I didnt knew where to ask this. So I asked it here.
    Why 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.

    ReplyDelete
  11. Anonymous18 January, 2010 17:40

    Hi Petr,

    We 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

    ReplyDelete
  12. Petr Mitrichev18 January, 2010 18:26

    Never participated in IMO. Biggest success was getting to the Russian MO.

    I don't think I could solve IMO problems in the given time back in high school, not sure about now.

    ReplyDelete
  13. Andy26 January, 2010 23:40

    please Petr can you upload testsets(input and output) from Sao Paolo Training Camp, thank you.

    ReplyDelete
  14. Prabh29 January, 2010 07:08

    petr how come you dont participate in GCJ while you are still active on topcoder

    ReplyDelete
  15. Anonymous31 January, 2010 10:36

    Developing ideas of Anonymous2 we obtain the answer:
    test 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.
    Мехмат, пожалуй, неплохое место.

    ReplyDelete
  16. Alex Z.10 May, 2013 11:36

     How about this: 

    Let 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... 

    ReplyDelete