{"group":{"id":1,"name":"Community","lockable":false,"created_at":"2012-01-18T18:02:15.000Z","updated_at":"2026-04-06T14:01:22.000Z","description":"Problems submitted by members of the MATLAB Central community.","is_default":true,"created_by":161519,"badge_id":null,"featured":false,"trending":false,"solution_count_in_trending_period":0,"trending_last_calculated":"2026-04-06T00:00:00.000Z","image_id":null,"published":true,"community_created":false,"status_id":2,"is_default_group_for_player":false,"deleted_by":null,"deleted_at":null,"restored_by":null,"restored_at":null,"description_opc":null,"description_html":null,"published_at":null},"problems":[{"id":45470,"title":"Count the number of reaction chains achievable in T mins","description":"This problem is related to Problem \u003c45467\u003e.\r\n\r\nLet'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 --\u003e 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:\r\n\r\n  Given N = 4 and the following valid reactions:\r\n  Reaction 1:    1 --\u003e 2 takes 1.5 mins\r\n  Reaction 2:    1 --\u003e 3 takes 2.5 mins \r\n  Reaction 3:    2 --\u003e 3 takes 0.6 mins\r\n  Reaction 4:    3 --\u003e 4 takes 4.1 mins \r\n  Reaction 5:    4 --\u003e 2 takes 3.2 mins\r\n  Sample reaction chains: 1 --\u003e 3 --\u003e 4         takes (2.5 + 4.1) mins\r\n                          1 --\u003e 2 --\u003e 3 --\u003e 4   takes (1.5 + 0.6 + 4.1) mins \r\n                          4 --\u003e 2 --\u003e 3         takes (3.2 + 0.6) mins\r\n\r\nNote 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.\r\n\r\nYour 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_? \r\n\r\nNote that if multiple valid reaction steps are possible between two compounds (e.g. \"1 --\u003e 2 takes 1.5 mins\" and \"1 --\u003e 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\". \r\n\r\nThe 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_: \r\n\r\n\"Reaction _i_: *R*( _i_, _1_) --\u003e *R*( _i_, _2_) takes *R*( _i_, _3_) mins\"\r\n\r\nOutput the required number of reaction chains. You are ensured that:\r\n\r\n* *N* and *T* are integers satisfying: 2 \u003c= *N* \u003c= 20 and 1 \u003c= *T* \u003c= 100.\r\n* *S* and all elements in the first 2 columns of *R* are integers within [1, *N*].\r\n* Completion times are decimal numbers within (0,10].\r\n* Each compound 1, ..., *N* is mentioned at least once in *R*. Hence, *N* can be inferred from matrix *R*.\r\n\r\nThe following sample test case is the one illustrated above:\r\n\r\n  \u003e\u003e R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];\r\n  \u003e\u003e reaction_chain2(R,1,5)\r\n  ans = \r\n       3\r\n\u003e\u003e reaction_chain2(R,1,10)\r\n  ans = \r\n       6\r\n\r\n\r\nIn this example, all the reaction chains starting from Compound 1 are:\r\n\r\n  (1.50 mins) 1 --\u003e 2\r\n  (2.10 mins) 1 --\u003e 2 --\u003e 3\r\n  (6.20 mins) 1 --\u003e 2 --\u003e 3 --\u003e 4\r\n  (2.50 mins) 1 --\u003e 3\r\n  (6.60 mins) 1 --\u003e 3 --\u003e 4\r\n  (9.80 mins) 1 --\u003e 3 --\u003e 4 --\u003e 2\r\n","description_html":"\u003cp\u003eThis problem is related to Problem \u003ca href = \"45467\"\u003e45467\u003c/a\u003e.\u003c/p\u003e\u003cp\u003eLet's denote a list of \u003cb\u003eN\u003c/b\u003e compounds as 1, 2, ..., \u003cb\u003eN\u003c/b\u003e. You are then given a list of valid reactions for converting one compound to another (e.g. 1 --\u0026gt; 2), as well as the time it takes to complete them ( \u003ci\u003ecompletion time\u003c/i\u003e ). With this information, we can generate \u003ci\u003ereaction chains\u003c/i\u003e. A reaction chain is a series of valid reaction steps taken one after the other. Examples are given below:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003eGiven N = 4 and the following valid reactions:\r\nReaction 1:    1 --\u0026gt; 2 takes 1.5 mins\r\nReaction 2:    1 --\u0026gt; 3 takes 2.5 mins \r\nReaction 3:    2 --\u0026gt; 3 takes 0.6 mins\r\nReaction 4:    3 --\u0026gt; 4 takes 4.1 mins \r\nReaction 5:    4 --\u0026gt; 2 takes 3.2 mins\r\nSample reaction chains: 1 --\u0026gt; 3 --\u0026gt; 4         takes (2.5 + 4.1) mins\r\n                        1 --\u0026gt; 2 --\u0026gt; 3 --\u0026gt; 4   takes (1.5 + 0.6 + 4.1) mins \r\n                        4 --\u0026gt; 2 --\u0026gt; 3         takes (3.2 + 0.6) mins\r\n\u003c/pre\u003e\u003cp\u003eNote 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.\u003c/p\u003e\u003cp\u003eYour task is this: Given a starting compound \u003cb\u003eS\u003c/b\u003e, can you count how many reaction chains are possible \u003ci\u003ewhose total completion time does not exceed \u003cb\u003eT\u003c/b\u003e mins\u003c/i\u003e?\u003c/p\u003e\u003cp\u003eNote that if multiple valid reaction steps are possible between two compounds (e.g. \"1 --\u0026gt; 2 takes 1.5 mins\" and \"1 --\u0026gt; 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\".\u003c/p\u003e\u003cp\u003eThe inputs to this problem are \u003cb\u003eR\u003c/b\u003e, \u003cb\u003eS\u003c/b\u003e, and \u003cb\u003eT\u003c/b\u003e. The meanings of \u003cb\u003eS\u003c/b\u003e and \u003cb\u003eT\u003c/b\u003e are given above. Variable \u003cb\u003eR\u003c/b\u003e is a 3-column matrix containing the list of valid reaction steps at each row \u003ci\u003ei\u003c/i\u003e:\u003c/p\u003e\u003cp\u003e\"Reaction \u003ci\u003ei\u003c/i\u003e: \u003cb\u003eR\u003c/b\u003e( \u003ci\u003ei\u003c/i\u003e, \u003ci\u003e1\u003c/i\u003e) --\u0026gt; \u003cb\u003eR\u003c/b\u003e( \u003ci\u003ei\u003c/i\u003e, \u003ci\u003e2\u003c/i\u003e) takes \u003cb\u003eR\u003c/b\u003e( \u003ci\u003ei\u003c/i\u003e, \u003ci\u003e3\u003c/i\u003e) mins\"\u003c/p\u003e\u003cp\u003eOutput the required number of reaction chains. You are ensured that:\u003c/p\u003e\u003cul\u003e\u003cli\u003e\u003cb\u003eN\u003c/b\u003e and \u003cb\u003eT\u003c/b\u003e are integers satisfying: 2 \u0026lt;= \u003cb\u003eN\u003c/b\u003e \u0026lt;= 20 and 1 \u0026lt;= \u003cb\u003eT\u003c/b\u003e \u0026lt;= 100.\u003c/li\u003e\u003cli\u003e\u003cb\u003eS\u003c/b\u003e and all elements in the first 2 columns of \u003cb\u003eR\u003c/b\u003e are integers within [1, \u003cb\u003eN\u003c/b\u003e].\u003c/li\u003e\u003cli\u003eCompletion times are decimal numbers within (0,10].\u003c/li\u003e\u003cli\u003eEach compound 1, ..., \u003cb\u003eN\u003c/b\u003e is mentioned at least once in \u003cb\u003eR\u003c/b\u003e. Hence, \u003cb\u003eN\u003c/b\u003e can be inferred from matrix \u003cb\u003eR\u003c/b\u003e.\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe following sample test case is the one illustrated above:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003e\u0026gt;\u0026gt; R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];\r\n\u0026gt;\u0026gt; reaction_chain2(R,1,5)\r\nans = \r\n     3\r\n\u0026gt;\u0026gt; reaction_chain2(R,1,10)\r\nans = \r\n     6\r\n\u003c/pre\u003e\u003cp\u003eIn this example, all the reaction chains starting from Compound 1 are:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003e(1.50 mins) 1 --\u0026gt; 2\r\n(2.10 mins) 1 --\u0026gt; 2 --\u0026gt; 3\r\n(6.20 mins) 1 --\u0026gt; 2 --\u0026gt; 3 --\u0026gt; 4\r\n(2.50 mins) 1 --\u0026gt; 3\r\n(6.60 mins) 1 --\u0026gt; 3 --\u0026gt; 4\r\n(9.80 mins) 1 --\u0026gt; 3 --\u0026gt; 4 --\u0026gt; 2\r\n\u003c/pre\u003e","function_template":"function y = reaction_chain2(R,S,T)\r\n  y = T;\r\nend","test_suite":"%%\r\nfiletext = fileread('reaction_chain2.m')\r\nassert(isempty(strfind(filetext, 'rand')))\r\nassert(isempty(strfind(filetext, 'fileread')))\r\nassert(isempty(strfind(filetext, 'assert')))\r\nassert(isempty(strfind(filetext, 'echo')))\r\n%%\r\nR = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];\r\nassert(isequal(reaction_chain2(R,1,5),3))\r\nassert(isequal(reaction_chain2(R,1,10),6))\r\n%%\r\nR = [2 1 1.5592;1 2 2.4465;7 6 5.9819;7 6 1.9563;5 7 4.9169; ...\r\n9 10 2.6206;9 10 3.6554;10 9 6.9576;2 1 1.5000;2 13 9.0677; ...\r\n13 2 7.3477;4 5 8.9883;5 4 7.8082;6 5 0.7312;10 8 2.5875; ...\r\n8 9 4.9516;10 9 3.9300;12 1 0.0830;1 12 9.7302;13 12 6.0841; ...\r\n3 5 0.0807;3 5 5.3663;4 5 2.4256;7 9 0.1973;7 9 8.2272; ...\r\n8 9 1.6038;11 12 8.2550;13 11 1.9458;13 11 1.3879;2 4 9.8468; ...\r\n3 2 4.8237;2 3 5.5103;7 6 9.9712;7 8 5.0623;7 6 8.8766; ...\r\n11 12 4.6054;10 12 1.0703;10 12 5.3461;3 2 5.4698;1 2 5.6282; ...\r\n2 1 2.9354;7 6 1.5597;6 5 8.5908;5 7 7.9862;9 11 5.0525; ...\r\n9 11 3.1038;11 10 2.6583];\r\nassert(isequal(reaction_chain2(R,4,100),1966))\r\nassert(isequal(reaction_chain2(R,2,3),3))\r\nassert(isequal(reaction_chain2(R,1,20),74))\r\n%%\r\nR = [3 2 8.2070;2 1 1.0576;5 6 4.3201;5 6 1.1111;6 7 5.3338; ...\r\n11 10 9.7877;10 11 5.9987;9 10 4.3743;14 13 2.7591;13 15 8.6333; ...\r\n14 13 5.6640;17 18 1.6193;17 1 2.8767;17 18 6.9178;4 3 5.6304; ...\r\n4 3 4.3412;5 4 0.5619;9 8 9.5380;9 7 0.0224;9 8 7.1412; ...\r\n11 13 2.7473;11 12 0.6646;12 11 1.2049;17 15 8.9250;16 15 3.4592; ...\r\n17 15 0.4951;1 2 4.0666;1 2 0.5611;2 3 6.7063;6 5 2.7088; ...\r\n5 7 7.1288;5 6 0.6856;11 9 4.1500;11 10 5.9775;9 10 8.3965; ...\r\n15 14 7.5966;14 15 4.1755;14 13 8.3002;1 18 5.0146;1 17 9.7139; ...\r\n17 18 0.2792;3 5 5.4500;5 3 2.3200;5 3 8.7088;7 8 4.0699; ...\r\n8 7 1.8611;9 8 7.8793;13 11 7.7952;11 13 5.4524;13 12 1.3119];\r\nassert(isequal(reaction_chain2(R,16,30),42))\r\nassert(isequal(reaction_chain2(R,16,20),9))\r\nassert(isequal(reaction_chain2(R,16,10),1))\r\n%%\r\nR = [2 3 3.1864;3 2 4.9359;1 2 7.7339;5 1 5.2448;2 5 1.3431; ...\r\n4 1 4.8876;4 1 9.5712;4 1 2.6840;4 3 0.0273;5 4 1.7028; ...\r\n5 4 5.2548;3 2 4.2046;3 4 8.6170;3 4 9.1101;2 1 3.3861];\r\nassert(isequal(reaction_chain2(R,1,20),8))\r\nassert(isequal(reaction_chain2(R,3,11),14))\r\nassert(isequal(reaction_chain2(R,3,12),18))\r\nassert(isequal(reaction_chain2(R,3,13),20))\r\nassert(isequal(reaction_chain2(R,3,14),23))\r\nassert(isequal(reaction_chain2(R,3,15),24))\r\nassert(isequal(reaction_chain2(R,3,100),44))\r\n%%\r\nR = [4 16 0.4237;2 9 0.0306;8 11 0.6388;1 13 0.1693;2 16 0.3843; ...\r\n8 6 0.5554;6 7 0.3490;17 7 0.1930;17 6 0.5509;17 2 0.2577; ...\r\n8 11 0.8995;4 18 0.4340;15 10 0.3313;8 13 0.9162;17 3 0.1199; ...\r\n17 12 0.0403;10 17 0.3857;6 5 0.2009;7 11 0.2684;12 15 0.1040; ...\r\n14 12 0.4747;17 2 0.5991;5 1 0.5799;16 11 0.8399;4 12 0.1740; ...\r\n6 1 0.7015;18 14 0.7567;10 6 0.2449;6 18 0.2307;10 4 0.4340; ...\r\n3 7 0.7936;15 17 0.5404;15 13 0.0432;3 5 0.2467;4 5 0.2755; ...\r\n18 7 0.2973;8 6 0.7573;7 3 0.6172;16 9 0.0776;17 6 0.6139; ...\r\n12 4 0.9600;12 10 0.8690;11 1 0.4827;15 14 0.5723;1 13 0.4494; ...\r\n12 14 0.8047;1 15 0.5674;2 5 0.1335;11 10 0.0689;18 5 0.3155; ...\r\n6 1 0.5279;5 8 0.9475;17 3 0.5919];\r\nassert(isequal(reaction_chain2(R,9,100),0))\r\nassert(isequal(reaction_chain2(R,3,100),3812))\r\nassert(isequal(reaction_chain2(R,3,1),4))\r\nassert(isequal(reaction_chain2(R,3,2),42))\r\n%%\r\nR = [1 2 5;1 2 9];\r\nassert(isequal(reaction_chain2(R,1,10),2))\r\nassert(isequal(reaction_chain2(R,2,10),0))\r\n%%\r\nR = [3 1 9.1338;2 1 2.7850;1 2 9.6489;5 2 9.5717;1 2 1.4189; ...\r\n5 1 7.9221;1 5 0.3571;5 4 7.0605;3 5 6.9483;3 5 0.3445; ...\r\n5 3 4.8976;4 2 6.7970;3 2 1.1900;3 4 3.4039;2 1 7.5127; ...\r\n1 2 6.9908;3 1 8.1428;5 2 3.4998;5 2 7.5373];\r\nassert(isequal(reaction_chain2(R,4,7),1))\r\nassert(isequal(reaction_chain2(R,1,5),3))\r\n%%\r\nR = [3 1 3.9978;1 3 4.3141;7 5 2.6380;7 6 3.5095;5 6 0.4965; ...\r\n10 9 7.8025;10 9 4.0391;1 10 0.5978;3 4 8.2119;4 5 6.4775; ...\r\n5 3 6.8678;7 8 6.2562;9 7 9.2939;9 8 4.3586;2 1 5.0851; ...\r\n2 3 7.9483;3 2 6.2248;6 5 3.0125;6 5 8.4431];\r\nassert(isequal(reaction_chain2(R,2,23),21))\r\nassert(isequal(reaction_chain2(R,2,25),25))\r\n%%\r\nR = [1 2 3.1110;3 2 1.8482;6 5 6.0284;7 5 1.1742;6 5 2.6248; ...\r\n11 9 9.2885;11 10 5.7853;9 10 9.6309;13 15 9.1329;15 13 2.6187; ...\r\n14 15 1.3655;4 2 6.5376;3 4 7.1504;4 2 0.3054;8 7 4.7992; ...\r\n8 7 6.1767;6 7 1.6793;11 10 6.8197;10 12 8.1755;12 10 6.5961; ...\r\n15 1 6.4899;1 15 4.3239];\r\nassert(isequal(reaction_chain2(R,3,30),4))\r\nassert(isequal(reaction_chain2(R,12,30),1))\r\nassert(isequal(reaction_chain2(R,6,30),4))\r\n\r\n","published":true,"deleted":false,"likes_count":4,"comments_count":0,"created_by":255320,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":15,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2020-04-21T14:15:20.000Z","updated_at":"2025-12-04T23:53:49.000Z","published_at":"2020-04-21T14:15:20.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"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\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThis problem is related to Problem\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"45467\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e45467\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eLet's denote a list of\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e compounds as 1, 2, ...,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e. You are then given a list of valid reactions for converting one compound to another (e.g. 1 --\u0026gt; 2), as well as the time it takes to complete them (\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ecompletion time\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e ). With this information, we can generate\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ereaction chains\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e. A reaction chain is a series of valid reaction steps taken one after the other. Examples are given below:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[Given N = 4 and the following valid reactions:\\nReaction 1:    1 --\u003e 2 takes 1.5 mins\\nReaction 2:    1 --\u003e 3 takes 2.5 mins \\nReaction 3:    2 --\u003e 3 takes 0.6 mins\\nReaction 4:    3 --\u003e 4 takes 4.1 mins \\nReaction 5:    4 --\u003e 2 takes 3.2 mins\\nSample reaction chains: 1 --\u003e 3 --\u003e 4         takes (2.5 + 4.1) mins\\n                        1 --\u003e 2 --\u003e 3 --\u003e 4   takes (1.5 + 0.6 + 4.1) mins \\n                        4 --\u003e 2 --\u003e 3         takes (3.2 + 0.6) mins]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eNote 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.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eYour task is this: Given a starting compound\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eS\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e, can you count how many reaction chains are possible\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ewhose total completion time does not exceed\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eT\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e mins\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e?\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eNote that if multiple valid reaction steps are possible between two compounds (e.g. \\\"1 --\u0026gt; 2 takes 1.5 mins\\\" and \\\"1 --\u0026gt; 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\\\".\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThe inputs to this problem are\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eS\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e, and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eT\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e. The meanings of\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eS\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eT\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e are given above. Variable\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e is a 3-column matrix containing the list of valid reaction steps at each row\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\\\"Reaction\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e(\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e1\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e) --\u0026gt;\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e(\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e2\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e) takes\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e(\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e3\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e) mins\\\"\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eOutput the required number of reaction chains. You are ensured that:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eT\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e are integers satisfying: 2 \u0026lt;=\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u0026lt;= 20 and 1 \u0026lt;=\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eT\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u0026lt;= 100.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eS\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and all elements in the first 2 columns of\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e are integers within [1,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e].\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eCompletion times are decimal numbers within (0,10].\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eEach compound 1, ...,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e is mentioned at least once in\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e. Hence,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e can be inferred from matrix\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThe following sample test case is the one illustrated above:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[\u003e\u003e R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];\\n\u003e\u003e reaction_chain2(R,1,5)\\nans = \\n     3\\n\u003e\u003e reaction_chain2(R,1,10)\\nans = \\n     6]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eIn this example, all the reaction chains starting from Compound 1 are:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[(1.50 mins) 1 --\u003e 2\\n(2.10 mins) 1 --\u003e 2 --\u003e 3\\n(6.20 mins) 1 --\u003e 2 --\u003e 3 --\u003e 4\\n(2.50 mins) 1 --\u003e 3\\n(6.60 mins) 1 --\u003e 3 --\u003e 4\\n(9.80 mins) 1 --\u003e 3 --\u003e 4 --\u003e 2]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"problem_search":{"errors":[],"problems":[{"id":45470,"title":"Count the number of reaction chains achievable in T mins","description":"This problem is related to Problem \u003c45467\u003e.\r\n\r\nLet'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 --\u003e 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:\r\n\r\n  Given N = 4 and the following valid reactions:\r\n  Reaction 1:    1 --\u003e 2 takes 1.5 mins\r\n  Reaction 2:    1 --\u003e 3 takes 2.5 mins \r\n  Reaction 3:    2 --\u003e 3 takes 0.6 mins\r\n  Reaction 4:    3 --\u003e 4 takes 4.1 mins \r\n  Reaction 5:    4 --\u003e 2 takes 3.2 mins\r\n  Sample reaction chains: 1 --\u003e 3 --\u003e 4         takes (2.5 + 4.1) mins\r\n                          1 --\u003e 2 --\u003e 3 --\u003e 4   takes (1.5 + 0.6 + 4.1) mins \r\n                          4 --\u003e 2 --\u003e 3         takes (3.2 + 0.6) mins\r\n\r\nNote 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.\r\n\r\nYour 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_? \r\n\r\nNote that if multiple valid reaction steps are possible between two compounds (e.g. \"1 --\u003e 2 takes 1.5 mins\" and \"1 --\u003e 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\". \r\n\r\nThe 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_: \r\n\r\n\"Reaction _i_: *R*( _i_, _1_) --\u003e *R*( _i_, _2_) takes *R*( _i_, _3_) mins\"\r\n\r\nOutput the required number of reaction chains. You are ensured that:\r\n\r\n* *N* and *T* are integers satisfying: 2 \u003c= *N* \u003c= 20 and 1 \u003c= *T* \u003c= 100.\r\n* *S* and all elements in the first 2 columns of *R* are integers within [1, *N*].\r\n* Completion times are decimal numbers within (0,10].\r\n* Each compound 1, ..., *N* is mentioned at least once in *R*. Hence, *N* can be inferred from matrix *R*.\r\n\r\nThe following sample test case is the one illustrated above:\r\n\r\n  \u003e\u003e R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];\r\n  \u003e\u003e reaction_chain2(R,1,5)\r\n  ans = \r\n       3\r\n\u003e\u003e reaction_chain2(R,1,10)\r\n  ans = \r\n       6\r\n\r\n\r\nIn this example, all the reaction chains starting from Compound 1 are:\r\n\r\n  (1.50 mins) 1 --\u003e 2\r\n  (2.10 mins) 1 --\u003e 2 --\u003e 3\r\n  (6.20 mins) 1 --\u003e 2 --\u003e 3 --\u003e 4\r\n  (2.50 mins) 1 --\u003e 3\r\n  (6.60 mins) 1 --\u003e 3 --\u003e 4\r\n  (9.80 mins) 1 --\u003e 3 --\u003e 4 --\u003e 2\r\n","description_html":"\u003cp\u003eThis problem is related to Problem \u003ca href = \"45467\"\u003e45467\u003c/a\u003e.\u003c/p\u003e\u003cp\u003eLet's denote a list of \u003cb\u003eN\u003c/b\u003e compounds as 1, 2, ..., \u003cb\u003eN\u003c/b\u003e. You are then given a list of valid reactions for converting one compound to another (e.g. 1 --\u0026gt; 2), as well as the time it takes to complete them ( \u003ci\u003ecompletion time\u003c/i\u003e ). With this information, we can generate \u003ci\u003ereaction chains\u003c/i\u003e. A reaction chain is a series of valid reaction steps taken one after the other. Examples are given below:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003eGiven N = 4 and the following valid reactions:\r\nReaction 1:    1 --\u0026gt; 2 takes 1.5 mins\r\nReaction 2:    1 --\u0026gt; 3 takes 2.5 mins \r\nReaction 3:    2 --\u0026gt; 3 takes 0.6 mins\r\nReaction 4:    3 --\u0026gt; 4 takes 4.1 mins \r\nReaction 5:    4 --\u0026gt; 2 takes 3.2 mins\r\nSample reaction chains: 1 --\u0026gt; 3 --\u0026gt; 4         takes (2.5 + 4.1) mins\r\n                        1 --\u0026gt; 2 --\u0026gt; 3 --\u0026gt; 4   takes (1.5 + 0.6 + 4.1) mins \r\n                        4 --\u0026gt; 2 --\u0026gt; 3         takes (3.2 + 0.6) mins\r\n\u003c/pre\u003e\u003cp\u003eNote 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.\u003c/p\u003e\u003cp\u003eYour task is this: Given a starting compound \u003cb\u003eS\u003c/b\u003e, can you count how many reaction chains are possible \u003ci\u003ewhose total completion time does not exceed \u003cb\u003eT\u003c/b\u003e mins\u003c/i\u003e?\u003c/p\u003e\u003cp\u003eNote that if multiple valid reaction steps are possible between two compounds (e.g. \"1 --\u0026gt; 2 takes 1.5 mins\" and \"1 --\u0026gt; 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\".\u003c/p\u003e\u003cp\u003eThe inputs to this problem are \u003cb\u003eR\u003c/b\u003e, \u003cb\u003eS\u003c/b\u003e, and \u003cb\u003eT\u003c/b\u003e. The meanings of \u003cb\u003eS\u003c/b\u003e and \u003cb\u003eT\u003c/b\u003e are given above. Variable \u003cb\u003eR\u003c/b\u003e is a 3-column matrix containing the list of valid reaction steps at each row \u003ci\u003ei\u003c/i\u003e:\u003c/p\u003e\u003cp\u003e\"Reaction \u003ci\u003ei\u003c/i\u003e: \u003cb\u003eR\u003c/b\u003e( \u003ci\u003ei\u003c/i\u003e, \u003ci\u003e1\u003c/i\u003e) --\u0026gt; \u003cb\u003eR\u003c/b\u003e( \u003ci\u003ei\u003c/i\u003e, \u003ci\u003e2\u003c/i\u003e) takes \u003cb\u003eR\u003c/b\u003e( \u003ci\u003ei\u003c/i\u003e, \u003ci\u003e3\u003c/i\u003e) mins\"\u003c/p\u003e\u003cp\u003eOutput the required number of reaction chains. You are ensured that:\u003c/p\u003e\u003cul\u003e\u003cli\u003e\u003cb\u003eN\u003c/b\u003e and \u003cb\u003eT\u003c/b\u003e are integers satisfying: 2 \u0026lt;= \u003cb\u003eN\u003c/b\u003e \u0026lt;= 20 and 1 \u0026lt;= \u003cb\u003eT\u003c/b\u003e \u0026lt;= 100.\u003c/li\u003e\u003cli\u003e\u003cb\u003eS\u003c/b\u003e and all elements in the first 2 columns of \u003cb\u003eR\u003c/b\u003e are integers within [1, \u003cb\u003eN\u003c/b\u003e].\u003c/li\u003e\u003cli\u003eCompletion times are decimal numbers within (0,10].\u003c/li\u003e\u003cli\u003eEach compound 1, ..., \u003cb\u003eN\u003c/b\u003e is mentioned at least once in \u003cb\u003eR\u003c/b\u003e. Hence, \u003cb\u003eN\u003c/b\u003e can be inferred from matrix \u003cb\u003eR\u003c/b\u003e.\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe following sample test case is the one illustrated above:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003e\u0026gt;\u0026gt; R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];\r\n\u0026gt;\u0026gt; reaction_chain2(R,1,5)\r\nans = \r\n     3\r\n\u0026gt;\u0026gt; reaction_chain2(R,1,10)\r\nans = \r\n     6\r\n\u003c/pre\u003e\u003cp\u003eIn this example, all the reaction chains starting from Compound 1 are:\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003e(1.50 mins) 1 --\u0026gt; 2\r\n(2.10 mins) 1 --\u0026gt; 2 --\u0026gt; 3\r\n(6.20 mins) 1 --\u0026gt; 2 --\u0026gt; 3 --\u0026gt; 4\r\n(2.50 mins) 1 --\u0026gt; 3\r\n(6.60 mins) 1 --\u0026gt; 3 --\u0026gt; 4\r\n(9.80 mins) 1 --\u0026gt; 3 --\u0026gt; 4 --\u0026gt; 2\r\n\u003c/pre\u003e","function_template":"function y = reaction_chain2(R,S,T)\r\n  y = T;\r\nend","test_suite":"%%\r\nfiletext = fileread('reaction_chain2.m')\r\nassert(isempty(strfind(filetext, 'rand')))\r\nassert(isempty(strfind(filetext, 'fileread')))\r\nassert(isempty(strfind(filetext, 'assert')))\r\nassert(isempty(strfind(filetext, 'echo')))\r\n%%\r\nR = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];\r\nassert(isequal(reaction_chain2(R,1,5),3))\r\nassert(isequal(reaction_chain2(R,1,10),6))\r\n%%\r\nR = [2 1 1.5592;1 2 2.4465;7 6 5.9819;7 6 1.9563;5 7 4.9169; ...\r\n9 10 2.6206;9 10 3.6554;10 9 6.9576;2 1 1.5000;2 13 9.0677; ...\r\n13 2 7.3477;4 5 8.9883;5 4 7.8082;6 5 0.7312;10 8 2.5875; ...\r\n8 9 4.9516;10 9 3.9300;12 1 0.0830;1 12 9.7302;13 12 6.0841; ...\r\n3 5 0.0807;3 5 5.3663;4 5 2.4256;7 9 0.1973;7 9 8.2272; ...\r\n8 9 1.6038;11 12 8.2550;13 11 1.9458;13 11 1.3879;2 4 9.8468; ...\r\n3 2 4.8237;2 3 5.5103;7 6 9.9712;7 8 5.0623;7 6 8.8766; ...\r\n11 12 4.6054;10 12 1.0703;10 12 5.3461;3 2 5.4698;1 2 5.6282; ...\r\n2 1 2.9354;7 6 1.5597;6 5 8.5908;5 7 7.9862;9 11 5.0525; ...\r\n9 11 3.1038;11 10 2.6583];\r\nassert(isequal(reaction_chain2(R,4,100),1966))\r\nassert(isequal(reaction_chain2(R,2,3),3))\r\nassert(isequal(reaction_chain2(R,1,20),74))\r\n%%\r\nR = [3 2 8.2070;2 1 1.0576;5 6 4.3201;5 6 1.1111;6 7 5.3338; ...\r\n11 10 9.7877;10 11 5.9987;9 10 4.3743;14 13 2.7591;13 15 8.6333; ...\r\n14 13 5.6640;17 18 1.6193;17 1 2.8767;17 18 6.9178;4 3 5.6304; ...\r\n4 3 4.3412;5 4 0.5619;9 8 9.5380;9 7 0.0224;9 8 7.1412; ...\r\n11 13 2.7473;11 12 0.6646;12 11 1.2049;17 15 8.9250;16 15 3.4592; ...\r\n17 15 0.4951;1 2 4.0666;1 2 0.5611;2 3 6.7063;6 5 2.7088; ...\r\n5 7 7.1288;5 6 0.6856;11 9 4.1500;11 10 5.9775;9 10 8.3965; ...\r\n15 14 7.5966;14 15 4.1755;14 13 8.3002;1 18 5.0146;1 17 9.7139; ...\r\n17 18 0.2792;3 5 5.4500;5 3 2.3200;5 3 8.7088;7 8 4.0699; ...\r\n8 7 1.8611;9 8 7.8793;13 11 7.7952;11 13 5.4524;13 12 1.3119];\r\nassert(isequal(reaction_chain2(R,16,30),42))\r\nassert(isequal(reaction_chain2(R,16,20),9))\r\nassert(isequal(reaction_chain2(R,16,10),1))\r\n%%\r\nR = [2 3 3.1864;3 2 4.9359;1 2 7.7339;5 1 5.2448;2 5 1.3431; ...\r\n4 1 4.8876;4 1 9.5712;4 1 2.6840;4 3 0.0273;5 4 1.7028; ...\r\n5 4 5.2548;3 2 4.2046;3 4 8.6170;3 4 9.1101;2 1 3.3861];\r\nassert(isequal(reaction_chain2(R,1,20),8))\r\nassert(isequal(reaction_chain2(R,3,11),14))\r\nassert(isequal(reaction_chain2(R,3,12),18))\r\nassert(isequal(reaction_chain2(R,3,13),20))\r\nassert(isequal(reaction_chain2(R,3,14),23))\r\nassert(isequal(reaction_chain2(R,3,15),24))\r\nassert(isequal(reaction_chain2(R,3,100),44))\r\n%%\r\nR = [4 16 0.4237;2 9 0.0306;8 11 0.6388;1 13 0.1693;2 16 0.3843; ...\r\n8 6 0.5554;6 7 0.3490;17 7 0.1930;17 6 0.5509;17 2 0.2577; ...\r\n8 11 0.8995;4 18 0.4340;15 10 0.3313;8 13 0.9162;17 3 0.1199; ...\r\n17 12 0.0403;10 17 0.3857;6 5 0.2009;7 11 0.2684;12 15 0.1040; ...\r\n14 12 0.4747;17 2 0.5991;5 1 0.5799;16 11 0.8399;4 12 0.1740; ...\r\n6 1 0.7015;18 14 0.7567;10 6 0.2449;6 18 0.2307;10 4 0.4340; ...\r\n3 7 0.7936;15 17 0.5404;15 13 0.0432;3 5 0.2467;4 5 0.2755; ...\r\n18 7 0.2973;8 6 0.7573;7 3 0.6172;16 9 0.0776;17 6 0.6139; ...\r\n12 4 0.9600;12 10 0.8690;11 1 0.4827;15 14 0.5723;1 13 0.4494; ...\r\n12 14 0.8047;1 15 0.5674;2 5 0.1335;11 10 0.0689;18 5 0.3155; ...\r\n6 1 0.5279;5 8 0.9475;17 3 0.5919];\r\nassert(isequal(reaction_chain2(R,9,100),0))\r\nassert(isequal(reaction_chain2(R,3,100),3812))\r\nassert(isequal(reaction_chain2(R,3,1),4))\r\nassert(isequal(reaction_chain2(R,3,2),42))\r\n%%\r\nR = [1 2 5;1 2 9];\r\nassert(isequal(reaction_chain2(R,1,10),2))\r\nassert(isequal(reaction_chain2(R,2,10),0))\r\n%%\r\nR = [3 1 9.1338;2 1 2.7850;1 2 9.6489;5 2 9.5717;1 2 1.4189; ...\r\n5 1 7.9221;1 5 0.3571;5 4 7.0605;3 5 6.9483;3 5 0.3445; ...\r\n5 3 4.8976;4 2 6.7970;3 2 1.1900;3 4 3.4039;2 1 7.5127; ...\r\n1 2 6.9908;3 1 8.1428;5 2 3.4998;5 2 7.5373];\r\nassert(isequal(reaction_chain2(R,4,7),1))\r\nassert(isequal(reaction_chain2(R,1,5),3))\r\n%%\r\nR = [3 1 3.9978;1 3 4.3141;7 5 2.6380;7 6 3.5095;5 6 0.4965; ...\r\n10 9 7.8025;10 9 4.0391;1 10 0.5978;3 4 8.2119;4 5 6.4775; ...\r\n5 3 6.8678;7 8 6.2562;9 7 9.2939;9 8 4.3586;2 1 5.0851; ...\r\n2 3 7.9483;3 2 6.2248;6 5 3.0125;6 5 8.4431];\r\nassert(isequal(reaction_chain2(R,2,23),21))\r\nassert(isequal(reaction_chain2(R,2,25),25))\r\n%%\r\nR = [1 2 3.1110;3 2 1.8482;6 5 6.0284;7 5 1.1742;6 5 2.6248; ...\r\n11 9 9.2885;11 10 5.7853;9 10 9.6309;13 15 9.1329;15 13 2.6187; ...\r\n14 15 1.3655;4 2 6.5376;3 4 7.1504;4 2 0.3054;8 7 4.7992; ...\r\n8 7 6.1767;6 7 1.6793;11 10 6.8197;10 12 8.1755;12 10 6.5961; ...\r\n15 1 6.4899;1 15 4.3239];\r\nassert(isequal(reaction_chain2(R,3,30),4))\r\nassert(isequal(reaction_chain2(R,12,30),1))\r\nassert(isequal(reaction_chain2(R,6,30),4))\r\n\r\n","published":true,"deleted":false,"likes_count":4,"comments_count":0,"created_by":255320,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":15,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2020-04-21T14:15:20.000Z","updated_at":"2025-12-04T23:53:49.000Z","published_at":"2020-04-21T14:15:20.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"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\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThis problem is related to Problem\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"45467\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e45467\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eLet's denote a list of\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e compounds as 1, 2, ...,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e. You are then given a list of valid reactions for converting one compound to another (e.g. 1 --\u0026gt; 2), as well as the time it takes to complete them (\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ecompletion time\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e ). With this information, we can generate\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ereaction chains\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e. A reaction chain is a series of valid reaction steps taken one after the other. Examples are given below:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[Given N = 4 and the following valid reactions:\\nReaction 1:    1 --\u003e 2 takes 1.5 mins\\nReaction 2:    1 --\u003e 3 takes 2.5 mins \\nReaction 3:    2 --\u003e 3 takes 0.6 mins\\nReaction 4:    3 --\u003e 4 takes 4.1 mins \\nReaction 5:    4 --\u003e 2 takes 3.2 mins\\nSample reaction chains: 1 --\u003e 3 --\u003e 4         takes (2.5 + 4.1) mins\\n                        1 --\u003e 2 --\u003e 3 --\u003e 4   takes (1.5 + 0.6 + 4.1) mins \\n                        4 --\u003e 2 --\u003e 3         takes (3.2 + 0.6) mins]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eNote 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.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eYour task is this: Given a starting compound\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eS\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e, can you count how many reaction chains are possible\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ewhose total completion time does not exceed\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eT\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e mins\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e?\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eNote that if multiple valid reaction steps are possible between two compounds (e.g. \\\"1 --\u0026gt; 2 takes 1.5 mins\\\" and \\\"1 --\u0026gt; 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\\\".\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThe inputs to this problem are\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eS\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e, and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eT\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e. The meanings of\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eS\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eT\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e are given above. Variable\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e is a 3-column matrix containing the list of valid reaction steps at each row\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\\\"Reaction\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e:\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e(\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e1\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e) --\u0026gt;\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e(\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e2\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e) takes\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e(\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003ei\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e3\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e) mins\\\"\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eOutput the required number of reaction chains. You are ensured that:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eT\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e are integers satisfying: 2 \u0026lt;=\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u0026lt;= 20 and 1 \u0026lt;=\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eT\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u0026lt;= 100.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eS\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and all elements in the first 2 columns of\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e are integers within [1,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e].\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eCompletion times are decimal numbers within (0,10].\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eEach compound 1, ...,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e is mentioned at least once in\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e. Hence,\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eN\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e can be inferred from matrix\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eR\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eThe following sample test case is the one illustrated above:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[\u003e\u003e R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];\\n\u003e\u003e reaction_chain2(R,1,5)\\nans = \\n     3\\n\u003e\u003e reaction_chain2(R,1,10)\\nans = \\n     6]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eIn this example, all the reaction chains starting from Compound 1 are:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[(1.50 mins) 1 --\u003e 2\\n(2.10 mins) 1 --\u003e 2 --\u003e 3\\n(6.20 mins) 1 --\u003e 2 --\u003e 3 --\u003e 4\\n(2.50 mins) 1 --\u003e 3\\n(6.60 mins) 1 --\u003e 3 --\u003e 4\\n(9.80 mins) 1 --\u003e 3 --\u003e 4 --\u003e 2]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"term":"tag:\"counting paths\"","current_player_id":null,"fields":[{"name":"page","type":"integer","callback":null,"default":1,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"per_page","type":"integer","callback":null,"default":50,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"sort","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"body","type":"text","callback":null,"default":"*:*","directive":null,"facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":false},{"name":"group","type":"string","callback":null,"default":null,"directive":"group","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"difficulty_rating_bin","type":"string","callback":null,"default":null,"directive":"difficulty_rating_bin","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"id","type":"integer","callback":null,"default":null,"directive":"id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"tag","type":"string","callback":null,"default":null,"directive":"tag","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"product","type":"string","callback":null,"default":null,"directive":"product","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_at","type":"timeframe","callback":{},"default":null,"directive":"created_at","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"profile_id","type":"integer","callback":null,"default":null,"directive":"author_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_by","type":"string","callback":null,"default":null,"directive":"author","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player_id","type":"integer","callback":null,"default":null,"directive":"solver_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player","type":"string","callback":null,"default":null,"directive":"solver","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"solvers_count","type":"integer","callback":null,"default":null,"directive":"solvers_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"comments_count","type":"integer","callback":null,"default":null,"directive":"comments_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"likes_count","type":"integer","callback":null,"default":null,"directive":"likes_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leader_id","type":"integer","callback":null,"default":null,"directive":"leader_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leading_solution","type":"integer","callback":null,"default":null,"directive":"leading_solution","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true}],"filters":[{"name":"asset_type","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":"\"cody:problem\"","prepend":true},{"name":"profile_id","type":"integer","callback":{},"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":"author_id","static":null,"prepend":true}],"query":{"params":{"per_page":50,"term":"tag:\"counting paths\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"counting paths\"","","\"","counting paths","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007ffbe709cd20\u003e":null,"#\u003cMathWorks::Search::Field:0x00007ffbe709caa0\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007ffbe7098fe0\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007ffbe709ea80\u003e":1,"#\u003cMathWorks::Search::Field:0x00007ffbe709e580\u003e":50,"#\u003cMathWorks::Search::Field:0x00007ffbe709e4e0\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007ffbe709cf00\u003e":"tag:\"counting paths\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007ffbe709cf00\u003e":"tag:\"counting paths\""},"queried_facets":{}},"query_backend":{"connection":{"configuration":{"index_url":"http://index-op-v2/solr/","query_url":"http://search-op-v2/solr/","direct_access_index_urls":["http://index-op-v2/solr/"],"direct_access_query_urls":["http://search-op-v2/solr/"],"timeout":10,"vhost":"search","exchange":"search.topic","heartbeat":30,"pre_index_mode":false,"host":"rabbitmq-eks","port":5672,"username":"cody-search","password":"78X075ddcV44","virtual_host":"search","indexer":"amqp","http_logging":"true","core":"cody"},"query_connection":{"uri":"http://search-op-v2/solr/cody/","proxy":null,"connection":{"parallel_manager":null,"headers":{"User-Agent":"Faraday v1.0.1"},"params":{},"options":{"params_encoder":"Faraday::FlatParamsEncoder","proxy":null,"bind":null,"timeout":null,"open_timeout":null,"read_timeout":null,"write_timeout":null,"boundary":null,"oauth":null,"context":null,"on_data":null},"ssl":{"verify":true,"ca_file":null,"ca_path":null,"verify_mode":null,"cert_store":null,"client_cert":null,"client_key":null,"certificate":null,"private_key":null,"verify_depth":null,"version":null,"min_version":null,"max_version":null},"default_parallel_manager":null,"builder":{"adapter":{"name":"Faraday::Adapter::NetHttp","args":[],"block":null},"handlers":[{"name":"Faraday::Response::RaiseError","args":[],"block":null}],"app":{"app":{"ssl_cert_store":{"verify_callback":null,"error":null,"error_string":null,"chain":null,"time":null},"app":{},"connection_options":{},"config_block":null}}},"url_prefix":"http://search-op-v2/solr/cody/","manual_proxy":false,"proxy":null},"update_format":"RSolr::JSON::Generator","update_path":"update","options":{"url":"http://search-op-v2/solr/cody"}}},"query":{"params":{"per_page":50,"term":"tag:\"counting paths\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"counting paths\"","","\"","counting paths","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007ffbe709cd20\u003e":null,"#\u003cMathWorks::Search::Field:0x00007ffbe709caa0\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007ffbe7098fe0\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007ffbe709ea80\u003e":1,"#\u003cMathWorks::Search::Field:0x00007ffbe709e580\u003e":50,"#\u003cMathWorks::Search::Field:0x00007ffbe709e4e0\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007ffbe709cf00\u003e":"tag:\"counting paths\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007ffbe709cf00\u003e":"tag:\"counting paths\""},"queried_facets":{}},"options":{"fields":["id","difficulty_rating"]},"join":" "},"results":[{"id":45470,"difficulty_rating":"medium"}]}}