Problemi 091

Kërkesa

Sot keni një agjendë të ngjeshur, plot me gjëra të rëndësishme. Jeni lodhur goxha për tu pregatitur dhe për tu siguruar që veprimtaritë nuk kanë mbivendosje me njëra-tjetrën. Tani është mëngjes dhe po filloni të merakoseni se pavarësisht nga entuziazmi dhe dëshira e mirë, ndoshta nuk do të keni energji të mjaftueshme për ti bërë të gjitha me përkushtim të plotë.

Duhet ti përdorni energjitë tuaja me kujdes. Ditën e filloni plot me energji - E xhaul (joules) për të qenë më të saktë. Niveli juaj i energjisë asnjëherë nuk mund të bjerë më poshtë se 0 (përndryshe do të binit i pafuqishëm), dhe po ashtu nuk mund të rritet më shumë se E. Për secilën nga veprimtaritë mund të shpenzoni një sasi jo-negative energjie (ndoshta zero), dhe pas çdo veprimtarie do rifitoni R xhaul energji, por gjithmonë pa e kaluar nivelin maksimal të energjisë prej E xhaul (energjia e tepërt thjesht shkon dëm).

Disa prej veprimtarive janë më të rëndësishme se të tjerat. Për secilën veprimtari i keni një vlerë \(v_i\) që shpreh rëndësinë e kësaj veprimtarie për ju. Përfitimi që keni nga secila veprimtari është vlera e kësaj veprimtarie, shumëzuar me sasinë e energjisë që shpenzoni për të. Sa është përfitimi më i madh total që mund të keni?

Radha e veprimtarive në kalendar nuk mund të ndryshohet, duhet ta përdorni energjinë sa më mirë të jetë e mundur me atë kalendar që keni.

Referenca: https://code.google.com/codejam/contest/2418487/dashboard#s=p1&a=1

Shembull

$ cat input.txt
3
5 2 2
2 1
5 2 2
1 2
3 3 4
4 1 3 5

$ python3 prog.py < input.txt
Case #1: 12
Case #2: 12
Case #3: 39

Në rreshtin e parë kemi numrat E, R dhe N. Në rreshtin pasardhës kemi N vlerat \(v_i\) për secilën prej N veprimtarive, sipas radhës.

Në rastin e parë, mund ti shpenzojmë të 5-ta xhaulët për veprimtarinë e parë, pas asaj do rifitojmë 2 xhaul, të cilat mund ti shpenzojmë për veprimtarinë e dytë. Kështu që përfitimi do jetë 52 + 21 = 12.

Në rastin e dytë mund të shpenzojmë 2 xhaul për veprimtarinë e parë, i rifitojmë ato, dhe shpenzojmë 5 xhaul për veprimtarinë e dytë. Përfitimi: 21 + 52 = 12.

Në rastin e tretë, rifitimi i energjisë është i barabartë me energjinë maksimale, që do të thotë se pas çdo veprimtarie i rifitojmë plotësisht të gjitha energjitë e harxhuara. Kështu që mund të shpenzojmë plot 3 xhaul për secilën veprimtari. Përfitimi total: 34 + 31 + 33 +35 = 39.

Zgjidhja 1

def max_gain(E, R, V, e_initial, e_remaining):
    """
    We start processing the array of values by having an initial energy
    of 'e_initial'. After processing the array of values we must still
    have 'e_remaining' energy left.

    """
    # if V is empty, gain is zero
    if not V: return 0
    
    # find max value and its index
    v_max = max(V)
    i = V.index(v_max)
    
    # split the array of values at the max value
    V_prev = V[:i]
    V_next = V[i+1:]

    # calculate the max energy that we can spend on v_max
    e1 = min(E, e_initial + R*len(V_prev))
    e2 = max(0, e_remaining - R*len(V_next))

    # calculate the max gain recursively
    gain = v_max * (e1 - e2)
    gain += max_gain(E, R, V_prev, e_initial, max(0, e1 - R))
    gain += max_gain(E, R, V_next, min(E, e2 + R), e_remaining)

    return gain
    
for t in range(int(input())):
    E, R, N = map(int, input().split())
    R = min(E, R)
    V = [int(v) for v in input().split()]
    print('Case #{}: {}'.format(t+1, max_gain(E, R, V, E, 0)))

Sqarime

Kjo zgjidhje përdor një algoritëm lakmitar (ose grykës, greedy). Fillimisht gjejmë veprimtarinë me vlerën më të madhe, dhe shpenzojmë për të sasinë më të madhe të mundshme të energjisë, pastaj vazhdojmë me vlerën tjetër më të madhe dhe shpenzojmë për të vlerën më të madhe të mundshme të energjisë, e kështu me radhë. Për një diskutim se pse dhe si ky algoritëm lakmitar jep një zgjidhje optimale për këtë problem shikoni: https://code.google.com/codejam/contest/2418487/dashboard#s=a&a=1

Implementimi është bërë me një funksion rekursiv (që thërret vetveten me parametra më të vegjël). Ky funksion gjen përfitimin më të madh të mundshëm për një pjesë të veprimtarive (nënvarg i V), duke ditur energjinë që kemi para fillimit të tyre (e_initial), dhe duke u munduar që të na ketë mbetur akoma një sasi e caktuar energjie pas përfundimit të tyre (e_remaining).

Rasti bazë, që mbyll përsëritshmërinë, është kur lista e veprimtarive është bosh. Në këtë rast është e qartë që përfitimi është zero.

