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

×

January Challenege Unofficial Editorial

Hey everyone,

I have written a short editorial for first five problems of January challenge.

Link to the editorial

I hope you all find this editorial helpful and please comment if you find anything wrong.

Thanks.

asked 15 Jan '18, 15:23

solo_loser's gravatar image

4★solo_loser
5112
accept rate: 0%

Your editorial is simple..publish editorial for other question if u can..plzz

(15 Jan '18, 16:06) doramon3★

@geforce Yes, there is problem in this approach. Just for example consider the following example :-

3

1 2 3

1 2 3

1 2 3

Then as per this approach max in first list is 3 which will be added to score then since this approach can't find any number greater than previous max (i.e 3) from the second list so it will return -1, but the correct answer is 6 obtained by picking 3 from last list, 2 from second and 1 from first list. I hope this clears your doubt. Happy coding :)

P.S. Do upvote this answer if you found it helpful.

link

answered 15 Jan '18, 16:42

darkhorse_36's gravatar image

4★darkhorse_36
111
accept rate: 0%

@simha I wasn't able to solve it myself, so I can't know for sure but people are saying it uses sos dp : http://codeforces.com/blog/entry/45223

link

answered 15 Jan '18, 19:05

fr4nkesti3n's gravatar image

4★fr4nkesti3n
864
accept rate: 12%

The whole contest was revolving around Dp.. they should do this more, where one or two topics are stressed on more so people can learn better.

(15 Jan '18, 21:55) simha4★

dp and binary search too.

(15 Jan '18, 22:22) abdullah7686★

@solo_loser i have read your approach for MAXIMUM SCORE and you are starting from last list. i have started from 1st list but my solution didn't get AC . i find max in first list add to sum and compare it with second list and find max which is greater then previous max and maximum in second list . if not found then -1. is there any problem in this approach

link

answered 15 Jan '18, 16:23

geforce's gravatar image

2★geforce
496
accept rate: 0%

Yes ! there is a problem in this approach. See this case.

1 2 3 4 3 3 3 3 11 13 13 18 121 131 141 151

In this case your answer will be -1 because after selecting 4 from first list you can't select from second list. So if you start from last list answer will be = 151 + 18 + 3 + 2. I hope it make sense.

(15 Jan '18, 16:33) solo_loser4★

Edited out the comment for clarity.

(15 Jan '18, 16:50) vijju123 ♦♦5★

@solo loser thanks for reply . but if i read the problem statement how can i figure that i have to go in reverse . bcz it says if not possible print -1?? thx in advance

(15 Jan '18, 16:59) geforce2★

Its the trick of the problem @geforce . If you go from back, it becomes a simple iteration. If you go from front, the problem gets more difficult. You will come across many such problems where you need to think a bit on how to easily do the problem.

(15 Jan '18, 21:58) vijju123 ♦♦5★

@geforce it can be figured it out because in problem statement says that you have to print maximum possible score not only maximum score it is depend on test case like.

1 2 3

1 2 3

1 2 3

According to you answer is -1 but here possible maximum score is 6. You had to print that.

link

answered 15 Jan '18, 17:09

chhekur's gravatar image

1★chhekur
233
accept rate: 0%

edited 15 Jan '18, 17:12

I wanted to know the solution to killing monsters and the rest... can anyone help?

link

answered 15 Jan '18, 18:45

simha's gravatar image

4★simha
1525
accept rate: 0%

for MAXSC best approach can be to start form bottom. for example-

3

1 2 3

1 2 3

1 2 3

now find the largest number in the last line, now go to second last line and find the largest number in that line which is smaller than the previous one.

link

answered 16 Jan '18, 15:13

syashra's gravatar image

1★syashra
11
accept rate: 0%

edited 16 Jan '18, 15:14

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,875
×1,424
×191

question asked: 15 Jan '18, 15:23

question was seen: 4,554 times

last updated: 16 Jan '18, 15:14