Wonsei's blog

By Wonsei, history, 5 years ago, In English

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 &mdash; 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;
}
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Wonsei (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try this test case:

1
10 
1 1 1 2 1 2 2 2 1 2 

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