google code jam 2014 R1 A A Charging chaos

A. Charging Chaos

나도 여러 콘센트와 플러그를 맞추기 위해 노력하는데,

문제 출제자도 그런 생각을 했었나 보네.

첫 번째 줄에 나온 2진수들의 몇 개 자릿 수를 flip해서

두 번째 줄 2진수들로 만들기.

흑, large input은 실패했다. small input 푸는 것만 3시간은 걸렸다. 사소한 실수를 좀 많이 했다.

performance 계산을 안해보고, 대충 연습을 시작해 본 것도 문제였다. large input은 못 푸는 algorithm을 너무 오랜 시간 동안에 구현해냈네.

한 가지 착안한 것은 공통의 자릿수가 바뀐다는 점이었다.

그것으로 다음 수들이 나오려면, 같은 자리 수에는 outlet과 plug에 대해서 1과 0의 개수가 같아야만 하겠다.

이것으로 문제가 풀릴 것 같은 좋은 예감으로 시작했는데,,

1과 0의 개수가 같은 경우에는 모든 경우의 수에 대해서는, flip이 발생했는지, 발생하지 않았는지를 알 수가 없었다..

brute force로 풀어야만 했다.

brute force만으로 2^n인 것을 random input에 대해서 평균적으로 2^(n-c) (?) 정도로 줄였는데, c가 너무 작아서 large input에서는 쓸모가 없었다.

brute force로 flipping하는 것을 flip, sort 횟수가 적도록 해볼 수 있을 것만 같았는데, 좋은 구현 방법을 생각해 내지 못했다.

포기..

나중에 해답을 보고 알았는데, 진짜 풀이 방법의 point는 그런 게 아니었다.

난 outlet을 switch해가면서 plug를 만들려고 했지만,

풀이는 plug가 나올 수 있는 모든 경우의 수를 n^2개 미리 나열해버리고, outlet을 맞춰 보는 방법인가 보다.

(맞게 이해한 건가..)

어쨋거나 거꾸로 생각해 보는 것도 좋은 시도인 것 같다.

# https://code.google.com/codejam/contest/2984486/dashboard

import sys
import os
#import numpy as np
import itertools

sample = "sample"
small = "A-small-practice"
large = "A-large-practice"
current = large

fin = open(current + ".in", "r")
fout = open(current + ".out", 'w')
f1out = open(current + "1.out", 'w')
f2out = open(current + "2.out", 'w')

T = int(fin.readline())

def solve(outlets, plugs, N, L):
    #print outlets, plugs
    plugs.sort()

    shuffle = []
    switch = []
    unknown = []
    for i in range(L):
        ips = [(p >> i) % 2 for p in plugs]
        ios = [(o >> i) % 2 for o in outlets]
        print i, ips, ios
        if ips.count(1) == ios.count(1):
            if ips.count(1) == ips.count(0):
                unknown.append(i)
        elif ips.count(0) == ios.count(1):
            if ips.count(1) == ips.count(0):
                unknown.append(i)
            else:
                shuffle.append(i)
        else:
            return "NOT POSSIBLE"


    shuffled_outlets = outlets[:]
    for s in shuffle:
        shuffled_outlets = [o ^ pow(2, s) for o in shuffled_outlets]

    print outlets, "-->", shuffled_outlets, shuffle, unknown
    shuffled_outlets.sort()

    result = len(shuffle)
    print plugs
    print shuffled_outlets

    if plugs == shuffled_outlets:
        return str(result)

    for i in range(len(unknown)):
        for j in itertools.combinations(unknown, i+1):
            shuffled_outlets2 = shuffled_outlets[:]
            for k in j:
                shuffled_outlets2 = [o ^ pow(2, k) for o in shuffled_outlets2]
            shuffled_outlets2.sort()
            #print shuffled_outlets
            if plugs == shuffled_outlets2:
                return str(result + i + 1)

    return "NOT POSSIBLE"

for i in range(T):
    N, L = map(int, fin.readline().split())
    outlets = [int(n, 2) for n in (fin.readline().split())]
    plugs = [int(n, 2) for n in (fin.readline().split())]
    print 'o', outlets
    print 'p', plugs
    solution = solve(outlets, plugs, N, L)
    if N == 1 and solution == "NOT POSSIBLE":
        print "ERROR1"
    if solution != "NOT POSSIBLE" and N < int(solution):
        print "ERROR2"
    answer = "Case #%d: %s\n" % (i+1, solution)
    print answer
    fout.write(answer)



fin.close()
fout.close()
f1out.close()
f2out.close()