'Terminated due to timeout'
'Terminated due to timeout'
为什么此代码在 Hackerrank 上显示“因超时而终止”？
我正在尝试在 第 29 天完成一项任务：在 30 天的代码 中按位与 [=23] =]黑客排名。这是任务：
Task
Given set S = {1,2,3,...N}. Find two integers, A and B (where A < B), from set S such that the value of A & B is the maximum possible and also less than a given integer, K. In this case, & represents the bitwise AND operator.
Input Format
The first line contains an integer, T, the number of test cases. Each of the T subsequent lines defines a test case as 2
space-separated integers, N and K, respectively.
Constraints
1 <= T <= 10^3
2 <= N <= 10^3
2 <= K <= N
Output Format
For each test case, print the maximum possible value of A & B on a new line.
Sample Input
3
5 2
8 5
2 2
Sample Output
1
4
0
Explanation
N = 5, K = 2, S = {1,2,3,4,5}
All possible values of and are:
1. A = 1, B = 2; A & B = 0
2. A = 1, B = 3; A & B = 1
3. A = 1, B = 4; A & B = 0
4. A = 1, B = 5; A & B = 1
5. A = 2, B = 3; A & B = 2
6. A = 2, B = 4; A & B = 0
7. A = 2, B = 5; A & B = 0
8. A = 3, B = 4; A & B = 0
9. A = 3, B = 5; A & B = 1
10. A = 4, B = 5; A & B = 4
The maximum possible value of A&B that is also < (K = 2) is 1, so we print 1 on a new line.
这是我的代码：
import math
import os
import random
import re
import sys
if __name__ == '__main__':
t = int(sys.stdin.readline())
for t_itr in range(t):
nk = sys.stdin.readline().split()
n = int(nk[0])
k = int(nk[1])
lst1 = [(a, b) for a in range(1, n + 1) for b in range(a + 1, n + 1)]
lst2 = [ a & b for (a,b) in lst1 if a & b < k]
print(max(lst2))
此任务共有 6 个测试用例，在测试用例 1 和 2 中，我的代码是 True，但在接下来的 4 个测试用例中，它引发：'因超时而终止 '.
你能帮我解释一下我哪里错了吗？我该怎么做才能完成所有测试用例？谢谢你帮助我！
使（某物）小于K的（某物）的最大值应该是K-1。除非出于某种原因不可能。
那么让我们来看看：
for n in range(2, 256):
for k in range(2, n + 1):
m = max(a & b for a in range(1, n + 1) for b in range(a + 1, n + 1) if a & b < k)
t = "*" if m == k - 1 else " "
print("{:s} {:3d} {:3d} {:3d} {:08b} {:08b} {:08b} {:3d} {:3d}".format(t, n, k, m, n, k, m, n - k, k - m))
示例输出：
N K M N K M N-K K-M
----------------------------------------------
2 2 0 00000010 00000010 00000000 0 2
* 3 2 1 00000011 00000010 00000001 1 1
* 3 3 2 00000011 00000011 00000010 0 1
* 4 2 1 00000100 00000010 00000001 2 1
* 4 3 2 00000100 00000011 00000010 1 1
4 4 2 00000100 00000100 00000010 0 2
* 5 2 1 00000101 00000010 00000001 3 1
* 5 3 2 00000101 00000011 00000010 2 1
5 4 2 00000101 00000100 00000010 1 2
* 5 5 4 00000101 00000101 00000100 0 1
* 6 2 1 00000110 00000010 00000001 4 1
* 6 3 2 00000110 00000011 00000010 3 1
6 4 2 00000110 00000100 00000010 2 2
* 6 5 4 00000110 00000101 00000100 1 1
6 6 4 00000110 00000110 00000100 0 2
* 7 2 1 00000111 00000010 00000001 5 1
* 7 3 2 00000111 00000011 00000010 4 1
* 7 4 3 00000111 00000100 00000011 3 1
* 7 5 4 00000111 00000101 00000100 2 1
* 7 6 5 00000111 00000110 00000101 1 1
* 7 7 6 00000111 00000111 00000110 0 1
* 8 2 1 00001000 00000010 00000001 6 1
* 8 3 2 00001000 00000011 00000010 5 1
* 8 4 3 00001000 00000100 00000011 4 1
* 8 5 4 00001000 00000101 00000100 3 1
* 8 6 5 00001000 00000110 00000101 2 1
* 8 7 6 00001000 00000111 00000110 1 1
8 8 6 00001000 00001000 00000110 0 2
* 9 2 1 00001001 00000010 00000001 7 1
* 9 3 2 00001001 00000011 00000010 6 1
* 9 4 3 00001001 00000100 00000011 5 1
* 9 5 4 00001001 00000101 00000100 4 1
* 9 6 5 00001001 00000110 00000101 3 1
* 9 7 6 00001001 00000111 00000110 2 1
9 8 6 00001001 00001000 00000110 1 2
* 9 9 8 00001001 00001001 00001000 0 1
显然，最大值通常是 K-1（加星号的行），因此当它不是 K-1 时可能更容易找出。另外，最大值似乎是 K-1 或 K-2。
另一个测试，仅在最大值不是K-1时显示。这次先按K排序，再按N排序。
for k in range(2, 256):
for n in range(k, 256):
m = max(a & b for a in range(1, n + 1) for b in range(a + 1, n + 1) if a & b < k)
if m != k - 1:
print("{:3d} {:3d} {:3d} {:08b} {:08b} {:08b} {:3d} {:3d}".format(n, k, m, n, k, m, n - k, k - m))
然后是输出中的示例。
N K M N K M N-K K-M
----------------------------------------------
2 2 0 00000010 00000010 00000000 0 2
----------------------------------------------
4 4 2 00000100 00000100 00000010 0 2
5 4 2 00000101 00000100 00000010 1 2
6 4 2 00000110 00000100 00000010 2 2
----------------------------------------------
6 6 4 00000110 00000110 00000100 0 2
----------------------------------------------
8 8 6 00001000 00001000 00000110 0 2
9 8 6 00001001 00001000 00000110 1 2
10 8 6 00001010 00001000 00000110 2 2
11 8 6 00001011 00001000 00000110 3 2
12 8 6 00001100 00001000 00000110 4 2
13 8 6 00001101 00001000 00000110 5 2
14 8 6 00001110 00001000 00000110 6 2
----------------------------------------------
10 10 8 00001010 00001010 00001000 0 2
----------------------------------------------
12 12 10 00001100 00001100 00001010 0 2
13 12 10 00001101 00001100 00001010 1 2
14 12 10 00001110 00001100 00001010 2 2
----------------------------------------------
14 14 12 00001110 00001110 00001100 0 2
----------------------------------------------
16 16 14 00010000 00010000 00001110 0 2
17 16 14 00010001 00010000 00001110 1 2
18 16 14 00010010 00010000 00001110 2 2
19 16 14 00010011 00010000 00001110 3 2
20 16 14 00010100 00010000 00001110 4 2
21 16 14 00010101 00010000 00001110 5 2
22 16 14 00010110 00010000 00001110 6 2
23 16 14 00010111 00010000 00001110 7 2
24 16 14 00011000 00010000 00001110 8 2
25 16 14 00011001 00010000 00001110 9 2
26 16 14 00011010 00010000 00001110 10 2
27 16 14 00011011 00010000 00001110 11 2
28 16 14 00011100 00010000 00001110 12 2
29 16 14 00011101 00010000 00001110 13 2
30 16 14 00011110 00010000 00001110 14 2
----------------------------------------------
18 18 16 00010010 00010010 00010000 0 2
----------------------------------------------
所以当max不是K-1时，好像总是K-2，而且K必须是偶数。
考虑 p>0 的 K=2**p，以简化（即，忘记 K 的高位，即使是 K）。 "natural" max应该是K-1，即2**p-1.
示例：
在二进制中，对于 K=1000，自然最大值为 111。但是如果我们手头的 A 和 B 的所有值都小于 K，则不会发生这种情况：B 的最大值为 111 ，但是 A 必须更小，因此至少会丢失一位。最大值将是 110，即 K-2。
当 N 不大于 1000 时会出现此问题：如果它足够大，那么我们就有足够的 A 和 B 值来得到 A&B=111。具体来说，如果 N 至少为 1111，则 A=111 且 B=1111，我们就完成了。
当 K 不是 2 的幂时，它只是稍微复杂一些。
现在，您应该完成了所有必要的工作。
最后检查。
def p2(k):
p = 1
while k % (2 * p) == 0:
p *= 2
return p
count1 = count2 = 0
for k in range(2, 256):
print("-" * 60)
for n in range(k, 256):
m = max(a & b for a in range(1, n + 1) for b in range(a + 1, n + 1) if a & b < k)
t1 = "*" if m == k - 1 else " "
if k % 2 == 0:
p = p2(k)
t2 = "*" if n <= k + p - 2 and m == k - 2 else " "
else:
t2 = " "
if t1 == t2:
count1 += 1
else:
count2 += 1
print("{:s} {:s} {:3d} {:3d} {:3d} {:08b} {:08b} {:08b} {:3d} {:3d}".format(t1, t2, n, k, m, n, k, m, n - k, k - m))
print(count1, count2)
从中可以学到什么？
- 想想算法：只抛出明显的解决方案通常不是很好。有时它足够好，但通常不在 Hacker Rank 上：他们设计测试来检测和拒绝复杂性较差的解决方案。
- 用铅笔和纸试试。如果它太复杂，最接近铅笔和纸的方法是使用糟糕的算法打印一些有用的输出，以尝试了解如何改进它。
- 仔细阅读输出，找到模式。改进程序以显示更多输出以证实您的直觉。
- 当有什么有趣的东西时，证明它（这里的证明远未完成，但你至少应该明白它为什么有效）。
- 通过 运行 另一项测试，检查您是否没有遗漏其他问题。
最后说明：为了得到除以 K 的 2 的最大次方，我使用了一个循环。有一个更好的方法，通过考虑 K^(K-1)（其中 ^ 表示异或，如 Python），你会发现。
这是一种在优化代码时经常有用的位黑客。您会发现其他示例 here and there.
回复评论
- 如果K是奇数，那么因为K<=N你可以选择B=K，A=K-1，然后A&B=K-1，所以如果K是奇数你总能得到K-1。最大值不能大于 K-1，因为它是条件之一（A&B 的最大值使得 A&B
- 如果K是偶数，N足够大，可以选A=K-1，K=K | (K ^ (K-1)), 然后选择 B=K | (K^(K-1))。所以A&B=K-1是可能的，而且不能更大，所以是max.
- 其他情况（K为偶数，N不够大），则取A=K-2，B=K-1，A&B=K-2。正如我在答案中的示例中解释的那样，不可能获得 K-1，因此 K-2 是最大值。
条件可以简化：
- 首先，K|(K^(K-1))总是等于K|(K-1)（在这两种情况下，我们将LSB侧的所有0替换为1）。
- 第二个化简：如果K是奇数，那么K|K-1总是等于K，那么N>=K|(K-1)总是成立。因此，在所有情况下检查是否 N>=K|(K-1) 就足够了，永远不要检查 K 是否为奇数。
总而言之：
如果N>=K|(K-1)，最大值为K-1，否则为K-2。
为什么此代码在 Hackerrank 上显示“因超时而终止”？
我正在尝试在 第 29 天完成一项任务：在 30 天的代码 中按位与 [=23] =]黑客排名。这是任务：
Task
Given set S = {1,2,3,...N}. Find two integers, A and B (where A < B), from set S such that the value of A & B is the maximum possible and also less than a given integer, K. In this case, & represents the bitwise AND operator.
Input Format
The first line contains an integer, T, the number of test cases. Each of the T subsequent lines defines a test case as 2 space-separated integers, N and K, respectively.
Constraints
1 <= T <= 10^3
2 <= N <= 10^3
2 <= K <= NOutput Format
For each test case, print the maximum possible value of A & B on a new line.
Sample Input
3
5 2
8 5
2 2
Sample Output
1
4
0
Explanation
N = 5, K = 2, S = {1,2,3,4,5}
All possible values of and are:
1. A = 1, B = 2; A & B = 0
2. A = 1, B = 3; A & B = 1
3. A = 1, B = 4; A & B = 0
4. A = 1, B = 5; A & B = 1
5. A = 2, B = 3; A & B = 2
6. A = 2, B = 4; A & B = 0
7. A = 2, B = 5; A & B = 0
8. A = 3, B = 4; A & B = 0
9. A = 3, B = 5; A & B = 1
10. A = 4, B = 5; A & B = 4The maximum possible value of A&B that is also < (K = 2) is 1, so we print 1 on a new line.
这是我的代码：
import math
import os
import random
import re
import sys
if __name__ == '__main__':
t = int(sys.stdin.readline())
for t_itr in range(t):
nk = sys.stdin.readline().split()
n = int(nk[0])
k = int(nk[1])
lst1 = [(a, b) for a in range(1, n + 1) for b in range(a + 1, n + 1)]
lst2 = [ a & b for (a,b) in lst1 if a & b < k]
print(max(lst2))
此任务共有 6 个测试用例，在测试用例 1 和 2 中，我的代码是 True，但在接下来的 4 个测试用例中，它引发：'因超时而终止 '.
你能帮我解释一下我哪里错了吗？我该怎么做才能完成所有测试用例？谢谢你帮助我！
使（某物）小于K的（某物）的最大值应该是K-1。除非出于某种原因不可能。
那么让我们来看看：
for n in range(2, 256):
for k in range(2, n + 1):
m = max(a & b for a in range(1, n + 1) for b in range(a + 1, n + 1) if a & b < k)
t = "*" if m == k - 1 else " "
print("{:s} {:3d} {:3d} {:3d} {:08b} {:08b} {:08b} {:3d} {:3d}".format(t, n, k, m, n, k, m, n - k, k - m))
示例输出：
N K M N K M N-K K-M
----------------------------------------------
2 2 0 00000010 00000010 00000000 0 2
* 3 2 1 00000011 00000010 00000001 1 1
* 3 3 2 00000011 00000011 00000010 0 1
* 4 2 1 00000100 00000010 00000001 2 1
* 4 3 2 00000100 00000011 00000010 1 1
4 4 2 00000100 00000100 00000010 0 2
* 5 2 1 00000101 00000010 00000001 3 1
* 5 3 2 00000101 00000011 00000010 2 1
5 4 2 00000101 00000100 00000010 1 2
* 5 5 4 00000101 00000101 00000100 0 1
* 6 2 1 00000110 00000010 00000001 4 1
* 6 3 2 00000110 00000011 00000010 3 1
6 4 2 00000110 00000100 00000010 2 2
* 6 5 4 00000110 00000101 00000100 1 1
6 6 4 00000110 00000110 00000100 0 2
* 7 2 1 00000111 00000010 00000001 5 1
* 7 3 2 00000111 00000011 00000010 4 1
* 7 4 3 00000111 00000100 00000011 3 1
* 7 5 4 00000111 00000101 00000100 2 1
* 7 6 5 00000111 00000110 00000101 1 1
* 7 7 6 00000111 00000111 00000110 0 1
* 8 2 1 00001000 00000010 00000001 6 1
* 8 3 2 00001000 00000011 00000010 5 1
* 8 4 3 00001000 00000100 00000011 4 1
* 8 5 4 00001000 00000101 00000100 3 1
* 8 6 5 00001000 00000110 00000101 2 1
* 8 7 6 00001000 00000111 00000110 1 1
8 8 6 00001000 00001000 00000110 0 2
* 9 2 1 00001001 00000010 00000001 7 1
* 9 3 2 00001001 00000011 00000010 6 1
* 9 4 3 00001001 00000100 00000011 5 1
* 9 5 4 00001001 00000101 00000100 4 1
* 9 6 5 00001001 00000110 00000101 3 1
* 9 7 6 00001001 00000111 00000110 2 1
9 8 6 00001001 00001000 00000110 1 2
* 9 9 8 00001001 00001001 00001000 0 1
显然，最大值通常是 K-1（加星号的行），因此当它不是 K-1 时可能更容易找出。另外，最大值似乎是 K-1 或 K-2。
另一个测试，仅在最大值不是K-1时显示。这次先按K排序，再按N排序。
for k in range(2, 256):
for n in range(k, 256):
m = max(a & b for a in range(1, n + 1) for b in range(a + 1, n + 1) if a & b < k)
if m != k - 1:
print("{:3d} {:3d} {:3d} {:08b} {:08b} {:08b} {:3d} {:3d}".format(n, k, m, n, k, m, n - k, k - m))
然后是输出中的示例。
N K M N K M N-K K-M
----------------------------------------------
2 2 0 00000010 00000010 00000000 0 2
----------------------------------------------
4 4 2 00000100 00000100 00000010 0 2
5 4 2 00000101 00000100 00000010 1 2
6 4 2 00000110 00000100 00000010 2 2
----------------------------------------------
6 6 4 00000110 00000110 00000100 0 2
----------------------------------------------
8 8 6 00001000 00001000 00000110 0 2
9 8 6 00001001 00001000 00000110 1 2
10 8 6 00001010 00001000 00000110 2 2
11 8 6 00001011 00001000 00000110 3 2
12 8 6 00001100 00001000 00000110 4 2
13 8 6 00001101 00001000 00000110 5 2
14 8 6 00001110 00001000 00000110 6 2
----------------------------------------------
10 10 8 00001010 00001010 00001000 0 2
----------------------------------------------
12 12 10 00001100 00001100 00001010 0 2
13 12 10 00001101 00001100 00001010 1 2
14 12 10 00001110 00001100 00001010 2 2
----------------------------------------------
14 14 12 00001110 00001110 00001100 0 2
----------------------------------------------
16 16 14 00010000 00010000 00001110 0 2
17 16 14 00010001 00010000 00001110 1 2
18 16 14 00010010 00010000 00001110 2 2
19 16 14 00010011 00010000 00001110 3 2
20 16 14 00010100 00010000 00001110 4 2
21 16 14 00010101 00010000 00001110 5 2
22 16 14 00010110 00010000 00001110 6 2
23 16 14 00010111 00010000 00001110 7 2
24 16 14 00011000 00010000 00001110 8 2
25 16 14 00011001 00010000 00001110 9 2
26 16 14 00011010 00010000 00001110 10 2
27 16 14 00011011 00010000 00001110 11 2
28 16 14 00011100 00010000 00001110 12 2
29 16 14 00011101 00010000 00001110 13 2
30 16 14 00011110 00010000 00001110 14 2
----------------------------------------------
18 18 16 00010010 00010010 00010000 0 2
----------------------------------------------
所以当max不是K-1时，好像总是K-2，而且K必须是偶数。
考虑 p>0 的 K=2**p，以简化（即，忘记 K 的高位，即使是 K）。 "natural" max应该是K-1，即2**p-1.
示例：
在二进制中，对于 K=1000，自然最大值为 111。但是如果我们手头的 A 和 B 的所有值都小于 K，则不会发生这种情况：B 的最大值为 111 ，但是 A 必须更小，因此至少会丢失一位。最大值将是 110，即 K-2。
当 N 不大于 1000 时会出现此问题：如果它足够大，那么我们就有足够的 A 和 B 值来得到 A&B=111。具体来说，如果 N 至少为 1111，则 A=111 且 B=1111，我们就完成了。
当 K 不是 2 的幂时，它只是稍微复杂一些。
现在，您应该完成了所有必要的工作。
最后检查。
def p2(k):
p = 1
while k % (2 * p) == 0:
p *= 2
return p
count1 = count2 = 0
for k in range(2, 256):
print("-" * 60)
for n in range(k, 256):
m = max(a & b for a in range(1, n + 1) for b in range(a + 1, n + 1) if a & b < k)
t1 = "*" if m == k - 1 else " "
if k % 2 == 0:
p = p2(k)
t2 = "*" if n <= k + p - 2 and m == k - 2 else " "
else:
t2 = " "
if t1 == t2:
count1 += 1
else:
count2 += 1
print("{:s} {:s} {:3d} {:3d} {:3d} {:08b} {:08b} {:08b} {:3d} {:3d}".format(t1, t2, n, k, m, n, k, m, n - k, k - m))
print(count1, count2)
从中可以学到什么？
- 想想算法：只抛出明显的解决方案通常不是很好。有时它足够好，但通常不在 Hacker Rank 上：他们设计测试来检测和拒绝复杂性较差的解决方案。
- 用铅笔和纸试试。如果它太复杂，最接近铅笔和纸的方法是使用糟糕的算法打印一些有用的输出，以尝试了解如何改进它。
- 仔细阅读输出，找到模式。改进程序以显示更多输出以证实您的直觉。
- 当有什么有趣的东西时，证明它（这里的证明远未完成，但你至少应该明白它为什么有效）。
- 通过 运行 另一项测试，检查您是否没有遗漏其他问题。
最后说明：为了得到除以 K 的 2 的最大次方，我使用了一个循环。有一个更好的方法，通过考虑 K^(K-1)（其中 ^ 表示异或，如 Python），你会发现。
这是一种在优化代码时经常有用的位黑客。您会发现其他示例 here and there.
回复评论
- 如果K是奇数，那么因为K<=N你可以选择B=K，A=K-1，然后A&B=K-1，所以如果K是奇数你总能得到K-1。最大值不能大于 K-1，因为它是条件之一（A&B 的最大值使得 A&B
- 如果K是偶数，N足够大，可以选A=K-1，K=K | (K ^ (K-1)), 然后选择 B=K | (K^(K-1))。所以A&B=K-1是可能的，而且不能更大，所以是max.
- 其他情况（K为偶数，N不够大），则取A=K-2，B=K-1，A&B=K-2。正如我在答案中的示例中解释的那样，不可能获得 K-1，因此 K-2 是最大值。
条件可以简化：
- 首先，K|(K^(K-1))总是等于K|(K-1)（在这两种情况下，我们将LSB侧的所有0替换为1）。
- 第二个化简：如果K是奇数，那么K|K-1总是等于K，那么N>=K|(K-1)总是成立。因此，在所有情况下检查是否 N>=K|(K-1) 就足够了，永远不要检查 K 是否为奇数。
总而言之：
如果N>=K|(K-1)，最大值为K-1，否则为K-2。