CCC '20 J2 - Epidemiology

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Python 3 3.0s
Memory limit: 512M

Problem type
Canadian Computing Competition: 2020 Stage 1, Junior #2

People who study epidemiology use models to analyze the spread of disease. In this problem, we use a simple model.

When a person has a disease, they infect exactly R other people but only on the very next day. No person is infected more than once. We want to determine when a total of more than P people have had the disease.

(This problem was designed before the current coronavirus outbreak, and we acknowledge the distress currently being experienced by many people worldwide because of this and other diseases. We hope that including this problem at this time highlights the important roles that computer science and mathematics play in solving real-world problems.)

Input Specification

There are three lines of input. Each line contains one positive integer. The first line contains the value of P. The second line contains N, the number of people who have the disease on Day 0. The third line contains the value of R. Assume that P \le 10^7 and N \le P and R \le 10.

Output Specification

Output the number of the first day on which the total number of people who have had the disease is greater than P.

Sample Input 1

750
1
5

Output for Sample Input 1

4

Explanation of Output for Sample Input 1

The 1 person on Day 0 with the disease infects 5 people on Day 1. On Day 2, exactly 25 other people are infected. On Day 3, exactly 125 other people are infected. A total of 1 + 5 + 25 + 125 + 625 = 781 people have had the disease by the end of Day 4 and 781 > 750.

Sample Input 2

10
2
1

Output for Sample Input 2

5

Explanation of Output for Sample Input 2

There are 2 people on Day 0 with the disease. On each other day, exactly 2 other people are infected. By the end of Day 4, a total of exactly 10 people have had the disease and by the end of Day 5, more than 10 people have had the disease.


