### Barsic's blog

By Barsic, history, 8 years ago, translation,

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

Thank you very much.

• +21

| Write comment?
 » 8 years ago, # |   0 Auto comment: topic has been translated by Barsic (original revision, translated revision, compare)
 » 8 years ago, # |   +6 Did you read Problems and Solutions section at official website?
•  » » 8 years ago, # ^ |   0 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.
•  » » » 8 years ago, # ^ |   +1 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. :)