Problemi 097
Kërkesa
Ana ka një rresht me N kuba, ku në secilin kub ndodhet një nga shkronjat e alfabetit (anglisht) nga A deri në Z. Kubat mund ti shënojmë me numrat nga 1 deri në N.
Boni i jep Anës Q pyetje, ku çdo pyetje i është e tillë: A mund të formohet një palindromë me shkronjat që ndodhen nga kubi \(L_i\) në kubin \(R_i\), duke u ndërruar vendet nëse është e nevojshme? Pas çdo pyetje kubet rivendosen në radhën që ishin në fillim. Ana në fund duhet të thotë se në sa prej pyetjeve përgjigja ka qenë “po”.
Shënim: Palindromë quhet një varg me shkronja që është njëlloj po ta lexosh nga fillimi në fund dhe nga fundi në fillim. P.sh. këto janë palindroma: ANNA, RACECAR, AAA, X, kurse këto nuk janë: AB, FROG, YOYO.
Referenca: https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050eda/0000000000119866
Shembull
$ cat input.txt
2
7 5
ABAACCA
3 6
4 4
2 5
6 7
3 7
3 5
XYZ
1 3
1 3
1 3
1 3
1 3
$ python3 prog.py < input.txt
Case #1: 3
Case #2: 0Në rastin e parë kemi N = 7 dhe Q = 5.
- Në pyetjen e parë Ana duhet të përdorë shkronjat AACC. Me këto mund të formohet palindroma ACCA (ose CAAC).
- Në pyetjen e dytë duhet të përdorë shkronjën A, e cila është palindromë.
- Në pyetjen e tretë duhet të përdorë shkronjat BAAC, por me këto shkronja nuk mund të formohet asnjë palindromë, sido që ti rendisim.
- Në pyetjen e katërt duhet të përdorë shkronjat CA, me të cilat nuk mund të formohet palindromë.
- Në pyetjen e pestë duhet të përdorë shkronjat AAC, me të cilat mund të formohet palindroma ACA.
Gjithsej, mund tu përgjigjet “po” 3 pyetjeve.
Në rastin e dytë kemi N = 3 dhe Q = 5. Në secilën nga pyetjet duhen përdorur shkronjat XYZ, por nuk është e mundur që të formohet ndonjë palindromë me to. Kështu që rezultati është 0.
Zgjidhja 1
for t in range(int(input())):
N, Q = [int(i) for i in input().split()]
S = input()
ans = 0
for q in range(Q):
l, r = [int(i) for i in input().split()]
nr_odd = 0
f = [0 for i in range(26)]
i = l - 1
while i < r:
j = ord(S[i])-ord('A')
f[j] += 1
i += 1
for j in range(26):
if f[j] % 2 == 1:
nr_odd += 1
if nr_odd <= 1:
ans += 1
print('Case #{}: {}'.format(t+1, ans))Sqarime
Mund të vëmë re që në një palindromë të gjitha shkronjat përsëriten një numër çift herësh, me përjashtim të shkronjës së mesit (kur kemi një numër tek shkronjash). Kështu që për të gjetur nëse me disa shkronja mund të formohet palindromë, mjafton të shikojmë se sa herë përsëritet secila shkronjë, dhe nëse secila prej tyre përsëritet një numër çift herësh, me përjashtim të njërës, atere mund të formohet palindromë, përndryshe jo.
Koha e kësaj zgjidhje është e rendit \(O(Q*N)\).
Zgjidhja 2
for t in range(int(input())):
N, Q = [int(i) for i in input().split()]
S = input()
F = []
F.append([0 for i in range(26)])
for i in range(0, N):
F.append(F[-1][:])
j = ord(S[i])-ord('A')
F[-1][j] += 1
ans = 0
for q in range(Q):
l, r = [int(i) for i in input().split()]
nr_odd = 0
for j in range(26):
if (F[r][j] - F[l-1][j]) % 2 == 1:
nr_odd += 1
if nr_odd <= 1:
ans += 1
print('Case #{}: {}'.format(t+1, ans))Sqarime
Në këtë zgjidhje fillimisht bëjmë disa llogaritje paraprake, të cilat na e thjeshtojnë punën për t’ju përgjigjur më pas pyetjeve. Për çdo pozicion të vargut të dhënë S ne gjejmë se sa herë është përsëritur secila shkronjë që nga fillimi e deri aty. Kjo gjendet shumë kollaj sepse mjafton të shtojmë 1 te përsëritjet e pozicionit të mëparshëm.
Duke ditur përsëritjet e shkronjave për secilin pozicion, ne mund të gjejmë shumë lehtë përsëritjet e secilës shkronjë midis dy pozicioneve të dhëna, duke zbritur nga pozicioni djathtas përsëritjet e pozicionit majtas.
Për punën paraprake na duhet një kohë \(O(N)\) (mund ta bëjmë me një bredhje të vargut). Për secilën pyetje na duhet koha \(O(26)\), dhe për të gjitha pyetjet koha \(O(Q*26)\) ose \(O(Q)\) (meqë konstantet nuk ngrënë peshë). Gjithsej koha e zgjidhjes është \(O(N+Q)\), që është shumë më e mirë se koha e zgjidhjes së mëparshme.
Zgjidhja 3
for t in range(int(input())):
N, Q = [int(i) for i in input().split()]
S = input()
char_frequencies = {}
nr_odd = [[0 for i in range(N)] for j in range(N)]
nr_even = [[0 for i in range(N)] for j in range(N)]
for i in range(0, N):
char_frequencies = {S[i]: 1}
nr_odd[i][i] = 1
nr_even[i][i] = 0
for j in range(i+1, N):
c = S[j]
f = char_frequencies.get(c, 0)
char_frequencies[c] = f + 1
if f == 0:
nr_odd[i][j] = nr_odd[i][j-1] + 1
nr_even[i][j] = nr_even[i][j-1]
else:
if f % 2 == 0:
nr_odd[i][j] = nr_odd[i][j-1] + 1
nr_even[i][j] = nr_even[i][j-1] - 1
else:
nr_odd[i][j] = nr_odd[i][j-1] - 1
nr_even[i][j] = nr_even[i][j-1] + 1
ans = 0
for q in range(Q):
l, r = [int(i) for i in input().split()]
if nr_odd[l-1][r-1] <= 1:
ans += 1
print('Case #{}: {}'.format(t+1, ans))Sqarime
Kjo zgjidhje llogarit paraprakisht se sa përsëritje teke ka për çdo segment. Edhe koha e kësaj zgjidhje është \(O(N+Q)\). Por hapësira në kujtesë që duhet për këtë zgjidhje është e rendit \(O(N^2)\), që është e papranueshme për vlera të mëdha të N (ndërkohë që hapësira në kujtesë që duhet për zgjidhjen e dytë është e rendit \(O(N)\)). Përveç kësaj, kjo zgjidhje është edhe pak më e komplikuar dhe më e gjatë se zgjidhja e dytë. Kështu që zgjidhja e dytë është më e mirë se kjo.
Detyra
Kemi një listë me pikë (numra natyrorë) të shkruara në një shirit të tejdukshëm. Kemi edhe një shirit me veprime modifikuese, me gjatësi më të madhe se lista e pikëve, mbi të cilin mund të vendoset shiriti i tejdukshëm dhe të llogariten veprimet totale.
Shiriti modifikues ka këto veprime:
- Pikë (.): nuk bën asnjë modifikim.
- Dyfisho pikët (d): dyfishon numrin e pikëve që përputhen me të.
- Trefisho pikët (t): trefishon numrin e pikëve që përputhen me të.
- Dyfisho totalin (D): dyfishon shumën e të gjitha pikëve, dhe zbatohet në fund.
- Trefisho totalin (T): trefishon shumën e të gjitha pikëve, dhe zbatohet në fund.
Shiriti me pikë vendoset mbi shiritin e modifikuesve në një pozicion të caktuar dhe bëhet shuma e pikëve, duke e dyfishuar ose trefishuar numrin e pikëve më parë, nëse përputhen me veprimet d dhe t. Kurse veprimet D dhe T bëjnë dyfishimin ose trefishimin e shumës totale dhe zbatohen gjithmonë në fund.
Gjeni pozicionin që jep vlerën më të madhe totale të pikëve dhe thoni sa është ajo vlerë.
Referenca: https://www.codechef.com/problems/MAXSCRAB
Shembull
$ cat input.txt
2
10
..d.t.D..d
10 11 12 9 8 10 11 15
22
dtDtTD..ddT.TtTdDT..TD
12297 5077 28888 17998 12125 27400 31219 21536
$ python3 prog.py < input.txt
270
35629632