Make difference array, where dif[i] = i - a[i]

4
3 1 4 2
answer : 3

12
1 3 5 6 4 1 3 5 7 10 8 2
answer : 11

8
8 2 5 8 1 3 4 5
answer : 4

9
5 3 2 5 4 7 9 2 1
answer : 9

10
2 2 4 4 5 8 7 9 9 1
answer : 1

Edited by author 10.11.2013 18:43

1) Don't forget, that pupils sit in a circle!
2) You have to count how many pupils you can satisfact with choice 'i' boy at first (even he doesn't to be so :-) ). There are algo claimed O(n)
3) If you have such info, it's so easy to calculate the answer ;-)
I can send the solution to your mail.

What is special about this problem?
I get WA 7 all the time.

My algo
[code deleted]
Edited by author 01.01.2013 16:44

Edited by author 01.01.2013 20:16

Edited by author 01.01.2013 20:18

Edited by moderator 29.11.2019 14:27

What is it???

Edited by author 16.10.2010 17:42

Edited by author 16.10.2010 17:43

I try with this program....but the answer is "wrong answer in test 10"...do you know why???

[code deleted]

Edited by moderator 29.11.2019 14:29

Пробовал тесты в другой теме-не помогает.
Программу уже тестил буквально на всё!!!!!!!!

if you have wa13, try test

4
4 4 4 3

answer is 2

i'm using shellSort and good algo, but wa 7, why???
my program on my machine passes 99999 numbers in 0.2-0.5 seconds! and your 7 test in 0.156 seconds!!!

and my algo passes 999 999 numbers(6.7Mb on the txt xD ) for 3 seconds!

AND i'm using new algo))) my new algo do O(n*2)(static) operation))
But WA 7((( in 0.14 seconds
If there are several possible answers, output any of them.???? check its condition

sorry for my english




Edited by author 12.11.2010 13:47

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

beg for sample...

Can someone give me test 6?

why????