What concepts did you learn in the July20 LONG contest? Thank you!

dardev · July 13, 2020, 9:51am

Well, Codechef and Organisers get a LOT of criticism. So I thought why not share some positive thoughts I feel right now.

Thank you Organizers. Thank you Admins.

Chef and Dragons: First time I used Seg Tree with great efficacy in a proper contest. The moment I saw this - I realized that this is a STACK+SegmentTree+Lazy problem. I was half-hearted about attempting the contest but this one drew me in. Thank you for boosting my Segment+Lazy confidence.
Weird Mul: I saw the rolling hash polynomial nature of the problem. I understood modular divisions rather well. I couldn’t solve this problem, but I could see how a given weird multiplication is like a substring.
Expected Repetitions: I couldn’t solve this problem fully, but now I am aware that there exists a thing called Ukkonen suffix tree array. This is what I am going after next.
Kirchoff’s Theorem and how spanning trees can be calculated from a matrix. Didn’t even attempt the problem though.

I now understand string hashing a little better.

dardev · July 13, 2020, 9:54am

This is why, to me, codechef is better than ‘speed programing only’ like codeforces.

If there were only short contests, I would not have to worry about learning about more advanced techniques - since those problems arise only after you have ranked up. A beginner will have to worry about basic DP, basic DS, sorting divide and conquer etc. Codechef Long allows testing upto limit.

Don’t tweak long contest. Don’t stop it. Don’t reduce its time. If you try to study up and solve all problems - 10 days is TOO less. Don’t worry too much about cheaters, let MOSS take out as much as they can.

Cheating can happen in short contests too. Especially in hostels. Especially when friends share a room and divide effort up.

dixith417 · July 13, 2020, 10:02am

What do I have to learn for doctor chef…?

anonym_chef · July 13, 2020, 10:02am

I knew segment trees and lazy . . . But was not able to apply in complex problems and now I am I think will be able to atleast can apply segtrees, thanks to Dragon problem.
I brushed up my Probability concepts too

dardev · July 13, 2020, 10:03am

Observation. And Implementation skills. It was a hard problem. I solved DragonDen First attempt but Dr Chef took more attempts.

knightknight · July 13, 2020, 10:06am

Though I had a partial score for Expected Repetitions ! But I got to know about Z function and KMP pattern matching a little more !
Also for expected spanning trees Kirchoff’s Tree Theorom to calculate number of spanning trees possible using adjacency matrix and degree matrix was a new concept I came to know ! Kudos to setters !

ibrijesh · July 13, 2020, 10:11am

i also learned STACK+SegmentTree+Lazy implementation

dardev · July 13, 2020, 10:12am

Great job.

Stack + Segtree + lazy - I didn’t learn these things in this contest (I learned seg/lazy due to another contest - BACREP).

But this problem was just the right amount of difficulty for me to confidently apply.

dixith417 · July 13, 2020, 10:12am

okay means …nothing like no special DS reqired for this besides STL etc.
Thanks

ibrijesh · July 13, 2020, 10:15am

i want codechef to give more question like these

dardev · July 13, 2020, 10:18am

Questions like these are around in codechef practice and SPOJ. But unless in an actual long contest where time is no excuse, one doesnt roll up sleeves and learn.

i_plusplus · July 13, 2020, 10:34am

From it i learnt to observe and think how can a greedy approach be used in a clever way.

hello_hell · July 13, 2020, 12:05pm

Meet in the middle technique. But I wouldn’t credit codechef for this. here is my comment on codeforces, which I posted after AtCoder’s beginner contest 173. Now I saw that LCMCONST can be solved with this.