Cześć,
Próbuję rozwiązać to zadanie:
https://www.codechef.com/problems/PALLIND i nic mi do głowy nie przychodzi.
Rozumiem, że x = {1, 2, 3, ..., 25, 26}, a oczekiwana wartość w tym przypadku to będzie coś w stylu E[xi] = xi * P(xi), gdzie xi to i-ty element z x, a funkcja P określa prawdopodobieństwo dla otrzymania palindroma po dodaniu xi elementu. Więc tak na prawdę, główny problem to znaleźć jakie wartości przyjmuje P(xi), a potem zsumuje E[xi].
No ale utknąłem, bo:
Dla 1 operacji, moje prawdopodobieństwo to 26/26, bo 1 znak jest zawsze palindromem.
Dla 2 operacji, moje prawdopodobieństwo to 1/26, bo muszę wylosować ten sam znak co w 1 operacji.
Dla 3 operacji, moje prawdopodobieństwo to 0, bo jeśli mam 2 takie same znaki, to dodając 3 na pewno nie uzyskam palindroma. Tu pojawią się problem, bo jeśli w 2 operacji nie stworzył bym palindroma, to stworzył bym go w 3. Ale jeśli zliczam prawdopodobieństwa dla sukcesu, to nie mogę podążać tą ścieżką (bo niby co miałbym wpisać w 2? 0 byłoby nieprawdą, a 25/26 jest prawdopodobieństwem dla porażki), więc ignoruję tę możliwość.
Dla 4 operacji, jeśli zliczam nastawiam się na sukcesy, to obecny string wygląda w stylu "aab", więc muszę dodać b żeby dostać palindrom, czyli prawdopodobieństwo to 1/26.
Widzę więc, intuicyjnie, że dla nieparzystego xi funkcja P(xi) = 0, a dla reszty przyjmie 1/26. No ale kolejny problem, bo jeśli mam dane N, to skąd mam wiedzieć jakie xi używać? W sensie, że np. jeśli N = 2, to mam liczyć oczekiwaną wartość dla 21 i 22, czy może dla 0 i 1, a może dla 3 i 4 albo dla 10 i 11? Albo lepszy przykład, jeśli N > 26, to jakie xi używać?
Jak podejść do tego zadanka? Gdzie popełniam błąd?