hackerrankで期限切れのタイムアウトが発生しました

Question

私のコードはC++の で、現在作業を完了しようとしています。

難易度下記のリンク：メディア

私のアルゴリズムは、20のテストケースのうち18のために正常に動作しています。 他の2はタイムアウトのために終了します。

私はそれが何を意味するのか知っていますが、今は自分のアルゴリズムの効率を上げることを考えていません。きちんとした、 - 私は以下の私のコードを与えている

は、誰もが「この 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

に取り組むために私を助けてくださいすることができます...すべての人間の問題によく知られた解決策が常にあります。もっともらしい、と間違っている」 - HLメンケンは

コンピュータサイエンスでは、言い換えることができます。

「そこにすべてのコンピューティングの問題の場合は、シンプルでエレガントなと間違っている解決策が存在する。」就職の面接でhackerrankのようなサイトで

問題、経路探索をゲーム内の俳優のために、3Dの宇宙船の艦隊を描きます実際にデータをふるい分けする生産システムでは、解決策があるかどうかは決してありません。

本当の問題は、常にこのです：

「この一見簡単な作業の複雑さの順序を軽減する方法を見つけます。」

aからbまでを数え、値を一緒に並べることは、線形時間アルゴリズム-O（b-a）である。 aとbが近いときはうまくいく。しかし、この問題は、最大で2^32-1の間隔を持つことが許されていることを示しています。これは40億テストのオーダーです。

この問題は、bがaよりも大きいことがわかっているので、O（log2（b-a））に減らすことができます。以下のバイナリ表現の最上位ビットで

ルック：

a 01001 (9) 
b 11001 (25) 

いくつかの共通のビットがありますので、直感的に、我々はこれらのビットが答えに1秒の残りの候補であることを想像してみてください。

しかし、bは1の値であるビットを持ち、その値はaの上位ビットよりも大きなオーダーです。

aからbまで数えるために、このトップビットより低いすべてのビットは、1と0のすべての置換に存在する必要があります。これはバイナリ表現が機能するためです。

各パーミュテーションでバイナリビットフィールドを並べ替えると、最終的にはそのフィールドのすべてのビットには0が含まれます。つまり、ビットフィールドのすべての並べ替えをAND演算した結果はゼロになります。

したがって、aの中にないbの1ビットが見つかる瞬間、aからのより低い大きさのすべてのビットを単にマスクすることができます。

今の問題は、次のようになります。

が内に存在してから、すべての下位ビットをマスクしないBにおける最上位ビットを探します。結果を返します。

私達はちょうどつまり0 < N < = 32に0 < N < 2^32）からGoogleの検索スペースを削減しました、複雑さはO（LOG2（にO（N）から減少させることができますN））。

ここでは、ビットマスクの計算を最適化することを気にしません。これは、ハッカーブランクのすべてのテストに合格します。

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