### kingofnumbers's blog

By kingofnumbers, history, 23 months ago, ,

Hello CodeForces Community!

We hope you all had a great time participating in November Long Challenge. Now it’s time to buckle up again and compete in November Cook-Off. So hurry up, note down the details and be there. Joining me on the problem setting panel are:

• Problem Setter and Admin: kingofnumbers (Hasan Jaddouh)
• Problem Tester: AmrMahmoud (Amr Mahmoud)
• Problem Editorialist:likecs (Bhuvnesh Jain)
• Russian Translator: CherryTree (Sergey Kulik)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: VNOI Team

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 19th November 2017 (2130 hrs) to 20th November 2017 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: https://www.codechef.com/COOK88

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes:

• Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck! Hope to see you participating!!

UPD: 90 minutes to start!

• +55

 » 23 months ago, # |   0 In Hasan and boring classes, I tried to do DP.DP[i][k] := the number of palindromic string ignoring S[i+1..N-1-i) with k times modifications dp[0][0] = 1; int M = N/2; rep(i, 0, M) rep(k, 0, K + 1){ if (S[i] == S[N - 1 - i]) { dp[i + 1][k] += dp[i][k]; dp[i + 1][k + 2] += dp[i][k] * 25; } else { dp[i + 1][k + 1] += dp[i][k] * 2; dp[i + 1][k + 2] += dp[i][k] * 24; } } This program can be optimized? I didn't come up with any ideas.
•  » » 23 months ago, # ^ |   0 I came to the solution with FFT, but assume that NTT was intended.Just count separately DP_equal, DP_different and DP_same and then multiply those.
•  » » » 23 months ago, # ^ |   +15 FFT is not completely necessary, fixing the number of +1s which happen because of a pair of different characters and then using some partial sums of binomial coefficients is enough.
•  » » » » 23 months ago, # ^ |   0 Interesting — does it still involve several DPs or can be done inplace by prefix sum?
•  » » » » » 23 months ago, # ^ |   +15 No dp, just a bunch of binomial coefficients and powers.
•  » » » » » » 23 months ago, # ^ |   0 Thanks, now I got it.
•  » » 23 months ago, # ^ | ← Rev. 2 →   -22 Thanks, helThazar and Kyoko-chan. I got your solution with the editorial. I missed that each pair in palindromic string is independent. I also want to know whether there is a general technique of optimization for above programs or not.