Please look into the solution as i am getting wrong answer
url for the solution:
https://www.codechef.com/viewsolution/15925239
THANKS!!
You missed some parts of question.
Firstly, it asks for maximum amount he can get. For this, imagine the best scenario, where all the questions he know come first. Let their number be K. He can win a prize money which requires \le K correct answers.
Now, it says that, its possible that he can earn more money by answering less number of correct questions. Meaning, it is possible that prize for answering only 2 questions correction is \ge prize for answer 3 questions correctly.
More formally, it is possible that-
Prize for answering 0 Q correctly = 50,000
Prize for answering 1 Q correctly= 10
Prize of answering 2 Q correctly=2000
.
.
.
(Such randomized pattern).
Read the question statement carefully:
Specifically: " Note that the game was invented by a twisted mind, and so a case where Wi ≥ Wi + 1 for some 0 ≤ i ≤ N − 1 is possible. "
If you get the point it’s good, but if you still haven’t figured it out then unhide the hint below:
Click to view
Mistake: You are actually just counting the total number of correct answers and printing the winnings corresponding to those number of correct answers, but this will be a wrong approach.
Failing Test Case:
1
5
ABCDE
ABCDF
5 4 3 2 1 0
In this case your solution will count 4 answers to be correct and output M[4] (i.e. 1), but Maximum can be 5.
How?? Consider while shuffling we get last question as the place of first question which you get wrong, So you will get 0 correct answers (i.e. winning of 5), which gives maximum winning.
So, consider all the winnings possible.
If still have doubt refer the editorial:
https://discuss.codechef.com/questions/75729/wdtbam-editorial
1 Like