2 replies to this topic

[geseeker]

Hi guys! I've come across a seemingly easy programming contest problem today, tried solving it all night with no luck, as the problem size can get insanely big and there's a strict time constraint. Here's the problem, hope someone can come up with a quicker solution:

Suppose a forum which numbers its threads(starting from 1) and several robots posting threads to it at regular intervals. The problems is to find out the exact robot who posted a thread with a given number. For example, there are two robots A and B, A begins posting at 1 o'clock and posts a new thread every 3 hours, while B begins posting at 3 o'clock and posts a new thread every 2 hours. Try to find out who will post the thread which is numbered 10. (1 <= number of robots <= 100, and 1 < thread number in question <= one billion)

Well this can seem easy. But if the thread number gets bigger my solution runs too slow. My solution basically is to "follow through" the whole process, but this can run in O(nm) time(n is number of user and m is thread number). As I said there's very strict time constraint, so O(nm) is simply not quick enough.

[manux]

First you need to find how much time it takes for the robots to get to the Nth post, so if you have the 2 robots you gave as examples, their total posting speed is of 5/6 post per hour.
So you can now know approx when the 10th post will be posted, its only a matter of modulo to find out which one might have posted it(just check the exact time and check if the robot you could have posted at this precise time)

[geseeker]

Sounds like a good idea, I'm gonna go figure out the details and see if it works.