페이스북 Hackercup Round 1 결과

알고스팟/알고리즘 2015.01.21 17:16


2주전에 Qualification을 한문제라도 통과한 사람들을 대상으로 저번주에 Round 1이 치뤄졌다. 전년도 와는 다르게 3문제에서 4문제가 출제 되었고 인풋 사이즈도 늘어났는데 (10-20Mb), 참여할 수 있는 여건이 너무 안좋아서 악조건 속에 4문제중 3문제를 풀었으나 티셔츠를 받을 수 있는 Round2 진출은 하지 못했다 ㅜㅜ. 아쉬운 대로 푼 문제에 대해 간단한 나의 풀이와 코드를 적어본다. 


모든 공식적인 풀이와 참가자들의 코드는 https://www.facebook.com/hackercup/problems.php?round=344496159068801 에서 확인 할 수 있다.




1)번 문제 


어떤 숫자 N을 소인수 분해 했을 때 그 N을 나타내는 고유한 소수의 수를 "Primacy"라고 지칭한다. 예를들어 9 = 3^3 이니 primacy = 1. 10은 2*5이니 primacy는 2이다. 이렇게 어떤 숫자의 primacy를 정의한 뒤, 구간 [A, B]와 상수 k가 주어 질 때, 구간안에 primacy K를 가진 숫자의 수를 세는 문제이다. 


1 ≤ T ≤ 100 
2 ≤ A ≤ B ≤ 107 
1 ≤ K ≤ 109 

 숫자를 보면 알다 시피 전혀 크지 않다. Sieve method를 활용해 소수의 배수를 지워 나가는게 아니라 소수의 배수에 대한 primacy를 하나씩 +1 해주는 방식으로 미리 다 구해놓은뒤 구간 [A, B]를 순회 하면서 primacy K인 숫자들만 찾아도 충분히 시간 안에 답을 구할 수 있다.


max=100000000 primacy=[0]*max for i in xrange(2,max): if primacy[i] == 0: #i = prime number for j in xrange(i, max, i): primacy[j]+=1 f = open('outputhomework.txt', 'w') f2 = open('homework.txt', 'r') for j in range(int(f2.readline())): l = map(int, f2.readline().split()) ans = 0 for i in range(l[0], l[1]+1): if primacy[i] == l[2]: ans+=1 txt = 'Case #' + str(j+1) + ': ' + str(ans) + '\n' f.write(txt) f.close()

2번 문제)


문제의 타이틀 autocomplete 이 알려주는 것 처럼 일련의 단어 = [s_1, s_2, s_3, .... , s_n]이 주어 질 때 이들을 모두 타이핑 하기 위해 눌러야 할 키보드 숫자 합의 최소값을 구하는 문제이다. 하지만 단순 len(s_1) + ... + len(s_n)이 아닌 이유는 각 단어를 사전에 미리 넣은 뒤 autocomplete이 가능 하기때문이다. 단, 사전에 넣는 작업은 키보드를 타이핑 하지 않아도 된다고 가정한다. 예제를 보면 이해가 빠르다.


hi
hello
lol
hills
hill

다음과 같은 일련의 단어 인풋이 주어질 때, hi = 먼저 hi를 사전에 넣고 h, 즉 h를 누르는데 1번만 누르면 hi가 완성된다. 다음 단어 hello를 사전에 집어 넣은뒤 h를 입력하면 hi 와 hello 모두가 autocomplete 될 수 있으므로 he 까지 쳐줘야 된다. h, e 2번. lol을 사전에 넣은 뒤 l만 누르면 자동 완성. l  = 1번. 다음단어 hills를 넣은뒤 hil까지 입력해야 hills가 추천된다. 즉 h, i , l  3번. 마지막으로 hill은 hills안에 완전히 포함되기 때문에 전체 hill을 모두 타이핑 해줘야 한다. 총 4번.
전체를 다 더하면 1+2+1+3 + 4 = 11번이다. 

