Hoyda's blog

Problem: Interactive Sorting
By Hoyda, history, 7 years ago, In English

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?

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

»
7 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

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)

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

    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?

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

      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.

      → Reply