1203 - K Secv

Enunt

Fie un vector V cu N elemente și un număr K. Vectorul V trebuie împărțit în exact K subsecvențe nevide, astfel încât fiecare element din vector să aparțină exact unei subsecvențe. Această împărțire trebuie făcută astfel încât maximul șmecheriei fiecărei subsecvențe să fie cât mai mic. (Această problemă concepe greșit sistemul de șmecherie și valoare). Șmecheria fiecărei subsecvențe se definește ca fiind parte întreagă din ((Vmax – Vmin + 1) / 2), unde Vmax este valoarea maximă din subsecvență, iar Vmin este valoarea minimă.

Vectorul V de N elemente va fi generat în felul următor: se dă un număr M și 2 vectori A și B de lungime M (indexați de la 0 la M - 1). Fiecare element i, 0 ≤ i < N, din vectorul V va fi calculat cu următoarea formulă: V[i] = (A[i % M] ^ B[i / M]), unde x % y reprezintă restul lui x la împărțirea cu y, x / y reprezintă câtul împărțirii lui x la y și x ^ y reprezintă rezultatul operației xor (sau exclusiv pe biți) dintre x și y.

Date de intrare

Pe prima linie a fișierului ksecv.in se află 3 numere naturale N, K și M, cu semnificația din enunț, separate prin câte un spațiu. Pe a doua linie a fișierului se află M numere naturale separate prin câte un spațiu, reprezentând vectorul A. Pe a treia linie se află M numere naturale separate prin câte un spațiu, reprezentând vectorul B.

Date de ieșire

Pe prima linie a fișierului de ieșire ksecv.out se va afișa cel mai mic număr natural S pentru care vectorul V poate fi împărțit în exact K subsecvențe nevide, fiecare având șmecheria mai mică sau egală cu S.

Restricţii şi precizări

• 1 ≤ N ≤ 1 000 000
• 1 ≤ K ≤ 1 000
• 1 ≤ M ≤ 2 048
• N < M*M
• 1 ≤ K < N
• Valorile vectorilor A și B vor fi din intervalul [0, 260 - 1]
• Fiecare din cele K subsecvențe trebuie să aibă cel puțin un element.
• Pentru 20% din teste N ≤ 100, K ≤ 50.
• Pentru alte 20% din teste N ≤ 100 000, K ≤ 1000.
• Pentru alte 20% din teste N ≤ 1 000 000, K ≤ 50.
• Vectorul V are indicii indexați de la 0 la N - 1.
• Vectorii A și B au indicii indexați de la 0 la M - 1.

Exemplul 1

ksecv.in

 6 3 6
 13 4 6 19 4 10
 0 0 0 0 0 0

ksecv.out

 5

Explicație

Valorile vectorului V sunt 13 4 6 19 4 10.

Dacă împărțim șirul în subsecvențele [0,2] [3,3] [4,5] obținem șmecheriile 5, 0 și 3. Șmecheria maxima este 5.

Nu putem împărți vectorul V astfel încât șmecheria maximă a unei subsecvențe să fie mai mică decât 5.

Exemplul 2

ksecv.in

 6 4 6
 13 4 6 19 4 10
 0 0 0 0 0 0

ksecv.out

3

Explicație

Valorile vectorului V sunt 13 4 6 19 4 10. O posibilă împărțire este: [0,0] [1,2] [3,3] [4,5]. Șmecheriile fiecărei subsecvențe sunt 0, 1, 0 și 3.

Exemplul 3

ksecv.in

 6 3 3
 3 4 2
 4 5 3

ksecv.out

 3

Explicație

Valorile vectorului V sunt 7 0 6 6 1 7.

Dacă împărțim în subsecvențele [0,0] [1,4] [5,5], obținem șmecheriile 0, 3 și 0.

Rezolvare

<syntaxhighlight lang="python" line> def calculate_smek(X):

   return (max(X) - min(X) + 1) // 2

def check_feasibility(N, K, M, A, B, S):

   count = 1
   min_smek = max_smek = calculate_smek([A[i % M] ^ B[i // M] for i in range(N)])

   for i in range(1, N):
       max_smek = max(max_smek, calculate_smek([A[i % M] ^ B[i // M] for i in range(N - i)]))
       if max_smek <= S:
           count += 1

   return count >= K

def binary_search(N, K, M, A, B):

   left = 0
   right = calculate_smek([A[i % M] ^ B[i // M] for i in range(N)])

   while left < right:
       mid = (left + right) // 2
       if check_feasibility(N, K, M, A, B, mid):
           right = mid
       else:
           left = mid + 1

   return left

def main():

   with open("ksecv.in", "r") as fin:
       N, K, M = map(int, fin.readline().split())
       A = list(map(int, fin.readline().split()))
       B = list(map(int, fin.readline().split()))

   with open("ksecv.out", "w") as fout:
       fout.write(str(binary_search(N, K, M, A, B)))

if __name__ == "__main__":

   main()

</syntaxhighlight>