SPOJ.com - Problem PROG0588

PROG0588 - Proizvolovs identity

List the first $2n$ positive integers, with $n \in \mathbb{N}_0$.

1, 2, 3, 4, 5, 6, 7, 8

Split these numbers arbitrarily into two groups of $n$ numbers, with half of the number going into the first group and the other half in the second group.

7, 1, 6, 4
2, 8, 5, 3

Arrange the numbers in the first group in ascending order, and the numbers in the second group in descending order.

1, 4, 6, 7
8, 5, 3, 2

Now if you compute the sum of the absolute values of the difference between each pair of numbers at corresponding positions in both groups, the sum will always equal $n^2$. $$|1 - 8| + |4 - 5| + |6 - 3| + |7 - 2| = 7 + 1 + 3 + 5 = 16 = n^2$$ This identity was proven by Vyacheslav Proizvolov.

Assignment

In this assignment we represent a group of numbers as a tuple of integers. Your task:

Write a function split that takes an even integer $n \in \mathbb{N}_0$. In case the number does not meet the conditions, the function must raise an AssertionError with the message invalid length. In addition, the function has an optional second parameter different that may take a Boolean value (default value: True). The function must return a tuple that contains two groups of $\frac{n}{2}$ integers from the interval $[1, n]$. In case the value True is passed to the parameter different, the function must also make sure that all numbers across both groups are different.
Write a function add that takes two groups of numbers. In case both groups do not have the same length, the function must raise an AssertionError with the message groups must have equal length. Otherwose, the function must return the sum of the absolute values of the difference between each pair of numbers at corresponding positions in both groups, after the numbers in the first group have been arranged in ascending order, and those in the second group in descending order.

Example

>>> split(8)
((7, 1, 6, 4), (2, 8, 5, 3))
>>> split(8, different=False)
((4, 4, 7, 3), (7, 1, 2, 3))
>>> split(3)
Traceback (most recent call last):
AssertionError: invalid length
>>> split(-3, different=True)
Traceback (most recent call last):
AssertionError: invalid length

>>> add((7, 1, 6, 4), (2, 8, 5, 3))
16
>>> add((4, 4, 7, 3), (7, 1, 2, 3))
13
>>> add((8, 3, 15), (27, 24, 5, 42))
Traceback (most recent call last):
AssertionError: groups must have equal length

Maak een reeks van de eerste $2n$ positieve natuurlijke getallen, waarbij $n \in \mathbb{N}_0$.

1, 2, 3, 4, 5, 6, 7, 8

Splits deze getallen willekeurig over twee groepen van $n$ getallen, waarbij de helft van de getallen in de eerste groep gaat en de andere helft in de tweede groep.

7, 1, 6, 4
2, 8, 5, 3

Rangschik de getallen van de eerste groep in oplopende volgorde, en de getallen van de tweede groep in dalende volgorde.

1, 4, 6, 7
8, 5, 3, 2

Als je nu de som berekent van de absolute waarden van het verschil van elk paar getallen op corresponderende posities in de twee groepen, dan is die som altijd gelijk aan $n^2$. $$|1 - 8| + |4 - 5| + |6 - 3| + |7 - 2| = 7 + 1 + 3 + 5 = 16 = n^2$$ Deze gelijkheid werd aangetoond door Vyacheslav Proizvolov.

Opgave

In deze opgave stellen we een groep getallen voor als een tuple van integers. Gevraagd wordt:

Schrijf een functie splitsen waaraan een even getal $n \in \mathbb{N}_0$ moet doorgegeven worden. Indien het getal niet aan deze voorwaarden voldoet, dan moet de functie een AssertionError opwerpen met de boodschap ongeldige lengte. De functie heeft ook nog een tweede optionele parameter verschillend waaraan een Booleaanse waarde kan doorgegeven worden (standaardwaarde: True). De functie moet een tuple teruggeven dat twee groepen van $\frac{n}{2}$ natuurlijke getallen uit het interval $[1, n]$ bevat. Indien aan de parameter verschillend de waarde True wordt doorgegeven, dan moet bovendien gelden dat alle getallen uit de twee groepen verschillend zijn.
Schrijf een functie optellen waaraan twee groepen getallen moeten doorgegeven worden. Indien deze twee groepen niet evenveel getallen bevatten, dan moet de functie een AssertionError opwerpen met de boodschap groepen moeten even lang zijn. Anders moet de functie som van de absolute waarden van het verschil van elk paar getallen op corresponderende posities in de twee groepen teruggeven, nadat de getallen van de eerste groep in oplopende volgorde en die van de tweede groep in dalende volgorde gerangschikt zijn.

Voorbeeld

>>> splitsen(8)
((7, 1, 6, 4), (2, 8, 5, 3))
>>> splitsen(8, verschillend=False)
((4, 4, 7, 3), (7, 1, 2, 3))
>>> splitsen(3)
Traceback (most recent call last):
AssertionError: ongeldige lengte
>>> splitsen(-3, verschillend=True)
Traceback (most recent call last):
AssertionError: ongeldige lengte

>>> optellen((7, 1, 6, 4), (2, 8, 5, 3))
16
>>> optellen((4, 4, 7, 3), (7, 1, 2, 3))
13
>>> optellen((8, 3, 15), (27, 24, 5, 42))
Traceback (most recent call last):
AssertionError: groepen moeten even lang zijn

Submit solution!

Added by:	Peter Dawyndt
Date:	2015-11-08
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC