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

11 Solutions
10 Solvers

Last Solution submitted on Aug 20, 2020

Last 200 Solutions

Problem Comments

Problem Recent Solvers10

Problem Tags

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

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers10

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 Solvers10

Suggested Problems

More from this Author19

Problem Tags

Players