[Solution] Game of Length solution codechef

CodeChef Starters 15 Division 3 (Rated) - CodeChef

Game of Length solution codechef

Alice and Bob are given an array of length of N. They decide to play a game with it.

Initially, Alice randomly shuffles the array, and then Bob takes N turns. In each turn, Bob chooses an index which he has not already chosen and then Alice reveals the number on that index to Bob. If this number is either the first number to be chosen or strictly larger than previously chosen numbers by Bob then he takes it and adds to his array else he throws it.

You only know the initial unshuffled array and want to know the expected length of Bob’s array at the end of the game.

The final expected length can be represented as a fraction of the form PQ. You are required to print PQ1mod998244353.

Game of Length solution codechef Input Format

  • First line will contain T, number of testcases. Then the testcases follow.
  • Each testcase contains two lines of input.
  • The first line contains N the length of the array.
  • The second line contains N space-separated integers A1,A2,...,ANrepresenting the initial array.

Game of Length solution codechef Output Format

For each testcase, output in a single line the expected length of Bob’s array at the end of the game modulo 998244353.

Game of Length solution codechef Constraints

  • 1T2104
  • 1N5105
  • 1Ai5105
  • Sum of N does not exceeds 5105 over all testcases.

Sample Input 1

4
2
1 2
3
1 2 3
3
1 1 1
3
2 3 2

Sample Output 1

499122178
831870296
1
665496237

Game of Length solution codechef Explanation

Test case 1: The possible final arrays will be [2,1] or [1,2]. If Bob chooses indexes in the order [2,1] then he will end up with 2 elements in the first case and 1 element in the second case, if he chooses indexes in the order [1,2] then he will end up with 1 element in the first case and 2 elements in the case. Hence his probability ending up with 2 elements is 12 and with 1 element is also 12. Hence the final answer will be calculated as 212+112 which is equal to 32.

Test case 2: The probability of Bob ending up with all three elements is 16, the probability that he ends up with any two elements is 12 and the probability that he ends with only a single element is 13. Hence the final answer is calculated as 316+212+113 which is equal to 116.

Test case 3: No matter what index Bob chooses initially he will only end up with 1element in his final array. Hence the final expected value is equal to 1.

Test case 4: The probability of Bob ending up with all three elements is 0, the probability that he ends up with any two elements is 23 and the probability that he ends with only a single element is 13. Hence the final answer is calculated as 223+113 which is equal to 53.


Updating Soon…


Game of Length solution codechef

Counting Tuples codechef solution

 

Leave a Comment