https://codeforces.me/contest/1335/problem/E1
When I run the test, it keeps going well, and suddenly it fails on test 10 data 596 or something, so I cannot see what test case is causing the problem. Im asking for help after 3+hours of coding ! Id really appreciate any help.
Source code below, with detail;
It works on almost all cases, but there seems to be a counterexample that I seem to be missing. Thanks :)
#include <iostream>
#include <vector>
using namespace std;
int min_num(int a, int b)
{
return a<b ? a : b;
}
void solve()
{
int n;
int a[200002];
vector<int> cnt[202];
int ccnt[200002]={0,};
cin >>n;
int i,j,k;
for(i=1 ; i<=n ; i++)
{
cin >>a[i];
cnt[a[i]].push_back(i);
//this cnt stores the location of each number
//ex) 1 1 3 3 2 1 -> cnt[1] = 1, 2, 6 cnt[2] = 5, cnt[3] = 3, 4
ccnt[a[i]]++;
}
int cntmax = 0;
for(i=1 ; i<=200000 ; i++) if(cntmax < ccnt[i]) cntmax = ccnt[i];
// this for loop is for a palindrome that uses only 1 kind of number, so the number
// with the most count is the longest palindrome
// realmax is where the final answer will be stored
int realmax=cntmax;
for(i=1 ; i<=200 ; i++) // middle part of palindrome
{
for(j=1 ; j<=200 ; j++) // left/right part of palindrome
// I am searching for the longest palindrome which uses i as the left/right part
// and j as the middle part such like i i i j j j j i i i
{
int max = 0;
if(i!=j && cnt[i].size() > 0 && cnt[j].size() > 0)
{
vector<int> b;
int l=0;
for(k=0; k<cnt[i].size() ; k++)
{
while(1)
{
if(l==cnt[j].size()) break;
if(cnt[j][l] < cnt[i][k])
{
l++;
}
else break;
}
b.push_back(l);
}
//b stores the number of cnt[j] members that is less than each cnt[i] members
//if cnt[i] = 1 2 7 8, cnt[j] = 3, 5
// b will be 0, 0, 2, 2 (b[i] = count of cnt[j] members that is less than cnt[i][k]
for(k=0 ; k<b.size() ; k++)
{
int sum=0;
int frontback = min_num(b[k], cnt[j].size()-b[k]);
sum += frontback * 2;
//frontback is the length of the surrounding two pallindromes
int t;
int count = 0;
// now we calculate the length of the middle part of the palindrome
// if cnt[j].size — b[t] is more than the frontback, we can extend the middle part
for(t=k ; t<b.size() ; t++)
{
if(cnt[j].size() - b[t] >= frontback) count++;
else break;
}
sum+=count;
if(max < sum) max=sum;
}
}
if(realmax < max) realmax = max;
}
}
cout << realmax << "\n";
return;
}
int main(void)
{
int n;
cin >> n;
while(n--)
{
solve();
}
return 0;
}
Auto comment: topic has been updated by Wonsei (previous revision, new revision, compare).
Try this test case:
Output of your code is 5, the answer is 6.
P.S. I recommend you to learn stress testing, it can help you a lot