LGSEG - Editorial

editorial
, , , ,
21

No
consider n = 5 , k = 1 , s = 7
5 2 3 1 1

according to your solution
( 5 2 ) ( 3 1 1 ) → 3
but we will be get max ans if we choose i = 2
(5 ) ( 2 3 1 1 ) → 4

In short you will have to check from each i

22

This could have also been solved in O(N) time. No need for binary lifting

23

it is too difficult for a division 3 candidate to understand the solution…seen its explaintory video also but it is difficult to understand.
if u can explain it in some easier manner!

24

How ??

25

Don’t even attempt this problem as a Div3 participant. I didn’t learn binary lifting until 1800 on CodeForces/1900 on CodeChef. It’s quite a rare topic and actually relies on understanding bitwise operations and DP, and is practically useless unless you have at least some a bit above average observation ability. So anyone below 4* will struggle to comprehend the whole idea/is wasting their time attempting to figure it out. Instead try solving some simpler problems and learn the most common thinking process ideas and later come back to the harder problems that involve some bit more advanced algorithm such as this one.

5 Likes
26

CodeChef: Practical coding for everyone could someone please explain why this returns TLE in one of the testcase? I believe my logic to be similar to what is posted here. thanks in advance.

27

and if there’s an edge case which is causing the TLE, how to treat it ?

28

Yeah, I think that is really bad advice, and I’m really surprised it’s coming from someone who is at a decent rating.

29

Use global array as the memory limit is strict for some reason.

30

if you found your mistake , then its not a waste .

31

No that’s not a bad advice at all , He is absolutely correct .

33

I didn’t learn binary lifting until 1800 on CodeForces/1900 on CodeChef.

If you think it is correct to be so rating-oriented and only learn new topics which are “suitable for your rating” - that’s up to you I guess, but I would still call it incorrect.

So anyone below 4* will struggle to comprehend the whole idea/is wasting their time attempting to figure it out.

I think this is a very brazen(euphemism) statement. When you are at an above-average rating, beginners take your words seriously, so we should be really particular about what we say, is what I believe.

1 Like
34

I think I worded my statement poorly, so I’ll try to explain what I mean.

Rating and skill are correlated with each other to some extent (there are many guys at 1600 more skilled than 1800 ones) and those at 2100 more skilled than 2300, because at the end of the day contest performance comes down to luck and whether you’ve previously seen or solve 4-5 specific problems or ideas.

But if you are 2* (Div. 3) in most cases it means you haven’t acquired the experience and intuition needed to attack problems from different directions. Learning an algorithm doesn’t help improve your thinking ability, so instead of focusing on algorithms one should focus on developing their thinking ability. This is done through solving ad-hoc problems, constructive problems, math problems, bitwise operator problems, simple greedy, game theory, etc, as you can get a grasp of what’s going on with only basic/without any prerequisites required. It is more efficient to learn to think this way, as you won’t have to struggle with an overwhelming amount of information on algorithms you don’t know.

So to conclude, you can only benefit from solving a problem, but the amount of information you’ll actually remember and understand is what’s crucial for one’s further success. Some algorithms are too much out of somebody’s comfort zone.

In this case, you should have experience with all the following to fully understand the approach necessary to solve this problem and the idea behind it:

  1. Encounter 50-60 ad-hoc logic-based problems
  2. Encounter 15-20 non-standard DP problems
  3. Encounter ~25 non-trivial greedy problems
  4. Know the idea of binary search (to better understand why binary lifting improves the complexity so much)

So I agree with you that we shouldn’t push newcomers away from learning the algorithms, but they should have at least some experience solving non-trivial problems.

3 Likes
35

Thanks @kingsumaaail , it worked!

36

Yeah, this makes sense. Thanks for the explanation!

I would still disagree with this problem requiring any sort of prior exposure to non-trivial DP or Greedy apart from basic binary search (I feel like, for some reason binary lifting is being shown as much more complex than it actually is; it is trivial binary search), but I guess we all speak from our own learning experiences, so I would agree to disagree with that part!
Thanks again : )

1 Like
37

i wasted 2 hr becoz i didn’t declare the up array globally :frowning:

1 Like
38

oh! my bad thank you very much

39

well thank you! for sharing your experience. Glad you could guide.

40

Thank you…for sharing what you thought was correct for a beginner.

41

Thanks worked for me too! Can you tell how declaring globally is more beneficial ?