Comments


  • 0
    underwriter2coder  commented on Sept. 8, 2022, 6:55 p.m. edited

    Hi! SO, I got this to work once. I wanted to try and write it another way and I am unclear why the input from the 2nd example is not working. Could someone take a look and give me a suggestion? Thanks!


    • 0
      volcano  commented on Sept. 8, 2022, 8:04 p.m.

      In the second example, n=2 (so people & infected are both 2) and r=1.

      Your problem seems to be here:

      people = infected * r

      Multiplying infected (2) with r (1) will result in 2. Therefore, your code loops endlessly for any case with r=1 (since the value of people is not changing). This results in Time Limit Exceeded (TLE) and your submission is wrong.


      • 0
        underwriter2coder  commented on Sept. 9, 2022, 12:26 p.m.

        Thank you very much! I am still learning ( as you can see) :)


        • 0
          volcano  commented on Sept. 9, 2022, 1:10 p.m.

          No problem!

          Btw you could shorten your code like this:

          while people<=p:

          Instead of using a while True loop that breaks when p exceeds people.


  • 0
    shiny_mew  commented on Sept. 5, 2022, 7:27 p.m.

    If the total of infected is greater OR EQUAL to P, then it should output the day. Hope this helps someone lol


  • -1
    sheikhmugees  commented on June 29, 2022, 7:02 a.m.

    If we follow the logic of the sample input 1: then the logic of sample input 2 contradicts the logic of the sample input 1.

    There are 2 infected people on the day 0, and 'each of them' infect 1 (r) more person. So, on day 0, 2 people had the infection so they infected two more people on day 1, and now we have a total of 4 infected people. The next day each of those four infect 4 more people because R == 1. So now we have 8 infected people, on day 2. Now on day 3, those 8 infect 1 person each, and the total infected-person count reached 16 and hence on the third day the condition 16 > 10 (p) holds true.

    Am I missing something?


    • -1
      allanclane  commented on July 12, 2022, 4:14 p.m.

      Your problem is that only the newly infected people infect others on the next day. That is, people are contagious for only one day, so don't continue to infect new people after that. So on day 0, we have 2 infected. They each infect 2 others on day 1, for a total of 4 infected so far, BUT on day 2, only the 2 newly-infected people from day 1 infect others, meaning only 2 people get newly infected. The numbers of the infected add up, but the infected are only contagious for one day, so that's just two more each day (at an R of 1). Hope this helps! Cheers, Allan


  • 1
    HopefulCreator  commented on June 13, 2022, 7:21 p.m.

    How am I supposed to be able to tell where I'm making a mistake if I can't see what the case was I failed on?


  • 14
    Spitfire720  commented on Feb. 21, 2022, 8:10 p.m.

    Only in Canada will you have contest organizers apologize for a pandemic that they didn't know would happen.


    • 8
      thomas_li  commented on Feb. 21, 2022, 8:38 p.m.

      meanwhile USACO made COWVID-19 themed problems


  • 1
    QooModa  commented on Feb. 21, 2022, 4:42 p.m.

    An important lesson I have learned. Don't forget to delete the code you write to check new values.

    I lost half an hour trying to find out why my answer was correct, and then I noticed I had some print statements to check the values.


  • 2
    dchoo333  commented on Oct. 17, 2021, 6:14 a.m. edit 2

    Two questions:

    1. When P = 500000 and and N = 1 and R = 2, what should the output be?

    2. In Sample Input 2, shouldn't the output be 3?

    When a person has a disease, they infect exactly R other people but only on the very next day. No person is infected more than once. We want to determine when a total of more than P people have had the disease.

    On Day 0, 2 people are infected.

    On Day 1, another 2 people are infected. The total amount of people infected now is 4.

    On Day 2, another four people are infected, as there are 4 infected people and they each infect R (1) person. The amount of people now infected is 8.

    Then on Day 3, another 8 people are infected, as there are 8 infected people and they each infect R (1) person. The amount of people infected now is 16.

    Now it is more than 10, so by my calculation it should be 3. I'm probably missing something, could anyone tell me? Thank you very much.

    I think my code kind of stuffs up when R = 1.


    • 1
      maxcruickshanks  commented on Oct. 17, 2021, 7:40 p.m. edited

      A person can only infect another person once and only on the next day.

      On day 0, 2 people are infected.

      On day 1, 2 more people are infected (2 previously infected + 2 currently infected = 4).

      On day 2, 2 more people are infected (4 previously infected + 2 currently infected = 6).

      On day 3, 2 more people are infected (6 previously infected + 2 currently infected = 8).

      On day 4, 2 more people are infected (8 previously infected + 2 currently infected = 10).

      On day 5, 2 more people are infected (10 previously infected + 2 currently infected = 12).

      If you need further help with this question, please join the DMOJ Discord.


    • -1
      d  commented on Oct. 17, 2021, 1:50 p.m.

      When a person has a disease, they infect exactly R other people but only on the very next day.

      This contradicts your explanation of Day 2.


      • 6
        dchoo333  commented on Oct. 23, 2021, 4:04 a.m.

        Thank you for help maxcruickshanks and d.

        For those who are stuck on this problem:

        When a person has a disease, they infect exactly R other people but only on the very next day. No person is infected more than once. We want to determine when a total of more than P people have had the disease.

        I thought originally that ‘they infect exactly R other people but only on the very next day’ meant that they only start infecting others on the very next day and they keep infecting others every day after that. maxcruickshanks’s comment and d’s comment told me that what it really means is that they only infect a person on the next day and stop infecting others once they have infected R people. Bad comprehension by me, so thanks for pointing that out.

        Test your code that it works for test cases when R = 1. Very interesting and challenging problem, 👍 to the creator. I would probably cry if I was taking part in CCC 2020 😂.


  • 0
    nicholas_heaton  commented on July 30, 2021, 8:45 a.m.

    If you try to solve this using the pow() function in python, you will likely get TLE errors. Instead, try to find another way to keep track of current infections and new infections without have to calculate from day 0 to current day for every iteration of the loop.

    Hope this helps someone else.


  • -13
    jbhero  commented on Jan. 22, 2021, 10:39 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -1
      0Power10  commented on July 19, 2021, 3:24 p.m.

      If R is 1 then the code kinda gets messed up i think.


    • 1
      drunkendog  commented on Jan. 26, 2021, 9:31 p.m.

      Switching to PyPy 3 fixed that problem for me, so it might be worth a try in your case


    • 5
      Kirito  commented on Jan. 22, 2021, 11:30 p.m.

      Firstly, the number of lines is a poor indication of runtime. Consider the following program:

      while True:
          pass
      

      it's only 2 lines, but will clearly take longer than the 4-line long program:

      print("That's")
      print("a")
      print("bad")
      print("argument")
      

      Your issue is that Python is quite slow, and might time out if you need to loop for many days. Can you find a way to compute the answer for small values of N and R without looping?


  • 7
    Amateur360  commented on Oct. 9, 2020, 9:53 p.m. edited

    It's a very interesting challenge though.


  • 20
    euphoria  commented on April 3, 2020, 3:59 p.m.

    This question was surprisingly difficult compared to the other questions during this years contest


  • -23
    Jacob_Tian  commented on March 28, 2020, 2:09 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -1
      Boyan  commented on Nov. 24, 2020, 12:36 p.m. edited

      Well, it can be seen as a geometric sequence, where the first term is N, common ratio is R, and the sum of geometric sequence is P. So the second case is the situation which the common ratio is 1, then the total number of people who are infected is N times day = 2 times (5 + 1) = 12. My code has passed and I used the formulas of geometric sequence


    • 9
      ross_cleary  commented on March 28, 2020, 8:16 p.m.

      When someone is infected, they infect R other people ONLY on the very next day, not every day after they are infected.


      • 9
        alihu264  commented on March 29, 2020, 12:22 p.m.

        Kinda doesn't make any sense when you think about it intuitively, but I guess it's what it is.

        Like people don't stop infecting others when they've already infected someone, how would they know?