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