G. Large array

Codeforces

IDCF10241G

Time3000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given an array $b$ of size $m$. An array $a$ of size $n$ is built from $b$ by the following formula: for every $i$ $(0 <= i < n)$ $a [ i ] = b [ i$ $m o d$ $m ]$. You should find a sub-array from the array $a$ with a sum equal to $k$ and minimum possible size. The arrays are 0 indexed. The first line of input contains one integer $t$ which is the number of test cases. For every test case : The First line contains three integers $m$ $n$ $k$, which are the size of array $b$ and the size of array $a$ and the needed sum $(1 <= m <= 10^5)$ $(m <= n <= 10^9)$ $(-10^(18) <= k <= 10^(18))$. The second line contains $m$ integers, the $i_{t h}$ one is $b_i$ $(-10^9 <= b_i <= 10^9)$, which is the $i_{t h}$ element in array $b$. it is guaranteed that the sum of $m$ between all test cases will not exceed $3 times 10^5$. For every test case : If there is no sub-array of sum $k$ print $-1$ on a line. Otherwise print two integers $l$ and $r$ $(1 <= l <= r <= n)$ which is a sub-array with minimal possible size and sum equal to $k$. If there is more than one answer print the sub-array with minimum possible $l$. ## Input The first line of input contains one integer $t$ which is the number of test cases.For every test case :The First line contains three integers $m$ $n$ $k$, which are the size of array $b$ and the size of array $a$ and the needed sum $(1 <= m <= 10^5)$ $(m <= n <= 10^9)$ $(-10^(18) <= k <= 10^(18))$.The second line contains $m$ integers, the $i_{t h}$ one is $b_i$ $(-10^9 <= b_i <= 10^9)$, which is the $i_{t h}$ element in array $b$.it is guaranteed that the sum of $m$ between all test cases will not exceed $3 times 10^5$. ## Output For every test case : If there is no sub-array of sum $k$ print $-1$ on a line.Otherwise print two integers $l$ and $r$ $(1 <= l <= r <= n)$ which is a sub-array with minimal possible size and sum equal to $k$.If there is more than one answer print the sub-array with minimum possible $l$. [samples]

**Definitions** Let $ t \in \mathbb{Z}^+ $ be the number of test cases. For each test case: - Let $ m, n \in \mathbb{Z}^+ $ with $ 1 \le m \le 10^5 $, $ m \le n \le 10^9 $. - Let $ b = (b_0, b_1, \dots, b_{m-1}) \in \mathbb{Z}^m $ be the base array. - Define array $ a = (a_0, a_1, \dots, a_{n-1}) $ by $ a_i = b_{i \bmod m} $. - Let $ k \in \mathbb{Z} $ with $ -10^{18} \le k \le 10^{18} $ be the target sum. **Constraints** 1. $ \sum_{\text{test cases}} m \le 3 \times 10^5 $ 2. All values are integers as specified. **Objective** Find a contiguous sub-array $ a[l:r] $ (0-indexed, $ 0 \le l \le r < n $) such that: $$ \sum_{i=l}^{r} a_i = k $$ and the length $ r - l + 1 $ is minimized. If multiple such sub-arrays exist, choose the one with minimum $ l $. If no such sub-array exists, output $-1$. Output the 1-indexed bounds $ (l+1, r+1) $.

API Response (JSON)

{
  "problem": {
    "name": "G. Large array",
    "description": {
      "content": "You are given an array $b$ of size $m$. An array $a$ of size $n$ is built from $b$ by the following formula:  for every $i$ $(0 <= i < n)$ $a [ i ] = b [ i$ $m o d$ $m ]$. You should find a sub-arr",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10241G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an array $b$ of size $m$.\n\nAn array $a$ of size $n$ is built from $b$ by the following formula:\n\n for every $i$ $(0 <= i < n)$ $a [ i ] = b [ i$ $m o d$ $m ]$.\n\nYou should find a sub-arr...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case:  \n- Let $ m, n \\in \\mathbb{Z}^+ $ with $ 1 \\le m \\le 10^5 $, $ m \\le n \\le 10^9 $.  \n- Let $ b = (b_0, b...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments