January Challenege Unofficial Editorial

editorial
, ,
1

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.

4 Likes
2

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

3

@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

4

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.

5

@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 :slight_smile:

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

1 Like
6

Edited out the comment for clarity.

7

@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

8

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

9

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

10

@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

1 Like
11

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.

12

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.

13

dp and binary search too.

14

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.