Problem S. 147. (November 2020)

S. 147. Subscribers can reach the text of the problem after signing in. The text will be public from November 28, 2020.]

(10 pont)

Deadline expired on December 15, 2020.

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

A feladat megoldható dinamikus programozás segítségével. Minden \(\displaystyle (i,j)\) párra ki kell számolnunk, el lehet-e jutni abba az állapotba, amikor az első program az \(\displaystyle i.\), a második pedig a \(\displaystyle j.\) zárműveletet hajtotta végre utoljára. Az állapot akkor holtpont, ha az \(\displaystyle (i,j)\) állapotba el lehet jutni, de az \(\displaystyle (i,j+1)\) és \(\displaystyle (i+1,j)\) állapotok egyikébe sem. Mivel \(\displaystyle x<10^6\), a lefoglalt zárakat számon tarthatjuk egy megfelelően nagy logikai tömbben.

Ha DP táblát sorfolytonosan töltjük ki, ezt a logikai tömböt minden mezőnél egy helyen kell frissíteni és egy zár lefoglalásához is egy logikai érték frissítése szükséges. Ez tehát nem befolyásolja a futási idő nagyságrendjét.

Komplexitás: \(\displaystyle O(N*M)\)

Statistics:

6 students sent a solution.
10 points:	Horcsin Bálint, Varga 256 Péter.
9 points:	Papp Marcell Miklós.
1 point:	1 student.
0 point:	2 students.

Problems in Information Technology of KöMaL, November 2020