Barsic's blog

Please help to solve a problem Scales from IOI 2015.
By Barsic, history, 8 years ago, translation, In English

Hello dear readers. Tell please how to solve a problem Scales ( ENG RUS ). ( from IOI 2015 day 1 ).

Thank you very much.

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by Barsic (original revision, translated revision, compare)

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Did you read Problems and Solutions section at official website?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. I read analysis. And want to solve problem with such algorithm :

    1) make list of comparison ( first, second ) where we put pair ( first, second ) when we know that first < second.

    2) look all permutations of { 1, 2, 3, 4, 5, 6 } ( with next permutation() in C++ ).

    2.1) if current permutation does not satisfy to list of comparison then look next permutation.

    2.2) if current permutation are satisfy to list of comparison then in this permutation find pair P[i] and P[i + 1] which not situated in list of comparison, compare them and add the result to list of comparison.

    We continue this procedure untill permutations are not finished or we not compare more than 6 founded pairs ( P[i], P[i + 1]). At the end we found right permutation.

    In this problem T <= 18 and all permutation of { 1, 2, 3, 4, 5, 6 } = 6! = 720 then O(18 * 780) = O (12960).

    No more than 1 second. But I got TL. Here is my code. Can you say where my mistake or show another solution with realization?

    Thank you.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Hi, it seems to me, that your code runs into an infinite loop, for example when the output would be {1,2,3,4,5,6}, since at the start of the "while(1==1)" loop k==0, and you only increase k 5 times (in the inner loop after if(t==1), for i=0..4), so k will remain 5 throughout the execution, therefore you don't execute the break; command (if(k>6) break;). On the other hand since t always remains 1, you don't execute the other break; command either (if((t==0) && ...) break;), so you never jump out of the while loop.

      I hope, I am not missing anything. :)

      → Reply