ilość podciągów o sreniej >= P - poziom olimpijski

Question

Witam, mam problem z zadaniem. Ktos ma jakis pomysl na rozwa?

Są wysokie ograniczenia na złoznosc, kombinowalem z backtrackingiem ale O(2^n) to nie jest zadowalające rozwiąznanie. Nie musi byc gotowiec, prosze chociaz o jakis pomysl
PODCIĄGI MAJĄ BYĆ SPÓJNE
Z gory dzieki :)

tresc nizej:

https://ibb.co/rGz2zp0

Comments

może tu coś podobnego

https://www.youtube.com/watch?v=qOHXdhtxyyQ

---

@jjanickij, Powiedziałbyś jakie było rozwiązanie?

Answer 1

Nie jestem pewien czy moje rozwiązanie jest poprawne, ale pomyśl co by było gdybyś podszedł do tego zadania od drugiej strony. Co gdybyś od ilości wszystkich spójnych podciągów odjął ilość spójnych podciągów o średniej mniejszej niż P.

Ilość wszystkich spójnych podciągów obliczymy ze wzoru n*(n+1)/2, natomiast problematyczne jest wyznaczenie podciągów o średniej < P. Mój pomysł jest taki, aby obliczyć to w następujący sposób:

1) od każdej liczby a_i ciągu podanego na wejściu odejmij P, co utworzy nam nowy ciąg, w którym niektóre wartości są ujemne, niektóre dodatnie, a niektóre zerami

2) na podstawie tego ciągu oblicz prefiksy, takie że p[0] = 0, a p[i] (gdzie i > 0) jest równe sumie wszystkich elementów ciągu od a_0 do a_{i-1}

3) teraz znajdź liczbę inwersji w tablicy sum prefiksowych

4) otrzymaną liczbę inwersji odejmij od ilości wszystkich spójnych podciągów i powinieneś otrzymać wynik końcowy

To powinno zadziałać, ale tak jak mówiłem, nie mam co do tego pewności.