hackercupai/hackercup
Data Preview The data available in this preview contains a 10 row dataset: Sample Dataset ("sample"): This is a subset of the full dataset, containing data from 2023. To view full dataset, download output_dataset.parquet. This contains data from 2011 to 2023. Fields The dataset include the following fields: name (string) year (string) round (string) statement (string) input (string) solution (string) code (string) sample_input (string) sample_output (string)… See the full description on the dataset page: https://huggingface.co/datasets/hackercupai/hackercup.
242.2k
1<p>2The starship Enterprise, bravely captained by Jean-Luc Picard, is on yet another mission to explore strange new worlds, seek out new life and new civilizations, 3and boldly go where no one has gone before! Equipped with a state-of-the-art warp drive capable of attaining warp factor 11 and revising the Enterprise's space-time coordinates almost at will4(even sending the ship back in time), not much can stand in the explorers' way. Though, they <em>are</em> low on medical supplies, so they will need to first stock up on neurozine gas for anesthetic purposes.5</p>6 7<p>8The Enterprise is heading to the Alpha Omicron solar system, which consists of <strong>N</strong> planets, numbered from 1 to <strong>N</strong>. 9It also features <strong>M</strong> space conduits, the <em>i</em>th of which allows the Enterprise to travel in either direction between two different planets 10<strong>A<sub>i</sub></strong> and <strong>B<sub>i</sub></strong>. 11No two conduits directly link the same unordered pair of planets, and <strong>each planet is reachable from each other planet</strong> by following a sequence of conduits.12</p>13 14<p>15There's a geyser capable of emitting neurozine located on each planet, though all <strong>N</strong> geysers are initially inactive. 16A sequence of <strong>K</strong> events will then take place, one per hour. The event at hour <em>i</em> is described by integers <strong>E<sub>i</sub></strong> and <strong>V<sub>i</sub></strong>, 17with <strong>E<sub>i</sub></strong> indicating the event's type, which is one of the following:18</p>19 20<ul style="list-style-type:disc; padding-inline-start: 30px;">21<li><strong>E<sub>i</sub></strong> = 1: The <strong>V<sub>i</sub></strong>th conduit (1 ≤ <strong>V<sub>i</sub></strong> ≤ <strong>M</strong>) collapses, 22and can no longer be used from that moment onwards. Each conduit collapses at most once. </li>23<li><strong>E<sub>i</sub></strong> = 2: The geyser on planet <strong>V<sub>i</sub></strong> (1 ≤ <strong>V<sub>i</sub></strong> ≤ <strong>N</strong>) activates, 24and begins emitting neurozine. Each geyser is activated at most once. </li>25<li><strong>E<sub>i</sub></strong> = 3: The geyser on planet <strong>V<sub>i</sub></strong> (1 ≤ <strong>V<sub>i</sub></strong> ≤ <strong>N</strong>) deactivates, 26and no longer emits neurozine from that moment onwards. Each geyser is deactivated at most once, and is guaranteed to not be deactivated before it has been activated. </li>27</ul>28 29<p>30The Enterprise will arrive in the Alpha Omicron system at some planet <em>x</em> and just before some hour <em>y</em>. 31When the starship is currently at a certain planet (and a certain time), Captain Picard may issue any of the following commands to his crew:32</p>33 34<ul style="list-style-type:disc; padding-inline-start: 30px;">35<li>Remain at that planet and wait until any future time. </li>36<li>Travel through an uncollapsed space conduit directly from that planet to another one. Thanks to warp technology, this may be done instantly. </li>37<li>Collect neurozine from that planet's geyser, if it's currently active. This may be done instantly. </li>38<li>Remain at that planet while travelling backwards to any past time which is <strong>at most 24 hours earlier than the Enterprise's original arrival time in the solar system</strong> 39(in other words, the Enterprise may end up just before hour (<em>y</em> - 24), but no earlier). However, <strong>this may only be done at most once</strong>. The Enterprise retains any neurozine that it had collected before this "temporal revision". 40</ul>41 42<p>43Picard wants his crew to collect neurozine from as many <em>different</em> geysers as possible; there's no additional value in collecting neurozine from any given geyser multiple times,44including both before and after travelling back in time. However, Picard hasn't yet decided where and when the Enterprise should arrive in the Alpha Omicron system. 45He has <strong>S</strong> such possible starting situations in mind, the <em>i</em>th of which would have the Enterprise arrive at planet 46<strong>X<sub>i</sub></strong> just before hour <strong>Y<sub>i</sub></strong>. 47For each hypothetical starting situation, please help Picard determine the maximum number of different geysers from which the Enterprise could then proceed to collect neurozine!48</p>49 50<p>51Letting <strong>ans<sub>i</sub></strong> be the answer for the <em>i</em>th starting situation, you must output the sum of <strong>ans<sub>1..S</sub></strong> 52in order to minimize the size of the output. Please note that this sum may not fit within a 32-bit integer.53</p>54 55<p>56The starting situations must be considered one after another. In order to enforce this, rather than being given <strong>X<sub>1..S</sub></strong> and <strong>Y<sub>1..S</sub></strong>57explicitly, you must compute them based on given values <strong>X'<sub>1..S</sub></strong> and <strong>Y'<sub>1..S</sub></strong>. 58For the first starting situation, <strong>X<sub>1</sub></strong> = <strong>X'<sub>1</sub></strong> and <strong>Y<sub>1</sub></strong> = <strong>Y'<sub>1</sub></strong>, 59while for each subsequent starting situation <em>i</em> (2 ≤ <em>i</em> ≤ <strong>S</strong>), 60<strong>X<sub>i</sub></strong> = <strong>X'<sub>i</sub></strong> xor <strong>ans<sub>i-1</sub></strong> and 61<strong>Y<sub>i</sub></strong> = <strong>Y'<sub>i</sub></strong> xor <strong>ans<sub>i-1</sub></strong> (where "xor" is the bitwise xor operator, "^" in most programming languages).62</p>63 64 65<h3>Input</h3>66 67<p>68Input begins with an integer <strong>T</strong>, the number of missions.69<br />For each mission, there is first a line containing the space-separated integers <strong>N</strong>, <strong>M</strong>, <strong>K</strong> and <strong>S</strong>.70<br />Then, <strong>M</strong> lines follow, the <em>i</em>th of which contains the space-separated integers <strong>A<sub>i</sub></strong> and <strong>B<sub>i</sub></strong>.71<br />Then, <strong>K</strong> lines follow, the <em>i</em>th of which contains the space-separated integers <strong>E<sub>i</sub></strong> and <strong>V<sub>i</sub></strong>.72<br />Then, <strong>S</strong> lines follow, the <em>i</em>th of which contains the space-separated integers <strong>X'<sub>i</sub></strong> and <strong>Y'<sub>i</sub></strong>.73</p>74 75 76<h3>Output</h3>77 78<p>79For the <em>i</em>th mission, print a line containing "Case #<em>i</em>: " followed by80one integer, the sum of the answers for the <strong>S</strong> starting situations.81</p>82 83 84<h3>Constraints</h3>85 86<p>871 ≤ <strong>T</strong> ≤ 100 <br />882 ≤ <strong>N</strong> ≤ 800,000 <br />891 ≤ <strong>M</strong>, <strong>K</strong>, <strong>S</strong> ≤ 800,000 <br />901 ≤ <strong>A<sub>i</sub></strong>, <strong>B<sub>i</sub></strong> ≤ <strong>N</strong> <br />911 ≤ <strong>E<sub>i</sub></strong> ≤ 3 <br />921 ≤ <strong>X<sub>i</sub></strong> ≤ <strong>N</strong> <br />931 ≤ <strong>Y<sub>i</sub></strong> ≤ <strong>K</strong> <br />940 ≤ <strong>X'<sub>i</sub></strong>, <strong>Y'<sub>i</sub></strong> ≤ 1,000,000,000 <br />95</p>96 97<p>98The sum of <strong>N</strong> across all <strong>T</strong> test cases is no greater than 2,000,000. <br />99The sum of <strong>M</strong> across all <strong>T</strong> test cases is no greater than 2,000,000. <br />100The sum of <strong>K</strong> across all <strong>T</strong> test cases is no greater than 2,000,000. <br />101The sum of <strong>S</strong> across all <strong>T</strong> test cases is no greater than 2,000,000.102</p>103 104 105<h3>Explanation of Sample</h3>106 107<p>108In the first case, if the Enterprise arrives at planet 1 just before hour 3, Picard could issue the following sequence of orders to help his crew collect neurozine from both planets' geysers:109 110<ol>111<li>Travel through the 1st space conduit to planet 2.112<li>Wait until after hour 3.113<li>Collect neurozine from planet 2's now-active geyser.114<li>Travel back in time to just before hour 2.115<li>Travel through the 1st space conduit to planet 1.116<li>Collected neurozine from planet 1's active geyser.117</ol>118 119<p>120In the second case, the starting situations and corresponding answers are as follows:121</p>122 123<pre>124 i | X<sub>i</sub> | Y<sub>i</sub> | ans<sub>i</sub>125 ------------------126 1 | 2 | 1 | 3127 2 | 1 | 6 | 2128 3 | 3 | 5 | 3129</pre>130 131<p>132For the first starting situation, the Enterprise could remain on planet 2 until its geyser activates at hour 6, collect its neurozine, travel back in time to just before hour 2, travel to planet 1 and collect its neurozine, travel to planet 2 and then to planet 3, and remain there to collect its neurozine after hour 5. On the other hand, for the second starting situation, neurozine from all 3 geysers cannot be collected.133</p>134 135<p>136In the third case, the starting situations and corresponding answers are as follows:137</p>138 139<pre>140 i | X<sub>i</sub> | Y<sub>i</sub> | ans<sub>i</sub>141 ------------------142 1 | 1 | 4 | 4143 2 | 5 | 8 | 3144 3 | 2 | 9 | 3145 4 | 3 | 6 | 4146</pre>147 148<p>149In the fourth case, the starting situations and corresponding answers are as follows:150</p>151 152<pre>153 i | X<sub>i</sub> | Y<sub>i</sub> | ans<sub>i</sub>154 ------------------155 1 | 6 | 16 | 7156 2 | 4 | 6 | 8157 3 | 10 | 22 | 7158 4 | 3 | 13 | 7159 5 | 6 | 11 | 8160 6 | 5 | 17 | 6161 7 | 2 | 21 | 7162</pre>163 164<p>165In the fifth case, the first 5 starting situations and corresponding answers are as follows:166</p>167 168<pre>169 i | X<sub>i</sub> | Y<sub>i</sub> | ans<sub>i</sub>170 ------------------171 1 | 20 | 47 | 2172 2 | 4 | 49 | 7173 3 | 24 | 47 | 1174 4 | 20 | 9 | 13175 5 | 3 | 38 | 9176</pre>177