DMOPC '14 Contest 2 P5 - Sawmill Scheme

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 2.5s
Memory limit: 256M
Authors:
Xyene, FatalEagle
Problem types

Having nearly completed their logging scheme, The Logging Company now wants to ship all logs collected at their logging station to some sawmills in the region. However, shipping logs with trucks costs money which can be better spent elsewhere (like in cutting more trees). To this end, The Company has devised a scheme where they will utilize the region's unique geography and abundant river networks for free shipping.

The geography of the land consists of some lakes and some rivers connecting them. Curiously, the latitudes of all the N (2 \le N \le 1\,000\,000) lakes are unique, and they are numbered from 1 to N from north to south. Even more strange are the facts that all the M (1 \le M \le 2\,000\,000) rivers between lakes only flow south, and there may be multiple rivers between the same two lakes. But thanks to this, logs the Company collects from up north can be moved south to their sawmills, for free!

The Logging Company has strategically built their collection point and sawmills next to lakes, the collection point being next to the lake numbered 1 and one sawmill next to each lake with no river flowing south from it.

The Company has built more than one sawmill because free transportation comes with a degree of unpredictability. At any lake which doesn't have a sawmill next to it, a log may randomly flow down one river that leads south, with all possible southbound rivers being chosen with uniform probability. Knowing this, The Company would like to know how many resources to allocate to each sawmill, based on the probability of a log reaching that sawmill. For this, they've hired you to calculate the probability of a log from the collection point arriving at each sawmill.

Input Specification

First line: two space-separated integers N and M.
Next M lines: two space separated integers i and j (1 \le i < j \le N), representing a river flowing south from lake i to lake j. There will always be at least one river flowing south from lake 1.

Output Specification

For each sawmill, output the probability of a log reaching it as a real number p_i (0 \le p_i \le 1). Your answer will be accepted as correct if it is within an absolute or relative error of no more than 10^{-9}.

Sample Input 1

6 5
1 2
2 3
2 4
4 5
4 6

Sample Output 1

0.5
0.25
0.25

Explanation of Output for Sample Input 1

The given scheme can be represented by the following image.

A log starting at C has a 1/2 chance of going into the sawmill at lake 3, and a 1/4 chance of reaching sawmills at lake 5 or 6.

Sample Input 2

5 4
1 2
1 3
2 4
3 4

Sample Output 2

1
0

Explanation of Output for Sample Input 2

The lake network may be disconnected. In Sample Input 2, lake 5 has no incoming rivers and no outgoing rivers. However, there is a sawmill on lake 5. No wonder the Logging Company is losing money!

Comments


  • 0
    a_sad_javamain  commented on Jan. 6, 2021, 2:23 p.m.

    Can some please check my submission: https://dmoj.ca/src/3269159. It uses the same approach as the editorial but only ACs half the cases.


    • 1
      Plasmatic  commented on Jan. 6, 2021, 2:44 p.m. ← edit 2

      You don't need to toposort. Also, your toposort is wrong since you aren't starting with all nodes with zero indegree


  • 2
    idkanything  commented on Sept. 23, 2020, 2:24 p.m.

    This problem helped me better understand floating-point precision!


  • 0
    julian33  commented on Aug. 15, 2020, 5:05 p.m.

    could someone please check my code? I feel like my solution is correct but I only AC 2 test cases. Also I checked the editorial and my solution is the same as the proposed solution. I must have implemented something wrong


    • 4
      Jonathan_Uy  commented on Aug. 15, 2020, 6:32 p.m. ← edited

      Floats don't have enough accuracy. Changing your dp vector from float to double will make your code AC.


      • 1
        julian33  commented on Aug. 15, 2020, 10:08 p.m.

        Thanks for the help!


  • 2
    rjamieson100  commented on May 24, 2019, 4:57 p.m.

    Hello,

    I'm having trouble optimizing my code. It already seems to resemble the editorial's algorithm. Can anyone please offer a suggestion?

    Thanks


    • 5
      Jonathan_Uy  commented on Sept. 8, 2019, 11:36 p.m. ← edit 2

      Hello,

      The code that you have commented out in your submission is optimized. Make an ArrayList for every lake at the start, instead of checking if it is null and then making one when getting input. When printing output for sawmills, check if ArrayList size is 0 instead of if the ArrayList is null.

      Please visit the DMOJ Discord for further help on problems.

      Hope this helps


  • 1
    alexzhang  commented on July 7, 2018, 2:37 a.m.

    Do the sawmills have to be in any specific order of output?


    • 2
      max  commented on July 7, 2018, 10:19 a.m.

      yes, output the probability of a log reaching the ith sawmill on the ith line


  • 1
    aeternalis1  commented on Aug. 5, 2017, 4:28 p.m. ← edit 4

    Why does my code raise a Value Error? It runs the sample cases just fine, but IRs in several of the test cases.


    • 1
      wleung_bvg  commented on Aug. 5, 2017, 5:06 p.m.

      An integer takes up 4 bytes (on C++ and Java). This means an array of (1e6)^2 will take up 4 TB, which is way over the memory limit. On Python, an integer is as much as 24 bytes.


      • 5
        aeternalis1  commented on Aug. 5, 2017, 5:23 p.m.

        The problems just keep on coming...


  • 4
    anishmahto  commented on Aug. 23, 2016, 3:40 a.m.

    For anyone solving this problem using C++ in the future, if you aren't already, it'll probably be useful to use scanf() AND printf() for this problem. RIP my 1 hour.


  • 1
    Flowright  commented on March 24, 2016, 4:02 a.m.

    This question takes an incredibly long time to judge :<


    • 5
      Xyene  commented on March 24, 2016, 4:23 a.m.

      The problem uses a generator to generate the input cases on the fly. It takes some time for the generator to run for all 10 cases.


  • 2
    minecraftyugi  commented on Jan. 5, 2016, 7:00 p.m.

    Is the output in order of increasing destination lake number?


    • 5
      Xyene  commented on Jan. 5, 2016, 7:34 p.m.

      Yes.


  • 0
    kobortor  commented on Jan. 24, 2015, 4:41 p.m.

    If there are lakes 1 2 and 3, then lake 1 has 2 connections to lake 2 but 1 connection to lake 1, then does lake 2 have 2/3 chance or 1/2 chance.


    • 3
      kobortor  commented on Jan. 24, 2015, 4:42 p.m.

      sorry I meant have lake 1 have 1 connection to lake 3


      • 3
        awaykened  commented on Jan. 24, 2015, 5:08 p.m.

        2/3 assuming connections 1-->2, 1-->2, 1--3