Codeforces 634div3 E doubt

1

If anyone has solved this question in 634 div3 contest , please tell why my code isn’t working . I have tried each and every possible input .

// #pragma GCC optimize "trapv" Uncomment when dealing with huge numbers
/*<----------PBDS---------->

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
template <typename T>
using order_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

order_set<datatype>oset;
Kth smallest : *oset.find_by_order(k-1); // 0 based index
No of elements less than k : oset.order_of_key(k);
Erase X : oset.erase(x)
<----------PBDS---------->*/
#include<iostream>
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define pb(x) push_back(x)
#define gcd(a,b) __gcd(a,b)
#define all(v) v.begin(),v.end()
#define lcm(a,b) (a*b)/gcd(a,b)
#define bits(x) __builtin_popcountll(x)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int32_t main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		int a[n];
		int pref[27][n];
		int suff[27][n];
		memset(pref,0,sizeof(pref));
		memset(suff,0,sizeof(suff));
		for(int i = 0 ; i < n ; i++ ){
			cin >> a[i];
		}
		if(n==1){
			cout << "1\n";
		}
		else if(n==2){
			if(a[0]==a[1]){
				cout << "2\n";
			}
			else{
				cout <<"1\n";
			}
		}
		else{
			for(int i = 0 ; i < n ; i++ ){
			if(i==0){
				pref[a[i]][i]++;
			}
			else{
				for(int j = 1 ; j <= 26 ; j++ ){
					pref[j][i]+=pref[j][i-1];
				}
				pref[a[i]][i]++;
			}
		}
		for(int i = n-1 ; i>=0 ; i--){
			if(i==n-1){
				suff[a[i]][i]++;
			}
			else{
				for(int j = 1 ; j <= 26 ; j++ ){
					suff[j][i]+=suff[j][i+1];
				}
				suff[a[i]][i]++;
			}
		}
		int ans = 1;
		for(int i = 1 ; i < n-1  ; i++ ){
			int c = 0;
			 for(int j = 1 ; j <= 26  ; j++ ){
			 	 if(j!=a[i])
			 		c = max(c,min(pref[j][i-1],suff[j][i+1]));
			 }
			 c = c*2;
			 c+=pref[a[i]][i-1]+suff[a[i]][i+1]+1;
			 ans = max(ans,c);
		}
		cout << ans << "\n";
		}
		
	}

}

Thanks in advance

2

I solved E1 using prefix sums as well. I am posting my code, maybe you get error idea. Sorry, I am too lazy to read code and find error. Please ignore array size I started to modify it for E2, just same array size of E1 constraints.

Code 
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const int inf = 1e9;
const int N = 2e5+10;
int t,f[N][208],n,a[N],lst[208],bst[N][208];

int main(){
    int t;
    cin >> t;
    while(t--){
        memset(f,0,sizeof(f));
        memset(lst,0,sizeof(lst));
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i)scanf("%d",a+i);
        for(int i = 1; i <= n; ++i){
            for(int j = 0; j < 28; ++j)f[i][j]=f[i-1][j];
            f[i][a[i]]++;
            lst[a[i]] = i;
        }
        int ans = 0;
        for(int i = 1; i <= n; ++i){
            int left = f[i][a[i]];
            for(int k = i+1; k < lst[a[i]]; ++k){
                int right = f[lst[a[i]]][a[i]] - f[k][a[i]];
                ans = max(ans,2*min(left,right)+f[k][a[k]]-f[i][a[k]]);
            }
            ans = max(ans,f[lst[a[i]]][a[i]]);
        }
        printf("%d\n",ans);
    }   
}
3

Okay thanks!! :slight_smile:

4

Can you link your submission? I want to see the kind of test case it failed on.

5

@everule1 , thanks for your concern :slight_smile: . Save your time :slight_smile: , i’ve just found the testcase where it fails. My logic is also considering non palindromic subsequences

Input
1
6
1 1 2 1 2 1

Expected output : 5
My code’s output : 6

6

How after seeing question you thought of this approach??

1 Like
7

Constraints were low, so O(N^2) was in my favour. Thus if I I can find two points i and j where my a part ends and restarts. Then to fill b maximum occurrence of any character will work.