Search code examples
c++graph-algorithmstl-algorithmnp

When will the residents of N (number of villages) meet again?

So, the problem is a part of a past programming competition paper I came across. Given a number N representing the number of villages around a city-center, the villagers of the first village go to the city every x1 to days to buy their supplies, the villagers of the second village every x2 days etc.. All the villagers met today in the city-center. We are asked to find when the villagers of at least N-1 villages will visit the city-center at the same day again!

EXAMPLES:

EXAMPLE 1:

INPUT 1: 1 2 3 4 5 6 7 8 9 10 -> OUTPUT:360 7 In the above example, all the villagers except those of the 7th village will meet again after 360 days.

EXAMPLE 2:

INPUT: 10 14 15 30 21 5 40 4 8 -> OUTPUT: 840 0 (all the villagers will meet again after 840 days).

EXAMPLE 3:

INPUT:25065 3575 12305 88590 1758 -> OUTPUT: 25845383485350 4 (so after 25845383485350 all the villagers except those of the 4th village will meet again).

Is there a solution approach that does not use recursion? Thanks!

Solution

  • Your problem is essentially the least common multiple. (If the villagers of a city visit every 5 days and they have visited on day 0, they will also visit on days 5, 10, 15, 20... those are clearly multiples.)

    Therefore, a good way to solve this is to split the numbers in prime factors and of each prime factor use the maximally found potency.

    With example 2:

    10, 14, 15, 30, 21, 5, 40, 4, 8 = 2*5, 2*7, 3*5, 2*3*5, 3*7, 5 2^3*5, 2^2, 2^3

    -> taking the maximal potencies: 2^3*3*5*7 = 840

    If you alter the problem to have offsets ("the villagers of village 1 were in the city 10 tens ago"), you could use the chinese remainder theorem, by the way.

    Edit:

    As for the N-1 villages variant, go like that:

    Build the prime factors again but this time, count which potency of which prime number is found how often. Create the maximal potencies again and then iterate through the villages to see how long it would take for the villages to meet ignoring that particular village. Having the count of potency, you can easily see the effect of removing the village.

    I think knowing this idea is enough to write the code, but if you need me to elaborate just say so.

    Elaborating on that one:

    For every prime number, store which potency is found how often.

    With example 2:

    10, 14, 15, 30, 21, 5, 40, 4, 8 = 2*5, 2*7, 3*5, 2*3*5, 3*7, 5 2^3*5, 2^2, 2^3

    • For the 10 = 2*5, we store:
    • 2 has the potencies 1 (x1)

    • 5 has the potencies 1 (x1)

    • For the 14 = 2*7, we update this to:

    • 2 has the potencies 1 (x2)
    • 5 has the potencies 1 (x1)
    • 7 has the potencies 1 (x1)

    -> at the end:

    • 2 has the potencies 1 (x3), 2 (x1), 3 (x2)
    • 3 has the potencies 1 (x3)
    • 5 has the potencies 1 (x5)
    • 7 has the potencies 1 (x2)

    Now we go through the whole list again, take out the current potencies if they are found only once and then see their product. We keep the minimum of this product.

    We initialize the minimum with the whole product, in this case 840.

    • We evaluate 10 = 2*5. Neither the potency 1 of 2 nor the potency 1 of 5 is found only once, so the product stays 840.
    • Same holds for all other numbers, except for the potency 2 of 2, as found in 4 = 2^2
    • But since we also have a potency 3 of 2, that is irrelevant and we stay with our 840.

    Let's make our own example: 72, 74, 75 and 296 = 2^3*3^2 2*37 3*5^2 and 2^3*37

    ->

    • 2 has the potencies 1 (x1), 3 (x2)
    • 3 has the potencies 2 (x1), 5 (x1)
    • 5 has the potencies 2 (x1)
    • 37 has the potencies 1 (x2)

    Until all villages meet again, we have to wait (2^3)(3^5)(5^2)*37 = 1798200 days

    • If we take out the 72, we loose one potency 3 of 2 and one 2 of 3. The first one is irrelevant since it exists more than once, the second is too since there is a higher potency of 3 (^5).
    • If we take out the 74, the same holds
    • If we take out the 75 however, we find that it's potency 2 of 5 is singular and we can take it out. (2^3)*(3^5)*37 = 71928, which is our new minimum
    • The 296 is irrelevant again, since 2^3 is found twice and 37^1 too.

    Thus, we get that the next time that N-1 villages meet is after 71928 days, when everybody but 75 is present.

    Did that help?