Zadatak LPERMUT
Pozdrav,
http://www.spoj.pl/problems/LPERMUT/
Trebam pomoc oko ovog zadatka. Nista sto napravim nije dovoljno brzo.
- +/- sve poruke
- ravni prikaz
- starije poruke gore
17 godina
neaktivan
offline
RE: Zadatak LPERMUT
Pošalji ovdje source pa ćemo optimizirati.
Poruka je uređivana zadnji put čet 23.12.2010 11:39 (Black Deus Typhon).
Zadatak LPERMUT
Moj algoritam gleda sljedeće.
Ukoliko je broj jedinstvenih elemenata nekog intervala( L ) jednaka duljini tog intervala,
te suma članova jednaka L * ( L / 2 ) / 2 tada je L rjesenje.
Da bi gledao broj jedinstvenih elemenata implementirao sam BIT( binary indexed tree, Fenwick tree ) ili logaritamsku strukturu kako je zovu kod nas.
Sada sam razmatrao još 2 rješenja.
Da tražim "1" i razrađujem elemente oko njih.
Da trazim do kojeg indexa neki element vrijedi.
val : 1 2 4 2 5 4 2 3
idx : 3 3 5 6 8 8 8 8
2 se pojavljuje na 7 mjestu te zbog toga svi brojevi koji prethode dvojci na poziciji 4 mogu vrijediti samo do 6 pozicije nakon toga sigurno se događa repeticija.
nakon toga razrađujem intervale.
Idem kroz array te za svaki element radim sljedeće.
neka je x - idx[x] + 1 duljina intervala gdje idx označuje do kojeg elementa vrijedi.
gledam koliko mi fali ili nedostaje do sume x - idx[x] + 1 brojeva te se za toliko pomaknem.
Ovo rješenje ne znam efikasno implementirati, ali mislim da se da u O( n^2 ) za razliku od onog prvog sa O( n^2 log^2 n )
Poruka je uređivana zadnji put ned 26.12.2010 12:07 (Budimir).
Zadatak LPERMUT
#include <cstdio>
#include <cstring>
const int NX = 100001;
typedef long long LL;
int N;
int A[ NX ];
int last[ NX ];
LL sum[ NX ];
struct Fenwick {
LL L[ NX ];
Fenwick() { memset( L, 0, sizeof L ); }
void add( int x ) { for( ; x <= N; x += x&-x ) ++L[x]; }
void remove( int x ) { for( ; x <= N; x += x&-x ) --L[x]; }
LL sum( int x ) { LL r = 0LL; for( ; x > 0; x -= x&-x ) r += L[x]; return r; }
LL query( int x, int y ) { return sum( y ) - sum( x-1 ); }
} F;
int main()
{
sum[0] = 0LL;
scanf( "%d", &N );
for( int i = 1; i <= N; i++ ) {
scanf( "%d", A+i );
sum[i] = sum[i-1] + (LL)A[i];
}
memset( last, 0, sizeof last );
int sol = 1;
for( int i = 1; i <= N; i++ ) {
if( last[ A[i] ] ) F.remove( last[ A[i] ] );
F.add( last[ A[i] ] = i );
for( int j = 1; j < i && i-j+1 > sol; j++ ) {
int L = i-j+1;
if( F.query( j, i ) != L ) continue;
if( sum[i] - sum[j-1] == (LL)( L*(L+1)/2 ) ) sol = L;
}
}
printf( "%d\n", sol );
}
Poruka je uređivana zadnji put ned 26.12.2010 12:09 (Budimir).