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 ?

I was recently solving a problem (ongoing contest. Will post the link after the contest ends) where I came up with a DP solution where dp[i][j] only depended on dp[][j-1]. Clearly one of the techniques to handle this type of problems is to use 1D array to compute dp[i] in an iterative manner for space optimization.

However, in the problem I was solving, even using a 2D array for dp[i][j] would not exceed memory limits. So I solved the problem using a 2D array and the verdict was Time Limit Exceeded.

But when I simply changed the 2D array to a 1D array and submitted again, the verdict was Accepted.

Why does changing a 2D array to a 1D array provide time complexity optimization too ?