infoarena

Aici puteţi discuta despre problema Password (http://infoarena.ro/problema/password).

Asta inseamna ca trebuie sa rotim cuvantul de cat mai putine ori astfel incat sa il obtinem in ordine cat mai crescatoare a litereror?

da  :ok:

Interesanta exprimare  [-X

Mi-ati putea da si mie un hint. Singura solutie pe care o stiu la problema asta merge in N^2 si evident nu intra in timp.

http://info.devnet.ro/download.php

downlodeaza-ti articolul. :)

Ok, o sa-l citesc si o sa incerc sa il implementez.

Nu e putin cam stransa limita de timp?

Cu suffix array in O(NlogN) nu scot decat 5 puncte

Se poate face in O(n) ... si constanta la suffix array in O(n log n) e cam mare.

oricum, e mult mai lejer sa implementezi rotatii decat suff array..

Stiu asta, am si facut implementarea in O(N), dar nu prea mi se pare firesc sa iei 5 puncte cu O(NlogN)

Practic nu se poate face o deparatajre intre solutii ca si complexitate. Si totusi nu puteti spune ca NlogN e brut, ca sa primeasca 0-10 puncte

Depinde ce suffix array ai facut, eu tin minte ca luam in jur de 80 cu suffix array la problema asta.

Eu am luat 100 cu suffix array :)

O modalitate care nu ar merge ar fi sa sortezi cu qsort sufixele :)).

Intr-adevar am incercat o alta implementare si am ajuns pana la 80 de puncte folosind aceasta abordare.

Prima oara inceram sa implementez la fel ca in articolul despre siruri de sufixe de la sectiunea downloads, cu o complexitate totala O(N*logN*logN), nu O(N*logN) cum am zis la inceput (am uitat sa includ si sortarea :P). Pana la urma nu m-am lamurit daca abordarea e gresita sau implementarea mea (totusi de ce TLE si nu WA atunci?).

Cu suffix array se ia 80 puncte din cauza timpului depasit , intotdeauna algoritmul va furniza raspunsul corect , cel putin asa cred !

Normal ca va furniza raspunsul corect, dar eu ma refeream la faptul ca poate am implementat gresit arborii de sufixe. Si acum depinde de fiecare implementare, pentru ca sunt destule posibilitati, de la O(N^2*logN) pana la O(N) se pare (nu am implementat niciodata). Teoretic, in O(N) ar trebui sa intre de 100 (folosind suffix array, nu rotatii), chiar daca constanta e ceva cam mare.

A incercat cineva cu suffix array in O(N) ?

Nu cred ca merg prea bine suff array in O(n) in practica.

Am rezolvat problema asa cum e descrisa in articolul "Rotatie lexicografic minima". Am luat 80 puncte cu 4 WA. Timpii de executie sunt de 0 si 4 ms... Un hint? ce poate fi gresit?

LE: am gasit... nu era chiar ca si in articol...

Ce nu era ca in articol?

in articol apare pseudocodul urmator:luam 80 de puncte cu asta. am luat 100 modificand la linia a doua din "cat timp (p < N)" in "cat timp (p < N-1)"

Nu cred ca modificarea ta este corecta, chiar daca ai luat 100. Cred ca motivul pentru care luai 80 era ca p+l poate fi mai mare ca N, deci trebuie sa faci (p+l)%N cand indexezi S.

care sunt rotatiile?
mississippi
ississippim
ssissippimi
sissippimis
issippimiss
ssippimissi
sippimissis
ippimississ
ppimississi
pimississip
mississipp
???

la problema asta ori eram eu prea ametit si nu faceam citirea bine :)) ori kiar nu merge cu FILE *f(..)...Andrici incearca sa folosesti fstream.La mine asta era problema :angry: :angry: :angry:

mie imi citeste bine, la testul acela imi face bine, dar pentru restu nu, nu inteleg ce am gresit:(( eu lucrez in pascal:d nu in cpp

Ce modificari au facut cei care luau 80 pentru a lua 100 (cu O (N) iau TLE) ? Nu vad unde gresesc   ](*,)

Operatia modulo consuma foarte mult timp. Incearca sa scapi de ea si ar trebui sa obtii 100 de puncte.

Am facut din modulo scadere dar acelasi rezultat -> TLE pe ultimele 4 teste :(
LE: Se pare ca greseala era ca initializam prost o variabila. Multumesc lui wef si blasterz pt ajutor :D

Ma ajuta si pe mine cineva? De ce iau 4 TLE-uri cu sursa asta? Ce complexitate are strcmp?

cod:
#include<stdio.h>
#include<string.h>
char s[200005],sol[200005];
int main()
{
   freopen("password.in","r",stdin);
   freopen("password.out","w",stdout);
   int n,i,n1,nr=0;char aux;
   gets(s);n1=strlen(s);
   strcpy(sol,s);
   strcat(s,sol);
   n=strlen(s);n--;s[n]=0;
   for(i=0;i<n1;i++)
      {
          aux=s[i+n1];s[i+n1]=0;
          if(strcmp(s+i,sol)<0)
          {
              strcpy(sol,s+i);
              nr=i;
          }
          s[i+n1]=aux;
      }
   printf("%d\n",nr);
   return 0;
}

O(n).

Asta ar insemna ca complexitatea totala ar fi O(N^2)? Dar atunci de ce iau asa de mult?

Asta ma intrebam si eu.

Am citit articolul despre rotatie lexicografic minima si am o intrebare despre cazul 3.
Rotatiile sunt :

mississippi 0
ississippim 1
ssissippimi 2
sissippimis 3
issippimiss 4
ssippimissi 5
sippimissis 6
ippimississ 7
ppimississi 8
pimississip 9
imississipp 10

La pasul 8 studiem rotatia 4(dupa tabelul din articol). Rotatia minima pana in acel moment este 1. Primele pantru caractere sunt identice pentru R1 si R4, iar al cincilea caracter este "mai mic" in R4 decat in R5. Daca folosesc pasii din cazul 3 o sa am : min = 6, p = 7, l = 0, dar R4 < R6. De ce nu avem min = 4 ca potential candidat ci 6?

L.E. : Mi-am dat seama pana la urma.

Cred ca ar trebui introduse niste teste noi. Spre exemplu, cu sursa mea de 100 la problema, pe testul bab imi da raspunsul 0, desi corect ar fi 1.

De ce nu poate fi solutia ippimississ (care necesita doar 8 rotatii), fata de solutia data imississipp care necesita 10 rotatii?

Pentru că nu este cea mai mică lexicografic. m este mai mic decât p.

Frumoasa problema, dupa ceva timp i-am dat si eu de cap. :weightlift: