PROBLEM LINK:Author: Tuan Anh DIFFICULTY:Hard PREREQUISITES:Fast Fourier Transform, bitwise operations. PROBLEM:Given a binary string A of size N and B of size M. For each substring x of A having length B, you need to find hamming distance between x and B. Hamming distance of the two binary string of the same length is the number of the positions where the two strings have different characters.
QUICK EXPLANATION:Primarily there are three possible solutions depending on the subtasks.
EXPLANATION:Let us start with subtasks in increasing order of difficulty. Subtask 1:As N and M are quite small, we can try all possible substrings x of A having length M and we can find hamming distance between two string x and B. Finding hamming distance between two strings can be done in O(sum of sizes of strings). For finding hamming distance between s and t, we can simply iterate over the string s and count the number of positions where s and t have different characters. Pseudo Code calculateHammingDistance(s, t): ans = 0; for i = 0 to s: if s[i] != t[i]: ans++; return ans; Subtask 2:Strings are binary Strings !!! Use bitwise operations Finding set bits in an integer Time Complexity Subtask 3Represent strings in terms of polynomials
What does hamming distance represent in terms of polynomials? Take string s and t. Reverse the string t. Represent both the strings as polynomials as described above. Let's take an example Note that if both the bits are equal, then product of those is 1 (as 1 * 1 = 1 and 1 * 1 = 1). As we know the number of different bits is precisely hamming distance. We also know that number of equal bits + hamming distance = 3. So solving these two equations, we get hamming distance = 2 and number of equal bits = 1. Complete Solution For each substring, we can get the answer by looking at the corresponding coefficients. Please look into previous example for better understanding. eg.
If A = 0100 and B = 100. Multiplying Two polynomials For understanding FFT, you can use the following links. Time Complexity: Problems to PracticePlease add more problems for practice !! AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:
This question is marked "community wiki".
asked 28 Dec '14, 14:03

Is fast fourier transform even there in the IOI syllabus? I don't think it is. What is the point of setting such a question in a competition meant for kids preparing for IOI? answered 28 Dec '14, 14:14
even lucas theorem or most of the modular arithmetic isn't in the IOI syllabus which was required to solve the second question.
(28 Dec '14, 14:20)
1
@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.
(28 Dec '14, 14:30)
@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.
(28 Dec '14, 14:35)

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. answered 28 Dec '14, 15:07

Like I said above, the problem is me and not the statements...Or the prerequisites 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 prerequisites which you claim are needed to be known by any high school student (DFS Order, LCA, graphs, heavylight 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" :D 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 :) answered 28 Dec '14, 22:22

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? :D ) 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 answered 28 Dec '14, 19:04
1
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.
(28 Dec '14, 19:10)
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 :p
(28 Dec '14, 19:20)
Well if someone doesn't know FFT then obviously not. In IOI you have 5 hours to solve 3 problems and 13 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
(28 Dec '14, 19:25)
8 people in school*
(28 Dec '14, 19:26)
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
(28 Dec '14, 19:35)
@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?
(28 Dec '14, 20:30)
@kuruma according to me challenge is the most fun part :)
(28 Dec '14, 21:26)
@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.
(28 Dec '14, 22:25)
showing 5 of 8
show all

hi guys, I solved this problem for all the sub tasks only using preprocessing (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). answered 28 Dec '14, 23:53
1
I also did the same... It works :D .. 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.
(29 Dec '14, 01:29)
You shouldn't be proud because you found a wrong way to solve a nice problem!
(29 Dec '14, 01:35)

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 Thank you for sharing your experience :) answered 29 Dec '14, 15:07

Wonderful problem highlighting a new concept. I think we shouldn't get lost in the quest of "IOI syllabus" so much that we cannot appreciate new challenges. The primary objective here is to learn and enjoy, and in that process win. @pushkarmishra :) answered 28 Dec '14, 16:13
You are correct that we should appreciate new challenges but a contest that is specifically conducted for IOI preparation should stick to the IOI syllabus.
(28 Dec '14, 16:38)
@gkcs That's a frivolous defence at best. Doesn't Codechef have long challenge and Short contest for such things? When something is being organised for a particular purpose, why void that purpose?
(28 Dec '14, 17:14)

What's the difference between this problem and http://codeforces.com/contest/472/problem/G this?
@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.