Yeetzhee SOLUTION KICKSTART ROUND F
Pommel is very bored at home so she has invented a new game involving N dice. Each die has the numbers from 1 to M written on it. Whenever she throws a die, it has an equal probability of landing on each of the M possible values.
Pommel places all the dice in a row. She goes through the dice one at a time from left to right. For each die she rolls, Pommel can either keep the value she rolled and move on to the next die or she can re-roll the die. Pommel can re-roll a die as much as she wants before moving on to the next die.
Once Pommel has gone through all the dice, the game is finished. To determine if she has won, she puts the dice into groups. All dice with the same value are put into the same group. So if she finishes the game with x distinct values, then there will be x groups. These groups of dice are then sorted by number of dice in non-decreasing order.
If the final dice results are [2, 2, 3, 2, 2, 3], the dice would be put into two groups and ordered as follows: [3, 3] and [2, 2, 2, 2].
If the final dice results are [1, 6, 7, 7], the dice would be put into three groups and ordered as follows: , , and [7, 7] (or equivalently, ,  and [7, 7]).
Pommel wins if she finishes the game with exactly K groups, and the i-th group contains exactly Ai dice, for all i.
What is the expected value of the total number of dice rolls it will take Pommel to win the game, assuming she plays optimally to minimize this expected value?
It is guaranteed that for any valid input, it is possible for Pommel to win the game.
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains the integers N, M and K. Then, K lines follow describing the groups she must finish with. The i-th line contains Ai.
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the expected number of times it will take to roll all the dice for Pommel to win the game.
y will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ M.
1 ≤ Ai, for all i.
A1 + A2 + … + AK = N.
Ai ≤ Ai+1, for all i.
Test Set 1
2 ≤ N ≤ 6.
2 ≤ M ≤ 6.
Test Set 2
2 ≤ N ≤ 50.
2 ≤ M ≤ 50.
3 6 2
5 2 1
Case #1: 4.7
Case #2: 9.0
March Long Challenge 2021 Solutions
- An Interesting Sequence ISS SOLUTION
- Tree House THOUSES SOLUTION
- Valid Paths VPATH SOLUTION
- Modular Equation MODEQ SOLUTION
- Tic Tac Toe TCTCTOE SOLUTION
- Xor Equality XOREQUAL SOLUTION
- Golf LKDNGOLF SOLUTION
- Solubility SOLBLTY SOLUTION
April Long Challenge 2021 Solutions
- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution
Codechef Long Challenge Solutions
February Long Challenge 2021
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef
November Challenge 2020 SOLUTION CodeChef
- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID
October Lunchtime 2020 CodeChef SOLUTIONS
- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP
- Top Best Keylogger in Python 3 Make One
- What is Hacking?
- Secrets of the Deep Dark Web
- CODECHEF September Lunchtime 2020 SOLUTIONS
- August Lunchtime 2020 SOLUTIONS
- A. Shandom Ruffle SOLUTION
- B. Pear TreaP SOLUTION
- C. Sneetches and Speeches 3 SOLUTION
- D. The Grim Treaper SOLUTION
- Y. Sneetches and Speeches 1 SOLUTION
- Z. Trick or Treap SOLUTION
- A. Floor Number SOLUTION CODE FORCES
- B. Symmetric Matrix SOLUTION CODE FORCES
- C. Increase and Copy SOLUTION CODE FORCES
- D. Non-zero Segments SOLUTION CODE FORCES
- E. Rock, Paper, Scissors SOLUTION CODE FORCES
- F. Number of Subsequences SOLUTION CODE FORCES
- Chef and Easy Queries SOLUTIONS CHEFEZQ
- Covid Run SOLUTIONS CVDRUN OCTOBER CHALLENGE
- Positive AND SOLUTIONS POSAND
- Replace for X SOLUTIONS REPLESX
- Village Road Network SOLUTIONS VILLNET
- Random Knapsack SOLUTIONS RANDKNAP
- D-Dimensional MST SOLUTIONS DDIMMST
- Compress all Subsegments SOLUTIONS SEGCOMPR
- Adding Squares SOLUTIONS ADDSQURE
- Inversions SOLUTIONS INVSMOD2 OCOTBER CHALLENGE
- Rooted Minimum Spanning Tree SOLUTIONS ROOTMST