WDTBAM - Editorial

editorial
, , ,
1

Problem Link

Practice

Contest

Difficulty

CakeWalk

Pre-requisites

Basic programming language constructions

Problem

Find the maximal value of the profit for playing a single-player game described in the problem statement

How to get 20 points

Let’s generate all permutations of the order of the questions and calculate the score for each of them. Among the scores for all the orders, choose the maximal. Then just output the maximal obtained score. Since there are exactly N! permutations of the set of N questions and a check of a single order takes O(N) time, the complexity of such a solution is O(N!*N).

In C++ you can use STL routine next_permutation for simple generation of all the permutations.

This solution solves the first subtask, however, it is too slow to get the full points.

How to get 100 points

Let us calculate K - the number of the questions that would be answered correctly by Chef. Clearly, the ith question will be answered correctly if the ith sumbol in the first string equals to the ith symbol in the second string.

If K = N, there is no other option than Chef answers all the questions correctly and gets WN dollars of profit.

Otherwise, using any question than can be answered incorrectly, we can obtain any number of correct answers between 0 and K inclusively. Then the answer is, therefore, the maximal value of Wi for 0 ≤ i ≤ K.

The complexity of such a solution is O(N) for a single test case.

Setter’s Solution:

Can be found here

Tester’s Solution:

Can be found here

2

Whats wrong with this code?

3

I too did the same thing here. But why still my code got WA? https://www.codechef.com/viewsolution/8530210

4

“If K = N, there is no other option than Chef answers all the questions correctly and gets WN dollars of profit.”

5

for (j=0; j<1001; j++)
W[i]=0;

The above line is wrong. make it,

for (j=0; j<1001; j++)
W[j]=0;

This gives 100pts

6

You are not considering the case where all the answers are correct.

Your modified code :
https://www.codechef.com/viewsolution/8530809

This gives AC

7

can any body please tell me where my solution is failing

8

Thanks for pointing it out. Really feeling bad that I missed 80 points due to that! :frowning:

9

@prasadram126 Please change long int to long long int and then try again. The constraints of the problem are such that they need a datatype as large as long long int.
This is the link to your updated solution.
https://www.codechef.com/viewsolution/8535868

10

please check what’s wrong with this code my code

11

@anuragkumar33 I think you need to make arrays A and B a little bit bigger (say, 1010), because string of length N needs N + 1 byte of memory (string itself plus ‘\0’).

12

can any one tell what’s wrong with this code

https://www.codechef.com/viewsolution/8437975

13

If cnt = n, Chef answers all questions correctly and there is no other option than Chef gets W_n dollars of profit, because he can’t leave the game when he wants. For example, for test

3

ABC

ABC

10 100 20 30

answer is 30, not 100.

14

can any one tell what’s wrong with this code?

https://www.codechef.com/viewsolution/8540459

15

check this video editorial

16

And again, for test

3

ABC

ABC

10 100 20 30

answer is 30, not 100.

17

Can anybody tell why my program has not given complete 100 points. where my program lacks.
https://www.codechef.com/viewsolution/8450527

18

Can anyone tell me whats wrong in my code?
https://www.codechef.com/viewsolution/8542452

19

@amitking you get WA because of no newline character at end of each testcase output check this https://www.codechef.com/viewsolution/8543127

20

@raunak_parijat thanks for you help , i have one question, in the problem page value of wi at max 10^9 i have tested my code with 10^9 it’s working fine .So can you please give me any test case where it’s giving WA?