ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1794. Masterpieces of World Architecture

Time Limit Exceeded #7
Posted by Anton Papin 25 Oct 2010 13:13
Here is my code:

#include <iostream>

using namespace std;

//long int _wants[200002];
//long int _nums[100001];
long int n;

long int *_wants;
long int *_nums;

int main()
{
   cin>>n;
   _wants = new long int[2*n];
   _nums = new long int[n];

   for (long int i=0; i<n; i++) cin>>_wants[i];

   for (long int i=0; i<n; i++)
   {
      _nums[i]=_wants[i];
      _wants[i]-=i+1;
      _wants[i+n]=_wants[i]-n;
   }

   long int _max=_wants[0];
   long int _pos=1;
   long int _count=1;
   for (long int j=0; j<n; j++)
   {
      if (_wants[j]>-n)
      {
         _count=1;
         for (long int i=j+1; i<2*n; i++)
         {
            if (_wants[i]==_wants[j])
            {
               _wants[i]=-n;
               _count++;
            }
         }
         _wants[j]=_count;
         if (j==0) _max=_wants[j];
         else if (_wants[j]>_max)
         {
            _max=_wants[j];
            _pos=j-(_nums[j])+2;
         }
      }
   }

   if (_pos<=0) _pos+=n;

   cout<<_pos<<endl;
   return 0;
}

My algo is following: we take the input twice, like this: for "4 1 2 3" - "4 1 2 3 4 1 2 3". For each standing in array of meanings we count arr[i]-i . For students standing in a right way to answer counting gives same results. Then we count a number of each difference in our array of 2*n elements, but only for meanings in left half of arr (and write it to the beginning of the arr). After that we will have the length of the longest sequence and its beginning position. There's no problem to say who must be first.

I found out that for n=99999 there's a TL. But why? This algo is enough fast...

Edited by author 25.10.2010 13:15
Re: Time Limit Exceeded #7
Posted by {SESC USU} Zaynullin 26 Oct 2010 23:58
your program do O(n^2) operation (you have two embedded loop)