Problem S. 145. (September 2020)

S. 145. Subscribers can reach the text of the problem after signing in. The text will be public from September 10, 2020.]

(10 pont)

Deadline expired on October 15, 2020.

Sorry, the solution is available only in Hungarian. Google translation

Horcsin Bálint megoldása:

Tároljuk egy \(\displaystyle map\)-ben vagy \(\displaystyle unordered\_map\)-ben azt, hogy egy adott szöveg hány \(\displaystyle elol_i\) -vel egyezik meg. És tároljuk minden \(\displaystyle i\)-re, hogy \(\displaystyle elol_i\overset{?}{=}hatul_i\).
Ezt követően nézzük végig az összes \(\displaystyle i\)-re, hogy \(\displaystyle hatul_i\) hány \(\displaystyle elol_j\)-vel egyezik meg, és ezek összegezzük, és vonjuk le azokat az eseteket, amire \(\displaystyle elol_i=hatul_i\).
Ha \(\displaystyle map\)-et használunk, akkor a futásidő: \(\displaystyle \mathcal{O}(N*logN*K)\)

Megjegyzés:

A feladat úgy is megoldható, hogy a szavak első és utolsó \(\displaystyle K\) karaktereiből két rendezett listát készítünk és ezeket párhuzamosan végignézzük. Ehhez így nem is kell fejlett adatszerkezet.

Statistics:

18 students sent a solution.
10 points:	Bertalan Dániel László, Horcsin Bálint, Németh Márton, Orosz Réka Ildikó, Szakács Ábel, Tóth 211 Bence, Varga 256 Péter.
9 points:	Szin Attila.
8 points:	1 student.
6 points:	1 student.
3 points:	4 students.
2 points:	3 students.
0 point:	1 student.

Problems in Information Technology of KöMaL, September 2020