Kur kemi disa veprimtari, fillimisht gjejmë atë që ka vlerën më të madhe dhe mundohemi të harxhojmë sa më shumë energji që të jetë e mundur për këtë. Pastaj e thërrasim funksionin në mënyrë rekursive për listën e veprimtarive në të majtë dhe në të djathtë të tij.

Kjo zgjidhje e ka kohën të rendit \(O(N^2)\), meqë gjetja e elementit më të madh të një liste normalisht është e rendit \(O(N)\), dhe ky veprim duhet përsëritur pak a shumë për çdo element. Megjithatë, duke përdorur disa struktura të veçanta (si pirgjet/heaps), mund ta zvogëlojmë kohën e gjetjes së elementit më të madh, dhe mund ta ulim kohën totale të zgjidhjes në \(O(N*ln(N))\).

Por ekziston edhe një zgjidhje e këtij problemi me kohë \(O(N)\), të cilën do ta shikojmë më poshtë. E bukura është se krijuesve të këtij problemi nuk u kishte vajtur në mëndje kjo zgjidhje, por e kishin gjetur disa prej konkurruesve.

Zgjidhja 2

for t in range(int(input())):
    E, R, N = map(int, input().split())
    R = min(E, R)
    V = [int(v) for v in input().split()]

    # for each V[i] find the index of the next value that is higher
    next_v = [None for i in range(N)]
    stack = [ {'v': max(V), 'i': None} ]
    for i in range(N):
        v = V[i]
        while v > stack[-1]['v']:
            item = stack.pop()
            next_v[item['i']] = i
        stack.append({'v': v, 'i':i})

    # find max_gain
    max_gain = 0
    e = E
    for i in range(N):
        if next_v[i] == None:
            max_gain += e*V[i]
            e = 0
        else:
            # find energy that needs to be left
            e1 = max(0, E - R*(next_v[i] - i))
            # find energy that can be spent for this activity
            spe = max(0, e - e1)
            max_gain += spe*V[i]
            e -= spe
        e = min(E, e + R)
    
    print('Case #{}: {}'.format(t+1, max_gain))

Sqarime

Kjo zgjidhje fillimisht gjen (në ndryshoren next_v) aktivitetin pasardhës që ka vlerë më të madhe se një aktivitet i caktuar. Me ndihmën e një stive (stack) kjo gjë mund të bëhet në kohë lineare (\(O(N)\)), përndryshe do të duhej një kohë që në rastin më të keq është kuadratike.

Më pas i shqyrtojmë aktivitetet me radhë (në kohë lineare). Nëse aktiviteti që po shqyrtohet nuk ka aktivitet pasardhës me vlerë më të madhe, atere të gjithë energjinë që kemi duam ta shpenzojmë për këtë aktivitet, sepse kështu do kemi përfitimin maksimal. Përndryshe, nëse ka një aktivitet pasardhës me vlerë më të madhe, atere llogarisim se sa energji mund të shpenzojmë tani, me qëllim që kur të vijë radha e atij aktiviteti të kemi sa më shumë energji që të jetë e mundur (mundësisht E).

Detyra

Një robot alien po kërcënon gjithësinë, me një rreze që mund të shkatërrojë gjithë njohurinë mbi algoritmet. Duhet ta ndalojmë!

Për fat, e dimë se si punon roboti. Duke filluar me një rreze me fuqi 1, ai zbaton njëri pas tjetrit udhëzimet në një program, nga e majta në të djathtë. Çdo udhëzim është një nga këto: - C (charge): Dyfisho fuqinë e rrezes. - S (shoot): Godit me rreze, duke shkaktuar një dëm të barabartë me fuqinë e rrezes.

P.sh. nëse programi është SCCSSC, roboti do bëjë këto: - Godit, duke shkaktuar 1 dëm. - Dyfisho, fuqia bëhet 2. - Dyfisho, fuqia bëhet 4. - Godit, dëmi 4. - Godit, dëmi 4. - Dyfisho, fuqia bëhet 8.

Në këtë rast dëmi total është: 1 + 4 + 4 = 9.

Algoritmistat më të mirë të gjithësisë kanë krijuar një mbështjellë mbrojtëse e cila mund të përballojë një dëm total deri në D. Mirëpo programi i robotit mund të shkaktojë dëm edhe më shumë se kaq.

Presidenti i Gjithësisë ka dalë vullnetar që të shkojë në hapësirë dhe të hakojë programin e robotit para se ai ta zbatojë atë. Mënyra e vetme se si mund ta hakojë (pa e kuptuar roboti) është duke u ndërruar vendin dy udhëzimeve fqinje. P.sh. programin e mësipërm mund ta ndryshojë duke u shkëmbyer vendet udhëzimeve 3 dhe 4, duke e bërë programin SCSCSC. Kjo do ta pakësonte dëmin total në 7. Pastaj mund ta ndryshonte prapë duke e bërë SCSSCC dhe duke e pakësuar dëmin total në 5, e kështu me radhë.

Që roboti mos të dyshojë, presidenti duhet të bëjë sa më pak hakime. Cili është numri më i vogël i hakimeve që janë të nevojshme për të siguruar që dëmi total që shkakton programi nuk e kalon vlerën D, nëse kjo është e mundur?

Referenca: https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard

Shembull

$ cat input.txt
6
1 CS
2 CS
1 SS
6 SCCSSC
2 CC
3 CSCSS

$ python3 prog.py < input.txt
Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 2
Case #5: 0
Case #6: 5

Jepet numri D dhe programi P.