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\$
9
  • 1
    \$\begingroup\$ This is not enough, but n**2 = n*n. \$\endgroup\$ Jul 7, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 11:51

2 Answers 2

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.

\$\endgroup\$
2
  • \$\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\$ Jul 8, 2020 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\$ Jul 8, 2020 at 11:48
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!

\$\endgroup\$
6
  • \$\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, 2020 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\$ Jul 7, 2020 at 10:46
  • \$\begingroup\$ Tank you. It's impossible to solve the problem without this sacred knowledge. \$\endgroup\$
    – Evgeny
    Jul 7, 2020 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\$ Jul 7, 2020 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\$ Jul 7, 2020 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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