You are not logged in. Please login at www.codechef.com to post your questions!

×

WDTBAM - Editorial

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

This question is marked "community wiki".

asked 04 Oct '15, 04:11

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
accept rate: 0%

edited 15 Jan '16, 13:12

admin's gravatar image

0★admin ♦♦
19.8k350498541


Whats wrong with this code?

link

answered 12 Oct '15, 15:14

vaibhav29498's gravatar image

4★vaibhav29498
312
accept rate: 0%

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

(12 Oct '15, 15:25) dragonemperor3★

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

(12 Oct '15, 20:06) vaibhav294984★

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

link

answered 12 Oct '15, 15:21

thabraze's gravatar image

2★thabraze
1
accept rate: 0%

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

(12 Oct '15, 15:23) sandeep93★

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

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

This gives AC

(12 Oct '15, 15:30) dragonemperor3★

can any body please tell me where my solution is failing

link

answered 12 Oct '15, 18:08

prasadram126's gravatar image

2★prasadram126
121
accept rate: 0%

edited 12 Oct '15, 18:08

@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

(13 Oct '15, 00:04) raunak_parijat4★

@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?

(14 Oct '15, 10:55) prasadram1262★

please check what's wrong with this code my code

link

answered 13 Oct '15, 01:08

anuragkumar33's gravatar image

2★anuragkumar33
1
accept rate: 0%

edited 13 Oct '15, 01:09

@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').

(13 Oct '15, 09:53) eartemov5★

@eartemov thanks a lot for the help

(16 Oct '15, 09:01) anuragkumar332★

can any one tell what's wrong with this code

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

link

answered 13 Oct '15, 19:08

tejaditya_cde's gravatar image

2★tejaditya_cde
1
accept rate: 0%

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.

(13 Oct '15, 19:36) eartemov5★

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

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

link

answered 13 Oct '15, 21:09

aishwarya333's gravatar image

3★aishwarya333
1
accept rate: 0%

And again, for test

3
ABC
ABC
10 100 20 30

answer is 30, not 100.

(13 Oct '15, 21:38) eartemov5★

check this video editorial https://www.youtube.com/watch?v=XT6Pmmi9zBk

link

answered 13 Oct '15, 21:20

ankit15's gravatar image

2★ankit15
412
accept rate: 0%

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

link

answered 13 Oct '15, 23:28

gaurav281195's gravatar image

1★gaurav281195
1
accept rate: 0%

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

link

answered 14 Oct '15, 02:10

amitking's gravatar image

1★amitking
1
accept rate: 0%

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

link

answered 14 Oct '15, 09:23

atulshanbhag's gravatar image

4★atulshanbhag
22629
accept rate: 9%

What is the problem with this solution: https://www.codechef.com/viewsolution/8587753

I tried running it this way: java Codechef< input.txt > output.txt

and had the test case input in input.txt and it runs fine.

link

answered 19 Oct '15, 17:56

ricsr's gravatar image

0★ricsr
1
accept rate: 0%

Hi every one cay any one please tell me whats wrong with this solution? After verifying with setter's solutions i modified my solution which is giving AC ,i got shocked because both solutions are same in perceptive of algorithms .The difference between two solutions are in the first one using one for loop i am checking no.of correct answers and taking input of w's , in the second solution i have separated the above logic into two different for loops , both are doing the same thing then why i got WA for first solution can one please tell me either reason or any test case where it's failling?

link

answered 24 Oct '15, 15:52

prasadram126's gravatar image

2★prasadram126
121
accept rate: 0%

Hi every one cay any one please tell me whats wrong with this solution? After verifying with setter's solutions i modified my solution which is giving AC ,i got shocked because both solutions are same in perceptive of algorithms .The difference between two solutions are in the first one using one for loop i am checking no.of correct answers and taking input of w's , in the second solution i have separated the above logic into two different for loops , both are doing the same thing then why i got WA for first solution can one please tell me either reason or any test case where it's failling?

link

answered 24 Oct '15, 16:28

prasadram126's gravatar image

2★prasadram126
121
accept rate: 0%

Can someone enlighten me as to why my code is not working?

link

answered 14 Nov '15, 00:43

theloneking's gravatar image

0★theloneking
1
accept rate: 0%

I keep on getting WA and SIGSEGV on this code. Can anyone please point out what I'm doing wrong?

this code

link

answered 12 Dec '15, 00:45

yash10p's gravatar image

3★yash10p
21
accept rate: 0%

edited 12 Dec '15, 01:15

WA and I don't know why!! https://www.codechef.com/viewsolution/9015414 Anybody Help

link

answered 25 Dec '15, 17:53

mk95825s's gravatar image

2★mk95825s
1
accept rate: 0%

I am a bit new here and a little help would be greatly appreciated. I tried the below code on Turbo C++, and it worked but here it says wrong answer. Any ideas why that may be?

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

link
This answer is marked "community wiki".

answered 28 Jan '16, 02:07

knewbie's gravatar image

0★knewbie
1
accept rate: 0%

like everyone else: I can't get this to work on the submission. It works on the sample data and I've compared to some of the completed solutions and it looks equivalent to me but I still get a WA.

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

link

answered 02 Feb '16, 23:44

zarquad's gravatar image

0★zarquad
1
accept rate: 0%

Whats the problem in this code? I cant find it :(

link

answered 18 May '16, 22:19

abhishkelohit's gravatar image

0★abhishkelohit
1
accept rate: 0%

T=int(input()) for t in range(0,T): N=int(input()) ca=input() ga=input() count=0 winnings=[] win=list(map(int,input().split())) for i in range(0,len(ca)): if ca[i]==ga[i]: count=count+1 if count==0: print(win[0]) else: for i in range(1,count+1): winnings.append(win[i]) print(max(winnings))

link
This answer is marked "community wiki".

answered 18 May '16, 22:19

abhishkelohit's gravatar image

0★abhishkelohit
1
accept rate: 0%

Whats the problem in this code? I cant find it :(

link

answered 18 May '16, 22:19

abhishkelohit's gravatar image

0★abhishkelohit
1
accept rate: 0%

can any tell whats wrong withthis code am getting correct answer in PC i gave the sample inputs getting same sample output but complilng in CodeChef showing wrong sir.please help me

link
This answer is marked "community wiki".

answered 28 Jun '16, 22:52

vigneshprabha's gravatar image

0★vigneshprabha
1
accept rate: 0%

wikified 28 Jun '16, 22:53

Why goes it give a WA? I'm sure my solution is similar to what the editorial says. https://www.codechef.com/viewsolution/12383128

link

answered 01 Jan '17, 03:05

savage_coder's gravatar image

4★savage_coder
111
accept rate: 0%

Whats wrong with my code https://ideone.com/0Jp7oi

link

answered 07 Nov '18, 00:57

krishyadav007's gravatar image

2★krishyadav007
1197
accept rate: 4%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,688
×968
×103

question asked: 04 Oct '15, 04:11

question was seen: 7,675 times

last updated: 07 Nov '18, 00:57