여기 까지 오는데 바로 이 문제를 풀기 위한 자료구조가 생각나지 않으면..사실 이 문제가 요구하는 바를 캐치 못한것이다. 
trie 라는 자료구조가 이문제에서 요구하는 답안이다. trie는 간단하게 설명하면 모든 주어진 문자열의 prefix 부분 문자열을 포함하는 트리 형태의 구조이다. 더 자세한 설명은 http://en.wikipedia.org/wiki/Trie 로 대체한다. 

이렇게 trie 구조가 생각났다면 해야할 일은 단순하다. n개의 단어가 주어 졌을 때 첫 단어부터 trie에 넣고 단어 s의 s[0] , s[1], ..., s[n-1]까지 트리를 내려 가면서 autocomplete 추천 단어가 하나로 정해질 때 까지의 숫자가 최소 필요한 숫자이다. trie에 각단어를 넣고, 찾는데 각각 O(n) (n = word length)가 소요 되며, 전체 n단어가 있으므로 O(n^2).  

코드는 나보다 깔끔한 구현을 한 그 유명한 PS신 petr의 코드로 대체.
http://attachment.fbsbx.com/hackercup_source.php?sid=1024133864268953


3번 문제)

문제는 굉장히 간단하다. 어떤 스포츠 경기에서 최종 스코어 A:B로 끝났을 때 (단, 항상 A > B이다. 즉 편의상 '우리'팀이 항상 이기는 경기이다.), 그 경기가 stressful , stress-free 였는지 여부를 다음과 같이 결정한다. 

stressful 즉 이기긴 이겼지만 암걸리는 경기였다면, 상대방의 스코어가 최종 스코어인 B이전 까지 우리는 항상 상대방 팀 점수와 같거나 비기고 있다. 말이 어려워서 5-3경기에 대해 예를 들어 본다. 이 경기에 대한 stressful sequence의 한 예는 다음과 같다. 0 - 0. 0 - 1. 1 - 1. 1 - 2. 2 - 2. 2 - 3. 3 - 3. 4 - 3. 5 - 3. 즉 이기긴 이겼지만 첫 6골에 대한 경기 과정에서 우리는 한번도 상대방을 비기긴 해도 이기고 있는 구간이 없다. 

반대로 stress-free는 모든 경기 구간에 대해 이기고 있는 경우이다. 

최종스코어가 5-3일때 1 - 0. 2 - 0. 2 - 1. 3 - 1. 3 - 2. 4 - 2. 4 - 3. 5 - 3. 인 경우에는 모둔 경우에 대해 우리가 이기고 있으므로 stress-free한 경우이다. 


3번 문제는 위와 같은 정의 하에 최종 스코어 A:B가 주어 졌을 때, 이로부터 얻을 수 있는 stress-ful, stress-free한 sequence 경우의 수를 구하는 문제이다.


스탠다드한 다이나믹 프로그래밍 정답은 페이스북 페이지에 잘 소개 되 어 있다. 직관적으로 생각해도 stress-free 같은 경우에 내가 2점 앞서고 있으면 그로 부터 상대방이 한골 넣는 경우의수 + 내가 한골 더 넣는 경우의 수로 생각 해볼 수 있다.


이 문제는 위와 같은 방법 말고도 다르게 풀 수 있는데 그게 바로 

