Największa suma mniejsza niż K
Dzisiaj zajmiemy się następującym problemem rekrutacyjnym: Mamy daną tablicę A[1..N] oraz wartość K. Chcemy znaleźć spójną podtablicę A[i..j] o jak największej sumie, ale mniejszej od K. Zacznijmy od pytania do rekrutera: Kandydat: Czy tablica może zawierać elementy ujemne?Rekruter: Tak. To pytanie wynika z tego, że istnieje algorytm rozwiązujący problem w czasie liniowym dla tablic z […]
Mopadulo
Dzisiaj zajmiemy się rozwiązaniem zadania mopadulo z potyczek algorytmicznych 2021. W zadaniu tym pytają się nas na ile sposobów można podzielić ciąg na spójne fragmenty tak aby suma każdego fragmentu modulo p była parzysta. Dla przykładu dla ciągu [10, 1, 5, 8] i p = 11 są trzy takie podziały: Zacznijmy od przestawienia algorytmu dynamicznego […]