0
\$\begingroup\$

Problem Statement:

A DOTA game has N heroes, each with a distinct rank from [1..N]. In DOTA every formation is characterized as a permutation [1...N] of ranks of players. A formation is Imba when the sum of ranks of every two consecutive players is less than or equal to (N+1). Given N, you are to print the lexicographically smallest permutation of ranks [1...N] that makes the formation Imba.

Input Format

The first line will contain an integer T, i.e. the number of the test cases followed by T lines, each containing the value of N.

Constraints

  • \$1 \le T \le 5\$
  • \$2 \le N \le 105\$

Output Format

\$T\$ lines each containing the permutation; the numbers in each line should be seperated by a single space.

Sample Input

2
2
3

Sample Output

1 2
2 1 3

Explanation

In the first case there are two possible permutations [1,2] and [2,1]. Both of the given permutations satisfy the given constraints and [1,2] is lexicographically smaller than [2,1]. In the second case, the two possible permutations are [2,1,3] and [3,1,2], of which the former is lexicographically smaller.

Is there a more efficient way to go about doing this?

from itertools import permutations
def check_condition(perm,checksum):
    for i in range(len(perm)-1):
        if perm[i] + perm[i+1] <= checksum:
            continue
        else:
            return False
    return True
testcases = int(raw_input())
current = 1
while current <= testcases:
    max_ = int(raw_input())
    checksum = max_ + 1
    list_ = range(1,max_+1)
    for perm in permutations(list_):
        #print(perm)
        if check_condition(perm,checksum):
            print(" ".join(map(str,perm)))
            break
    current += 1
\$\endgroup\$
4
\$\begingroup\$

If you print out the solutions for the first couple of numbers, a pattern becomes obvious:

def print_first_imba(max_):
    """
    >>> print_first_imba(2)
    1 2
    >>> print_first_imba(3)
    2 1 3
    >>> print_first_imba(4)
    2 3 1 4
    >>> print_first_imba(5)
    3 2 4 1 5
    >>> print_first_imba(6)
    3 4 2 5 1 6
    >>> print_first_imba(7)
    4 3 5 2 6 1 7
    """

The pattern looks like:

  • given an input sequence 1, 2, 3, ..., n, and an empty output list
  • pop the last number from the sequence and prepend to the output
  • pop the first number from the sequence and prepend to the output
  • keep popping until there are no elements left in the sequence

That will be substantially faster than searching the permutation space.

The doc tests I wrote above should help a lot in implementing this alternative algorithm. Your current implementation passes these tests btw, if you reorganize your code to fit it into this method:

checksum = max_ + 1
list_ = range(1, max_ + 1)
for perm in permutations(list_):
    if check_condition(perm, checksum):
        print(" ".join(map(str, perm)))
        break

My alternative implementation also passes these tests:

from collections import deque

imba = deque()
highest = max_
lowest = 1
while lowest <= highest:
    imba.appendleft(highest)
    highest -= 1
    if lowest < highest:
        imba.appendleft(lowest)
        lowest += 1
print(" ".join(map(str, imba)))

In case you don't know, you can run doc tests with python -m doctest yourfile.py.

I also recommend to go a bit further and separate printing from the main logic, by renaming this method to get_first_imba and make it return perm instead of printing it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.