CD
Забавно
Size: a a a
2020 March 11
KK
Лол а это же линия
Можно и линией
KK
Но мне лень думать
KK
Квадрат вроде очевиден
CD
Можно и линией
Ну там прикол что у тебя \sum dp[x] + dp[n - x - CONST]
CD
Симметричная
CD
Просто сумму делишь на два и это одна и та же сумма
KK
А, ну да, логично
AT
(Околофилософское) Как думаете будет выглядеть решение (за полиномиальное время) задачи из NP (если это возможно)? Может быть кто-то эвристику красивую, но необъяснимую найдёт, но она всегда будет решать за полиномиальное время? Может такое быть?
KK
Просто тупые префикс суммы
A
ну то есть F(N) = sum(по i от 1 до N, F(i-1)+F(N-i-1))/N
CD
Просто тупые префикс суммы
Сумма всех кроме двух последних
KK
CD
а это хорошая рекуррентность должна быть
A
а когда там раскрываем, то там получаются просто суммы всех предыдущих
CD
а, черт, там знаменатель есть
A
не всех, чуть сложнее
CD
ну короче линия у нас есть
CD
(Околофилософское) Как думаете будет выглядеть решение (за полиномиальное время) задачи из NP (если это возможно)? Может быть кто-то эвристику красивую, но необъяснимую найдёт, но она всегда будет решать за полиномиальное время? Может такое быть?
Если речь про NPC, то его не будет
AT
Если речь про NPC, то его не будет
Почему?