|
|
Very good opportunity to apply Gosper's hack trick. m is number of different colors in the input. Then iterate through all subsets of size k of m. It's really works. But I don't understand why this algo work. Can you explain me? Sort elements by count and use some combinatorics Change the statement, don't be ashamed Could somebody who solved this problem send some examples of tests and solutions? I thought that I wrote a correct algorithm, that summarise number of stones of each type, then sort it and then check how many permutations of the last one that makes it equal to K, there is and calculate a number of possibilities. But I get error on Test 3. Or may be I did not understood the task, I found the bug, but now I get wrong answer for test 26 Finally solved it. The last bug was to find a function that calculates factorial coefficients (ncr) without going to big numbers. What is the principle of this function? Please, somebody, give the 4th test Notice that k maybe be bigger than n. please change the wording of the statement: "there should be at most k Rocks of pairwise different colors among the Rocks taken from the Cave" would be much better read if it is changed to "there should be at most k Rocks of different colors among the Rocks taken from the Cave." in other words, the word 'pairwise' should be removed to make the statement clear. Edited by author 14.01.2015 05:20 Edited by author 14.01.2015 05:21 Could someone please explain me what does phrase "Rocks of pairwise different colors" mean? I assume that in second example the only possible set of Rocks is "ababa", but I can see there 6 pairs of Rocks with different colors. The only possible match to the samples I can see is if you could pick a set of Rocks with at most k different colors, but I don't think it is the right meaning of the statement. Update: Yep, my last guess was correct after all. Edited by author 25.12.2014 00:30 Yep, I don't understand the phrase either. Please fix the problem statement. :) |
|
|