Efficient Algorithm to Count Permutations of Boss Fights with Divisibility Constraints in an RPG Game

Question

I'm trying to find an efficient algorithm to calculate the amount of permutations for this problem. I've only slightly simplified the problem to be easier to read. But the original problem, is Problem K from here: https://prog4fun.csse.canterbury.ac.nz/pluginfile.php/26/question/questiontext/11874/1/30809/problemset.pdf

In this RPG, you have a team of 4 players, and you can fight $N$ different bosses. Each boss $i$ has a payout $b_i$ (an integer), which represents the amount of gold you receive for defeating that boss.

Your task is to fight a minimum of $L$ rounds and a maximum of $U$ rounds. You can choose to fight the same boss multiple times, and the order in which you fight the bosses matters (i.e., permutations are considered).

The goal is to determine the number of different valid permutations of boss fights such that the total amount of gold obtained is divisible by 4 (so that each teammate can receive an equal share).

Brute-forcing is too slow, as the lower bound and upper bound for amount of boss fights can be 10ドル^9$. So I assume this has something to do with dynamic programming.

How can I approach this problem? Any guidance or methods to count these permutations would be greatly appreciated.

What is the number of valid permutations of boss fights under these conditions?

Constraints:

• $N$ is the number of bosses.
• $L$ is the minimum number of rounds.
• $U$ is the maximum number of rounds.
• $b_i$ is the payout for boss $i$, where $b_i \in \mathbb{Z}$.
• The sum of gold from any valid sequence of boss fights must be divisible by 4.

Any help with how to structure the solution or the relevant combinatorial methods would be appreciated!

I've only come up with this equation so far: (where $a_i$ is how many times you defeated boss $i$)

$$a_1 \cdot b_1 + a_2 \cdot b_2 + \dots + a_N \cdot b_N \equiv 0 \pmod{4}$$

And I've thought about using stars and bars on $ L \leq a_1 + a_2 + \dots + a_N \leq U $

But I'm not sure where to go from there.

• D.W.: I suggest you review the material at cs.stackexchange.com/tags/dynamic-programming/info, then follow the guidelines there for how to approach the problem and revise the question accordingly.

Answer 1

State Definition: Let $dp[i][s][k]$ be the number of ways to select elements from the first $i$ items such that:

• The sum modulo 4 is $s$ (i.e., $s = (\sum_{j=1}^{i} a_j b_j) \mod 4$)
• The number of selected elements is $k$

Base Case: $dp[0][0][0] = 1$ (There is one way to select zero elements with a sum of 0 modulo 4)

Transition: For each $i$ from 1 to $N$:

• Not selecting $b_i$: $dp[i][s][k] += dp[i-1][s][k]$

• Selecting $b_i$: Let $s_{new} = (s_{old} + b_i) \mod 4$, then $dp[i][s_{new}][k+1] += dp[i-1][s_{old}][k]$

Final Answer: The total number of ways is the sum of $dp[N][0][k]$ for all $k$ from $L$ to $U$

from concurrent.futures import ThreadPoolExecutor, ProcessPoolExecutor
from typing import List, Tuple
import concurrent.futures
import random
import time
import unittest
def check_combination(a_list, b_list, L, U):
 """
 Check if a given combination of a_i values satisfies all conditions:
 1. The dot product with b_list should be ≡ 0 (mod 4)
 2. L ≤ sum(a_i) ≤ U
 Args:
 a_list: List of selected indices (1 for selected, 0 for not selected)
 b_list: List of b_i values
 L: Lower bound for sum of a_i
 U: Upper bound for sum of a_i
 Returns:
 bool: True if all conditions are satisfied, False otherwise
 """
 # Check sum bounds
 sum_a = sum(a_list)
 if sum_a < L or sum_a > U:
 return False
 # Check dot product modulo 4
 dot_product = sum(a * b for a, b in zip(a_list, b_list))
 return dot_product % 4 == 0
def count_subsets_modulo(N, L, U, b_list):
 # Initialize DP table
 dp = [[[0] * (U + 2) for _ in range(4)] for _ in range(N + 1)]
 dp[0][0][0] = 1 # Base case
 for i in range(1, N + 1):
 b_i = b_list[i - 1] % 4 # We only care about modulo 4
 for s in range(4):
 for k in range(U + 1):
 # Not selecting b_i
 dp[i][s][k] += dp[i - 1][s][k]
 # Selecting b_i, only if k + 1 <= U
 if k + 1 <= U:
 s_new = (s + b_i) % 4
 dp[i][s_new][k + 1] += dp[i - 1][s][k]
 # Calculate the final answer
 total_count = 0
 for k in range(L, U + 1):
 total_count += dp[N][0][k]
 return total_count
def generate_all_combinations(N, L, U, b_list):
 """
 Generate and check all possible combinations (for testing purposes).
 Warning: This is brute force and should only be used for small N.
 """
 def backtrack(pos, current):
 if pos == N:
 if check_combination(current, b_list, L, U):
 return 1
 return 0
 # Try not selecting pos
 count = backtrack(pos + 1, current + [0])
 # Try selecting pos
 count += backtrack(pos + 1, current + [1])
 return count
 return backtrack(0, [])
def generate_test_case(max_n: int = 10, max_b: int = 20) -> Tuple[int, int, int, List[int]]:
 """
 Generate a random test case with reasonable bounds.
 Args:
 max_n: Maximum number of elements
 max_b: Maximum value for b_i elements
 Returns:
 Tuple of (N, L, U, b_list)
 """
 N = random.randint(1, max_n)
 # Generate reasonable bounds for L and U
 max_possible_sum = N # Since we're selecting 0/1 for each position
 L = random.randint(0, max_possible_sum - 1)
 U = random.randint(L, max_possible_sum)
 b_list = [random.randint(1, max_b) for _ in range(N)]
 return N, L, U, b_list
