https://codeforces.net/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;↵
}↵
~~~~~
↵
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;↵
}↵
~~~~~
