Problemi 092
Kërkesa
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: 1Në 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.
Zgjidhja 1
def troublesort(L):
done = False
while not done:
done = True
for i in range(len(L) - 2):
if L[i] > L[i+2]:
done = False
L[i], L[i+2] = L[i+2], L[i]
def check(L):
for i in range(len(L)-1):
if L[i] > L[i+1]:
return i
return 'OK'
T = int(input())
for t in range(T):
N = int(input())
L = list(map(int, input().split()))
troublesort(L)
print("Case #{}: {}".format(t+1, check(L)))Sqarime
Trouble Sort ka të njëjtën kohë renditje si Bubble Sort, që është \(O(N^2)\). Kështu që edhe kjo zgjidhje ka po këtë kohë. Zgjidhja e dytë është më e shpejtë.
Zgjidhja 2
def troublesort(L):
n = len(L)
L1 = [L[i] for i in range(n) if i % 2 == 0]
L2 = [L[i] for i in range(n) if i % 2 == 1]
L1.sort()
L2.sort()
for i in range(n):
L[i] = L1[i//2] if i % 2 == 0 else L2[i//2]
def check(L):
for i in range(len(L)-1):
if L[i] > L[i+1]:
return i
return 'OK'
T = int(input())
for t in range(T):
N = int(input())
L = list(map(int, input().split()))
troublesort(L)
print("Case #{}: {}".format(t+1, check(L)))Sqarime
Mund të vihet re se Trouble Sort krahason vetëm numrat që janë në vende tek me njëri-tjetrin, dhe numrat që janë në vende çift me njëri-tjetrin, por asnjëherë një numër që ndodhet në një vend çift me një numër që ndodhet në një vend tek. Kështu që kryen renditje të pavarur të dy nënlistave. (Në fakt ky është edhe problemi se pse rezultati i algoritmit Trouble Sort nuk është gjithmonë i saktë.)
Të njëjtin rezultat që jep Trouble Sort ne mund ta marrim edhe nëse i veçojmë dy nënlistat, i rendisim në mënyrë të pavarur nga njëra-tjetra, por me një algoritëm me kohë më të shpejtë se \(O(N^2)\), dhe i bashkojmë sërish. Në këtë mënyrë kjo zgjidhje do ketë një kohë më të shpejtë se \(O(N^2)\) (zakonisht \(O(N*log(N)\)).
Detyra
Në grupin e programimit ne kemi qejf ti dërgojmë njëri tjetrit panagrama. Një fjali ose shprehje quhet panagram kur i përmban të gjitha shkronjat e alfabetit anglisht të paktën një herë. P.sh. shprehja “the quick brown fox jumps over the lazy dog” është një panagram. Ndonjëherë panagramat tona përmbajnë informata sekrete, si p.sh. “CJ QUIZ: KNOW BEVY OF DP FLUX ALGORITHMS”, dhe duhen mbajtur të fshehta.
Pasi lexuam për disa minuta një libër rreth shifrimit(enkriptimit), dhe mësuam se është shumë e vështirë të gjenden përbërësit e prodhimit të dy numrave të thjeshtë shumë të mëdhenj, hartuam një skemë shifrimi të bazuar në këtë fakt. Fillimisht bëmë këto përgatitje:
- Zgjodhëm 26 numra të thjeshtë të ndryshëm nga njëri tjetri dhe më të vegjël se N.
- I renditëm nga më i vogli te më i madhi. Pastaj më të voglit i caktuam shkronjën A, të dytit shkronjën B, e kështu me radhë.
- Të gjithë pjesëtarët e grupit e mbajtën shënim këtë listë.
Tani, kur duam të dërgojmë ndonjë panagram si mesazh, fillimisht heqim të gjitha vendet bosh midis fjalëve, pastaj shkruajmë prodhimin e numrave të thjeshtë që i korrespondojnë shkronjës së parë dhe të dytë të mesazhit, pastaj shkruajmë prodhimin e numrave të thjeshtë të shkronjës së dytë dhe të tretë, e kështu me radhë, duke përfunduar me prodhimin e numrave të shkronjës së fundit dhe të parafundit. Kjo listë me numra që formohet është versioni i shifruar i mesazhit.
P.sh. nqs N=103 dhe kemi zgjedhur të përdorim 26 numrat e parë të thjeshtë pas numrit 2 (sepse kemi frikë se faktorizimi i numrave çift është shumë i thjeshtë), do kemi A=3, B=5, C=7, D=11, e kështu me radhë, deri te Z=103. Nqs duam të kriptojmë panagramën “CJ QUIZ…” më sipër, teksti do jetë “CJQUIZKNOWBEVYOFDPFLUXALGORITHMS”. Atere numri i parë i mesazhit të shifruar do jetë 7*31=217 (sepse C=7 dhe J=31), numri i dytë do jetë 1891, e kështu me radhë, numri i fundit do jetë 3053.
Nëse ju jepet një mesazh i shifruar në këtë mënyrë dhe numri N i përdorur, por pa ju thënë se cilët numra të thjeshtë janë përdorur, a mund ta deshifroni atë dhe të gjeni mesazhin origjinal.
Referenca: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/000000000008830b
Shembull
$ cat input.txt
2
103 31
217 1891 4819 2291 2987 3811 1739 2491 4717 445 65 1079 8383 5353 901 187 649 1003 697 3239 7663 291 123 779 1007 3551 1943 2117 1679 989 3053
10000 25
3292937 175597 18779 50429 375469 1651121 2102 3722 2376497 611683 489059 2328901 3150061 829981 421301 76409 38477 291931 730241 959821 1664197 3057407 4267589 4729181 5335543
$ python3 prog.py < input.txt
Case #1: CJQUIZKNOWBEVYOFDPFLUXALGORITHMS
Case #2: SUBDERMATOGLYPHICFJKNQVWXZPër çdo rast testimi jepen numrat N dhe L, ku N është kufiri i numrave të thjeshtë të përdorur, dhe L është gjatësia e listës me prodhimet e numrave të thjeshtë, e cila jepet në rreshtin pasardhës.