State Definition:
We use dp[c][gcd] represents the minimal total B[i] to achieve GCD gcd with c elements.
Transfer function:
$$
dp[c][\text{new_gcd}] = \min(dp[c][\text{new_gcd}], \quad dp[c-1][\text{existing_gcd}] + B[i]).
\\
\text{ where } \text{new_gcd}=\operatorname{GCD}(\text{existing_gcd}, A[i])
$$
Initial condition:
$
dp[0][0]=0
$ since when choosing 0 elements, the GCD is 0, and the total cost is 0.
The desired result: it is stored in dp[k][1], representing the minimum cost to select k elements whose GCD is 1.
If dp[k][1] is not defined, it means it's impossible to select k elements with GCD 1.
from dataclasses import dataclass
from functools import reduce
from itertools import combinations
from math import gcd
from time import time
from typing import List, Tuple, Optional
import concurrent.futures
import math
import random
@dataclass
class TestCase:
test_num: int
n: int
k: int
A: List[int]
B: List[int]
@dataclass
class TestResult:
test_num: int
n: int
k: int
A: List[int]
B: List[int]
brute_force_result: Optional[int]
brute_force_time: float
dp_result: int
dp_time: float
indices: Optional[List[int]]
is_valid: bool
solutions_match: bool
def find_gcd_array(numbers):
"""Calculate GCD of an array of numbers."""
return reduce(gcd, numbers)
def find_min_sum_with_gcd_one(A, B, k):
"""
Find minimum sum of k elements from array B where corresponding elements
from A have GCD = 1
"""
n = len(A)
min_sum = float('inf')
chosen_indices = None
for indices in combinations(range(n), k):
selected_A = [A[i] for i in indices]
current_gcd = find_gcd_array(selected_A)
if current_gcd == 1:
current_sum = sum(B[i] for i in indices)
if current_sum < min_sum:
min_sum = current_sum
chosen_indices = list(indices)
if min_sum == float('inf'):
return None, None
return min_sum, chosen_indices
def min_total_b_dp(n, k, A, B):
"""Dynamic programming solution."""
dp = [dict() for _ in range(k + 1)]
dp[0][0] = 0
for i in range(n):
Ai = A[i]
Bi = B[i]
new_dp = [dict(dp_c) for dp_c in dp]
for c in range(k, 0, -1):
for g in dp[c - 1]:
new_gcd = math.gcd(g, Ai)
new_cost = dp[c - 1][g] + Bi
if new_gcd not in new_dp[c] or new_dp[c][new_gcd] > new_cost:
new_dp[c][new_gcd] = new_cost
dp = new_dp
return dp[k].get(1, -1)
def generate_test_case(n_min=5, n_max=20, k_min=2, val_max=100) -> TestCase:
"""Generate a random test case."""
n = random.randint(n_min, n_max)
k = random.randint(k_min, n)
# Generate A array with some numbers that ensure GCD=1 is possible
A = [random.randint(1, val_max) for _ in range(n)]
# Make sure at least k numbers are coprime
coprime_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
for i in range(min(k, len(coprime_numbers))):
A[i] = coprime_numbers[i]
random.shuffle(A)
# Generate B array
B = [random.randint(1, val_max) for _ in range(n)]
return TestCase(0, n, k, A, B) # test_num will be set later
def verify_solution(n, k, A, B, min_sum, indices):
"""Verify that a solution is valid."""
if min_sum is None or indices is None:
return False
if len(indices) != k:
return False
if any(i >= n for i in indices):
return False
selected_A = [A[i] for i in indices]
if find_gcd_array(selected_A) != 1:
return False
selected_B = [B[i] for i in indices]
if sum(selected_B) != min_sum:
return False
return True
def run_single_test(test_case: TestCase) -> TestResult:
"""Run a single test case and return the results."""
start_time = time()
brute_force_result, indices = find_min_sum_with_gcd_one(test_case.A, test_case.B, test_case.k)
brute_force_time = time() - start_time
start_time = time()
dp_result = min_total_b_dp(test_case.n, test_case.k, test_case.A, test_case.B)
dp_time = time() - start_time
# Verify results
if brute_force_result is not None:
brute_force_valid = verify_solution(test_case.n, test_case.k, test_case.A,
test_case.B, brute_force_result, indices)
else:
brute_force_valid = (dp_result == -1)
dp_matches = (dp_result == brute_force_result) or (dp_result == -1 and brute_force_result is None)
return TestResult(
test_num=test_case.test_num,
n=test_case.n,
k=test_case.k,
A=test_case.A,
B=test_case.B,
brute_force_result=brute_force_result,
brute_force_time=brute_force_time,
dp_result=dp_result,
dp_time=dp_time,
indices=indices,
is_valid=brute_force_valid,
solutions_match=dp_matches
)
def print_test_result(result: TestResult):
"""Print the results of a single test."""
print(f"\nTest {result.test_num + 1}:")
print(f"n={result.n}, k={result.k}")
print(f"A={result.A}")
print(f"B={result.B}")
print(f"Brute Force Result: {result.brute_force_result} (Time: {result.brute_force_time:.4f}s)")
print(f"DP Result: {result.dp_result} (Time: {result.dp_time:.4f}s)")
print(f"Solutions match: {result.solutions_match}")
print(f"Brute force solution valid: {result.is_valid}")
def run_tests_concurrent(num_tests=100, max_workers=None):
"""Run multiple random tests concurrently and compare both implementations."""
print(f"Running {num_tests} random tests concurrently...")
# Generate all test cases first
test_cases = [generate_test_case() for _ in range(num_tests)]
for i, test_case in enumerate(test_cases):
test_case.test_num = i
# Run tests concurrently
start_time = time()
with concurrent.futures.ProcessPoolExecutor(max_workers=max_workers) as executor:
future_to_test = {executor.submit(run_single_test, test_case): test_case
for test_case in test_cases}
results = []
for future in concurrent.futures.as_completed(future_to_test):
test_case = future_to_test[future]
try:
result = future.result()
results.append(result)
print_test_result(result)
if not result.solutions_match or not result.is_valid:
print("ERROR: Solutions don't match or invalid solution found!")
return False
except Exception as e:
print(f"Test {test_case.test_num} generated an exception: {e}")
return False
total_time = time() - start_time
# Calculate and print statistics
avg_brute_force_time = sum(r.brute_force_time for r in results) / len(results)
avg_dp_time = sum(r.dp_time for r in results) / len(results)
print("\nTest Summary:")
print(f"Total tests: {num_tests}")
print(f"Total time: {total_time:.2f}s")
print(f"Average brute force time: {avg_brute_force_time:.4f}s")
print(f"Average DP time: {avg_dp_time:.4f}s")
print("All tests passed successfully!")
return True
def main():
# First test the example case
print("Testing example case:")
n, k = 5, 4
A = [10, 2, 5, 7, 8]
B = [7, 9, 11, 2, 3]
min_sum, indices = find_min_sum_with_gcd_one(A, B, k)
dp_result = min_total_b_dp(n, k, A, B)
print(f"Brute Force - Minimum sum: {min_sum}")
print(f"Brute Force - Chosen indices: {indices}")
print(f"DP Solution Result: {dp_result}")
# Then run concurrent random tests
run_tests_concurrent(1000)
if __name__ == "__main__":
main()
