Baltic Olympiad in Informatics 2018 - day 1

Start

2018-04-28 07:00 UTC

Baltic Olympiad in Informatics 2018 - day 1

End

2018-04-28 12:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -226 days 0:07:48

Time elapsed

5:00:00

Time remaining

0:00:00

Problem B
Marsboer-DNA

Som du kanskje vet så kan menneskelig DNA representeres som en lang streng over et alfabet på størrelse 4 (A, C, G, T), hvor hvert symbol representerer en forskjellig nukleobase (henholdsvis adenine, cytosine, guanine, og thymine).

For marsboere derimot, så er ting litt annerledes. Forskning utført på en marsboer som NASA har fanget har vist at marsboer-DNA består av hele $K$ forskjellige nukleobaser! Marsboer-DNA kan dermed representeres som en streng over et alfabet med størrelse $K$.

En forskningsgruppe ønsker å utnytte marsboer-DNA til utviklingen av kunstig intelligens og vil i den sammenhengen få tak i en sammenhengende del av DNA strengen til en marsboer. For $R$ av nukleobasene har de spesifisert et minimumsantall av hvor mange instanser av den nukleobasen de trenger i strengen.

Du ønsker å finne den korteste substrengen fra marsboer-DNAet som tilfredstiller kravene til forskningsgruppen.

Input

Første linje inneholder 3 heltall, $N$, $K$, og $R$, som beskriver henholdsvis den totale lengden på marsboerens DNA, størrelsen av alfabetet, og antall nukleobaser som forskerene har spesifisert et minstekrav for antallet av. Disse tilfredsstiller $1 \le R \le K \le N$.

Andre linje inneholder $N$ heltall andskilt med mellomrom, som representerer hele DNA-strengen til marsboeren. Det $i$-te av disse heltallene, $D_ i$, indikerer hvilken nukleobase som er på den $i$-ende posisjonen i DNA-strengen. Nukleobasene er $0$-indekserte. Dvs. $0 \leq D_ i < K$. Hver nukleobase vil opptre minst én gang i DNA strengen.

Hver av de neste $R$ linjene inneholder to heltall $B$ og $Q$ som representerer henholdsvis en nukleobase og dens minste påkrevde antall ($0 \le B < K, 1 \le Q \le N$). Ingen nukleobase vil være nevnt mer enn én gang i disse $R$ linjene.

Output

Skriv ut et enkelt heltall, lengden av den korteste sammenhengende substrengen med DNA som tilfredsstiller forskerenes krav. Dersom ingen slik substreng eksisterer, skriv ut “impossible”.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Limits

1

16

$1 \le N \le 100, R \le 10$

2

24

$1 \le N \le 4\, 000, R \le 10$

3

28

$1 \le N \le 200\, 000, R \le 10$

4

32

$1 \le N \le 200\, 000$

Explanation of Samples

I det første eksempelet så er det tre substrenger av lengde $2$ som inneholder en av hver av nukleobasene 0 og 1 (nemlig “0 1”, “1 0” and “0 1”), men ingen substreng av lengde $1$. Dermed er den korteste lengden $2$.

I det andre eksempelet er den (unike) optimale substrengen “1 3 2 0 1 2 0”.

I det tredje eksempelet så er det ikke nok nukleobaser av type 0.

Sample Input 1 Sample Output 1
5 2 2
0 1 1 0 1
0 1
1 1
2
Sample Input 2 Sample Output 2
13 4 3
1 1 3 2 0 1 2 0 0 0 0 3 1
0 2
2 1
1 2
7
Sample Input 3 Sample Output 3
5 3 1
1 2 0 1 2
0 2
impossible