25
\$\begingroup\$

Here's a fairly simple task from CSES Problem Set - Permutations 1070 that reads:

A permutation of integers 1,2, …, n is called beautiful if there are no adjacent elements whose difference is 1.

Given n, construct a beautiful permutation if such a permutation exist

The constraints are pretty tight:

  • Time limit: 1.00 s
  • Memory limit: 512 MB
  • 1 ≤ n ≤ 10^6

Here's the code:

n = int(input())
if n == 2 or n == 3:
    print("NO SOLUTION")
elif n == 1:
    print(1)
elif n == 4:
    print("3 1 4 2")
else:
    for i in range(1, n + 1, 2):
        print(str(i) + " ", end=" ")
    for i in range(2, n + 1, 2):
        print(str(i) + " ", end=" ")

It passes all tests except for n = 1000000. For that test it takes 15 sec. on my machine. The code is in Python 3.8

The question is, what can can be improved in terms of printing the numbers?

\$\endgroup\$
  • 2
    \$\begingroup\$ Doesn't this depend on the speed of the terminal? \$\endgroup\$ – Matt Nov 15 at 20:20
  • \$\begingroup\$ @Matt, it does. Just to add it is executed on CPython \$\endgroup\$ – Bor Nov 16 at 3:04
30
\$\begingroup\$

Nice solution, few suggestions:

  • Printing the numbers one by one might be the issue. Generate the list of numbers first and then call print only once.
  • The case n==1 is already handled, so the first elif can be removed.

Applying the suggestions:

n = int(input())
if n == 2 or n == 3:
    print("NO SOLUTION")
elif n == 4:
    print("3 1 4 2")
else:
    beautiful_perm = [*range(1, n + 1, 2), *range(2, n + 1, 2)]
    print(' '.join(map(str, beautiful_perm)))

By inverting the ranges we don't need to check for n==4:

n = int(input())
if n == 2 or n == 3:
    print("NO SOLUTION")
else:
    beautiful_perm = [*range(2, n + 1, 2), *range(1, n + 1, 2)]
    print(' '.join(map(str, beautiful_perm)))

Runtime on CSES:

n = 906819 (CPython3)
Original: 0.92 s
Improved: 0.26 s

n = 1000000 (CPython3)
Original: timeout
Improved: 0.28 s

n = 1000000 (PyPy3)
Original: 0.61 s
Improved: 0.15 s
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ print(' '.join(map(str, range(2, n + 1, 2))), ' '.join(map(str, range(1, n + 1, 2)))) is slightly more efficient. \$\endgroup\$ – GZ0 Nov 15 at 11:40
  • 4
    \$\begingroup\$ I'd even add that the fact they tell that the memory limit is 512Mb is a hint that you shouldn't print everything one by one. \$\endgroup\$ – Walfrat Nov 16 at 9:18
  • \$\begingroup\$ @Walfrat Maybe I'm missing something. How does a memory limit of 512MB prevent you from printing everything one by one? \$\endgroup\$ – Asher Nov 16 at 14:06
  • 7
    \$\begingroup\$ Nothing, but if instead it was 52Kb, you would have problem printing everything in one go. Since you have that much of memory, it is more likely that you are expected to build the full solution before printing it. \$\endgroup\$ – Walfrat Nov 16 at 14:51
  • \$\begingroup\$ If the solution on your machine goes down from 0.61 to 0.15, how do you expect OP going from 15.0 to 1.0? \$\endgroup\$ – Thomas Weller Nov 16 at 19:15
18
\$\begingroup\$

Your code gets accepted as-is. Just need to choose PyPy3 instead of CPython3.

Another version that also gets accepted with CPython3 (using Marc's logic but a simpler way to print):

n = int(input())
if 2 <= n <= 3:
    print("NO SOLUTION")
else:
    print(*range(2, n + 1, 2), *range(1, n + 1, 2))

Printing like that moves the loop from your own Python loop with lots of print calls to a single call and looping in C. Even faster is Marc's way with ' '.join, though. Times for test case #20, where n=906819, the largest where yours is fast enough to not get killed:

        CPython3  PyPy3
Yours   0.93 s    0.56 s
Mine    0.37 s    0.32 s
Marc's  0.25 s    0.14 s

Why is Marc's way even faster? The print documentation says "The file argument must be an object with a write(string) method". And if we use our own such object we can see a lot fewer write calls in Marc's than in mine:

class Write:
    def write(self, string):
        print(f'write({string!r})')

nums = range(5)

print(' '.join(map(str, nums)), file=Write())
print()
print(*nums, file=Write())

Output:

write('0 1 2 3 4')
write('\n')

write('0')
write(' ')
write('1')
write(' ')
write('2')
write(' ')
write('3')
write(' ')
write('4')
write('\n')

The overhead of all those function calls is probably what makes mine slower. The overhead of ' '.join(... just seems to be smaller.

That said, I usually prefer my way if it's fast enough and thus try that first. Except maybe in a competition where I have reason to believe it might not be fast enough and there's a penalty for unsuccessful submissions.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for the compact code. If I run it on CSES (PyPy3 n=100000), it runs in 0.34 s, two times slower than mine. Do you know why? Or is CSES not reliable? \$\endgroup\$ – Marc Nov 14 at 13:00
  • 2
    \$\begingroup\$ @Marc I'd say it actually runs about three times slower. The minimum times (for small n like n=1) are 0.05 s. If we subtract that overhead, it's 0.10 s for yours and 0.29 s for mine. To me CSES does look "reliable", in the sense that repeatedly submitting the same code repeatedly gives me the same times and that that overhead is relatively small (unlike for example LeetCode, where times for the same code vary widely and the overhead can be over 99% of the reported time). And from experience (with CPython) I expect my way to be slower, I just prefer it for simplicity when it's fast enough. \$\endgroup\$ – superb rain Nov 14 at 13:17
  • 2
    \$\begingroup\$ @Marc Btw with CPython3, the difference is smaller. Mine gets 0.02 s for n=1 and 0.44 s for n=1e6, so 0.42 s without overhead. For yours it's 0.02 s and 0.28 s, so 0.26 s without overhead. So yours is about factor 1.6 times faster there. \$\endgroup\$ – superb rain Nov 14 at 13:45
  • 1
    \$\begingroup\$ Thanks a lot for the explanation! It could have been a review on its own ;) \$\endgroup\$ – Marc Nov 14 at 14:06
  • 1
    \$\begingroup\$ @Marc Yeah you're right, especially since the question's title and last paragraph both explicitly make it about printing. Added stuff to my answer now. \$\endgroup\$ – superb rain Nov 14 at 14:59

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.