MenOfPassion   2년 전

안녕하세요.

Google codejam에서 codejam, kick start에 참여할때 개인적으로 사용할 컴퓨터 사양에 대해서 문의 드립니다.

올해 일반 Note PC로 codejam에 참여해 봤는데요..

Website에서 test case 100인 input을 받아서,

N=1000이고, O(N^3) (즉, 1개 TC당 10억번의 연산) 인 솔루션을 Note PC에서 돌려서 output을 만들고,

3분안에(input을 받은 시각으로 부터 3분) Website에 output과 소스 코드를 올려야 되는 경우가 있었는데요..

제 Note PC에서는 tc 100개를 돌리는데 3분 이상 걸려서 결과적으로 제 솔루션을 제출할 수 가 없었습니다.

시험이 끝나고 통과된 다른 분의 솔루션을 봤는데.. 저랑 동일하게 O(N^3)이었습니다.

codejam에 참여하기 위해서 고사양의 workstation 이나 Server가 필요한 걸까요?

아니면, 고사양의 Note PC면 될까요?

혹시 multi-threading(tc1개당 thread 1개)을 해야 하는걸까요?

유경험자분들의 조언 부탁드립니다.

미리 감사드립니다~

dlwodnsdl   2년 전

연산 1억번에 1초정도 걸리니까 1000억개면 3분이상 걸리는 거 맞습니다.

작년에 5년된 노트북+자바로도 코드잼 1라운드를 통과한 경험이 있는데 좋은 컴퓨터 보다는 좋은 코드가 필요할 것 같습니다.

MenOfPassion   2년 전

dlwondsdl님,

답변 감사드립니다.

말씀하신 내용 전적으로 동의합니다.

저도 TC 1개당 수억 이상 넘어가면 제출 자체를 시도하지 않고, 더 개선해 보려고 노력했는데요..

codejam은 다른거 같아서요.. codejam에서 contest analysis를 보면 수억정도면 large data에서 충분하다고 하는경우가 있는것 같아요..

( The overall complexity of our DP approach is O(N2M2(N + M)), which is fast enough for the Large dataset. N=M=40)


아래는 실제로 N=1000인경우 통과된 코드 입니다.(O(N^3))

댓글을 작성하려면 로그인해야 합니다.