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.

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,

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