1
\$\begingroup\$

Input: from STDIN number of vertices in Graph \$2 \leq N \leq 100\$.

Rules: [Code size] = max ([code length without spaces, tabs and newlines], [total code length divided by 4])

Math formulation: In the graph of N vertices, between each pair of vertices can be 3 road states:

  • there is no road
  • there is a road from A to B
  • there is a road from B to A

Find the number of different graphs on given vertices.

We can apply next formula (number of different road states in pow of pairs number): $$\huge3 ^ {\frac{n(n - 1)}{2}}$$.

My Python 3 37 bytes solution here:

n = int(input())
print(3 ** ((n ** 2 - n) // 2))

I know that exists 34 bytes solution. Then I started to think about 1 liner, and find next formula for sum of arithmetic progression, which use N only once: $$\frac{(2n - 1) ^ 2}{8} - \frac18$$

Unfortunately the code only increased:

x = 2 * int(input()) - 1
print(3 ** ((x ** 2 - 1) // 8))
\$\endgroup\$
  • 1
    \$\begingroup\$ This is not enough, but n**2 = n*n. \$\endgroup\$ – my pronoun is monicareinstate Jul 7 at 10:17
  • \$\begingroup\$ If someone knows how to make inline latex formula, pls edit my question. I don't know why it's not working here. \$\endgroup\$ – Evgeny Jul 7 at 10:18
  • \$\begingroup\$ @mypronounismonicareinstate I looked at this formula for 3 hours and did not see an elephant, thank you. \$\endgroup\$ – Evgeny Jul 7 at 10:21
  • 2
    \$\begingroup\$ Note that your 2nd formula can be turned into a 38-byte one-liner. But of course, that's still too long. \$\endgroup\$ – Arnauld Jul 7 at 10:50
  • 1
    \$\begingroup\$ @Arnauld I think you can remove the -1 too, but 36 bytes is still too long. \$\endgroup\$ – xnor Jul 7 at 11:51
4
\$\begingroup\$

Python 3, 34 bytes (not counting the newline)

Uses the conventional formula for the sum of the arithmetic progression (\$\frac{n(n-1)}2\$) and the trick that n-1 = ~-n (but with higher operator precedence). This way, one pair of parentheses can be omitted.

n=int(input())
print(3**(n*~-n//2))

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Is it possible to get real binary representation of -n? How many bits it use? Because for n = -6, bin(n) give me '-0b110'. I'm trying to understand how is it working. \$\endgroup\$ – Evgeny Jul 7 at 10:41
  • 1
    \$\begingroup\$ @Evgeny You may want to read the Wikipedia article on two's complement. Flipping all bits of n simply results in -n-1. (of course, that's what flipping all bits does in languages with machine-word-sized integers, but in many other languages ~ has the same behaviour) \$\endgroup\$ – my pronoun is monicareinstate Jul 7 at 10:46
  • \$\begingroup\$ Tank you. It's impossible to solve the problem without this sacred knowledge. \$\endgroup\$ – Evgeny Jul 7 at 10:51
  • \$\begingroup\$ @Evgeny Is Python 3 mandatory? Based on your question title I assume it is, but if not, this could be 2 bytes shorter in Python 2 (print a instead of print(a) and / instead of // which uses integer division implicitly on integers). \$\endgroup\$ – Kevin Cruijssen Jul 7 at 11:44
  • \$\begingroup\$ @KevinCruijssen int(...) is also not necessary. (if this is a problem from acmp.ru, like OP's previous question, then Python 3 seems to be mandatory) \$\endgroup\$ – my pronoun is monicareinstate Jul 7 at 11:48
12
\$\begingroup\$

Python 3, 34 bytes

print(3**sum(range(int(input()))))

Try it online!

In Python 2 this is just print 3**sum(range(input())) for 28.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Why does this answer have five times as many upvotes as mine? (I think they're mostly the same) Am I doing something wrong? (note: the question I am trying to ask is not "where are my upvotes" but "what am I doing wrong or what can I do better") \$\endgroup\$ – my pronoun is monicareinstate Jul 8 at 2:19
  • \$\begingroup\$ I posted this because it was a one-liner, which OP said they started thinking about. I'm not sure why it has so many more upvotes as I would not class this as a "better" code-golf solution (given the altered scoring mechanism), just an alternative one. You've certainly done nothing wrong. \$\endgroup\$ – Jonathan Allan Jul 8 at 11:48

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.