alexkrunker's blog

By alexkrunker, history, 7 weeks ago, In English

We have two arrays: A and B. A has n numbers, B has m numbers. Each of the elements in A are integers in the interval [1,m], while each of the elements in B are integers in the interval [1,n]. Our task is to find a subsequence in A and a subsequence in B such that they have the same sum. By subsequence I mean an array that can be obtained by removing some (but not all, and possibly 0) numbers from the original array. The constraints are: 1<=n,m<=1000000 We have 2.5 seconds and 512 MB. I saw this problem yesterday and I can't get it off my mind. I have thought of a dynamic programming solution but it only works when n and m are smaller than 1000 If you have any ideas or suggestions, please tell me! Note: This problem was given at the second day of IATI Shumen at the junior age group, which was yesterday. I do not know of any place where you can submit your solutions, sorry!

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Probably some pigeonhole similar to 618F - Двойной рюкзак (which is same problem but n = m).