[editorial] TCO 08 Qualification Round 3

  • Being
    Being

    tco08q3.png
    상당히 많은 사람이 easy/med/hard를 모두 풀었습니다. 그레이가 순위권 찍은게 눈에 띄네요. 사실 Qualification Round 3 자체가 한번 unrated match가 되어서 그 매치 때 2, 3등을 기록했던 한국인 두 명만 초안습이 됐습니다. 그래도 저는 8등이라도 했지 .. 지못미 ㅠ_ㅠ

    Easy (250 pts.)

    • 문제 설명 시키는대로 NxN array를 채우시오. 먼저 -1로 initialize하고 (0, 0)에 1을 써넣는다. 어떤 한 칸에 값을 써 넣은 다음에는 항상 아래로 a칸, 오른쪽으로 b칸 이동하여 2부터의 값을 차례대로 채운다. 만일 이미 -1이 아닌 값이 들어있다면 그 위치에서부터 아래로 c칸 오른쪽으로 d칸 이동해 본다. 그 칸에도 이미 -1이 아닌 값이 들어있다면 종료한다. 채워진 array를 출력하라. 단, array의 모양은 toroidal하다고 가정한다. (즉, 행/열 방향으로 cyclic하다) # 1 <= n <= 10 [spoiler="풀이 보기"]매우 심플한 문제입니다. 그냥 정말 시키는 대로 하면 되겠습니다. a, b, c, d가 음수일 수도 있었다면 그나마 조금 더 재미있는 문제가 되었을 지도 모르겠습니다. Failed solution도 거의 없었습니다. 재미있는 챌린지로는
      • 두 글자에 맞춰 char 타입으로 문자를 하나씩 출력하다가 100을 출력할 때 ":0" 출력 (이런 사람이 다섯이나 있더군요 ...)
      • 좀 더 나아가서 한 글자에 맞춰 char 타입으로 출력 (이런 사람은 둘이나..)
      • 맨 뒤에 공백 출력 또는 공백 없이 출력 (캐안습 ㅠㅠ....)
      • array의 크기를 5x5로 잡았다가 패망 [/spoiler]

    Medium (500 pts.)

    • 문제 설명 N개의 방과 그들을 연결하는 케이블들이 있다. 케이블들의 정보는 NxN 행렬의 형태로 주어지며, element (i, j)는 방 i과 방 j 사이의 케이블의 길이를 나타낸다. (구체적으로, '0'은 케이블이 없음을, 'a-z'는 1-26, 'A-Z'는 27-52) 물론 (i, j)와 (j, i)가 둘 다 케이블이 있다면 이중으로 연결된 것이다. 자기 자신과 연결된 쓸모없는 케이블이 있을 수도 있다. 방들을 모두 서로 연결된 상태로 유지하면서 최대한 쓸데없는 케이블을 많이 날리고 싶다. 얼마만큼을 없앨 수 있는가? 단, 초기에 연결되지 않았다면 -1을 리턴한다. # 1 <= N <= 50 [spoiler="풀이 보기"]눈에 뻔한 MST(minimum [cost] spanning tree) 문제입니다. prim 또는 kruskal 중에 구현이 빠를 것 같은 것을 골라내어 사용하면 됩니다. 재미있는 챌린지로는
    • N = 1인 경우 (연결되지 않았다며 -1을 내는 등) 오답을 내는 솔루션들
    • 엣지를 하나씩 제거해 보며 그래프가 연결된 그래프인지 판단하되, 그들 중 가장 가중치가 큰 엣지만 반복해서 제거함으로써 O(N^6) time complexity를 내는 솔루션들 이외에는 역시 traditional한 문제다 보니 솔루션 자체의 공통적인 결함보다는 사소한 부분의 실수를 잡아내는 것이 주효합니다. [/spoiler]

    Hard (1000 pts.)

    • 문제 설명 0 또는 1로 채워진 RxC matrix가 있다. 이 matrix의 임의의 한 열 또는 행을 잡아서 그 원소를 모두 반전하는 것을 1회의 연산이라고 하자. matrix의 모든 행과 열이 짝수개의 1을 갖도록 만들려면 몇 회의 연산이 최소 필요하겠는가? 불가능하면 -1을 되돌려라. # 1 <= R, C <= 49, R*C \in odd

    [spoiler="풀이 보기"]사람마다 아이디어를 표현하는 방식이 조금씩 다른 문제였습니다. 제 풀이를 설명하죠.
    이런 류의 boolean(modular) matrix operation 을 풀 때 주로 사용하는 방법으로 연립일차합동식을 나열하는 것입니다. 만일 연립합동식을 나열했을때 가우스 소거법으로 풀릴 수 있는 형태의 문제라면 쌩큐죠. 이 문제에서도 나열해 봅시다.
    r_k는 k번째 행의 1의 수가 현재 홀수개라면 1, 짝수개라면 0입니다. c_k도 열에 대해 비슷하게 정의합시다.
    R_k는 k번째 행을 잡아서 반전시킬 것인지(1) 말 것인지(0)를 결정하는 변수입니다. C_k 역시 그렇구요.
    편의상 행렬의 크기를 NxM으로 바꿉시다. 그렇다면 아래와 같이 식을 얻을 수 있습니다.
    R_1 + C_1 + C_2 + .. + C_M + r_1 = 0 (mod 2)
    R_2 + C_1 + C_2 + .. + C_M + r_2 = 0 (mod 2)
    R_3 + C_1 + C_2 + .. + C_M + r_3 = 0 (mod 2)
    ...
    R_N + C_1 + C_2 + .. + C_M + r_N = 0 (mod 2)
    C_1 + R_1 + R_2 + .. + R_N + c_1 = 0 (mod 2)
    C_2 + R_1 + R_2 + .. + R_N + c_2 = 0 (mod 2)
    C_3 + R_1 + R_2 + .. + R_N + c_3 = 0 (mod 2)
    ...
    C_M + R_1 + R_2 + .. + R_N + c_M = 0 (mod 2)
    이 식들을 모두 만족해야 일단 가능한 솔루션이겠죠.
    식을 가만히 보니 예쁜 모양의 common term이 있습니다. (C_1 + C_2 + ... + C_M)과 (R_1 .. R_N) 이죠.
    앞의 식을 X라 합시다. X를 2로 나눈 나머지는 0 혹은 1일 것입니다. 즉, 열을 뒤집는 횟수는 당연히 짝수번 또는 홀수번 뒤집게 되겠죠.
    그런데 열을 구체적으로 어떻게 뒤집을 것인지 모르더라도, 짝수번 뒤집을 것인지 홀수번 뒤집을 것인지만 결정하면 저 식에 대입해 보면 R_k꼴의 변수가 모조리 결정됩니다. 즉, 행을 뒤집을지 말지는 행의 1의 개수와 전체 열바꿈의 parity만 알면 되는 것이죠.
    따라서 C_1 + C_2 + ... + C_M(을 2로 나눈 나머지)가 0 또는 1이므로, 0 또는 1이라고 일단 치고 R_k 변수들을 모두 구합니다. 그리고 나면 C_k 변수들도 같은 원리로 모두 구할 수 있습니다. 따라서 전체 가능한 방법은 최대 두 개 뿐입니다.
    조금 더 생각해 보면, 불가능할 때의 -1 없이 항상 두 가지의 방법이 존재함을 알 수 있습니다.
    [/spoiler]

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    16년 전
10개의 댓글이 있습니다.
  • Toivoa
    Toivoa

    ㅠㅠ
    Hard 문제 해법은 생각해둔게 있는데 풀어볼 의욕이 안생겨서 gg -_-q


    16년 전 link
  • nocut98
    nocut98

    2부 리그도 누가 에디토리얼 점... 아무도 안 써서 매번 Hard풀기 짱 어려움 ㅡ.ㅜ 물어볼 데도 없고


    16년 전 link
  • Being
    Being

    보통 하드는 DIV1과 문제가 겹치지 않나요?=ㅁ= 미디엄-이지가 겹칠 때도 있긴 하지만..


    16년 전 link
  • nocut98
    nocut98

    보통은 미디엄-이지가 겹치는 편이고, 하드-이지가 겹치는 경우는 좀 드문 편입니다. 특히 이번에는 coding phase중에 푼 사람이 아무도 없을 정도로 좀 난이도가 있었던 편이라서(레드들은 연습방에서 잘들 푸시더군요 ㅎㅎ) 이해하기가 어렵더군요;;
    뭔가 graph + dp를 적용한 거 같은데... ㅎㅎㅎ 그리고 2부리그에서 1등하고 에디토리얼 쓰는 경우도 별로 없고, 채널에서 물어볼려고 해도 다들 1부리그라 제가 모르는 문제니까 풀어보고 알려달라고 할 수도 없고 해서 좀 외롭습니다. ㅡ.ㅜ
    제 개인적인 꿈은 2부리그 1등 먹고 알고스팟 분들한테 하카다 쏘는 거 정도? ㅋㅋㅋ


    16년 전 link
  • helloneo
    helloneo

    저도 에디토리얼좀 써보고싶어요.. ㅠ_ㅠ 이번에 다시 2부리그로 떨어진김에.. hard를 집중공략해봐야겠군요!!


    16년 전 link
  • nocut98
    nocut98

    welcome to div 2 !! 이제 에디토리얼 쓰시면 될 듯 ㅎㅎㅎ (왜냐면 2부는 아무도 안 쓰니까요 ㅋㅋㅋ)


    16년 전 link
  • zolac
    zolac

    저도 srm391 은 미디엄까지 금방풀었고, 미디엄은 좀 다른방법(?)으로 풀어서 하드 풀고 에디토리얼쓰고 싶었는데.ㅠㅠ
    하드는 못풀고 미디엄은 fail받고 ㅡㅡ;; (하드는 연습방에서 계속해봐도 못풀고있고.ㅠㅠ)
    저도 2부리그 세문제 풀고 에디토리얼쓰고싶어요..ㅎㅎ


    16년 전 link
  • nocut98
    nocut98

    미디엄 진짜 금방 푸셨네요- 언젠가 에디토리얼 쓰시길 바라겠습니다- ^^


    16년 전 link
  • 김우현
    김우현

    와.... 1000번 해법 감동입니다!


    16년 전 link
  • dgsquare
    dgsquare

    말씀하신 문제가 SRM 401의 Hard 문제라면, KMP 매칭의 Automata를 묻는 문제입니다. 즉 P[i]로 매치시 틀렸을때 돌아가는 index를 계산하면, 전체 문자열 길이에서 에서 P[n-1]의 값을 빼면 최소길이 반복 문자길이를 구할수 있습니다. 저역시 Forum에서 힌트를 보고 알았는데, 바로 알아내는 사람들 보면 놀랍다는 ㅠㅠ


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