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>2In preparation for his final exam, Ethan is doing his fourth programming assignment: finding the subarray with the maximum sum in an array of integers.3</p>4 5<p>6Given an array of <strong>N</strong> integers <strong>A<sub>1..N</sub></strong>, 7Ethan's task is to find the maximum sum of any (possibly empty) contiguous subarray of <strong>A</strong>. 8Ethan has implemented an algorithm to solve this problem, described by the following pseudocode:9</p>10 11<ul>12<li> 1. Set <strong>s</strong> and <strong>m</strong> to both be equal to 0. </li>13<li> 2. Iterate <em>i</em> upwards from 1 to <strong>N</strong>: </li>14<li> 2a. If <strong>A<sub>i</sub></strong> ≥ 0, increment <strong>s</strong> by <strong>A<sub>i</sub></strong>, 15otherwise set <strong>s</strong> to be equal to 0. </li>16<li> 2b. If <strong>s</strong> > <strong>m</strong>, set <strong>m</strong> to be equal to <strong>s</strong>. </li>17<li> 3. Output <strong>m</strong>. </li>18</ul>19 20<p>21Is there any hope for Ethan? With exasperation, you set out in vain to teach another lesson.22</p>23 24<p>25The professor of the class has once again left you with some half-written test cases. 26You're given an initial array <strong>B<sub>1..M</sub></strong>, such that the absolute value of each element is at most <strong>K</strong>. 27You'd like to insert <strong>M</strong> - 1 more integers into the array, one between each pair of adjacent elements in the original array, 28to construct a new array <strong>A<sub>1..N</sub></strong> where <strong>N</strong> = 2<strong>M</strong> - 1.29 Each of the inserted elements must likewise have an absolute value of at most <strong>K</strong>. 30You'll then feed the new array <strong>A</strong> into Ethan's algorithm. 31Your goal is to maximize the absolute difference between the final array's correct maximum subarray sum and the output of Ethan's algorithm.32</p>33 34 35<h3>Input</h3>36 37<p>38Input begins with an integer <strong>T</strong>, the number of test cases.39For each test case, there is first a line containing the space-separated integers <strong>M</strong> and <strong>K</strong>.40Then one more line follows containing the <strong>M</strong> space-separated integers <strong>B<sub>1</sub></strong> through <strong>B<sub>M</sub></strong>.41</p>42 43 44<h3>Output</h3>45 46<p>47For the <em>i</em>th test case, output a line containing "Case #<em>i</em>: " 48followed by the maximum possible absolute difference between the correct maximum subarray sum and the output of Ethan's algorithm.49</p>50 51 52<h3>Constraints</h3>53 54<p>551 ≤ <strong>T</strong> ≤ 60 <br />561 ≤ <strong>M</strong> ≤ 50 <br />571 ≤ <strong>K</strong> ≤ 50 <br />58-<strong>K</strong> ≤ <strong>A<sub>i</sub></strong> ≤ <strong>K</strong> <br />59</p>60 61 62<h3>Explanation of Sample</h3>63 64<p>65In the first case, <strong>A</strong> = [3], and both Ethan's answer and the correct answer are equal to 3.66</p>67 68<p>69In the second case, <strong>A</strong> = [-3], and both Ethan's answer and the correct answer are equal to 0.70</p>71 72<p>73In the third case, one value will be inserted into <strong>B</strong>, and you should choose to insert -1 to yield <strong>A</strong> = [2, -1, 2]. 74This results in Ethan's answer being 2 and the correct answer being 3, yielding an absolute answer difference of 1.75</p>76 77<p>78In the fourth case, there are multiple choices of inserted elements which result in an absolute answer difference of 3. 79For example, it's possible for Ethan's answer equal to be made to equal 3 while the correct answer equals 6.80</p>81