Problemi 090

Kërkesa

Kemi një pemë me N nyje (të shënuara me numrat 1 deri në N), ku rrënja është nyja 1. Çdo nyje i ka një vlerë \(A_i\) (që mund të jetë edhe numër negativ).

Mund të zgjedhim një nyje çfarëdo të pemës dhe të fshijmë gjithë nënpemën (degën) poshtë saj, përfshirë edhe vetë nyjen. Këtë veprim mund ta përsërisim disa ose asnjë herë.

Le të përkufizojmë si përfitim shumën e të gjitha vlerave të nyjeve të mbetura në pemë, minus \(X * k\), ku X është një numër i dhënë paraprakisht, dhe k është numri i herëve që është kryer veprimi i përshkruar më sipër. Gjeni vlerën më të madhe të mundshme të përfitimit.

Referenca: https://www.codechef.com/APRIL19B/problems/SUBREM

Shembull

$ cat input.txt
1
3 5
1 -5 -10
1 2
2 3

$ python3 prog.py < input.txt
-4

Kemi një rast testimi. Në rreshtin e parë jepen numrat N dhe X. Në rreshtin e dytë jepen N vlerat \(A_i\). Në N-1 rreshtat pasardhës jepen dy numra u dhe v, që tregojnë se ka një brinjë midis dy nyjeve të shënuara me u dhe v.

Në rastin e dhënë pema është e tillë: (1)–>(2)–>(3). Duke shënuar edhe vlerat përkatëse të çdo nyje mund ta paraqesim kështu: (1,1)–>(2,-5)–>(3,-10).

Nqs nuk fshijmë asnjë nyje/degë përfitimi do jetë: 1 + -5 + -10 = -14. Nqs fshijmë nyjen 3, do jetë: 1 + -5 - 1x5 = -9. Nqs fshijmë nyjen 3 dhe pastaj fshijmë nyjen 2, do jetë: 1 - 2x5 = -9. Nqs fshijmë vetëm nyjen 2 do jetë: 1 - 1x5 = -4. Nqs fshijmë nyjen 3, pastaj 2, pastaj 1, do jetë: 0 - 3x5 = -15. Nqs fshijmë nyjen 2 pastaj nyjen 1, do jetë: 0 - 2x5 = -10. Nqs fshijmë vetëm nyjen 1, përfitimi do jetë: 0 - 1x5 = -5.

Nga të gjitha këto vlera të përfitimeve, vlera më e madhe është -4, e cila është edhe përgjigja.

Zgjidhja

for _ in range(int(input())):
    # get the input
    n, x = map(int, input().split())
    values = [int(i) for i in input().split()]
    values = [0] + values
    edges = [[] for i in range(n+1)]
    for i in range(n-1):
        u, v = map(int, input().split())
        edges[v].append(u)
        edges[u].append(v)

    # make a pre-order tranversal of the tree and
    # find the parent and the children of each node
    parent = [0 for i in range(n+1)]
    children = [[] for i in range(n+1)]
    stack = [1]
    while stack:
        v = stack.pop()
        children[v] = [u for u in edges[v] if u != parent[v]]
        for u in children[v]:
            parent[u] = v
        stack.extend(children[v])

    # make a post-order tranversal of the tree and
    # find the maximum possible profit for each node
    visited = [False for i in range(n+1)]
    stack = [1]
    while stack:
        v = stack.pop()
        unvisited_children = [u for u in children[v] if not visited[u]]
        if unvisited_children:
            stack.append(v)
            stack.extend(unvisited_children)
        else:
            # process (visit) node v
            s = values[v] + sum([values[u] for u in children[v]])
            values[v] = max(s, -1*x)
            visited[v] = True

    # print the maximum possible profit for the root node
    print(values[1]) 

Sqarime

Pasi lexojmë vlerat N dhe X, te lista values ruajmë vlera \(A_i\), dhe më pas te lista edges ndërtojmë listën e brinjëve për çdo nyje. Lista e brinjëve për një nyje të caktuar në fakt është lista e nyjeve ku mund të shkojmë me anë të një brinje, duke u nisur nga nyja e dhënë. Kjo listë përmban edhe prindin (paraardhësin në hierarkinë e pemës), edhe fëmijët (pasardhësit në hierarkinë e pemës) e nyjes së dhënë, sepse mënyra se si na jepen brinjët nuk e përcakton se cila prej nyjeve të brinjës është paraardhësi dhe cila është pasardhësi në hierarkinë e pemës.

Vini re që listat values dhe edges (dhe të gjitha listat e tjera që përdoren më poshtë) janë me gjatësi N+1, dhe kjo bëhet për shkak se nyjet e pemës në problemë janë të numëruara duke filluar nga 1-shi, dhe jo duke filluar nga 0-ja. Me këtë marifet shmangim nevojën për të konvertuar indekset.

Më poshtë, duke bërë një bredhje para-rendore në pemë, gjejmë se cili është prindi për çdo nyje, dhe cilët janë fëmijët. Bredhje para-rendore do të thotë që fillimisht vizitohet prindi, dhe më pas fëmijët e tij. Këtë mund ta realizojmë duke përdorur një stack (stivë). Në një stivë, ajo që futet e fundit, del e para. Fillimisht fusim në stivë rrënjën e pemës (nyjen 1). Pastaj, përderisa stiva nuk ka ngelur bosh, nxjerrim nyjen që është në krye të stivës, e përpunojmë (vizitojmë), pastaj fusim në stivë gjithë fëmijët e saj. Përpunimi që i bëhet nyjes në këtë rast është përcaktimi i fëmijëve të saj, si dhe caktimi si prind për të gjithë fëmijët e saj. Është e rëndësishme që bredhja të jetë para-rendore, sepse caktimi i prindit për fëmijët e një nyje bën të mundur gjetjen e fëmijëve të fëmijëve.

