BekzhanKassenov's blog

By BekzhanKassenov, 11 years ago, translation, In English

Hello everyone!

Topcoder SRM 586 will take place today, at 12.00 EDT.

Let's discuss problems here after the contest.

GL & HF

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

»
11 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Great contest, interesting tasks. :-)
EDIT
By the way, can someone explain me 1000 problem DIV2? Thanks

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If the length of the string is at most 26, we can build a string using each letter only once. If the length is more than 26, we should use all the letters and always put all occurrences of a letter next to each other. The answer can be calculated using dynamic programming.

  • »
    »
    11 years ago, # ^ |
    Rev. 5   Vote: I like it +1 Vote: I do not like it

    For L <= 26:

    The answer is 26*..*(26-L+1), since we have 26 letters for the first choice, 25 for the second one, etc. The minimum weight of a word is 0.

    For L > 26:

    First of all, we should use each letter at least once (since we could easily lower the weight using the unused letter). What to do with the remaining L — 26 choices? Actually, it doesn't matter which letter we pick for each of these choices, since, as long as all occurrences of a letter are next to each other, they contribute to weight identically. For example, if we already have AAB (for simplicity assume that A and B are the only letters in the alphabet) picking A and forming AAAB, or picking B and forming AABB adds the same weight (+1). So we have L — 26 "balls", and we need to distribute them to 26 "urns". The number of ways to do that is
    C[balls+urns-1][urns-1] = C[L-26+26-1][26-1] = C[L-1][25]. Also, we can arbitrarily rearrange groups of identical letters, and the answer becomes
    C[L-1][25] * 26!. The minimum weight of a word is L — 26.

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      You can calculate answer for second case much easier. Look:

      C[L — 1][25] * 26! = (L — 1)! / (25! * (L — 1 — 25!)) * 26! = (L — 1) ! / (L — 26)! * 26 = (L — 1) * (L — 2) * ... * (L — 25) * 26;

      It means, that you don't need calculate C — just use one loop.

»
11 years ago, # |
  Vote: I like it +22 Vote: I do not like it