Just Make Sure Your Computer Doesn't Crash

Let $P_i$ be the popularity index of player $i.$ The desired quantity is $\displaystyle \sum_{i \neq j} P_i P_j,$ which is also equal to $\dfrac{\left( \displaystyle \sum_{i=1}^{10000} P_i \right) ^2 - \displaystyle \sum_{i=1}^{10000} P_i^2}{2}.$ We write the following code to print this.

f = open('input.txt', 'r') #open the file
S1= 0 #variable to store the sum of the popularity indices
S2= 0 #variable to store the sum of the squares of the popularity        indices
for line in f:
  S1 += int(line) #increment S1 by the number written in the line 
  S2 += int(line)**2 #increment S2 by the square of the number written in the line
tickets= (S1**2 - S2)/2 #find the total number of tickets sold
print tickets #print

Suppose we already have the number of tickets for three players $n=ab + ac + bc$ . For a new player, we add $ad + bd + cd = (a+b+c)·d$ .

Doing the same for each new player, we add a number of ticket that equals the sum of previous values multiplied by the new value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

indexes = [48,85,40, ... ,21,3,22]

tickets = 0 
partialSum = indexes[0]

for i in xrange(1, len(indexes)):
        tickets += indexes[i] * partialSum
        partialSum += indexes[i]

print tickets

x=open("C:\Users\MASBA\Dropbox\P-index.txt","r")

k=0

a=[]

for i in x:

a.append(i)

s=0

for p in range(len(a)-1):

for q in range(p+1,len(a)):

    s=s+int(a[p])*int(a[q])

print s

This reads the data and calculates the value directly

a=[]
ticks=0
f = open('tournament.txt', 'r')
for i in f:
    a.append(int(i))
print(len(a))
for i in range(len(a)):
    for j in range(i+1,len(a)):
        pop = (a[i]*a[j])
        ticks+= pop
        ticks = ticks % 1000
print(ticks)

My Pascal solution, I think it's O(n) solution

var
    i : integer;
    A : array[1..10000] of integer;
    sum : longint;
    sticket : longint;
begin
    sum := 0;
    for i := 1 to 10000 do begin
        readln(A[i]);
        sum := sum + A[i];
    end;
    sticket := 0;
    for i := 1 to 9999 do begin
        sum := sum - A[i];
        sticket := sticket + (sum mod 1000) * A[i];
        if (sticket >= 1000) then sticket := sticket mod 1000;
    end;
    writeln(sticket);
end.

It gave result 441.

My simple Python solution:

import operator

summation = 0; tickets = 0
for line in open('input.txt'):
    tickets += int(line)*summation
    summation += int(line)
print (operator.mod(tickets, 1000))

I used a simple Python coding. Just the simple logic of:

{ \sum { i=1 }^{ 9999 }{ \left( { a } { i }\sum { j=i+1 }^{ 10000 }{ { a } { j } } \right) } ]

where $a_n$ is the popularity index.

from sys import argv

script, filename = argv

txt = open(filename)

s = []

for i in range(10000):

s.append(int(txt.readline()))

sum = 0

for j in range(9999):

for k in range(j+1,10000):

  sum += s[j]*s[k]

print j, sum

Python bruteforce + string slicing (or mod by 1000)

1
2
3
4
5
6
7
8
9

data = []
with open('tournament.txt') as fp:
    for line in fp:
        data.append(int(line))
s = '0'
for num, i in enumerate(data):
    for j in data[num+1:]:
        s = str(int(s) +int(str(i*j)[-3::1]))[-3::1]
print s

Though it's bruteforce, here rejecting the other digits and keeping the last 3 digit only saves complex computation.

Answer: 441

Here is another solution: First count the number of players with popularity pop in [1,...,100]. This groups the players into 100 popularity bins (I'll call them count below), which can be used to caluclate the number of tickets like this:

1
2
3
4
5

sum = 0;
for pop in [1,...,100]:
  sum += pop*pop * count[pop]*(count[pop]-1)/2;
  for pop2 in [pop+1,...,100]:
    sum += pop*pop2 * count[pop]*count[pop2];

Throw in a sum = sum % 1000 in the loop in case the number precision isn't sufficient.

First thing to notice is that we have a triangular sum. To avoid repeats of matches. The sum can be written as $\left(\sum^{10000}_{i=0}\sum^{10000}_{j=i+1}(P_i\times P_j\mod 1000)\right)\mod 1000$ using the distributive properties of $\mod{}$ .

Here is my C# code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

int[] popularities = new int[10000];
string[] popStrings = 
System.IO.File.ReadAllLines(@"!!_FileLocationCensored_!!");

for (int i = 0; i < 10000; i++)
{
    popularities[i] = int.Parse(popStrings[i]); ;
}

int numOfTickets = 0;

for (int i = 0; i < 10000; i++)
{
    for (int j = i + 1; j < 10000; j++)
    {
        numOfTickets += popularities[i] * popularities[j];
         numOfTickets %= 1000;
    }
}

Console.WriteLine(numOfTickets);
Console.ReadLine();

This runs pretty fast. (Under a second easily).

StreamReader sr = new StreamReader(@"....\indexes.txt"); long kq = 0; string cidx; List<int> idx = new List<int>(); for (int i = 0; i < 10000; i++) { cidx = sr.ReadLine(); idx.Add(Convert.ToInt32(cidx)); } for (int i = 0; i < 10000 - 1; i++) { for (int j = i + 1; j < 10000; j++) { kq += (idx[i] * idx[j]); } } kq = kq % 1000; $Result = \boxed{441}$