Tani jemi gati të gjemë përgjigjen e problemit.

Fillimisht vërejmë se nuk ka kuptim të presim një degë dhe pastaj të presim një prind të saj, sepse kjo vetëm rrit numrin e veprimeve të kryera dhe zvogëlon përfitimin. Gjithashtu mund të vërejmë se gjatë llogaritjes së përfitimit, vlerën e një nyje mund ta zëvendësojmë me përfitimin më të madh të degës që varet nga ajo nyje, meqenëse kjo vetëm mund ta rrisë rezultatin përfundimtar (dhe ne atë duam, të gjejmë vlerën më të madhe të përfitimit). Një vëzhgim tjetër është që nqs përfitimi më i madh për një nyje faktikisht është më i vogël se vlera **(-1*X)**, atere na del më mirë që ta presim këtë degë (me një goditje/veprim), sepse në këtë rast vlera që do kontribonte kjo nyje në përfitimin total do ishte (-1*X), më e madhe se kontributi në rast se nuk do ta prisnim.

Përgjigja gjendet nga një bredhje pas-rendore e pemës, ku fillimisht vizitohen fëmijët e një nyje dhe pastaj vetë nyja. Për çdo nyje llogarisim vlerën më të madhe të përfitimit për atë nyje, duke ditur vlerat më të mëdha të përfitimit për secilin nga fëmijët (prandaj është e rëndësishme që bredhja të jetë pas-rendore). Në fund, përgjigja do jetë vlera më e madhe e përfitimit e llogaritur për nyjen rrënjë (nyjen 1).

Bredhjen pas-rendore mund ta realizojmë me ndihmën e një stive, si në rastin më sipër, vetëm se në këtë rast është e nevojshme të mbajmë shënim edhe nyjet që kemi vizituar tashmë. Kjo është e nevojshme sepse në stivë futet e para vetë nyja dhe pastaj fëmijët e saj, në mënyrë që nyja të përpunohet pasi të jenë përpunuar fëmijët e saj. Nëse nuk do të mbanim shënim nyjet që kemi përpunuar (vizituar) tashmë, nuk do ta dinim nëse fëmijët janë përpunuar ose jo, kur ta nxjerrim nga stiva nyjen për herë të dytë.

Detyra

Një nxënës ka studiuar me kujdes algoritmin e renditjes Bubble Sort dhe ka shpikur një variant të ri të tij.

Veprimi kryesor i algoritmit Bubble Sort është shqyrtimi i dy numrave të njëpasnjëshëm dhe ndërrimi i vendit të tyre, nëse i pari është më i madh se i dyti. Por algoritmi i shpikur shqyrton 3 numra të njëpasnjëshëm, dhe nëse i majti është më i madh se i djathti, ndryshon radhën e tyre në të kundërt. Meqenëse ky algoritëm është si një “triplet bubble sort”, shkurtimisht po e quajmë “Trouble Sort”.

  TroubleSort(L): // L is a 0-indexed list of integers
    let done := false
    while not done:
      done = true
      for i := 0; i < len(L)-2; i++:
        if L[i] > L[i+2]:
          done = false
          reverse the sublist from L[i] to L[i+2], inclusive

Për shembull, për listën L = 5 6 6 4 3, Trouble Sort do funksionojë si më poshtë:

• Hapi i parë:
  • shqyrton 5 6 6 dhe nuk bën asgjë: 5 6 6 4 3
  • shqyrton 6 6 4, shikon që 6 > 4, i ndryshon radhën: 5 4 6 6 3
  • shqyrton 6 6 3, shikon që 6 > 3, i ndryshon radhën: 5 4 3 6 6
• Hapi i dytë:
  • shqyrton 5 4 3, shikon që 5 > 3, i ndryshon radhën: 3 4 5 6 6
  • shqyrton 4 5 6, nuk bën gjë: 3 4 5 6 6
  • shqyrton 5 6 6, nuk bën gjë: 3 4 5 6 6
• Hapi i tretë i shqyrton të treja treshet dhe nuk bën asgjë, kështu që algoritmi përfundon.

Megjithatë është e mundur që ky algoritëm mos ta bëjë gjithmonë saktë renditjen e listës. P.sh. shqyrtoni listën: 8 9 7.

Për një listë numrash të dhënë, gjeni nëse Trouble Sort e rendit saktë këtë listë ose jo. Nëse jo, gjeni indeksin e gabimit të parë në renditjen e bërë nga Trouble Sort, dmth gjeni pozicionin e numrit të parë që është më i madh se numri pasardhës.

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

Shembull

$ cat input.txt
2
5
5 6 8 4 3
3
8 9 7

$ python3 prog.py < input.txt
Case #1: OK
Case #2: 1

Në rastin e parë Trouble Sort e rendit saktë listën e dhënë.

Në rastin e dytë, numri i dytë i listës (me treguesin 1) është më i madh se ai pasardhës, pas renditjes me Trouble Sort.