kingofnumbers's blog

Invitation to CodeChef November Cook-Off 2017!
By kingofnumbers, history, 7 years ago, In English

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: RetiredAmrMahmoud (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 [email protected])

Good Luck! Hope to see you participating!!

UPD: 90 minutes to start!

  • Vote: I like it
  • +55
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it -22 Vote: I do not like it

    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.

    → Reply