Problemi 147

Kërkesa

Vanesa ka N xhingla në raftin e saj, të numëruara 1, 2, …, N nga e majta në të djathtë. Xhinglat janë të llojeve të ndryshme, ku çdo lloj shënohet me një numër. Xhingla që ndodhet në pozicionin i në raftin e saj është e llojit \(A_i\).

Vanesa studion jashtë dhe sot do kthehet që të vizitojë familjen. Ajo do që të marrë sa më shumë xhingla me vete, por ngaqë është me nxitim i duhet të rrëmbejë një varg të vazhdueshëm xhinglash. Po ta themi me gjuhë shkencore, Vanesa zgjedh me mënd dy pozicione l dhe r dhe vërvit në çantë të gjitha xhinglat që ndodhen në vendet \(l, l+1, ..., r-1, r\). Gjithashtu, për shkak të rregullave të aeroportit, kontrolluesit do hedhin poshtë të gjitha xhinglat e një lloji të caktuar, nëse ajo ka më shumë se S të tilla.

P.sh. nqs S = 2 dhe Vanesa ka me vete 6 xhingla, një të llojit 0, dy të llojit 1, dhe tre të llojit 2, asaj do ti lejohen xhinglat e llojit 0 dhe 1, por do ti hidhen poshtë të treja xhinglat e llojit 2.

Vanesa duhet të zgjedhë l dhe r të tilla që të marrë sa më shumë xhingla me vete. Sa është numri më i madh i xhinglave që mund të marrë me vete Vanesa?

Referenca: https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050eda/00000000001198c1

Shembull

$ cat input.txt
4
6 2
1 1 4 1 4 4
8 1
1 2 500 3 4 500 6 7
10 1
100 200 8 8 8 8 8 300 400 100
12 2
40 50 1 1 1 60 70 2 2 2 80 90

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

Për çdo rast testimi jepet numri i xhinglave N dhe maksimumi i lejuar në aeroport S. Pastaj jepet vargu i xhinglave sipas llojit të secilës prej tyre.

Në rastin e parë Vanesa duhet të zgjedhë l=2 dhe r=5. Kjo i lejon asaj të marrë xhinglat [1, 4, 1, 4], asnjë prej të cilave nuk hidhet poshtë në aeroport.

Në rastin e dytë Vanesa duhet të zgjedhë l=1 dhe r=8. Xhinglat e llojit 500 do hidhen poshtë meqë janë më shumë se S=1 të tilla, kështu që ajo do marrë me vete 6 xhingla.

Në rastin e tretë duhet të zgjedhë l=1 dhe r=9 dhe të sjellë në aeroport xhinglat [100, 200, 8, 8, 8, 8, 8, 300, 400]. Xhinglat e llojit 8 do hidhen poshtë dhe do ti ngelen 4 xhingla me vete.

Në rastin e katërt duhet të zgjedhë l=1 dhe r=12. Xhinglat e llojit 1 dhe 2 do hidhen poshtë meqë ka më shumë se S=2 të tilla, kështu që do ti mbeten 6 xhingla.

Zgjidhja

for t in range(int(input())):
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    max_items = 0
    for i in range(N):
        type_freq = {}
        nr_items = 0
        for j in range(i,N):
            a = A[j]
            type_freq[a] = type_freq.get(a, 0) + 1
            if type_freq[a] <= S:
                nr_items += 1
            elif type_freq[a] == S + 1:
                nr_items -= S
            if nr_items > max_items:
                max_items = nr_items

    print('Case #{}: {}'.format(t+1, max_items))

Sqarime

Koha e kësaj zgjidhje është e rendit \(O(N^2)\).

Detyra