In input 3 you cannot be certain whether n=6 or n=3 has been used, therefore you can only return the intersection of the two sets.

yeah, figured out that part, intersection of all possible n is to be used. But everything done, my code now dies in TLE.I figure I am having O(n^2) complexity. Please help me out, by directing me to some better approach. Is there any DP approach or did I miss some crucial optimization step? Please help

int main(){
   int no,n,i,j,kbase,kval,top,N,misVal,counter;
   char tmp;
   bool flag;
   cin>>no;
   while(no>0){
      no--;
      string x,y;
      cin>>N;//Max length of cypher
      cin>>x;//Plain text
      cin>>y;//Encrypted text
     int kMap[x.length()][2];
     int mismatch[N+1];//As 0 is left unconsidered
    //Initializing the array containing the values of n that is never possible
     for(i=0;i<=N;i++)
         mismatch[i]=-1;
     top = -1;
     for(i=0;i<x.length();i++){
        //If both the values are known, we can determine the k values
        if((x[i]!='*')&&(y[i]!='*')){
           kval=(y[i]+26-x[i])%26;
           //Chekcing for possible mismatch
           for(j=top;j>=0;j--){
              //Mismatch occurs
              if(kMap[j][1]!=kval){
                 misVal=i-kMap[j][0];
                 mismatch[misVal]=1;
              }
           }
           top++;
           //Insert the k value and the index in the k-map
           kMap[top][0]=i;
           kMap[top][1]=kval;
        }
      }
      //If a n is not possible, so is all its factors also, calculating those values
      for(i=0;i<=N;i++){
         if(mismatch[i]==1)
           storeMisVal(misVal,N,mismatch);
      } 
      n=-1;
      char mem[x.length()];
      int k[N];//Array holding cyphers.
      counter=-1;
      //Initialzing array to hold the plaintext
      for(i=0;i<x.length();i++)
        mem[i]=1;
      //Detecting the value of n
      for(i=N;i>0;i--){
         if(mismatch[i]==-1){
            n=i;
         }else
            continue;
        counter++;
        //Initializing the values of k.
        for(j=0;j<N;j++)
          k[j]=-1;
        for(j=0;j<=top;j++){
          kbase=kMap[j][0];
          kbase%=n;
          k[kbase]=kMap[j][1];
        }
        for(j=0;j<x.length();j++){
           //The text is inelligible to compute, meaning for different n, the value is not unique.
           if(mem[j]==0) 
              continue;
          //If encrypted text is inelligible or plaintext is elligible,then print the plaintext as it is.
           if((y[j]=='*')||(x[j]!='*')){
             if(counter==0)
                mem[j]=x[j];
             else if(mem[j]!=x[j]){
                mem[j]=0;
             }
             continue;
           }
           kbase=j%n;
           if(k[kbase]==-1){
             if(counter==0)
                mem[j]=x[j];
             else if(mem[j]!=x[j]){
                mem[j]=0;
             }
             continue;
           }
           tmp=y[j]-k[kbase];
           if(tmp<65){
             if(counter==0)
            mem[j]=(char)(tmp+26);
         else if(mem[j]!=(char)(tmp+26)){
            mem[j]=0;
         }
       }
       else{
         if(counter==0)
            mem[j]=tmp;
         else if(mem[j]!=tmp){
            mem[j]=0;
         }
       }
    }
  }
  //Print the generated plaintext, for those values with conflicting for different n, original plaintext letter is used.
  for(i=0;i<x.length();i++){
     
     if(mem[i]!=0)
       cout<<mem[i];
     else
       cout<<x[i];
  }
  cout<<endl;
   }
}
//Function to store the value and all their factors as well in the mismatch array.
int storeMisVal(int val,int max,int mismatch[]){
    int i;
    if(val<=max)
       mismatch[val]=1;
    for(i=val-1;i>0;i--){
        if(val%i==0){
           if(mismatch[i]!=1)
              storeMisVal(i,max,mismatch);
        }
    }
}

BlueMary struggled with optimizing this solution in another thread. If they struggled with it, I don't stand a chance.
Search for CRYPTO4. It's easier for us to find the problem you're discussing if you reference the problem using it's code (CRYPTO4)

Good luck.

Hey leppy,
Thanks but unfortunately I can't find any such thread. Could you please give the link to the thread. Search is not showing anything

Searching the forum for CRYPTO4 returns plenty of results.

Use "oh" not "zero"

Yeah thanks, now I got it, sorry for being such a moron

Zauważyć, że skoro potrzebujemy tylko wynik modulo 10, to potęgi szybko zaczną się powtarzać, np. dla dwójki mamy 1-> 2->4->8->6->2->4->8->6 itd

Ewentualnie można problem rozwiązać ogólniej za pomocą algorytmu szybkiego (binarnego) potęgowania ;p

2
777 1
2 2

