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 0

Pë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

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

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

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

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

Sqarime

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
2

Në 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.