TURNOFFTHELIGHTS.. 감을 못잡겠네요ㅠㅠ

  • restart
    restart

    TURNOFFTHELIGHTS를 풀고 있는데요, 사흘간 자나깨나 기회될때마다 관계식을 떠올리려 노력해도 도저히 나오질 않네요.. 다른 문제도 손에 잡히질 않고 입맛도 떨어지고 고민만 늘어가는 중.. 도저히 안되겠다 싶어서 도움의 손길을 청합니다.ㅠㅠ

    지금까지 제가 생각했던 건
    dp(i,j)=i를 행번호, j를 각행이 열변환되었는지 비트별로 나타낸다고 할 때(0110_2 : 1열, 2열이 열변환되었음), i행을 j열변환시키면서 [0..i]행을 모두 0으로 만드는 최소 가짓수라 정의하고

    dp[i][j]=min(dp[i-1][k]+bitcnt(j-k \And j)+linear[row_i \oplus j]), k=0..2^C
    \And = 비트AND, \oplus = 비트XOR

    인데요... 1차원의 행변환의 해를 구하는 linear는 미리 계산해 둬서 O(1)이라 해도 시간복잡도가 O(R2^{2C})라 답이 없더라구요...ㅠㅠ

    부족한 제게 가르침을 부탁합니다.. dp는 너무 형태가 다양하네요..ㅠㅠ


    9년 전
8개의 댓글이 있습니다.
  • 일루
    일루

    거의 다 오신것 같습니다. 가능한 (j, k)의 pair에 대해 생각해보시면...


    9년 전 link
  • WeissBlume
    WeissBlume

    현재 점화식 정의에서 상태를 나타내는 변수를 늘리면 더 쉽게 해결 가능합니다.

    d[i][j][k][l] : i를 행번호, j를 열번호, k를 각 열이 뒤집어진 상태인가, l을 현재 행을 뒤집는 중인가(연속적으로 뒤집을 수 있으니까).
    이렇게 정의하면 현재 (행,열)위치에서만 뒤집어보면 되니까 시간 안에 충분히 수행되겠죠!


    9년 전 link
  • wookayin
    wookayin

    2011년 대회 당시 공개했던 솔루션 슬라이드 입니다. 좀 더 오래 고민해보시고 도저히 모르시겠으면 참고하세요~


    9년 전 link
  • restart
    restart

    일루/ j에서 고려하는 k를 제한해보려고 했는데, 그게 잘 안됩니다..ㅠㅠ
    11
    11
    11
    00
    의 경우를 생각해보면, dp[3][00]에 답이 있을 텐데, 이건 dp[2][11]→dp[1][11]→dp[0][11]로 연결이 되는데.. 결국 고려하는 k의 범위가 00~11에 놓여 있다는 거고, j에 의존하지 않는 것 같아서요..ㅠㅠㅠ


    9년 전 link
  • restart
    restart

    WeissBlume/

    저도 열번호를 상태공간에 포함시키려 계속 노력했는데, [i][j-1]과 [i][j]간 연관관계가 뚜렷하지 않아 번번히 막히고 있습니다.ㅠㅠ 정의상 i*(j-1)과 i*j의 부분해일텐데,
    ＠＠＠Ａ
    ＠＠＠Ａ
    ＠＠＠Ａ
    ＃＃＃＊
    ＊이 현재 고려하는 dp[i][j][k][l]이라 할 때, dp[i][j-1][..][..]를 이용해 해당 부분해를 구해야 할텐데, 항상 Ａ에서 추가발생하는 부분이 문제가 됩니다. 이걸 또 따로 가지고 있어야 하는걸까요..ㅠㅠ으으으


    9년 전 link
  • restart
    restart

    wookayin/ 슬라이드가 공개되지 않은 것 같습니다.ㅜㅜ not found가 뜨네요..


    9년 전 link
  • restart
    restart

    뭔가 답까지 한계단 남은 것 같은데 눈앞에 길을두고 헤메는 느낌이라 엄청 답답하네요-_-;; 으아!


    9년 전 link
  • restart
    restart

    해결했습니다:) 5일간 끙끙 앓았네요..ㅠㅠ


    9년 전 link

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