Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### Hoyda's blog

By Hoyda, history, 12 months ago, ,

There is an array A of N numbers and some number K(you will be given N and K. N<1000,sqrt(N)<=K<=N). You can only query for K indices( indices are a subset of {0,1...N-1} ) and you will get them in sorted order.

What is the best strategy for sorting this array in minimum number of queries?

•
• +11
•

 » 12 months ago, # | ← Rev. 7 →   0 Up, maybe someone wants to solve it.One example: (Computer) - 6(N) 3(K) - 2 1 0 - 3 4 5 - 3 2 4 - 1 5 0 - 2 4 1 (Player) - 0 1 2 - 3 4 5 - 2 3 4 - 1 0 5 - 1 4 2- 3 2 4 1 5 0(Player finds answer)
•  » » 12 months ago, # ^ |   0 Maybe you should give some necessary details, like:"What is the best strategy for sorting this array" so I suppose we're getting an array in the input and we need to sort it?What happens when we pick indicies? does it sort them? do we just get them in sorted order?
•  » » » 12 months ago, # ^ |   0 We dont know values of the array. We only know its size and we can query for some subset's ordering of size K. When we are sure about complete odering we need to print its indices in sorted order and exit. When we pick indices we get them in sorted oder.