Unexpected behavior from the judge


  • 0
    I

    So I tried to solve the problem using a suffix array, and my algorithm runs in O(nlogn). I got a TLE on the largest test case (namely "aaaa...bcaaa...aa") has a length of 1000. I tried to change different parts of code to make it better, but I had no success. After that I tried to return the original string if the length was equal to 1000. To my sheer surprise, the code was judged TLE on the same test case. After that I submitted an accepted solution to check if it would get an accepted verdict again, and the judge did accept it. So, I believe there are some issues with the judge, because it keeps TLEing my code on the largest test case even if I do absolutely nothing with that string. Hope an admin would help me with this situation. Here is my code:

    class Solution {
    char A[3100];
    
    pair < pair<int, int>, int> L[3100];
    
    int P[16][3100], N, stp, cnt;
    
    int lcp(int x, int y)
    {
        if(y>= N)
            return 0;
    	int k, ret = 0;
    	if (x == y) return N - x;
    	for (k = stp - 1; k >= 0 && x < N && y < N; k--)
    	if (P[k][x] == P[k][y])
    		x += 1 << k, y += 1 << k, ret += 1 << k;
    	return ret;
    }
    
    void constructSArray()
    {
        int i;
    	for (i = 0; i < N; i++)
    		P[0][i] = A[i];
    	for (stp = 1, cnt = 1; cnt >> 1 < N; stp++, cnt <<= 1)
    	{
    		for (i = 0; i < N; i++)
    		{
    			L[i].first.first = P[stp - 1][i];
    			L[i].first.second = i + cnt < N ? P[stp - 1][i + cnt] : -1;
    			L[i].second = i;
    		}
    		sort(L, L + N);
    		for (i = 0; i < N; i++)
    			P[stp][L[i].second] = i > 0 && L[i].first.first == L[i - 1].first.first && L[i].first.second == L[i - 1].first.second ? P[stp][L[i - 1].second] : i;
    	}
    }
    
    public:
    	string longestPalindrome(string s) {
    	    if(s.length() == 1000)
    	        return s;
    	    int i;
    		int sLen = s.size();
    		if (!sLen)
    			return 0;
    		N = sLen << 1;
    		N++;
    		i = 0;
    		int j = N-1;
    		for(auto x: s)
    		{
    		    A[i++] = x;
    		    A[j--] = x;
    		}
    		A[sLen] = (char)127;
    		A[N] = 0;
    		
    		constructSArray();
    		int prv = -1;
    
    		int ans = 1, lptr = 0, rptr, cur;
    		
    		for(i=0; i<sLen; i++)
    		{
    		    cur = lcp(i+1, N-i);
    		    cur <<= 1;
    		    cur++;
    		    if(cur>ans)
    		    {
    		        ans = cur;
    		        lptr = i - (cur>>1);
    		    }
    		    cur = lcp(i+1, N - i - 1);
    		    cur <<= 1;
    		    if(cur>ans)
    		    {
    		        ans = cur;
    		        lptr = 1 + i - (cur>>1);
    		        
    		    }
    		}
    		
    		string ret = "";
    		for ( i = lptr ; i<ans+lptr; i++)
    			ret += A[i];
    
    		return ret;
    	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.