W zadaniu jest Limit pamięci: 1536MB
Dla b równego 1 000 000 000 przy wykonaniu wspomnianej instrukcji system sprawdzający nie pozwala zaalokować ~4000MB.

Sorry nie 724 KB tylko 724 K - odczytałem w menedżerze zadań.

Można jeszcze jedną rzecz zauważyć (dotyczącą podstawy) - nie widzę tego u Ciebie w kodzie, chyba, że też robisz to w taki zakręcony sposób, jak resztę i nie rzuciło mi się w oczy

Nie wiem co dokładnie pokazuje "menedżer zadań" w Windows i co dokładnie sprawdzasz, ale prosta analiza kodu wskazuje, że nie może to być pamięć alokowana przez proces.
windows.microsoft.com/pl-pl/wind ... =windows-7

Ja pod Linuxem sprawdzam zużycie pamięci używając valgrind-a

==29479== Memcheck, a memory error detector
==29479== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==29479== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==29479== Command: ./a.out
==29479== 
1   
1000000000 1000000000
==29479== Warning: set address range perms: large range [0x395a5040, 0x127c57840) (undefined)
0
==29479== Warning: set address range perms: large range [0x395a5030, 0x127c57850) (noaccess)
==29479== 
==29479== HEAP SUMMARY:
==29479==     in use at exit: 24 bytes in 5 blocks
==29479==   total heap usage: 7 allocs, 2 frees, 4,000,000,032 bytes allocated
==29479==

Tak jak się można spodziewać dla wejścia z b=10^9 Twój program alokuje ~4GB pamięci i stąd na spoj-u przekracza limit.

Proponuje zapoznaj się z narzędziami, które pokazują zużycie/alokacje pamięci pod Windows. Znalazłem taki wątek:
stackoverflow.com/questions/4134 ... or-windows2

Weź proszę przetestuj swój program. 2 do 2 = 4 - Twój algorytm mówi, że 6. 3 do 3 = 9 - daje mi odpowiedź 1.

Poddaję się. To już kolejny wariant który testuje. Szybciej i krócej nie potrafie. Spoj wskazuję błąd.

[bbone=CPP,2663]

include

include

using namespace std;

int ostatnia(int liczba)
{
int wynik=0;
wynik = liczba % 10; // pobiera cyfrę
liczba = liczba / 10; // obcina liczbę o wybraną cyfrę
return(wynik);
}

int main()
{
int ile,b;
int liczba,potega;
double wynik;

cin>>ile;
for(int i=0;i<ile;i++)
{
    cin>>liczba>>potega;
    b=ostatnia(liczba);
    wynik=pow(b,potega);
    cout<<ostatnia(wynik)<<endl;
}
return 0;

}
[/bbone]

Tu nie chodzi o to żeby napisać jak najkrócej tylko żeby działało dla zakresów podanych w zadaniu. Na forum było pisane o tym problemie w tym zadaniu wiele razy - wystarczy poszukać. Test:

1
999999999 1000000000

Poprawna odpowiedź to:

1

Twoja odpowiedź:

-8

To nie łatwiej tak:

cin >> liczba;
b = liczba % 10;

względnie tak:

int ostatnia(int liczba)
{
     return liczba % 10;
}

Jeśli wprowadzasz jakąś funkcję pomocniczą, to dobrze, żeby rzeczywiście pomagała - czy to wydajnościowo, czy jeśli chodzi o czytelność kodu. W tym przypadku w ogóle się to nie opłaca, bo dochodzi koszt wywołania, ponadto czytający musi skakać po kodzie, żeby zobaczyć, co robi Twoja dodatkowa funkcja.

Dokładnie tak.
Możesz nawet pójść jeszcze jeden albo dwa, trzy kroki dalej:
[bbone=cpp,2260] wynik = pow(liczba % 10, potega);
cout << ostatnia(wynik) << endl;[/bbone]
lub drugi krok:[bbone=cpp,2261] wynik = pow(liczba % 10, potega);
cout << wynik % 10 << endl;[/bbone]
trzeci:
[bbone=cpp,2262]cout << pow(liczba % 10, potega) % 10 << endl;[/bbone]
ale dla zakresu danych z zadania i tak pow się wysypie.

Musisz jeszcze w jakiś sposób "skrócić" wykładnik [potęgę], lub poczytać o szybkim potęgowaniu i możesz na jego bazie [algorytmie] rozwiązać to zadanie..

[tex]30^{30} = 205891132094649000000000000000000000000000000[/tex]

[tex]unsigned\; long\;long < 2^{64} = 18446744073709551616[/tex]

[tex]1\;000\;000\;000^{1\;000\;000\;000} = .............000\;000..........?????[/tex]

Tak, że nie, źle nie napisałeś, ale warto też czytać, także to co trochę wyżej już zostało napisane i warto też zaglądnąć do regulaminu - są tam też podpowiedzi, a nie od razu wrzucać pytanie.