Saturday, September 7, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 2


Link : https://www.acmicpc.net/contest/scoreboard/7

A. RNG - Accepted
Change the form of the equation
y = a(x^2)+bx+c mod (2^n)  into  a(x^2)+bx+c`=0 mod (2^n)
if x is a solution for n, (x mod 2^(n-1)) is a solution for n-1
So, if x is an unique solution for n-1
1) x is possible solution for n
2) x + 2^(n-1) is possible solution for n
Maintaining solutions for increasing n
1) if solution is unique, continue.
2) else we can't get the unique solution.

B. 나쁜과학자
Minimum vertex cover

C. 큐빙
I didn't read the problem because the cube makes me tired.

D. 차원 워프 드라이브
I didn't read the problem.

E. 아! - Accepted
Simple strings' length comparison.

F. 도어맨 - Accepted
Greedy method.

G. 전화번호 목록 - Accepted
Ordinary Trie problem.
http://en.wikipedia.org/wiki/Trie

H. 무글 맵스 - Accepted
Dynamic programming. d[i][j] = min(d[k][j-1] + s[k][i])

I. 대충 정렬
I didn't read the problem.

J. 연결
It might be solved with Minimum Cost-Maximum Flow(MCMF)
Similar problem : http://poj.org/problem?id=2195

No comments:

Post a Comment