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
1For this problem, a _possible median_ is defined as: The median value of a set2containing an odd number of values. -or- One of all the integers between, but3not including, the two median values of a set containing an even number of4values. 5**Examples:** 3 is the only possible median of the set (1, 5, 3, 2, 4). 2, 3 and 4 are all of the possible median values for the set (5, 1). There are **no** possible median values for the set (1, 2, 3, 4), since there are no integers between 2 and 3. 6 7You are given an array **A** of **N** unique nonnegative integers, all of8which are < **N** (i.e. a permutation of the numbers 0...**N-1**), where 3 ≤9**N** ≤ 200,000. You are also given a length **L** (1 ≤ **L** ≤ **N**).10Additionally, you are given **Q** (1 ≤ **Q** ≤ 200,000) queries, each11containing a number **x** (0 ≤ **x** < N) and two indices **i** and **j** (0 ≤12**i** < **j** ≤ **N**).13 14Each query returns TRUE if and only if there exists at least one subrange, of15at least **L** elements, of the range **A[i]**...**A[j-1]** (where the array16indices start at 0), with **x** as a possible median. In other words, the17answer is TRUE precisely when there exist **a**, **b** with **i** ≤ **a** <18**b** < **j** with **b** \- **a** ≥ **L** \- 1 and with **A[a]**...**A[b]**19having **x** as a possible median.20 21You wish to determine the number of queries which will return TRUE.22 23### Input24 25The first line contains a positive integer **T** (1 ≤ **T** ≤ 20), the number26of test cases. **T** test cases follow.27 28The first line of each test case consists of a single integer, **N**. The next29line consists of **N** space-separated integers, the **A[i]**. The line after30that contains two space-separate d integers, **L** and **Q**.31 32Each of the remaining **Q** lines in the test case contains three space-33separated integers, **x**, **i** and **j**.34 35These inputs are all integers, and will be input in decimal form, with no36leading zeros, and no decimal points.37 38### Output39 40For each of the test cases numbered in order from 1 to T, output "Case #",41followed by the case number, followed by ": ", followed by a single integer,42the number of passing queries.43 44These outputs are all integers, and must be output in decimal form, with no45leading zeros, and no decimal points.46 47