Catalan number (http://en.wikipedia.org/wiki/Catalan_number) 를 만약에 알고있다면 바로 알아 차릴 수 있다. stress-ful한 경우에 최종 스코어가 A:B라면 첫 2*B 골에 대해 상대방이 항상 이기거나 비기고 있다. 이는 balanced structure의 개수를 세는 catalan number와도 동치 인데 예를 들면 (( )) () () 와 같은 경우이다. 따라서 stress-full 경우는 2*B개의 숫자에 대한 catalan number이다. 즉 'B' Catalan 'B' 인 경우이다. 비슷하게 stress-free 같은 경우 내가 첫골을 넣은 뒤 부터는 똑같이 항상 비기거나 이기고 있으면 되니깐 'A-1' Catalan 'B' 이다. Catalan number에 대한 좀 더 확장된 개념인 셈이다. 더 자세한 내용은 http://en.wikipedia.org/wiki/Catalan's_triangle 참조.



설정

트랙백

댓글

페이스북 Hackercup Challnege

알고스팟/알고리즘 2015.01.13 18:57


구글의 Codejam과 비슷한 페이스북의 Hackercup Challenge의 예선전이 저번 주말 실시 되었다. 

예선전은 그 어느 대회의 예선전과 비슷하게 비교적 쉬운 난이도의 문제들로 구성되었다. (문제링크 ,https://www.facebook.com/hackercup/problems.php?round=742632349177460).


1번 문제는. 간단한 구현 문제로 

0으로 시작하지 않는 어떤 숫자 n이 주어 졌을 때 단 한번의 두 숫자간의 swap을 통해서 얻을 수 있는 최대, 최소의 수를 구하는 문제이다. 첫 leading digit이 0으로 시작하지 않는 다는 조건을 지키면서 O(n^2)개의 스왑을 다하거나 아니면 greedy하게 가장 오른쪽에 있는 제일 작거나 큰 숫자를 찾아 바꿔주는 방식으로 (이 방법도 최악의 경우 O(n^2))풀면 답이 나온다. 간단한 구현 문제. 


for t in range(input()):
    x = raw_input()
    a = b = int(x)
    x = list(x)
    for i in range(len(x)):
        for j in range(i):
            x[i],x[j] = x[j],x[i]
            if x[0] != '0':
                v = int("".join(x))
                a = min(a, v)
                b = max(b, v)
            x[i],x[j] = x[j],x[i]
    print "Case #%d: %d %d" % (t+1, a, b)




2번문제는 binary knapscak의 변형된 형태이다. n개의 음식 리스트가 있고 각 음식은 c_i, p_i, f_i (각 탄수화물, 단백질, 지방) 함량이 표기되어 있다. 이 n개의 리스트의 음식을 각 안먹거나 한번막 먹을 수 있을 때 목표 각 G_c, G_p, G_f의 함량합을 섭취 할 수 있는냐 하는 문제이다.


사실 qualification round 자체의 인풋 사이즈가 크지 않고 제한 시간이 길기 때문에 2^n개의 모든 부분집합을 다 해보는 경우도 충분히 가능할 것 같다. 하지만 이 문제에서 함량합들이 각각 낮은 숫자이기에 (최대 1000미만) 동적계획법을 이용해 한 개의 음식군에 대해 O(nW)로 찾은 뒤, 이 후보 부분집합들을 각각 고려해 나머지 두개의 음식군에 대해 함량합을 만족시키는 지를 확인하면 좀 더 빠르게 가능하다.


#binary knapscak for one variable. memo = dp table.
def fcompute(v, i, S, memo):
  if i >= len(v): return 1 if S == 0 else 0
  if (i, S) not in memo:  # <-- Check if value has not been calculated.
    count = fcompute(v, i + 1, S, memo)
    count += fcompute(v, i + 1, S - v[i], memo)
    memo[(i, S)] = count  # <-- Memoize calculated result.
  return memo[(i, S)]     # <-- Return memoized value.

#backtrack to construct the actual solutions
def gAll(v, S, i, memo):
  sol = []
  if S == v[i]: return [[i]]
  if S == 0: return [[]]
  if i == len(v): return [[]]
  #answers that include 'i'th food
  if fcompute(v, i + 1, S - v[i], memo) > 0:
      for each in gAll(v, S - v[i], i+1, memo):
        each.append(i)	  
        sol.append(each)
  #answers that don't.		
  if fcompute(v, i + 1, S, memo) > 0:
      sol.extend(gAll(v, S, i + 1, memo))
  #find all without including ith item.	  
  return sol
  
#given answers, see if other two are satisfied.
def checkOhters(ans, ingredients, p, f):
	for each in ans:
		fsum, psum = 0, 0
		for index in each:
			fsum += ingredients[index][2]
			psum += ingredients[index][1]
		if fsum == f and psum == p:
			#print [ingredients[i] for i in each], p, f
			return 'yes'
	return 'no'


def solve(ingredients, c, fat, p):
	carb = [each[0] for each in ingredients]
	memo = {}
	fcompute(carb, 0, c, memo)
	ans = gAll(carb, c, 0, memo)
	return checkOhters(ans, ingredients, fat, p)
inputfile = open('new_years_resolution.txt', 'r')

q = open('output.txt' , 'w')

n = int(inputfile.readline())
for i in range(n):
	l = map(int, inputfile.readline().rstrip().split())
	c,fat,p = l[0], l[1], l[2]
	num = int(inputfile.readline())
	ing = []
	for _ in range(num):
		ing.append(map(int, inputfile.readline().rstrip().split()))
	ans = 'Case #' + str(i + 1) + ': ' + solve(ing, c, fat, p) + '\n'
	if i == n - 1: ans.rstrip()
	q.write(ans)
q.close()

3번문제는 스탠다드한 미로 찾기 알고리즘의 변형 된 형태이다. 목표지점 S에서 시작해 도착지점 G로 가는 최소의 step 수를 찾는 문제이지만, 미로안에 레이저들이 있다. 이 레이저는 동,서,남,북의 각기다른 위치를 가르키고 있는데 한걸음 딛을 때 마다 위치가 90도씩 시계방향으로 돌아 간다. 이 후, 발사하게 되는데 발사되는 동선 위에 있다면 죽게 된다. 이를 방지하면서 도착지점 G로 가는 최소 step 수를 구하는 문제이다. 


한가지 관찰할 점은 레이저의 현재 상태를 모두 저장할 필요없이. 현재 까지 몇걸음을 갔나 하는 정보만 저장하면 된다. 또한 4번 돌고 나면 처음 가르키던 방향으로 돌아오는 점을 이용해 (현재걸음수)%4의 정보만 저장하면 된다. 또하나의 speedup은 레이저에 위험한 cell을 미리 O(n^2)만에 계산 한 뒤 저장하는 방법인데 이를 이용하면 현재 위치가 위험한지 안 위험한지의 여부를 O(1)에 판별 가능함으로 전체 O(n^2) (bfs에 걸리는 시간)만에 구 할 수 있다.



from collections import *
for T in range(input()):
    m,n=map(int,raw_input().split())
    board=[list(raw_input()) for i in range(m)]
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'S':
                start = i,j
                board[i][j] = '.'
            elif board[i][j] == 'G':
                goal = i,j
                board[i][j] = '.'
    boards = []
    for _ in range(4):
        B = [r[:] for r in board]
        for i in range(m):
            for j in range(n):
                c = B[i][j]
                if c not in '^>v<': continue
                dx,dy = {'^':(0,-1), '>':(1,0), 'v':(0,1), '<':(-1,0)}[c]
                x,y = j+dx,i+dy
                while 0<=x<n and 0<=y<m and B[y][x] not in '^>v<#':
                    B[y][x]='*'
                    x += dx
                    y += dy
        boards.append(B)
        for i in range(m):
            for j in range(n):
                board[i][j] = {'^':'>','>':'v','v':'<','<':'^'}.get(board[i][j],board[i][j])
    q = deque([(start,0)])
    v = {(start,0):0}
    res = "impossible"
    while q:
        (Y,X),M = state = q.popleft()
        M = (M+1)%4
        c = v[state]
        if (Y,X) == goal:
            res = c
            break
        for dx,dy in [(0,-1), (1,0), (0,1), (-1,0)]:
            x,y=X+dx,Y+dy
            if 0<=x<n and 0<=y<m and boards[M][y][x] == '.':
                s2 = (y,x),M
                if s2 not in v:
                    v[s2] = c+1
                    q.append(s2)

    print "Case #%d: %s" % (T+1, res)






설정

트랙백

댓글