AntiPalindromic Strings

Question

На самом деле это одна из проблем, связанных с хакерством. Вот ссылка на проблему: https://www.hackerrank.com/challenges/antipalindromic-strings

Я как-то понял способ найти ответ. Но проблема в том, что мой код не принимается из-за тайм-аута. Пожалуйста, помогите мне, какая часть делает мой код медленнее.

Это мой код:

int anti_palindrome(long int n,long int m,int mod) 
{ 

    int prod; 
    prod=m; 
    if(n>1) 
     prod=prod*(m-1); 
    if(n>2) 
    { 
     n=n-2; 
     while(n) 
     { 
      prod=prod*(m-2); 
      n--; 
     } 
    } 
    return prod%mod; 
} 

int main() 
{ 
    char scanned[1000]; 
    int input = 0; 
    int T=0; 
    int T_cur=0; 
    long int N,M; 
    char str[1000]; 
    int mod=1000000007; 



    while(fgets(scanned,1000,stdin)) 
    { 
     switch(input) 
     { 
     case 0: { 
      T=atoi(scanned); 
      input=1; 
     } 
      break; 
     case 1: { 
      T_cur++; 
      strcpy(str,scanned); 
      sscanf(str,"%d %d",&N,&M); 
      //printf("%lf %lf\n",N,M); 
      printf("%d\n",anti_palindrome(N,M,mod)); 
     } 
      break; 
     } 

     if(T_cur==T) 
      break; 
    } 

    return 0; 
} 

Любой один прогон программы, возможно, придется обрабатывать до 10 N, M пар, с N и M каждого между 1 и 10 .

Answer 1

Пожалуйста, помогите мне, какая часть делает мой код медленнее.

Не так много деталей для рассмотрения. Вообще говоря, I/O намного медленнее, чем вычисление, но у вас больше нет ввода-вывода, чем нужно, поэтому давайте не будем этого делать.

Рассмотрите, пожалуйста, свою функцию anti_palindrome(). В общем случае он петли N раз, выполняя три арифметические операции и два назначения на каждой итерации. Это не так дорого, но вы можете иметь миллиард итераций на каждый тестовый пример и десять тысяч тестовых случаев, в общей сложности около 5x10 смешанных операций. Это количество операций займет больше нескольких секунд.

Пока я нахожусь, я вижу, что ваш алгоритм в любом случае ошибочен. Вы должны сообщить ответ modulo 10 + 7, но задолго до того, как вы дойдете до конца вычисления, вы переполнили бы переменную prod. Полученное поведение не определено. Если prod имел неподписанный тип, тогда поведение было бы определено, но все же неправильно. Переключение на pow() вместо цикла значительно улучшило бы производительность, но не решило бы эту проблему. Вам нужно что-то умнее.

Answer 2

Как m-2 является постоянным, напишите m= m-2; перед циклом. Теперь остается то, что выполняется n раз prod=prod*m;. Это эквивалентно prod= prod*pow(m,n);. Математическая библиотека может иметь эффективную реализацию pow(), которая предотвратит вашу проблему с синхронизацией.

В C вам, возможно, придется указывать параметры в double, а возвращаемое значение - в long int.

int anti_palindrome(long int n,long int m,int mod) 
{ 
    int prod; 
    prod=m; 
    if(prod>1) 
     prod=prod*(m-1); 
    if(prod>2) 
    { 
     n=n-2; 
     m=m-2; 
     prod= prod*pow(m,n); 
    } 
    return prod%mod; 
}