Problemi 100
Kërkesa
Në një rrugë janë N + 2 vende parkimi në një rresht të vetëm. Vendi i parë dhe i fundit janë gjithmonë të zënë nga policia bashkiake, kurse N të tjerat janë për përdoruesit.
Kur vjen një person për të parkuar ai përpiqet të zërë një vend që të jetë sa më larg nga makinat e tjera. Për të shmangur ngatërresat ata ndjekin disa rregulla të paracaktuara. Për çdo vend parkimi bosh \(V\) llogarisin vlerat \(M_V\) dhe \(D_V\), që janë numrat e vendeve bosh midis këtij vendi dhe vendeve të zëna në të majtë dhe në të djathtë. Pastaj shqyrtojnë ato vende që kanë fqinjin më të largët, dmth ato vende \(V\) për të cilat \(min(M_V, D_V)\) është maksimale. Nëse është vetëm një vend i tillë, atere atë zgjedhin. Përndryshe zgjedhin prej tyre atë vend që e ka vlerën \(max(M_V, D_V)\) maksimale. Nëse prapë ka disa vende të tilla, atere zgjedhin atë prej tyre që është sa më majtas.
Në parkim vijnë K persona. Secili prej tyre parkon para se të vijë personi pasardhës (duke ndjekur rregullat më sipër), dhe asnjë prej tyre nuk largohet.
Kur parkon personi i fundit, sa do jenë vlerat \(max(M_V, D_V)\) dhe \(min(M_V, D_V)\)?
Referenca: https://code.google.com/codejam/contest/3264486/dashboard#s=p2&a=2
Shembull
$ cat input.txt
7
4 2
5 2
6 2
1000 1000
1000 1
1000000 500000
1000000000000000000 500000000000000000
$ python3 prog.py < input.txt
Case #1: 1 0
Case #2: 1 0
Case #3: 1 1
Case #4: 0 0
Case #5: 500 499
Case #6: 1 0
Case #7: 1 0Për çdo rast testimi jepen numrat N dhe K.
Në rastin e parë situata është e tillë: 0.12.0 (me 0 shënojmë makinat e policisë, me pikë (.) shënojmë vendet bosh, dhe me numrat 1 dhe 2 shënojmë vendet që kanë zënë i pari dhe i dyti). Kështu që përgjigja është “1 0”.
Në rastin e dytë situata është e tillë: 02.1..0, kështu që përgjigja është “1 0”.
Në rastin e tretë situata është e tillë: 0..1.2.0, kështu që përgjigja është “1 1”.
Në rastin e katërt çdo vend do jetë i zënë në fund, pavarësisht nga radha se si zihen, kështu që përgjigja është “0 0”.
Zgjidhja 1
for t in range(int(input())):
n, k = [int(i) for i in input().split()]
segments = [n] # sorted list of segment sizes
for i in range(k): # repeat k times
# get one of the largest segments
s = segments[0]
del(segments[0])
# split it into 2 other segments
s1 = (s - 1) // 2
s2 = s // 2
# insert these 2 segments on the list
if s1 > 0: segments.append(s1)
if s2 > 0: segments.append(s2)
# sort the list of segments
segments.sort(reverse=True)
# print the last two segments
print('Case #{}: {} {}'.format(t+1, s2, s1))Sqarime
Në një simulim naiv mund të mbanim një listë me vendet e parkimit, për çdo vend bosh të gjenim sa vende bosh ka në të majtë dhe në të djathtë, të gjenim maksimumin e minimumeve etj. (sipas rregullave të përshkruara në problem). Kjo do ishte edhe e vështirë për tu implementuar edhe jashtëzakonisht jo-efiçente.
Mund të vëmë re se pozicionet e segmenteve me vende bosh nuk kanë rëndësi, rëndësi ka vetëm madhësia e tyre. Po ashtu, kur ndahet një segment, ai në të majtë është ose i barabartë ose një më pak se ai në të djathtë.
Në këtë zgjidhje ne i mbajmë segmentet (madhësinë e tyre) në një listë të renditur nga më i madhi te më i vogli. Për çdo person që vjen heqim nga lista segmentin më të madh (të parin), e ndajmë në dy segmente të tjera, i shtojmë këto në fund të listës, dhe e rendisim listën sërish.
Kjo zgjidhje është shumë e ngadaltë për testin 6. Koha e saj është e rendit \(O(K*K*log(K))\) (sepse zakonisht \(O(K*log(K))\) është koha që duhet për të renditur listën).
Zgjidhja 2
import heapq
for t in range(int(input())):
n, k = [int(i) for i in input().split()]
segments = [-1*n] # sorted list of segment sizes
heapq.heapify(segments)
for i in range(k): # repeat k times
# get one of the largest segments
s = -1 * heapq.heappop(segments)
# split it into 2 other segments
s1 = (s - 1) // 2
s2 = s // 2
# insert these 2 segments on the list
if s1 > 0: heapq.heappush(segments, -1*s1)
if s2 > 0: heapq.heappush(segments, -1*s2)
# print the last two segments
print('Case #{}: {} {}'.format(t+1, s2, s1))Sqarime
Kur na intereson vetëm elementi më i madh, heap (pingu) është një strukturë më efiçente sesa një listë e renditur. Veprimet e saj janë të kohës \(O(log(K))\), kështu që kjo e përmirëson kohën e zgjidhjes së parë dhe e bën \(O(K*log(K))\). Kjo zgjidhje e kalon edhe testin 6, por ngec te testet e mëposhtme.
Vini re që moduli heapq i Python-it ka vetëm një min-heap, dmth një pirg që në majë ka elementin më të vogël. Por ne na intereson elementi më i madh, kështu që të gjitha vlerat që fusim në pirg i shumëzojmë me -1, dhe vlerat që nxjerrim nga pirgu i shumëzojmë përsëri me -1. Në këtë mënyrë, praktikisht e bëjmë që të funksionojë si një max-heap.
Zgjidhja 3
import heapq
for t in range(int(input())):
n, k = [int(i) for i in input().split()]
segments = [-1*n] # sorted list of segment sizes
counts = { n: 1 } # keep the count of each segment size
heapq.heapify(segments)
for i in range(k): # repeat k times
# remove one of the largest segments
s = -1 * segments[0]
counts[s] -= 1
if counts[s] == 0:
del(counts[s])
heapq.heappop(segments)
# split it into 2 other segments
s1 = (s - 1) // 2
s2 = s // 2
# insert these 2 segments
if s1 > 0:
counts[s1] = counts.get(s1, 0) + 1
if counts[s1] == 1:
heapq.heappush(segments, -1*s1)
if s2 > 0:
counts[s2] = counts.get(s2, 0) + 1
if counts[s2] == 1:
heapq.heappush(segments, -1*s2)
# print the last two segments
print('Case #{}: {} {}'.format(t+1, s2, s1))Sqarime
Mund të vihet re që ka shumë segmente me madhësi të njëjtë. P.sh. nqs
N është përafërsisht \(2^10\) atere do jenë përafërsisht \(2^9\)
segmente me gjatësi 2. Nqs do të mbanim shënim numrin e segmenteve me
të njëjtën gjatësi, atere gjatësia e listës/pirgut segments do ishte
shumë e vogël dhe veprimet në të do ishin më të shpejta. Kjo zgjidhje
bën pikërisht këtë, dmth për një segment me një gjatësi të caktuar
mban shënim se sa herë ndodhet ky segment në listë.
Mund të vërtetohet që gjatësia e pirgut segments është
\(O(log(K))\), kështu që koha e kësaj zgjidhje është e rendit
\(O(K*log(log(K)))\), që praktikisht është pothuajse \(O(K)\).
Gjithsesi, te testi 7 kjo zgjidhje ngec.
Zgjidhja 4
import heapq
for t in range(int(input())):
n, k = [int(i) for i in input().split()]
segments = [-1*n] # sorted list of segment sizes
counts = { n: 1 } # keep the count of each segment size
heapq.heapify(segments)
while k > 0: # repeat until all the people are done
# process all the largest segments of the same size
s = -1 * heapq.heappop(segments)
c = counts[s]
del(counts[s])
# process *c* people at once
k -= c
# split the segments
s1 = (s - 1) // 2
s2 = s // 2
# insert these *c* _s1_ segments and *c* _s2_ segments
if s1 > 0:
counts[s1] = counts.get(s1, 0) + c
if counts[s1] == c:
heapq.heappush(segments, -1*s1)
if s2 > 0:
counts[s2] = counts.get(s2, 0) + c
if counts[s2] == c:
segments.append(s2)
heapq.heappush(segments, -1*s2)
# print the last two segments
print('Case #{}: {} {}'.format(t+1, s2, s1))Sqarime
Mund të vërejmë gjithashtu se të gjithë segmentet me gjatësi të njëjtë përpunohen njëri pas tjetrit (sepse gjithmonë marrim një nga segmentet që kanë gjatësinë më të madhe). Kështu që në vend që ti përpunojmë veç e veç, mund ti përpunojmë të gjithë së bashku. Kjo i shkurton shumë përsëritjet e ciklit, sepse në një hap të vetëm ne mund të përpunojmë p.sh. \(2^10\) segmente, në vend që të bëjmë \(2^10\) hapa për çdo segment.
Koha e kësaj zgjidhje është e rendit \(O(log(K)*log(log(K)))\) ose praktikisht \(O(log(K))\). Kjo është jashtëzakonisht e shpejtë edhe për vlera shumë të mëdha të K, dhe përfundon shumë shpejt të gjitha rastet e testimit.
Zgjidhja 5
for t in range(int(input())):
n, k = [int(i) for i in input().split()]
people = k
segs = 1
size = n
free = n
while people > segs:
people -= segs
free -= segs
size = size // 2
segs *= 2
if people > free - segs*(size - 1):
size -= 1
print('Case #{}: {} {}'.format(t+1, size // 2, (size - 1) // 2))Sqarime
for t in range(int(input())):
n, k = [int(i) for i in input().split()]
people = k # number of people to come
segs = 1 # total number of segments
size = n # size of the largest segment
free = n # total number of free places
while people > segs:
people -= segs # one person splits each segment
free -= segs # each of these persons occupies a place
size = size // 2 # halve the size of the segments
segs *= 2 # double the number of the segments
# Now we have people <= segs. The last person will split one of
# these segments. Some of these segments are of size "size" and
# the others of size "size-1". Which one of these will split the
# last person? The number of segments of size "size" is
# "free - segs*(size - 1)". If there are more people left than
# this number, then the last person will split a segment of size
# "size - 1"
if people > free - segs*(size - 1):
size -= 1
print('Case #{}: {} {}'.format(t+1, size // 2, (size - 1) // 2))Po ta shikojmë me kujdes zgjidhjen e mëparshme (zgjidhjen 4) mund të vërejmë që në çdo hap numri i segmenteve që përpunohen është sa dyfishi i segmenteve që u përpunuan në hapin e mëparshëm, kurse gjatësia e segmenteve është pothuajse sa gjysma e gjatësisë së segmenteve që përpunohen në hapin e mëparshëm (mund të ndryshojnë ndoshta me 1). Bazuar në këtë vëzhgim, mund ta heqim nga përdorimi listën (pirgun) me gjatësitë e segmenteve dhe listën (hartën) me numrin e segmenteve të çdo gjatësie.
Zgjidhja që rezulton është më e shkurtër, më e thjeshtë dhe më elegante se zgjidhja e mëparshme. Megjithatë koha e kësaj zgjidhje është e rendit \(O(log(K))\), njëlloj sa ajo e zgjidhjes së mëparshme. Kështu që edhe kjo zgjidhje jep rezultat shumë shpejt, sado e madhe të jetë K-ja dhe N-ja.
Detyra
Jepet një varg me numra natyrorë \(A_1, A_2, ... , A_N\). Ju mund të zgjidhni një numër natyror X dhe të bëni me të veprimin bitwise XOR me secilin nga numrat e vargut, pastaj të merrni shumën e këtyre numrave. Sa është vlera më e vogël e mundshme e kësaj shume.
Referenca: https://www.codechef.com/LTIME71B/problems/MINARRS
Shembull
$ cat input.txt
3
5
2 3 4 5 6
4
7 7 7 7
3
1 1 3
$ python3 prog.py < input.txt
14
0
2Në rastin e parë mund të zgjedhin X = 6, dhe vargu bëhet (4, 5, 2, 3, 0).
Në rastin e dytë mund të zgjedhim X = 7 dhe të gjithë numrat e vargut bëhen 0.
Në rastin e tretë mund të zgjedhim X = 1, dhe vargu bëhet (0, 0, 2), shuma e të cilit është 2.