Monday, January 20, 2014

This week in competitive programming

There were no Codeforces or TopCoder rounds this week. However, SnarkNews Winter Series 2014 Round 2 has finished on Wendesday (top 5 on the left, full results), so let me share a nice problem from that round. We want to assign integers starting from 2 to (an infinite amount of) users and groups of users of our service in such a way that:

  • each user is assigned a different positive integer number.
  • each group (set) of at least two users is assigned a positive integer number that is different for all groups and is different from all user's numbers.
  • each integer more than one is assigned to either a user or a group.
  • the number for each group is the product of the numbers of the users in that group.
The problem then asked to find the users belonging to the group with the given number. It did not claim this explicitly, but it implicitly relied on the fact that there's exactly one way to choose which numbers belong to users and which belong to groups so that all above conditions are satisfied. Can you figure it out?

Thanks for reading, and see you next week!

No comments:

Post a Comment