HowToFail - SRM626D1-600

  • Neon
    Neon

    NegativeGraphDiv1


    Problem Description

    TopCoder Link(doesn't require login)

    Idea

    charge가 작은 경우에는 그냥 경우의 수를 모두 계산해서 문제를 풀 수 있다. D[c, s, e] := c개만큼 charge를 사용해서 s부터 e까지 가는 데 드는 최소 비용. 이라고 정의하고 DP로 풀면 됨. 다만 c가 꽤 큰 문제이기 때문에, 이걸 그대로 적용하진 않고, 다음과 같은 경우가 성립할 거라고 가정했다.(오른쪽 반례 부분은 추후 설명함)

    CtrlV Free Image Hosting


    Image hosted for free at CtrlV.in

    즉, 답 S = {p_0, p_1, p_2, ... p_m} 라고 가정할 때, 그 중 어딘가(p_i라고 부르자)에서 동일한 사이클을 여러번 돌고 그 다음 목표지점으로 이동하는 방식으로 답이 구성될 거라는 가정을 세워 봤다. 이때 p_0부터 p_i까지의 중간 점의 갯수는 N 이하일 것이고, 또 p_i에서 뺑뺑이 도는 사이클의 크기도 N 이하일 거라고 판단했다. 왜냐하면 N보다 커지면 같은 점을 두번 방문하는 꼴인데... 그렇게 되면 또다른 사이클이 존재하게 되는 셈이니 처음 가정에서 벗어나기 때문이다.

    실제 풀이 코드

    https://gist.github.com/blmarket/84bc3ae1941242a06a70#file-negativegraphdiv1-fail-cpp

    당당하게 N 이하일 거라고 가정했지만, 넉넉한 버퍼를 뒀다. 일단 c=0..120까지 계산을 수행하고, i가 100 이하, 사이클의 길이가 100 이하인 모든 경우에 대해 계산해보도록 했다.

    반례

    위 그림에서 같이 적어놓았듯, 사이클이 딱 한종류로만 존재할 거라는 가정이 틀렸다. 생각해보면 위의 base idea는 charge의 갯수가 특정 interval일 때에만 올바른 답을 제공하게 된다.

    CtrlV Free Image Hosting
    Image hosted for free at CtrlV.in

    따라서 여러 가지 다른 cycle을 섞어서 charges에 맞게 사용할 때 더 좋은 답안을 얻을 수 있게 된다. 기본 가정 자체가 틀렸으니 이건 뭐 땜빵으로 해결할 수 없는 FAIL!

    정답 풀이

    실은 c가 커져도 DP 대신 matrix multiplication의 아이디어를 적용해서 풀면 바로 계산해낼 수 있음. 제가 짠 코드 말고도 연습방에 좋은 풀이가 많습니다.

    https://gist.github.com/blmarket/84bc3ae1941242a06a70#file-negativegraphdiv1-success-cpp

    Written with StackEdit.


    6년 전
3개의 댓글이 있습니다.
  • Neon
    Neon

    으앙. 회심의 이미지들이 몽땅 오른쪽이 짤려서 FAIL.
    https://gist.github.com/blmarket/84bc3ae1941242a06a70 에서도 동일한 문서를 볼 수 있습니다.


    6년 전 link
  • wookayin
    wookayin

    gist에서도 수식 렌더링 되면 참 좋을거 같은데 말이죠..ㅋㅋ


    6년 전 link
  • kwangswei
    kwangswei

    와 How to Fail 도 정말 좋은 것 같아요! 하하 저도 공부하면서 왜 틀렸는 지 정리 좀 해놔야 겠군요...


    6년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.