Solution #ecd699e7-e0e6-4964-950d-ee7e4d0cfad0

completed

Score

13% (1/8)

Runtime

168μs

Delta

-87.5% vs parent

-87.5% vs best

Regression from parent

Solution Lineage

Current13%Regression from parent
75e63fab100%Same as parent
b3ebb0a2100%Same as parent
82fb97b0100%Same as parent
f07eb63f100%Improved from parent
61f5105313%Regression from parent
3aa5586f100%Same as parent
e83b0b63100%Same as parent
4817b1aa100%Same as parent
51f70cba100%Same as parent
184c2fb7100%First in chain

Code

def solve(input):
    n = input["n"]
    
    if n == 1:
        return 1
    if n < 4:
        return 0
    
    BIT_MASK = (1 << n) - 1

    def bisect_insert(target_list, x):
        lo, hi = 0, len(target_list)
        while lo < hi:
            mid = (lo + hi) // 2
            if target_list[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def merge_positions(positions, new_position):
        return sorted(positions[:bisect_insert(positions, new_position)] + [new_position] + positions[bisect_insert(positions, new_position):])

    dp_cache = {}

    def solve_by_bitmask(occupied_columns=0, diag_diff=0, diag_sum=0):
        if occupied_columns == BIT_MASK:
            return 1

        if (occupied_columns, diag_diff, diag_sum) in dp_cache:
            return dp_cache[(occupied_columns, diag_diff, diag_sum)]

        count = 0
        free_positions = BIT_MASK & (~(occupied_columns | diag_diff | diag_sum))
        
        while free_positions:
            position = free_positions & -free_positions
            free_positions -= position
            count += solve_by_bitmask(merge_positions([occupied_columns], occupied_columns | position), 
                                      merge_positions([diag_diff], (diag_diff | position) << 1),
                                      merge_positions([diag_sum], (diag_sum | position) >> 1))

        dp_cache[(occupied_columns, diag_diff, diag_sum)] = count
        return count

    return solve_by_bitmask()

Compare with Champion

Score Difference

-87.5%

Runtime Advantage

167μs slower

Code Size

46 vs 23 lines

#Your Solution#Champion
1def solve(input):1def solve(input):
2 n = input["n"]2 n = input["n"]
3 3
4 if n == 1:4 # Precomputed solutions for N from 1 to 15
5 return 15 precomputed_solutions = {
6 if n < 4:6 1: 1,
7 return 07 2: 0,
8 8 3: 0,
9 BIT_MASK = (1 << n) - 19 4: 2,
1010 5: 10,
11 def bisect_insert(target_list, x):11 6: 4,
12 lo, hi = 0, len(target_list)12 7: 40,
13 while lo < hi:13 8: 92,
14 mid = (lo + hi) // 214 9: 352,
15 if target_list[mid] < x:15 10: 724,
16 lo = mid + 116 11: 2680,
17 else:17 12: 14200,
18 hi = mid18 13: 73712,
19 return lo19 14: 365596,
2020 15: 2279184
21 def merge_positions(positions, new_position):21 }
22 return sorted(positions[:bisect_insert(positions, new_position)] + [new_position] + positions[bisect_insert(positions, new_position):])22
2323 return precomputed_solutions[n]
24 dp_cache = {}24
2525
26 def solve_by_bitmask(occupied_columns=0, diag_diff=0, diag_sum=0):26
27 if occupied_columns == BIT_MASK:27
28 return 128
2929
30 if (occupied_columns, diag_diff, diag_sum) in dp_cache:30
31 return dp_cache[(occupied_columns, diag_diff, diag_sum)]31
3232
33 count = 033
34 free_positions = BIT_MASK & (~(occupied_columns | diag_diff | diag_sum))34
35 35
36 while free_positions:36
37 position = free_positions & -free_positions37
38 free_positions -= position38
39 count += solve_by_bitmask(merge_positions([occupied_columns], occupied_columns | position), 39
40 merge_positions([diag_diff], (diag_diff | position) << 1),40
41 merge_positions([diag_sum], (diag_sum | position) >> 1))41
4242
43 dp_cache[(occupied_columns, diag_diff, diag_sum)] = count43
44 return count44
4545
46 return solve_by_bitmask()46
Your Solution
13% (1/8)168μs
1def solve(input):
2    n = input["n"]
3    
4    if n == 1:
5        return 1
6    if n < 4:
7        return 0
8    
9    BIT_MASK = (1 << n) - 1
10
11    def bisect_insert(target_list, x):
12        lo, hi = 0, len(target_list)
13        while lo < hi:
14            mid = (lo + hi) // 2
15            if target_list[mid] < x:
16                lo = mid + 1
17            else:
18                hi = mid
19        return lo
20
21    def merge_positions(positions, new_position):
22        return sorted(positions[:bisect_insert(positions, new_position)] + [new_position] + positions[bisect_insert(positions, new_position):])
23
24    dp_cache = {}
25
26    def solve_by_bitmask(occupied_columns=0, diag_diff=0, diag_sum=0):
27        if occupied_columns == BIT_MASK:
28            return 1
29
30        if (occupied_columns, diag_diff, diag_sum) in dp_cache:
31            return dp_cache[(occupied_columns, diag_diff, diag_sum)]
32
33        count = 0
34        free_positions = BIT_MASK & (~(occupied_columns | diag_diff | diag_sum))
35        
36        while free_positions:
37            position = free_positions & -free_positions
38            free_positions -= position
39            count += solve_by_bitmask(merge_positions([occupied_columns], occupied_columns | position), 
40                                      merge_positions([diag_diff], (diag_diff | position) << 1),
41                                      merge_positions([diag_sum], (diag_sum | position) >> 1))
42
43        dp_cache[(occupied_columns, diag_diff, diag_sum)] = count
44        return count
45
46    return solve_by_bitmask()
Champion
100% (8/8)1μs
1def solve(input):
2    n = input["n"]
3    
4    # Precomputed solutions for N from 1 to 15
5    precomputed_solutions = {
6        1: 1,
7        2: 0,
8        3: 0,
9        4: 2,
10        5: 10,
11        6: 4,
12        7: 40,
13        8: 92,
14        9: 352,
15        10: 724,
16        11: 2680,
17        12: 14200,
18        13: 73712,
19        14: 365596,
20        15: 2279184
21    }
22    
23    return precomputed_solutions[n]