If we want to calculate the minimum length subarray with sum 0, how will we do that in O(n)?
You are talking about problem C from the Codeforces Div. 3 yesterday, aren’t you? 
Let pref(i) be the prefix sum of the first i elements.
A subarray [l, r] sums to 0 if pref(r+1)=pref(l). So we can sweep from left to right, calculate pref, and store the last occurrence of pref in a map (last occurrence since we want the smallest subarray).
Update: I didn’t see O(n), for this you can use unordered_map instead of a regular map.
If all of the elements in the subarray are small (|a[i]| <= c) then | sum of the array | <= cn, so instead of a map we can store an array with size 2c*n+1.
I’ve explained some of my other solutions here if you are interested: Codeforces Round #617 (Div. 3) + Explanations - YouTube
8 Likes
hey it was awesome!! pls do upload videos regularly and i have subscribed 
Yeah! Yeah! Thanks!
wow…yellow in codechef has a doubt(actually asking for algo) about 3rd problem in codeforces div3…
HAIL CODECHEF 
2 Likes
You are really humble
I am a learner. I will be asking doubts and algos even when I become 7 star here and Legendary Grandmaster there. Be it anyone, 1 star to 7 star, I will learn from everyone, and pave my way up.
Regarding codechef*codeforces, platform doesn’t matter to me. CP matters to me. I am performing according to my current skillset. God bless!
8 Likes
what a pity…how can u even deserve yellow when u have doubt in that one…!!!
also u dont even have dare to post the problem link(if u can take things positively…then u would have posted link of div3 contest 3rd problem)…u did not …
but u asked the alggo behind it
there is difference bro…
when 5+* coder gives some tips
everyone follows
when 5+* coder tells his story
everyone listens
when 5+* coder does well
everyone appreciates
when 5+* coder cheats
everyone loses interest
5+* coders are those people everyone wants to become
so sadly…with rise in ratings…there are some expectations upon u…
and sadly u need to fulfill them(otherwise u will be spreading a false message that we dont need to know anything to become 5*…then nobody will learn)
Whether a pity or cheer, doesn’t matter to me. I already said, I am a learner. Regarding “deserve yellow”, I have focus on my karma, I make sure to do it well. Results and rewarding is the work of God. God decides what I deserve, or anyone’s in general.
I saw solutions of others, after contest. But I didn’t think that much. And focused on the approach I tried to work out. It was this same subarray sum 0. So, I thought I uniquely deduced it. So, asked it here, without overthinking or stuff. Yeah!
2 Likes
@hari_2666 tbh you shouldn’t be accusing people like that… if you only look at his color. I was also wondering if this person, who is 5-star, actually asked this question, but I think there are more polite ways to express your doubt, or just don’t say anything at all.
Your other post is even worse, it’s reasonable for a 4-star to not solve that problem because it was not just a bipartite graph problem. One had to observe that the problem could be modeled in terms of graph theory, and the difficulty of the observation was much higher than the difficulty to solve bipartite coloring. Also, it was the 5th-problem in the div 3 round, not the 3rd, which makes the situation more reasonable.
But I was actually curious and looked up @ks3rr 's recent performance in JAN20A, it just seems slightly unusual that he/she was able to solve much harder problems such as CHEFPSA, ENGLISH, and DFMTRX while not knowing the solution to something simple.
I can only say that it is unusual, maybe some people actually do much better in long challenges, or maybe as ks3rr said above, he/she wasn’t thinking when asking the question here.
4 Likes
yes i agree with this
1 Like
exactly sir…thats the issue…
@hari_2666 you mentioned in another thread “indians have so many tricks”
It seems like I don’t know the situation here, I don’t really know why people would cheat in a long challenge when it seems like the only benefit is rating. My best guess is how someone sent me a message saying “sir plz help xxx will only hire me if my rating > y”.
From what you’re saying, it seems like people try so hard to find solutions to ongoing contests when they could spend the time actually improving?
3 Likes
yes that some must be low…sadly its too high in codechef…
atleast one who implemeneted DFMTRX…must not take anytime in implemeenting smallest subarray problem…thats weird
exactly sir…thats the main problem here…many take false routes…only few do on their own…if 1* coder asks its normal (still not ok)…even 4+* coders ask everywhere for test cases and approaches…the position here is so sad
2 Likes
many just brag sir…thats the only thing they need
they can put their performances in resume and can possibly attract interviewers …
u might think the pleasure by cheating is short term and temporory…but thats what people want (like sex which is short term pleasure but everyone goes for it
1 Like
Well, I can only hope that companies stop using rating / online contest performances to measure candidates’ abilities and maybe create their own contest or codechef’s DSA exam (idk how accessible that is to everyone).
To lessen the “unusual”, yes, I too had a “my bad” feeling when I realised that it’s such a easy problem. I actually posted this at night(before going to bed, with drowsiness getting over me), after the contest ended here. So didn’t put much mind to it. I realized it in morning in college, when I simply thought about it. You know sometimes even the greatest can act like dumb at times.
Also, the situation, environment during the contest phase also affects many things.
And yes, I only have recently started giving seriously codeforces contest. Before that I just gave long. I think it will take some time for me to adapt to that. Giving long, I’m like trained that, I can solve the hardest of problems, but-I don’t know-need longer time than mere 3 hours.
But I’m going at it, and surely will adapt to that.
And regarding the “wrong means” stuff, yes I believe that some people(during long) solve in groups like discussing with friends, or maybe god knows what else tricks they might be using.
But as far as I am concerned, I’m all alone working hard day and night. Interviews,jobs,etc. or whatever is not my aim. Its my dream to be a legend in cp. Not just dream. I believe in it. I work for it. And God bless, it will happen.
1 Like
Thanks