K. Cutting Strings

Codeforces

IDCF10149K

Time2000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Alice, Beto, and Carlos are playing with twine. Alice starts by pulling taut the string of twine, then she folds it and holds the string at the fold. Beto holds the loose ends on the other side. They then repeat the following procedure. Carlos cuts the string with scissors, thus separating Alice and Beto. Alice, without letting go of the strings she was holding, grabs the loose ends of the strings held by Beto and he does the same to the loose ends of the strings held by Alice. How many separate strings will they have after the procedure is repeated K times? The input has a single integer, K. The output has a single integer, the amount of separate strings at the end of the process. ## Input The input has a single integer, K. 0 ≤ K ≤ 30 ## Output The output has a single integer, the amount of separate strings at the end of the process. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ A = (a_1, a_2, \dots, a_N) $ be an array of $ N $ integers. A *subarray* is a contiguous non-empty sequence $ A[i:j] = (a_i, a_{i+1}, \dots, a_j) $ for $ 1 \leq i \leq j \leq N $. The *strength* of a subarray is the sum of its elements: $ \text{strength}(A[i:j]) = \sum_{k=i}^j a_k $. **Constraints** 1. $ 1 \leq T \leq 100 $ 2. For each test case: - $ 2 \leq N \leq 10^5 $ - $ -10^9 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, N\} $ 3. Two subarrays $ A[i_1:j_1] $ and $ A[i_2:j_2] $ are *non-intersecting* if $ j_1 < i_2 $ or $ j_2 < i_1 $. **Objective** For each test case, compute: $$ \max_{\substack{A[i_1:j_1], A[i_2:j_2] \\ \text{non-intersecting}}} \left| \text{strength}(A[i_1:j_1]) - \text{strength}(A[i_2:j_2]) \right| $$

API Response (JSON)

{
  "problem": {
    "name": "K. Cutting Strings",
    "description": {
      "content": "Alice, Beto, and Carlos are playing with twine. Alice starts by pulling taut the string of twine, then she folds it and holds the string at the fold. Beto holds the loose ends on the other side. They ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10149K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice, Beto, and Carlos are playing with twine. Alice starts by pulling taut the string of twine, then she folds it and holds the string at the fold. Beto holds the loose ends on the other side. They ...",
      "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, let $ A = (a_1, a_2, \\dots, a_N) $ be an array of $ N $ integers.  \nA *subarray* is a contiguous non-empty...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments