D. Colorful Points

Codeforces

IDCF909D

Time2000ms

Memory256MB

Difficulty—

data structuresgreedyimplementation

English · Original

Chinese · Translation

Formal · Original

You are given a set of points on a straight line. Each point has a color assigned to it. For point _a_, its neighbors are the points which don't have any other points between them and _a_. Each point has at most two neighbors - one from the left and one from the right. You perform a sequence of operations on this set of points. In one operation, you delete all points which have a neighbor point of a different color than the point itself. Points are deleted simultaneously, i.e. first you decide which points have to be deleted and then delete them. After that you can perform the next operation etc. If an operation would not delete any points, you can't perform it. How many operations will you need to perform until the next operation does not have any points to delete? ## Input Input contains a single string of lowercase English letters 'a'-'z'. The letters give the points' colors in the order in which they are arranged on the line: the first letter gives the color of the leftmost point, the second gives the color of the second point from the left etc. The number of the points is between 1 and 106. ## Output Output one line containing an integer - the number of operations which can be performed on the given set of points until there are no more points to delete. [samples] ## Note In the first test case, the first operation will delete two middle points and leave points "ab", which will be deleted with the second operation. There will be no points left to apply the third operation to. In the second test case, the first operation will delete the four points in the middle, leaving points "aa". None of them have neighbors of other colors, so the second operation can't be applied.

你被给定一条直线上的一组点。每个点都被赋予一种颜色。对于点 #cf_span[a]，它的邻居是那些与 #cf_span[a] 之间没有其他点的点。每个点最多有两个邻居——一个在左边，一个在右边。你对这组点执行一系列操作。在一次操作中，你删除所有具有颜色不同于自身邻居的点。点是同时被删除的，即你首先确定哪些点需要被删除，然后一次性删除它们。之后你可以执行下一次操作，依此类推。如果某次操作不会删除任何点，则你不能执行该操作。问：你需要执行多少次操作，直到下一次操作不再有可删除的点？输入包含一个由小写英文字母 'a'-'z' 组成的字符串。这些字母按其在直线上的排列顺序给出点的颜色：第一个字母给出最左边点的颜色，第二个字母给出从左数第二个点的颜色，以此类推。点的数量在 1 到 #cf_span[106] 之间。输出一行，包含一个整数——在给定点集中可以执行的操作次数，直到没有更多点可删除为止。在第一个测试用例中，第一次操作将删除两个中间点，留下点 "ab"，这些点将在第二次操作中被删除。第三次操作将没有点可删除。在第二个测试用例中，第一次操作将删除中间的四个点，留下点 "aa"。它们都没有颜色不同的邻居，因此无法执行第二次操作。 ## Input 输入包含一个由小写英文字母 'a'-'z' 组成的字符串。这些字母按其在直线上的排列顺序给出点的颜色：第一个字母给出最左边点的颜色，第二个字母给出从左数第二个点的颜色，以此类推。点的数量在 1 到 #cf_span[106] 之间。 ## Output 输出一行，包含一个整数——在给定点集中可以执行的操作次数，直到没有更多点可删除为止。 [samples] ## Note 在第一个测试用例中，第一次操作将删除两个中间点，留下点 "ab"，这些点将在第二次操作中被删除。第三次操作将没有点可删除。在第二个测试用例中，第一次操作将删除中间的四个点，留下点 "aa"。它们都没有颜色不同的邻居，因此无法执行第二次操作。

**Definitions** Let $ S = s_1 s_2 \dots s_n $ be a string of length $ n \in \mathbb{Z}^+ $, where $ s_i \in \{a, b, \dots, z\} $, representing colors of points on a line in left-to-right order. Let $ P = \{p_1, p_2, \dots, p_n\} $ be the sequence of points, where point $ p_i $ has color $ s_i $. For each point $ p_i $, its neighbors are $ p_{i-1} $ (left) and $ p_{i+1} $ (right), if they exist. **Constraints** $ 1 \leq n \leq 10^6 $ **Operation Rule** In one operation, delete all points $ p_i $ such that at least one neighbor has a different color: $$ \text{Delete } p_i \iff (i > 1 \text{ and } s_i \ne s_{i-1}) \text{ or } (i < n \text{ and } s_i \ne s_{i+1}) $$ All such points are deleted simultaneously. **Objective** Compute the maximum number of such operations that can be performed until no point is deleted in an operation.

Samples

Input #1

aabb

Output #1

Input #2

aabcaa

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Colorful Points",
    "description": {
      "content": "You are given a set of points on a straight line. Each point has a color assigned to it. For point _a_, its neighbors are the points which don't have any other points between them and _a_. Each point ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF909D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a set of points on a straight line. Each point has a color assigned to it. For point _a_, its neighbors are the points which don't have any other points between them and _a_. Each point ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一条直线上的一组点。每个点都被赋予一种颜色。对于点 #cf_span[a]，它的邻居是那些与 #cf_span[a] 之间没有其他点的点。每个点最多有两个邻居——一个在左边，一个在右边。\n\n你对这组点执行一系列操作。在一次操作中，你删除所有具有颜色不同于自身邻居的点。点是同时被删除的，即你首先确定哪些点需要被删除，然后一次性删除它们。之后你可以执行下一次操作，依此类推。如果某次操作不会删除...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S = s_1 s_2 \\dots s_n $ be a string of length $ n \\in \\mathbb{Z}^+ $, where $ s_i \\in \\{a, b, \\dots, z\\} $, representing colors of points on a line in left-to-right order.  \nLe...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments