Codejam for Women - 2018 - ex3

A treia problemă propusă de acest Codejam: Centrists

Trei politicieni candidează pentru niște alegeri. Numele/poreclele lor sunt distincte, dar au aceeași lungime.
Ei sunt preocupați de ordinea în care intră la vorbitor - ei știu că mereu vor intra dupa o ordine alfabetică necunoscută.
Văzând că cel care intră nici primul nici ultimul are mai mult succes, candidații sunt preocupați să existe cel puțin un alfabet prin care numele lor va ajunge la mijlocul listei.
Astfel, dându-se numele lor, se cere să se afle cine va fi întotdeauna dezavantajat - candidatul al cărui nume este imposibil să fie așezat la jumătatea listei, conform oricărui alfabet.
// Alfabetul reprezintă o ordonare a tuturor literelor care apar în numele candidaților

-----

Idee:
Pentru 3 candidați vor exista întotdeauna 6 ordini posibile în care pot fi așezați.
Pentru fiecare ordine, se extrag reguli de precedență ale literelor în alfabet, conform așezării numelor lor. Dacă una din reguli este inversul alteia deja salvate, înseamnă că acea ordine nu este posibilă și cel care se află la mijloc în acea ordonare (imposibilă) este un candidat dezavantajat.

Ex.
Nume: BCB, CAB, CBC
Pentru ordonarea [CAB, BCB, CBC] regulile extrase sunt C>B (C înaintea lui B), apoi B>C care contrazice regula anterioară. Deci BCB nu se poate afla la mijloc, conform niciunui alfabet.

-----

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

def isRuleAccepted(rules, char1, char2):
    if str(char2+char1) in rules:
        return False
    return True


def addRule(rules, char1, char2):
    # char1 comes before char2
    if str(char1+char2) not in rules and char1 != char2:
        rules.append(str(char1+char2))


def findIfPossible(L, names, rules): 
    if L == 0:
        return True

    if len(names) == 3 and names[0][0] == names[1][0] and names[1][0] == names[2][0]:
        if L > 0:
            return findIfPossible(L-1, [x[1:] for x in names], rules)
        else:
            # all names are equal
            return True

    if isRuleAccepted(rules, names[0][0], names[1][0]):
        addRule(rules, names[0][0], names[1][0])
    else:
        return False

    if len(names) == 3:
        if isRuleAccepted(rules, names[1][0], names[2][0]):
            addRule(rules, names[1][0], names[2][0])
        else:
            return False
 
    if names[0][0] == names[1][0]:
        return findIfPossible(L-1, [names[0][1:], names[1][1:]], rules)
 
    if len(names) == 3 and names[1][0] == names[2][0]:
        return findIfPossible(L-1, [names[1][1:], names[2][1:]], rules)

    return True


def solve(L, names):

    result = ["YES", "YES", "YES"]
    orderings = [[0,1,2], [0,2,1], [1,2,0], [1,0,2], [2,1,0], [2,0,1]]

    for order in orderings:
        rules = []  # list of "ab" where a is before b in the alphabet
        newNamesOrdering = [names[order[0]], names[order[1]], names[order[2]]]
        if not findIfPossible(L, newNamesOrdering, rules):
            result[order[1]] = "NO"

    return result[0] + " " + result[1] + " " + result[2]


with open("C-large-practice.in", "r") as myFile:
    T = eval(myFile.readline()) 
    for case in range(T):

        L = eval(myFile.readline())
        names = [k.replace("\n","") for k in myFile.readline().split(' ')]

        line = "Case #" + str(case+1) + ": " + solve(L, names) + "\n"
        #print(line)
        outputFile.write(line)

myFile.close()
outputFile.close()

Codejam for Women - 2018 - ex2

Mi-am stors creierii la propriu cu problema asta.. pe care am rezolvat-o în trei feluri până când a trecut și testele pe seturile largi...

CEO search

Într-o companie există angajați structurați pe mai multe niveluri în funcție de experiență. Fiecare angajat trebuie să aibă un șef direct, iar șeful trebuie să îndeplinească două condiții:
- să aibă experiența mai mare decât a subordinatului său
- să aibă cel mult E subordonați, unde E = experiența șefului

