hackerrank에서 마감 시간 초과 됨

Question

내 코드는 C++ 이며 현재 작업을 완료하려고합니다. 내 알고리즘 (18) (20) 중 테스트 케이스에 대한 벌금을하고있다

매체 링크

난이도 아래에 주어진. 기타 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 멘켄은

컴퓨터 과학에서 우리는 바꿔 수 있습니다

,536,913 63,210

"이 모든 컴퓨팅 문제는, 간단한 우아하고 잘못된 해결책을 존재한다."면접에서 hackerrank 같은 사이트에

문제, 길 찾기 게임에서 배우에 대한 차원에서 우주선의 함대를 그리기 , 실제로 데이터를 거치는 모든 생산 시스템에서 솔루션이 있는지 여부는 결코 아닙니다.

은 진짜 문제는 항상 이것이다 : ".이 겉으로는 간단한 작업의 복잡성의 순서를 줄일 수있는 방법을 찾아"

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의 whos 값인 비트가 a의 최상위 비트보다 큰 순서입니다.

a에서 b까지 계산하려면이 최상위 비트보다 낮은 모든 비트가 1과 0의 모든 순열에 존재해야합니다. 이진 표현이 작동하는 방식이기 때문입니다.

각 순열을 통해 이진 비트 필드를 순차적으로 바꾸면 결국 해당 필드의 모든 비트는 0을 포함하게됩니다. 즉, 비트 필드의 모든 순열을 AND 연산 한 결과는 0입니다.

그래서 우리가 a에없는 b에서 1 비트를 찾으면, a에서 하위 비트의 모든 비트를 단순히 마스크 할 수 있습니다.

은 이제 문제가된다 :

는 존재와 모든 하위 순서 비트를 마스크하지 않는 B에서 가장 높은 비트를 찾아보십시오. 결과를 리턴하십시오.

우리는 단지 환언 0 < N < = 32. 0 < N < 2^32)에서 우리의 검색 공간을 축소 한 복잡도는 O (LOG2 (에 O (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); 
}