242 Password

[•mathboy]

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

[•wefgef]

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

[•mathboy]

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

[•dariusdarius]

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;
}

[•klamathix]

O(n).

[•dariusdarius]

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

[•klamathix]

Asta ma intrebam si eu.

[•SebiSebi]

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.

[•Kira96]

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.

[•calinbrita]

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

[•vladrochian]

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.

[•MareSite]

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