### BekzhanKassenov's blog

By BekzhanKassenov, 9 years ago, translation, Hello everyone!

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

Let's discuss problems here after the contest.

GL & HF srm, Comments (6)
 » 9 years ago, # | ← Rev. 3 →   Great contest, interesting tasks. :-) EDIT By the way, can someone explain me 1000 problem DIV2? Thanks
•  » » 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.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   Can you talk more about the DP part? Thanks.
•  » » 9 years ago, # ^ | ← Rev. 5 →   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 isC[balls+urns-1][urns-1] = C[L-26+26-1][26-1] = C[L-1]. Also, we can arbitrarily rearrange groups of identical letters, and the answer becomesC[L-1] * 26!. The minimum weight of a word is L — 26.
•  » » » You can calculate answer for second case much easier. Look:C[L — 1] * 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.
 »