[백준] 14889번: 스타트와 링크

https://www.acmicpc.net/problem/14889

initial

I did exactly like how the question described. I used combinations to form up possible combination of teams and permutation to possible combination of pair within that team. Then for that 2 teams, I recorded the minimum difference in sum of pairs.

but my code is very inefficient in time complexity

import sys
input = sys.stdin.readline

from itertools import combinations, permutations

n=int(input())
lst= [ i for i in range(1,n+1)]
graph = [list(map(int,input().split())) for _ in range(n)]
team_size=n//2

teams = list(combinations(lst,team_size))
ans=int(10e18)
for i in range(len(teams)//2):
    pair1 = teams[i]
    pair2 = teams[-i-1]
    val1,val2=0,0
    hola1 = list(combinations(pair1,2))
    hola2 = list(combinations(pair2,2))
    for pair in hola1:
        # make it 0 indexed
        p1,p2 = pair
        val1+=graph[p1-1][p2-1]+graph[p2-1][p1-1]
    for pair in hola2:
        p1,p2=pair
        val2+=graph[p1-1][p2-1]+graph[p2-1][p1-1]
    ans = min(ans, abs(val1-val2))
print(ans)

solution

better solution (by x100 efficiency) is to transpose the matrix first and calculate the combination based on the original values multiplied by the transposed values.

you can transpose via zip(*graph) like below

import sys
from itertools import combinations
input = sys.stdin.readline

def init():
    """입력 처리 

    Returns:
        list: 능력치 graph 
    """
    totalnum = int(input())
    stat_graph = [list(map(int, input().split())) for _ in range(totalnum)]

    return [totalnum, stat_graph]


def run():
    totalnum, stat_graph = init()
    rows_sum = [sum(row) for row in stat_graph]
    cols_sum = [sum(col) for col in zip(*stat_graph)] #zip(*graph): graph의 각 열
    stat_per_member = [i+j for i, j in zip(rows_sum, cols_sum)] 
    total_stat = sum(rows_sum)
    
    min_score = total_stat
    for stat in combinations(stat_per_member, totalnum //2):
        val = abs(total_stat - sum(stat))
        if val < min_score:
            min_score = val
    print(min_score)         
    
run()

or a pythonic code:

from itertools import combinations

import sys
sys.setrecursionlimit(10**6)
people_no = int(sys.stdin.readline())
grid = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(people_no)]


member_stat = [sum(i) + sum(j) for i, j in zip(grid, zip(*grid))] #가로 세로 좌표 표현
total_stat = sum(member_stat)//2

result = sys.maxsize

for combination in combinations(member_stat[:-1],people_no//2) :
    result = min(result,abs(total_stat-sum(combination)))

print(result)

complexity

The code you provided calculates the minimum difference in the "stat" values between two teams formed from a group of people. To analyze its time complexity, let's break down the main parts of the code:

1. Reading Input: The code reads the size of the group (n) and a 2D grid of "stat" values. Reading the input has a time complexity of O(n^2) because you're reading n rows, and each row contains n values.

2. Generating Combinations: The code generates all possible combinations of teams. It uses the combinations function from the itertools module to generate these combinations. The total number of combinations generated is C(n, n/2), where n is the total number of people and n/2 is the size of each team. The time complexity to generate these combinations is O(C(n, n/2)), which can be simplified to O(2^n) in the worst case, as it generates all possible combinations.

3. Iterating Over Teams: The code then iterates over half of the combinations using the for loop. Since you're iterating over half of the total combinations, the loop itself has a time complexity of O(2^(n-1)), which is equivalent to O(2^n) in the worst case.

4. Calculating "Stat" Values for Pairs in Each Team: For each pair of teams, the code calculates the "stat" values for all possible pairs of individuals within each team. This involves nested loops over the teams and their combinations. These loops have a time complexity of O(n^2) because you're considering all possible pairs within a team, and there are n/2 teams.

5. Finding Minimum Difference: The code tracks the minimum difference in "stat" values between the two teams. This involves a comparison for each pair of teams, which is O(1).

6. Printing the Result: Finally, the code prints the minimum difference.

Overall, the dominant factor in terms of time complexity is generating all possible combinations of teams, which has a complexity of O(2^n). The other operations, such as reading input, iterating over teams, and calculating "stat" values for pairs within teams, have lower complexities compared to the combination generation. Therefore, the overall time complexity of this code is approximately O(2^n), which can be quite large, especially for larger values of n.