BekzhanKassenov's blog

Topcoder SRM 586
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

→ Reply
  • »
    »
    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.

    → Reply
  • »
    »
    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.

    → Reply
    • »
      »
      »
      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.

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

Editorial

→ Reply