În această companie cu mulți angajați dar neasignați încă unor șefi, se caută să se angajeze (din exterior) un CEO - care va avea experiența cea mai mare și îi va avea ca subordonați direcți și indirecți pe toți din companie. Ce experiență minimă trebuie să aibă noul CEO?

---- (exemple la link) ----

Varianta 1: Am făcut o clasă/câte un obiect ca să salvez pentru fiecare angajat experiența și o listă de subordonați. Mi s-a părut cam greoaie abordarea așa că am simplificat-o...

------------------------

Varianta 2: Două liste care rețin experiența fiecărui angajat respectiv șeful lui. Soluția merge pentru seturi mici de date, dar când vine vorba de milioane de angajați, surpriză!!!

------------------------

Varianta 3: Să tratăm angajații ca pe niște cifre. Nu ne interesează cine șeful cui e, ci strict ce experiență minimă va trebui să aibă CEO-ul. Pun datele de intrare într-o matrice:

M = ( e1 n1
          e2 n2
          .....
          ep np )

Observ că (ei * ni) reprezintă câți angajați de rang mai mic pot fi luați „sub aripa” angajaților de pe nivelul i, și mă plimb pe rangurile inferioare în căutarea lor.
CEO-ul va avea ca experiență fie numărul total de angajați fără șef, fie experiența angajaților cu rangul cel mai înalt + 1, în funcție de care e mai mare.

Soluția mai jos:

# Idea: treat employees as numbers
M = []

def solve_optimal():
 
    p = len(M)
    for i in range(1, p):
        cota = M[i][0] * M[i][1]
        for j in range (i-1, -1, -1):
            if M[j][1] > 0 and cota > 0:
                if cota > M[j][1]:
                    decrease = M[j][1]
                else:
                    decrease = cota # consume all the available
                M[j][1] -= decrease
                cota -= decrease

    # find the CEO's experience
    ceo = 0
    for i in range(0, p):
       ceo += M[i][1]
    if M[p-1][0] + 1 > ceo: # check max experience
        ceo = M[p-1][0] + 1

    return ceo


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


with open("B-large-practice.in", "r") as myFile:
    T = eval(myFile.readline()) 
    for case in range(T):

        L = eval(myFile.readline())
        M = []

        for i in range(L):
            Ei = [eval(k) for k in myFile.readline().split(' ')]
            line = [Ei[1], Ei[0]]
            M.append(line)

        line = "Case #" + str(case+1) + ": " + str(solve_optimal()) + "\n"
        outputFile.write(line)

myFile.close()
outputFile.close()


------------------------

Postez și soluția mai puțin optimă :(


experiences = []
bosses = []

def acceptsEmployee(boss, employee):
    nrSubordinates = len([x for x in bosses if x == boss])
    return nrSubordinates < experiences[boss] and experiences[employee] < experiences[boss]

def takeEmployee(boss, employee):
    bosses[employee] = boss

def getEmployeesWithNoBoss():
    employees = []
    for i in range(len(bosses)):
        if bosses[i] == -1:
            employees.append(experiences[i])
    return employees


# This works fine for the small dataset
def solve():
    for emp in range(len(experiences)):
        hooked = False
        for boss in range(emp+1, len(experiences)):
            if acceptsEmployee(boss, emp) and not hooked:
                takeEmployee(boss, emp)
                hooked = True

    subordinatesCEO = getEmployeesWithNoBoss()
    return max(len(subordinatesCEO), max(subordinatesCEO) + 1)


outputFile = open("ex2-suboptimal.out", 'w')

with open("B-small-practice.in", "r") as myFile:
    T = eval(myFile.readline()) 
    for case in range(T):
     
        print(case)
        experiences = []
        bosses = []

        L = eval(myFile.readline())

        for i in range(L):
            Ei = [eval(k) for k in myFile.readline().split(' ')]
            for j in range(Ei[0]):
                experiences.append(Ei[1])
                bosses.append(-1)

        line = "Case #" + str(case+1) + ": " + str(solve()) + "\n"
        outputFile.write(line)

myFile.close()
outputFile.close()

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()

L.A.E. demo

Tool-ul la care lucrăm deocamdată (nume de cod L.A.E.)

Nu pot să dau mai multe detalii