Algorithm

D. Colorful Points
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/909/D
input
standard input
output
standard output

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.

Examples
input
Copy
aabb
output
Copy
2
input
Copy
aabcaa
output
Copy
1
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.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e5 + 1;
int ax, ay, bx, by, tx, ty;
int n;
int xi[N], yi[N];
long double dp[N][2][2];

long double dist(int x1, int y1, int x2, int y2) {
	return sqrt(pow(x1 - x2, 2.0) + pow(y1 - y2, 2.0));
}

long double rec(int idx, bool at, bool bt) {
	if(idx == n)
		return (at || bt) ? 0 : 2e18;

	long double &ret = dp[idx][at][bt];
	if(ret == ret)
		return ret;
	ret = rec(idx + 1, at, bt) + dist(tx, ty, xi[idx], yi[idx]) * 2;

	if(!at)
		ret = min(ret, rec(idx + 1, 1, bt) + dist(ax, ay, xi[idx], yi[idx]) + dist(tx, ty, xi[idx], yi[idx]));

	if(!bt)
		ret = min(ret, rec(idx + 1, at, 1) + dist(bx, by, xi[idx], yi[idx]) + dist(tx, ty, xi[idx], yi[idx]));

	return ret;
}

int main() {
  cin >> ax >> ay >> bx >> by >> tx >> ty;
  cin >> n;
  for(int i = 0; i < n; ++i)
  	cin >> xi[i] >> yi[i];

  memset(dp, -1, sizeof dp);
  cout << fixed << setprecision(12) << rec(0, 0, 0) << endl;

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
aabb

Output

x
–
+
cmd
2
Advertisements

Demonstration

Codeforces Solution-Colorful Points-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+