Because of the weak hash function, this problem can be passed using a simple O(n) solution. So it’s better to select a stronger hash function next time.
2 Likes
Hi,
I think almost all problems that appear on Codechef are pretty hard in general if one does not have the right preparation, or the right amount of training… That is true for me on almost every contest… (my all time best was solving 4 full problems+1 challenge problem)
I also pointed this out to @Suraj, for the short time where I was an editorialist for the lunchtime contests (I hope to be back as a setter around february/March for those who are wondering where I am =)) ) and I also “complained” about how hard these contests are becoming in general (you never wondered why only teams or Google Software Engineers/Algorithms researchers seem to win them? 
) and even for me, it is becoming quite exhausting/demotivating to “insist” on trying to perform well on contests for which I’m simply not made for ^^
Either they plan to form highschool prodigies, or I believe that these kids will get somewhat mindblown or demotivated by how hard these contests are…It’s good to push oneself forward (for me, long contests give me that with DP+Trees problems which I almost never end up solving) but maybe pushing too forward might just make you fall of a cliff 
I don’t mean this for myself nor to scare the pros away from here, but, maybe some adjustment should be considered to all contests to have more…appraochable problems, o at least more problems where one can actually learn by reading some university curriculum or something… The teachers I’ve spoken with at my university would be crushed here 
Best,
Bruno
Like I said above, the problem is me and not the statements…Or the pre-requisites for each problem!!
I believe nobody is born a genius and that most people can be trained and I’m sure that my reality as someone from a country as Portugal where almost no incentive is given to computer programming competitions, is faaaaar different from your realities, possibly being in constant exposure to IOI problems, training for gold in these competitions, writing lots of problems and mastering basic algorithms from an early stage, etc, etc.
I only coded a DFS for the first time 1 year ago (and I’m 24 years old now, how’s that for a late start?). Given this, I am not making that bad of a progress imho, I even managed to solve some cool mathematical problems I’m proud of and definitely learnt a lot since I first came here…
The pre-requisites which you claim are needed to be known by any high school student (DFS Order, LCA, graphs, heavy-light decomposition, FFT, etc) are only thaught at the later years of a Bachelor’s degree here in Portugal or only in Master’s degree (meaning only someone really choosing Algorithms as a subject to master will be exposed to these concepts, so, as you see, this reality of having high school kids crushing everyone really “confuses me” and makes me feel dumb/useless).
I think that some scaling down should be done, according to my own reality, at least.
Instead of having only really, really skilled coders setting problems, I think a platform like Codechef would gain a lot if it had the direct intervention of a group of teachers from several universities (India or outside too) which would scale down the problems to be more suitable for “eager kids wanting to learn more” (or maybe I just don’t want to face the fact that 15 year old kids solved harder problems than I’ll ever solve in my lifetime as a competitor/enthusiast) or at least would follow any university curriculum more closely, I don’t really know or maybe my opinion is biased due to the fact that I’m a “loser”
What do you think? I mean, how did YOU trained for IOI yourself before there was a Codechef? When did you wrote your first DFS? In the end, it’s all up to how trained or smart someone is, but, maybe I would change some things, although I’m totally biased to be discussing this…
It’s just my two cents
1 Like
hi guys,
I solved this problem for all the sub tasks only using pre-processing (but it was after the contest). please see the solution link. I just added the contribution due to ith bit of first string to the final answer in the main loop. Complexity O(n log n).
1 Like
I agree with you completely that difficulty level of some tasks can be degraded.
I also think that lunchtime has small subtasks which are really cakewalk most of the times which makes it a good learning point for beginners. Though it is slightly disappointing for one to not get even one problem accepted. But one will learn a lot by this format and slowly this problem of not getting even one accepted will go away.
Scaling down difficulty level is an important idea and this is why I think codechef introduced subtasks in even long contests.
I would say that though these advance ideas/ algorithms seem complicated, they are actually not that complicated and can be understood by High school students specially people who are preparing for IOI. Many of the big coders learn them mostly in high school.
Personal Experience
Regarding advance algorithms, I feel same as you. I had learned them at my university. I learned C language in my first year at college. I got started with serious algorithmic programming at the end of 2nd year. The advanced topics some of them I have learned in 4th year or so. Still there are a lot of competitive programming algorithm which I don’t know. Also I did not train for IOI as I did not know about it all. I wrote my first dfs program in the summers of 2nd year.
Thank you for sharing your experience
even lucas theorem or most of the modular arithmetic isn’t in the IOI syllabus which was required to solve the second question.
@gdisastery1: Solution for that problem is much more complex by using data structures etc. It is not simple FFT as it is the case here.
@pushkarmishra: Sometimes setters are not from IOI background, I also did not knew IOI syllabus I have notified admins, they have said that it won’t happen again.
1 Like
@dpraveen I have raised this point several times before. I even talked to Anup Kalbalia about this in person. I hope this won’t happen again.
I think that problem difficulty should be increased but there should be easy subtasks that everyone could solve. This way no one will be demotivated and people who want to do hard problems will be satisfied too. Also IOI has much tougher problems so lowering the level of problems is not good.
1 Like
IOI problems are harder? Really? Harder than using FFT? Clearly I’m still just a newbie when it comes to programming competitions… should have started earlier 
Well if someone doesn’t know FFT then obviously not. In IOI you have 5 hours to solve 3 problems and 1-3 people get perfect score out of hundreds. Now consider today’s lunchtime 2 problems required concepts out of the course of IOI to get full marks. Still 8 people got perfect score so I think IOI problems are definitely harder than lunchtime’s
8 people in school*
Well yes, I understand that and I’m not saying otherwise, I’m just commenting that for me, as someone who is not so used to competitive programming and never ever attended IOI, SWERC, whatever, these problems are hard and untangling statements about trees/DP problems when I’ve only been exposed to the basics at university, it’s super hard… Add to that lack of previous experience and time to train and all of a sudden solving 6 problems or 5 problems consistently in the long challenge becomes a real challenge for me
@kuruma: IMHO problems were not that hard, but you needed to know few concepts for solving that (prerequisite for solving the problems was more than expected from high school student)). But I think IOI problems are more harder than codechef lunchtime problems. Codechef has introduced subtasks to make sure every person learns something. So it should be interesting enough for everybody. What change you think can be done?
@dpraveen is right. The questions weren’t tough. Just required prerequisite knowledge of things which are not a part of the IOI syllabus. My IOI experience tells me that IOI problems are certainly longer than the codechef ones. Whether they are tougher, thats a subjective issue. My only request is that please remain within the scope of IOI as far as lunchtimes are concerned.
I also did the same… It works … But this we could do only due to the nature of the hash function. Our solution would fail if the hash function is something more complex.
1 Like
You shouldn’t be proud because you found a wrong way to solve a nice problem!