J. Best division

Codeforces

IDCF10240J

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Diego is out with $3$ of his friends (Jorge, Juan and Bob), when out of nowhere one of them realizes that there is a gigantic bar or chocolate, every single one of them is greedy so they want to eat as much chocolate as possible. After many hours of arguing who gets to eat the most chocolate they came up with the following: the best division is one such that the difference between the person who eats the most chocolate and the person who eats the least chocolate is as small as possible. As they are about to begin distributing the chocolate bar they came up to a realization, this bar has the shape of a rectangle, has exactly length $L$ and also has exactly $N -1$ different cutting spots, each spot located at a specific position $x_i$ (assuming that the chocolate bar begins in position $0$). So they must cut the chocolate bar in exactly $3$ of the cutting spots. Help Diego find out the optimal way of dividing the chocolate bar in $4$ such that the difference between whoever eats less and whoever eats most is minimal. A line with 2 integers, $N, L$ $(4 <= N <= 10^5, 4 <= L <= 10^(15))$, the amount of cutting spots within the chocolate bar and the length of the chocolate bar. Followed by a line with $N -1$ integers in increasing order, representing the position of the ith cutting spot $(1 <= x_i < 10^(15))$. It's guaranteed that $x_i < x_{i + 1}$ for $1 <= i < N -1$. A single integer $M$, the minimal delta between the smallest and biggest piece of chocolate if we divide the bar into exactly $4$ pieces. In the test case, given the positions it's the equivalent of saying that we have 8 pieces of the following lengths: 3 1 1 3 2 2 3 3 There are 2 optimal answers, we can either split it in such a way that the 4 chocolate pieces the friends are going to eat are of sizes 5 5 5 3, or of sizes 4 4 4 6. ## Input A line with 2 integers, $N, L$ $(4 <= N <= 10^5, 4 <= L <= 10^(15))$, the amount of cutting spots within the chocolate bar and the length of the chocolate bar.Followed by a line with $N -1$ integers in increasing order, representing the position of the ith cutting spot $(1 <= x_i < 10^(15))$. It's guaranteed that $x_i < x_{i + 1}$ for $1 <= i < N -1$. ## Output A single integer $M$, the minimal delta between the smallest and biggest piece of chocolate if we divide the bar into exactly $4$ pieces. [samples] ## Note In the test case, given the positions it's the equivalent of saying that we have 8 pieces of the following lengths: 3 1 1 3 2 2 3 3 There are 2 optimal answers, we can either split it in such a way that the 4 chocolate pieces the friends are going to eat are of sizes 5 5 5 3, or of sizes 4 4 4 6.

**Definitions** Let $ N \in \mathbb{Z} $, $ L \in \mathbb{Z} $, with $ 4 \leq N \leq 10^5 $, $ 4 \leq L \leq 10^{15} $. Let $ X = (x_1, x_2, \dots, x_{N-1}) $ be a strictly increasing sequence of cutting positions, with $ 1 \leq x_i < 10^{15} $, and define $ x_0 = 0 $, $ x_N = L $. Let $ P = (p_1, p_2, \dots, p_N) $ be the sequence of segment lengths: $$ p_i = x_i - x_{i-1}, \quad \text{for } i = 1, \dots, N $$ **Constraints** We must choose exactly 3 distinct cutting indices $ 1 \leq i < j < k \leq N-1 $ to split the bar into 4 contiguous pieces: - Piece 1: $ \sum_{m=1}^{i} p_m $ - Piece 2: $ \sum_{m=i+1}^{j} p_m $ - Piece 3: $ \sum_{m=j+1}^{k} p_m $ - Piece 4: $ \sum_{m=k+1}^{N} p_m $ **Objective** Minimize the difference between the maximum and minimum piece sizes: $$ \min_{1 \leq i < j < k \leq N-1} \left( \max_{\ell=1}^4 S_\ell - \min_{\ell=1}^4 S_\ell \right) $$ where $ S_1, S_2, S_3, S_4 $ are the four resulting contiguous segment sums.

API Response (JSON)

{
  "problem": {
    "name": "J. Best division",
    "description": {
      "content": "Diego is out with $3$ of his friends (Jorge, Juan and Bob), when out of nowhere one of them realizes that there is a gigantic bar or chocolate, every single one of them is greedy so they want to eat a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10240J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Diego is out with $3$ of his friends (Jorge, Juan and Bob), when out of nowhere one of them realizes that there is a gigantic bar or chocolate, every single one of them is greedy so they want to eat a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ L \\in \\mathbb{Z} $, with $ 4 \\leq N \\leq 10^5 $, $ 4 \\leq L \\leq 10^{15} $.  \nLet $ X = (x_1, x_2, \\dots, x_{N-1}) $ be a strictly increasing sequence of ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments