Problem 45470. Count the number of reaction chains achievable in T mins

Created by Karl Ezra Pilario

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This problem is related to Problem</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"45467\"><w:r><w:t>45467</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Let's denote a list of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> compounds as 1, 2, ...,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t>. You are then given a list of valid reactions for converting one compound to another (e.g. 1 --&gt; 2), as well as the time it takes to complete them (</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>completion time</w:t></w:r><w:r><w:t> ). With this information, we can generate</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>reaction chains</w:t></w:r><w:r><w:t>. A reaction chain is a series of valid reaction steps taken one after the other. Examples are given below:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[Given N = 4 and the following valid reactions:\nReaction 1: 1 --> 2 takes 1.5 mins\nReaction 2: 1 --> 3 takes 2.5 mins \nReaction 3: 2 --> 3 takes 0.6 mins\nReaction 4: 3 --> 4 takes 4.1 mins \nReaction 5: 4 --> 2 takes 3.2 mins\nSample reaction chains: 1 --> 3 --> 4 takes (2.5 + 4.1) mins\n 1 --> 2 --> 3 --> 4 takes (1.5 + 0.6 + 4.1) mins \n 4 --> 2 --> 3 takes (3.2 + 0.6) mins]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note that conversion reactions can only move forward. But if the list states that converting to and from the same two compounds is possible, then a reaction chain can take only one of these paths.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your task is this: Given a starting compound</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>S</w:t></w:r><w:r><w:t>, can you count how many reaction chains are possible</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>whose total completion time does not exceed</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> </w:t></w:r><w:r><w:rPr><w:b/><w:i/></w:rPr><w:t>T</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> mins</w:t></w:r><w:r><w:t>?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note that if multiple valid reaction steps are possible between two compounds (e.g. \"1 --&gt; 2 takes 1.5 mins\" and \"1 --&gt; 2 takes 2.5 mins\" both appear in the list), then reaction chains that take either of these paths are distinct. Lastly, for this problem, reaction chains must not contain duplicate compounds; otherwise, they become \"cycles\" rather than \"chains\".</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The inputs to this problem are</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>S</w:t></w:r><w:r><w:t>, and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>T</w:t></w:r><w:r><w:t>. The meanings of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>S</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>T</w:t></w:r><w:r><w:t> are given above. Variable</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t> is a 3-column matrix containing the list of valid reaction steps at each row</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>\"Reaction</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>:</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>1</w:t></w:r><w:r><w:t>) --&gt;</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>2</w:t></w:r><w:r><w:t>) takes</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>3</w:t></w:r><w:r><w:t>) mins\"</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output the required number of reaction chains. You are ensured that:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>T</w:t></w:r><w:r><w:t> are integers satisfying: 2 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> &lt;= 20 and 1 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>T</w:t></w:r><w:r><w:t> &lt;= 100.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>S</w:t></w:r><w:r><w:t> and all elements in the first 2 columns of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t> are integers within [1,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t>].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Completion times are decimal numbers within (0,10].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Each compound 1, ...,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> is mentioned at least once in</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>. Hence,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> can be inferred from matrix</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The following sample test case is the one illustrated above:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[>> R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];\n>> reaction_chain2(R,1,5)\nans = \n 3\n>> reaction_chain2(R,1,10)\nans = \n 6]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In this example, all the reaction chains starting from Compound 1 are:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[(1.50 mins) 1 --> 2\n(2.10 mins) 1 --> 2 --> 3\n(6.20 mins) 1 --> 2 --> 3 --> 4\n(2.50 mins) 1 --> 3\n(6.60 mins) 1 --> 3 --> 4\n(9.80 mins) 1 --> 3 --> 4 --> 2]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This problem is related to Problem <a href = "45467">45467</a>.Let's denote a list of N compounds as 1, 2, ..., N. You are then given a list of valid reactions for converting one compound to another (e.g. 1 --&gt; 2), as well as the time it takes to complete them ( completion time ). With this information, we can generate reaction chains. A reaction chain is a series of valid reaction steps taken one after the other. Examples are given below:<pre class="language-matlab">Given N = 4 and the following valid reactions:
Reaction 1: 1 --&gt; 2 takes 1.5 mins
Reaction 2: 1 --&gt; 3 takes 2.5 mins 
Reaction 3: 2 --&gt; 3 takes 0.6 mins
Reaction 4: 3 --&gt; 4 takes 4.1 mins 
Reaction 5: 4 --&gt; 2 takes 3.2 mins
Sample reaction chains: 1 --&gt; 3 --&gt; 4 takes (2.5 + 4.1) mins
 1 --&gt; 2 --&gt; 3 --&gt; 4 takes (1.5 + 0.6 + 4.1) mins 
 4 --&gt; 2 --&gt; 3 takes (3.2 + 0.6) mins
</pre>Note that conversion reactions can only move forward. But if the list states that converting to and from the same two compounds is possible, then a reaction chain can take only one of these paths.Your task is this: Given a starting compound S, can you count how many reaction chains are possible whose total completion time does not exceed T mins?Note that if multiple valid reaction steps are possible between two compounds (e.g. "1 --&gt; 2 takes 1.5 mins" and "1 --&gt; 2 takes 2.5 mins" both appear in the list), then reaction chains that take either of these paths are distinct. Lastly, for this problem, reaction chains must not contain duplicate compounds; otherwise, they become "cycles" rather than "chains".The inputs to this problem are R, S, and T. The meanings of S and T are given above. Variable R is a 3-column matrix containing the list of valid reaction steps at each row i:"Reaction i: R( i, 1) --&gt; R( i, 2) takes R( i, 3) mins"Output the required number of reaction chains. You are ensured that:<ul><li>N and T are integers satisfying: 2 &lt;= N &lt;= 20 and 1 &lt;= T &lt;= 100.</li><li>S and all elements in the first 2 columns of R are integers within [1, N].</li><li>Completion times are decimal numbers within (0,10].</li><li>Each compound 1, ..., N is mentioned at least once in R. Hence, N can be inferred from matrix R.</li></ul>The following sample test case is the one illustrated above:<pre class="language-matlab">&gt;&gt; R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];
&gt;&gt; reaction_chain2(R,1,5)
ans = 
 3
&gt;&gt; reaction_chain2(R,1,10)
ans = 
 6
</pre>In this example, all the reaction chains starting from Compound 1 are:<pre class="language-matlab">(1.50 mins) 1 --&gt; 2
(2.10 mins) 1 --&gt; 2 --&gt; 3
(6.20 mins) 1 --&gt; 2 --&gt; 3 --&gt; 4
(2.50 mins) 1 --&gt; 3
(6.60 mins) 1 --&gt; 3 --&gt; 4
(9.80 mins) 1 --&gt; 3 --&gt; 4 --&gt; 2
</pre>

Solve

Solution Stats

8 Solutions
8 Solvers

Last Solution submitted on Aug 04, 2020

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Problem Tags

Problem 45470. Count the number of reaction chains achievable in T mins

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author19

Problem Tags

Problem 45470. Count the number of reaction chains achievable in T mins

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author19

Problem Tags

Players