Code Jam for women - 2018 - ex1

In acest exercitiu de codejam este vorba despre un emoji de forma unui burger, care contine ingrediente distincte aranjate pe straturi. Pentru fiecare ingredient, exista doua metrici: prima este distanta pana la cea mai apropiata jumatate de chifla, iar a doua este o distanta optima, aflata in urma "unor testari". Ambele metrici sunt date de intrare (Di - distanta optima, xi - distanta unui ingredient aflat intr-o anumita ordine), precum si K (numarul de ingrediente).

"Eroarea" se defineste ca fiind the sum of the squared differences between each ingredient's optimal and actual distance-to-bun values. Eroarea optima corespunde unei anumite asezari a ingredientelor astfel incat suma patratelor diferentei intre cele doua metrici sa fie minima. Se cere deci sa se afle eroarea minima.

Ex.

Avem ingredientele A, B, C, D, E cu distanta optima {0, 2, 1, 1, 2}, care este eroarea minima?

Raspuns:
Distantele optime reprezinta o ordonare a ingredientelor numita "optima".  In functie de cum le asezam, de sus in jos, ingredientele respective vor avea distantele pana la chifla de 0, 1, 2, 1, 0 pasi. 

Eroarea optima = min ( sum (Di - xi) ^ 2 ) , pt i = 1, K

Se desfasoara aceasta suma, se despart termenii constanti (sumele patratelor) si ramane de maximizat produsul Di*xi, care e maxim daca Di si xi sunt sortate descrescator.
Eroarea optima = 10 + 6 - 2 * (2*2 + 2*1 + 1*1 + 1*0 + 0*0) = 2

0=C/D
1=nu e A
2=B/E
1=nu e A
0=A

Una din ordini ar putea fi: D, C, B, E, A.
D => D[3] * 0 = 1 * 0
C => D[2] * 1 = 1 * 1
B => D[1] * 2 = 2 * 2
E => D[4] * 1 = 2 * 1
A => D[0] * 0 = 0 * 0

--------

def squaredSum_di(Di):

    total = 0

    for di in Di:

        total += pow(di,2)

        

    return total

    

def squaredSum_xi(K):

    total = 0

    theRange = K//2

    if K % 2 == 1:

        total += pow((K-1)/2,2)

    

    for j in range(theRange):

        total += 2 * pow(j,2)

    return total

def getXi(K):

    result = []

    for i in range(K//2):

        result.append(i)

    if K%2 == 1:

        result.append((K-1)//2)

    for i in range(K//2-1, -1, -1):

        result.append(i)

    

    return result

def find_minimum(K, Di):

    xi = getXi(K)

    myMin = squaredSum_di(Di) + squaredSum_xi(K)

    maxSumOfProducts = 0

    Di.sort(reverse = True)

    xi.sort(reverse = True)

    myMin = myMin - 2 * sum([Di[i]*xi[i] for i in range(len(Di))])

    return int(myMin)

outputFile = open("ex1.out", 'w')

with open("A-large-practice.in", "r") as myFile:

    T = eval(myFile.readline())

    for i in range(T):

        K = eval(myFile.readline())

        Di = [eval(k) for k in myFile.readline().split(' ')]

        line = "Case #" + str(i+1) + ": "

        the_min = find_minimum(K, Di)

        line = line + str(the_min) + "\n"

        outputFile.write(line)

myFile.close()

outputFile.close()