Terminé en raison du délai d'expiration dans hackerrank

Question

Mon code est en C++ et tente actuellement de terminer la tâche. lien ci-dessous

Niveau de difficulté: moyen

mon algorithme fonctionne bien pour 18 des 20 cas de test. autres 2 sont terminées en raison du délai d'expiration.

Je sais ce que cela signifie mais maintenant je ne comprends pas l'idée d'augmenter l'efficacité de mon algorithme.

J'ai donné mon code ci-dessous, quelqu'un peut me aider S'IL VOUS PLAÎT pour lutter contre cette https://www.hackerrank.com/challenges/and-product

#include <cmath> 
    #include <cstdio> 
    #include <vector> 
    #include <iostream> 
    #include <algorithm> 
    using namespace std; 

    int main() 
    { 
     int t; 
     unsigned long int x,y,a; 
     cin>>t; 
     while(t) 
     {  
      cin>>x>>y; 
      a=x; 
       for(;x<=y;x++) 
       a=a&(x); 

      cout<<a<<"\n"; 
      t--; 
     } 

    return 0; 
    } 

Answer 1

» ... il y a toujours une solution bien connue à chaque problème humain - propre, . plausible, et le mal » - HL Mencken

En Informatique, nous pouvons reformule:

« Pour tous les problèmes de l'informatique, il existe une solution simple, élégante et le mal. »

Problèmes sur des sites comme HackerRank, dans les entretiens d'embauche, pathfinding pour les acteurs dans un jeu, en tirant une flotte de vaisseaux spatiaux en 3D et, en fait, dans tout système de production qui consiste à passer au crible des données, il ne s'agit jamais de savoir s'il existe une solution.

La vraie question est toujours ceci:

« Trouver un moyen de réduire l'ordre de complexité de cette tâche apparemment banale. »

comptage a-b tandis que les valeurs Anding ensemble est un algorithme en temps linéaire - O (b-a). C'est bien quand a et b sont proches. Mais ce problème vous indique qu'ils sont autorisés à avoir un intervalle allant jusqu'à 2^32-1, ce qui est de l'ordre de 4 milliards de tests. En l'occurrence, ce problème peut être réduit à O (log2 (b-a)) car nous savons que b est plus grand que a.

Regardez le bit haut des représentations binaires suivantes:

a 01001 (9) 
b 11001 (25) 

Il y a quelques morceaux communs si intuitivement nous imaginons que ces bits sont candidats pour rester 1s dans la réponse.

Cependant, b a un bit qui est un 1 dont la valeur est d'un ordre de grandeur plus grand que le bit supérieur de a. Pour compter de a à b, chaque bit inférieur à ce bit de tête devra exister dans chaque permutation de 1s et 0s - car c'est ainsi que fonctionnent les représentations binaires.

Si nous permutons un bitfield binaire à travers chaque permutation, alors finalement chaque bit de ce champ contiendra à un certain point un 0. Cela signifie que le résultat de ANDing ensemble chaque permutation d'un champ de bit est zéro.Donc, au moment où nous trouvons un 1 bit dans b qui n'est pas dans un, nous pouvons simplement masquer tous les bits de magnitude inférieure à partir de a.

Maintenant, le problème devient:

Trouver le bit de b qui n'existe pas dans un masque et tous les bits hors d'ordre inférieur d'un. Renvoie le résultat.

Nous avons juste réduit notre espace de recherche de 0 < N < 2^32) à 0 < N < = 32. En d'autres termes, la complexité peut être réduit de O (N) à O (log2 (N)).

Voici une solution naiive - il ne s'agit même pas d'optimiser le calcul des masques de bits - qui passe tous les tests sur hackerrank.

#define TESTING 0 

#include <iostream> 
#include <string> 
#if TESTING 
    #include <sstream> 
#endif 
#include <cstdint> 

using namespace std::literals; 

#if TESTING 

const char test_data[] = 
R"__(
3 
12 15 
2 3 
8 13 
)__"; 
#endif 

bool has_bit(const std::uint32_t x, int bitnum) 
{ 
    return (x & (1 << bitnum)) != 0; 
} 

constexpr std::uint32_t mask_here_down(int bitnum) 
{ 
    std::uint32_t result = 0; 
    while (bitnum--) 
    { 
     result |= std::uint32_t(1) << bitnum; 
    } 
    return result; 
} 

void algo(std::istream& in, std::ostream& out) 
{ 
    std::uint32_t a,b; 
    in >> a >> b; 

    for (int bit = 32 ; bit-- ;) 
    { 
     if (has_bit(b, bit) and not has_bit(a, bit)) 
     { 
      std::cout << (a & ~mask_here_down(bit)) << std::endl; 
      break; 
     } 
    } 
} 

void run_tests(std::istream& in, std::ostream& out) 
{ 
    int n; 
    in >> n; 

    while (n--) 
    { 
     algo(in, out); 
    } 
} 

int main() 
{ 
    #if TESTING 
    auto in = std::istringstream(test_data); 
    #else 
    auto& in = std::cin; 
    #endif 

    run_tests(in, std::cout); 
}