Codejam R1B

Today's codejam was excellent. I must say the problems were nice. One easy, one technical where you needed to be careful about a lot of conditions and finally one hard which was quite interesting:

"I have a set of positive integers S. Can you find two non-empty, distinct subsets with the same sum?
Small dataset:  |S|=20. Each number in S will be a positive integer less than 10⁵
Large dataset: |S|=500. Each number in S will be a positive integer less than 10¹²"

I did only manage to solve the easy input. However, asking Misof about the solution, it seems that the trick was to use Birthday paradox. Assuming that the resulting numbers are of size 10¹⁴, it should suffice to generate 10⁷(different) random subsets and we have a collision. I must admit I love that idea. It is so unconventional for a problem in contests such like this to really depend on randomness/probability but here it actually makes sense as the number of random subsets is quite large but we can process ten million random subsets quite fast. Great job, problemsetters!