Faulty Test Cases in ONEVALUE

general
21

Anybody try this test
7
2 1 2 3 2 4 2
The correct answer is 3, but I found in accepted solution is 4

23

See this comment:

Author’s solution is sub optimal, that’s why there were so few accepted submission, people who made the same mistake as the author got accepted

24

so this contest should be unrated, shouldn’t it

25

@bansals888 , Can you explain why both of these questions are same. I saw the editorial of the mentioned Codeforces problem, and I don’t see how that approach can be used here. I also tried to think of another DP, which could solve both of these problems with a minor tweak, but didn’t succeed.
Since you say that both of these questions are same, I am assuming that you have a similar solution to both of them.
It would be very helpful if you could share your approach

26

Our first observation is that the length of each region has no bearing on the answer. Let C_i be the character on the ith region.
The second observation is that we must change the C_i to either C_{i-1} or C_{i+1}. If C_{i-1} \neq C_{i+1}, then C_i gets added to one of them, and is essentially deleted.
If C_{i-1} = C_{i+1}, then a new region is formed containing C_{i-1}, C_i, and C_{i+1}, and since it’s length doesn’t matter, C_i can again be assumed to be deleted. Therefore any set of valid moves on regions in both questions is essentially the same.

We just need to subtract 1 from the code of that question(Deleting the last region).

28

Let’s take the following case:
2 2 2 3 3 3 2 2 2 4 4 4 2 2 2

This can be simply reduced the the following test case.
2 3 2 4 2

In this particular case, lets consider the subarray 3 2 4, for this particular subarray your second observation doesn’t make sense. Because in the long run it doesn’t make sense to convert 2 to either 3 or 4.

Also, observations are not enough to reach a working solution, it would be helpful if you could share code, which solves the above question using similar DP as the codeforces question.

29

That statement was a bit unclear. If we change C_i we will change it to either C_{i-1} or C_{i+1}.

Code 
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int n;
vector<int> s;
int dp[N][N];
int calc(int l, int r){	
	int &res = dp[l][r];
	if(res != -1) return res;
	
	if(l > r) return res = 0;
	if(l == r) return res = 1;
    
	res = 1 + calc(l + 1, r);
	for(int i = l + 1; i <= r; ++ i)
		if(s[l] == s[i])
			res = min(res, calc(l + 1, i - 1) + calc(i, r));
	return res;
}
int main(){
	cin >> n;
    s.resize(n);
    for(auto &x : s){
        cin>>x;
    }
	memset(dp, -1, sizeof dp);
	cout << calc(0, n - 1) - 1;
	return 0;
}
30

I was not able to use the approach that is mentioned in the editorial. I said they are same because the answer to the question ONEVALUE is always 1 less than the question Clear The String.

I have another approach that I asked from my friend.
Let dp[I][j] be the number of moves to convert the subarray a[i…j] to the value a[i].
So dp[i][j] = 0 if all values in the subarray are equal to a[i] else dp[i][j] = min(dp[i][k]+dp[k+1][j]+u) where k varies from i to j-1 and u is 0 if a[i]==a[k+1] otherwise u is 1.
Now why am I converting always to 1st value of the array. I claim that there always exist such an optimal solution in which it will take minimum number of moves in converting the array to the first value of the array. You can think about it using some examples. If you don’t get it I will try to explain.
I submitted the AC solution in the Clear the String using the above approach.

31

Thanks for sharing your approach, your claim makes sense.