## DMOPC '14 Contest 2 P5 - Sawmill Scheme

View as PDF

Points: 10 (partial)
Time limit: 2.5s
Memory limit: 256M

Authors:
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 lakes are unique, and they are numbered from to from north to south. Even more strange are the facts that all the 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 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 and .
Next lines: two space separated integers and , representing a river flowing south from lake to lake . There will always be at least one river flowing south from lake .

#### Output Specification

For each sawmill, output the probability of a log reaching it as a real number . Your answer will be accepted as correct if it is within an absolute or relative error of no more than .

#### 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 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!

• 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.

• 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

• commented on Jan. 6, 2021, 3:09 p.m.

Thanks!

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

This problem helped me better understand floating-point precision!

• 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

• 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.

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

Thanks for the help!

• 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

• 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

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

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

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

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

• 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.

• 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.

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

The problems just keep on coming...

• 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.

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

This question takes an incredibly long time to judge :<

• 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.

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

Is the output in order of increasing destination lake number?

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

Yes.

• 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.

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

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

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

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