def run_concurrent_test_case(N: int, L: int, U: int, b_list: List[int]) -> Tuple[bool, str]:
 """Run a single test case and return results with detailed information."""
 try:
 dp_result = count_subsets_modulo(N, L, U, b_list)
 bf_result = generate_all_combinations(N, L, U, b_list)
 assert dp_result == bf_result, (
 f"Results don't match!\n"
 f"DP Result: {dp_result}\n"
 f"BF Result: {bf_result}\n"
 f"Input: N={N}, L={L}, U={U}, b_list={b_list}"
 )
 return True, f"Test passed: N={N}, L={L}, U={U}, Result={dp_result}"
 except AssertionError as e:
 return False, str(e)
 except Exception as e:
 return False, f"Unexpected error: {str(e)}"
class TestSubsetModulo(unittest.TestCase):
 def setUp(self):
 """Set up test cases that will be used across multiple tests."""
 self.basic_test_cases = [
 (1, 0, 1, [4]), # Single element
 (2, 1, 1, [2, 2]), # Exact sum requirement
 (3, 0, 3, [1, 2, 3]), # Full range
 (4, 2, 2, [1, 1, 1, 1]), # Mid-range exact
 ]
 self.edge_test_cases = [
 (5, 0, 0, [1, 2, 3, 4, 5]), # Only empty set
 (3, 3, 3, [1, 1, 1]), # Must select all
 (4, 1, 4, [4, 4, 4, 4]), # All same values
 (3, 1, 2, [0, 0, 0]), # All zeros
 ]
 def test_basic_functionality(self):
 """Test basic functionality with simple cases."""
 for N, L, U, b_list in self.basic_test_cases:
 with self.subTest(N=N, L=L, U=U, b_list=b_list):
 dp_result = count_subsets_modulo(N, L, U, b_list)
 bf_result = generate_all_combinations(N, L, U, b_list)
 self.assertEqual(dp_result, bf_result)
 def test_edge_cases(self):
 """Test edge cases."""
 for N, L, U, b_list in self.edge_test_cases:
 with self.subTest(N=N, L=L, U=U, b_list=b_list):
 dp_result = count_subsets_modulo(N, L, U, b_list)
 bf_result = generate_all_combinations(N, L, U, b_list)
 self.assertEqual(dp_result, bf_result)
 def test_invalid_inputs(self):
 """Test invalid inputs."""
 # with self.assertRaises(Exception):
 # count_subsets_modulo(0, 1, 2, []) # Invalid N
 # with self.assertRaises(Exception):
 # count_subsets_modulo(2, 3, 2, [1, 2]) # L > U
 with self.assertRaises(Exception):
 count_subsets_modulo(2, 0, 1, [1]) # b_list length mismatch
 def test_large_numbers(self):
 """Test with larger numbers that might cause overflow."""
 N, L, U = 5, 2, 4
 b_list = [1000000007, 1000000009, 1000000021, 1000000033, 1000000087]
 dp_result = count_subsets_modulo(N, L, U, b_list)
 bf_result = generate_all_combinations(N, L, U, b_list)
 self.assertEqual(dp_result, bf_result)
def run_concurrent_stress_test(num_tests: int = 100, max_workers: int = 4):
 """Run multiple test cases concurrently using both threads and processes."""
 def generate_test_cases(num: int) -> List[Tuple[int, int, int, List[int]]]:
 return [generate_test_case() for _ in range(num)]
 test_cases = generate_test_cases(num_tests)
 results = {'passed': 0, 'failed': 0, 'errors': []}
 # Test with ThreadPoolExecutor
 print("\nRunning threaded tests...")
 start_time = time.time()
 with ThreadPoolExecutor(max_workers=max_workers) as executor:
 futures = []
 for N, L, U, b_list in test_cases:
 futures.append(
 executor.submit(run_concurrent_test_case, N, L, U, b_list)
 )
 for future in concurrent.futures.as_completed(futures):
 success, message = future.result()
 if success:
 results['passed'] += 1
 else:
 results['failed'] += 1
 results['errors'].append(message)
 thread_time = time.time() - start_time
 # Test with ProcessPoolExecutor
 print("\nRunning multiprocess tests...")
 start_time = time.time()
 with ProcessPoolExecutor(max_workers=max_workers) as executor:
 futures = []
 for N, L, U, b_list in test_cases:
 futures.append(
 executor.submit(run_concurrent_test_case, N, L, U, b_list)
 )
 for future in concurrent.futures.as_completed(futures):
 success, message = future.result()
 if success:
 results['passed'] += 1
 else:
 results['failed'] += 1
 results['errors'].append(message)
 process_time = time.time() - start_time
 # Print results
 print("\nTest Results:")
 print(f"Total tests: {num_tests * 2}") # * 2 because we ran both threaded and process tests
 print(f"Passed: {results['passed']}")
 print(f"Failed: {results['failed']}")
 print(f"Thread execution time: {thread_time:.2f}s")
 print(f"Process execution time: {process_time:.2f}s")
 if results['errors']:
 print("\nErrors encountered:")
 for error in results['errors']:
 print(f"- {error}")
 return results
if __name__ == '__main__':
 # Run unit tests
 print("Running unit tests...")
 unittest.main(argv=['dummy'], exit=False)
 # Run concurrent stress tests
 print("\nRunning concurrent stress tests...")
 results = run_concurrent_stress_test(num_tests=5000, max_workers=4)