Recently I encountered the following problem in the recruitment test for IBM research.
There is an array of size K with elements from 1 to N and an array of size N with elements from 1 to K. Prove that there exists a sub-array of the first array and a sub-array of the second array with the same sum.
I was thinking of applying pigeonhole principle using difference of prefix sums but could not get anything concrete. Any ideas about how to prove this ?
both of them have a sub-array of sum 1
EDIT: just removed an annoyingly large image
There isn't every element presented neccesarily. If N=2, K=5, then arrays can be e.g. {2,2,2,2,2} and {3,5}.
oh
in my defense it wasn't very clearly stated... though I should've figured :face_palm:
Nice problem. It is quite not straightforward, so no shame if you can't solve it. Not going to burn the IBM interview question though, because it is hard to find nice problems like this. Usually interviewers give hints for such hard problems or don't expect the candidate to fully solve it, looking at approaches the candidate tries to use.
http://codeforces.com/contest/618/problem/F
Thank you. Such clever uses of the pigeonhole principle never fail to amaze me.