우리 팀 789가 대회 1등을 차지했다.

내가 푼 문제는 C, I, J, K 이다.


J. Starwars (32 min., +2, First Solve; 2nd AC from 789)

n(≤1,000)개의 정점(solar system)이 있고, 그중 일부는 human-controlled이며, 또 다른 일부는 military base가 설치되어 있다.
human-controlled와 military-base-installed 여부는 독립적이다.

또한 각 정점 사이에 m(≤8,000)개의 간선(wormhole)이 있다. 간선을 사용할 때마다, 그 간선에서 인증서(certificate)를 발급해 준다.
여러 간선을 사용하면, 그 경로에 의해 얻는 인증서가 순서대로 쌓인다.
인증서는 총 C(≤20)가지가 존재한다.

이 때, 어떤 human-controlled 정점에서 시작해 임의의 military-base-installed 정점으로 도달하는 경로와,
어떤 non-human-controlled 정점에서 시작해 임의의 military-base-installed 정점으로 도달하는 경로가
같은 certificate 수열을 가지게 되는, 두 경로 쌍이 존재하는지를 묻는 문제이다.
(두 경로의 마지막의 military-base-installed 정점은 서로 달라도 된다.)




이 문제는 2018 서울 리저널 인터넷 예선 K번 문제(Suffix-freeness)와 거의 똑같은 문제이다.
같은 certificate 수열의 경로 쌍이 존재한다면, 두 개의 말(駒)을 각각 human-controlled 정점과 non-human-controlled 정점에 놓고,
매 step마다 같은 certificate를 얻게 되는 정점으로 양쪽 말을 동시에 움직였을 때,
두 개의 말이 각각 military-base-installed인 정점에 도달하게 되는 움직이는 방법이 존재하게 된다.

즉 모든 human-controlled 정점 i와 non-human-controlled 정점 j에 대해 (i, j)의 쌍을 정점으로 잡고,
두 개 모두가 military-base-installed인 곳에 도달할 수 있는지를 BFS를 통해 확인해주면 된다.

모든 (i, j) 쌍에 대해 (i에서 시작하는 간선의 수)×(j에서 시작하는 간선의 수)만큼 탐색하게 되는데,
임의의 두 쌍의 간선이 고려되는 경우는 최대 1번 뿐이므로 O(n²c + m²)의 시간복잡도를 가진다고 말할 수 있다.


문제를 이해하고 나서는 인터넷 예선과 너무나도 똑같은 문제라서 당황했다.
그 때도 IJKL번을 담당했던 내가 풀었고, 그 때도 First solve였는데, 이번에도 완벽히 똑같았다.

s에서 t까지 움직일 때 c의 인증서를 받는데, s-t-c 순서가 아니라 s-c-t 순서로 입력이 들어오길래
왜 굳이 순서를 바꿔서 주는지 불평했는데, 오히려 '이 생각의 방향이 맞다'는 힌트가 되었던 것 같다.
(s, c) 쌍에 대해 하나의 t만 존재한다고 생각하고는 배열에 단순 대입을 해버렸더니 WA를 두 번 받았다.


K. TV Show Game (58 min., +0; 3rd AC from 789)

어느 TV 쇼에서는, red 혹은 blue 색의 lamp가 k개 주어져 있다. 불이 꺼져 있어 색을 알 수는 없다.
n명의 참가자가 각각 (i번째 lamp의 색은 X이다)의 추측을 정확히 세 개 하며, 이들 중 두 개 이상이 맞으면 상품을 받는다.
램프의 색깔을 잘 조절해 모든 참가자가 상품을 받을 수 있도록 할 수 있는가? 있다면 그 방법 중 하나를 출력하라.



참가자의 세 개의 추측 중 하나가 틀렸다면 나머지 두 개가 반드시 맞아야 한다.
각각의 추측을 (i가 blue이다)를 명제 i로 생각하고, (i가 red이다)를 명제 ¬i로 생각하면,
(¬a⇒b) 및 (¬a⇒c)는 항상 성립해야 한다.
각 참가자의 요구사항마다 이러한 조건식을 6개 세울 수 있다. (실은 이중 2개씩 세 쌍은 각자 대우 명제이다.)

아무튼 참가자의 요구사항은 이러한 "implies" 관계의 조건식으로 바꿀 수 있고,
V ≤ 5,000이고 E ≤ 30,000 × 2 인 2-SAT 그래프를 만들어 탐색하면 풀 수 있다.


"두 개 이상이 맞으면.."의 조건을 "한 개 이상이 맞으면..."으로 생각하고,
3-SAT인가? 특별한 경우에 성립하는 3-SAT인가? (실은 그러기에는 특별한 조건이 거의 없었기에 꼼짝없이 NP-Complete였다) 하고 넘겨버려서 늦어졌다.


C. Disk Arrangement (171 min., +0; 9th AC from 789)

직선 상에 원 n(≤1, 000)개를 나열한다. 직선 상이라는 말은, x축에 접하게 놓으면서 y≥0 평면에 놓이도록 한다는 이야기이다.
원들의 반지름만 정해져 있기 때문에 자유롭게 순서를 재배열할 수 있다.

이때, 이들을 최대한 tight하게 이어 붙였을 때 원들의 가장 왼쪽의 점과 가장 오른쪽의 점 사이의 거리(즉 max{x} - min{x})가 있을 텐데,
원들을 잘 재배열해서 이 값을 최소화하는 문제이다.
단, 원끼리는 서로 겹쳐서는 안 된다.

어떤 원이 너무 작거나 너무 크면, x좌표 상으로 서로 인접한 원끼리 겹치지 않더라도, 몇 개 떨어져 있는 원이 서로 겹치는 경우가 있을 수 있다.
가장 큰 원의 반지름이 가장 작은 원의 반지름의 4배 이상일 때만 이런 경우가 발생함이 알려져 있다고 문제에서 주어진다.
또한 그런 입력은 주어지지 않음이 보장된다.
즉 n!개의 배열 중 어떤 방법을 고르더라도, 인접한 것끼리 tight하게 붙였을 때, 원의 내부가 겹치는 경우는 절대로 없음이 보장된다.




수식을 가지고 엄청나게 고민했었다. 인접한 네 개 끼리의 순서 관계에 대해 (부등식을 세워) 규칙을 찾아보려고 하기도 하고...
하지만 대부분의 시도가 그럴 듯 하기만 할 뿐 확실하지가 않았다.

그래서 차라리, r을 랜덤하게 잡고, 작은 n에 대해 n!가지를 모두 해 봤을 때
혹시 크기 순서에 규칙이 나오지 않을까, 하고 코딩으로 확인해 보자고 팀원에게 제안했다.
처음에는 뭔가 다르게 나오길래 아닌가보다, 하고 포기했는데,
r값을 모두 다르게 하고(같은게 있으면 서로 순서가 섞여도 되기 때문에 헷갈릴 여지가 있었다) 보니까,
n이 짝수이면 한 가지 방법(n=8이라면 5 3 7 1 8 2 6 4)과 그것을 뒤집은 것(4 6 2 8 1 7 3 5)만이 답이 됨을 확인할 수 있었다.
n=10과 n=8에 대해 확인했다.

n이 홀수더라도 약 4가지 종류로 분류됨(가운데 값이 1인가 n인가 × 가운데 값에서 출발하는 방향과 그 옆에서 출발하는 방향이 같은가)을 찾았다.

r을 아무리 임의로 잡아도 n!가지 중에 항상 정해진 형태의 답만 값이 최소가 됨을 확인하자 자연스레
"대회 중에 확인은 못 하지만 신묘한 원리가 있겠지?" 라는 결론에 다다르게 되었다. 그럴 수밖에 없다.
그러고 보니 다른 팀들의 AC도 이런 느낌으로 빨리 나온 게 아닐까 싶었다. n이 작은 것은 위장전술이라고 생각했다.
아무튼 코딩해 제출했더니 아니나 다를까, AC를 받았다.


설마 이런 풀이일까에 대한 반신반의가 있었다.
하지만 대회 시작 후 약 1시간 시점(60 min.에 A: Circuits가 +1로 풀리고, 68 min.에 E: LED가 +3으로 풀렸다)에,
"패널티 말고 AC 갯수에 집중하자"라고 세 명 모두 의견을 모았다.
8 solve에서 9 solve가 되며 등수를 올렸던, 상당히 짜릿한 AC였다.

I. Square Root (294 min., +4, First solve; 11th AC from 789)

리저널 1위를 결정한 문제이다.
트리 T에 대해, 이 트리의 square라는 새로운 그래프 G를 구할 수 있는데,
정점 집합은 동일하고, T에서의 최단경로의 길이가 1 이상 2 이하였던 정점쌍들만이 G에서 연결되어 있다.

G가 주어지면, G가 T의 square인 트리 T가 존재하는지 판별하고, 존재한다면 T를 출력하시오.
G의 V ≤ 100,000이고, E ≤ 1,000,000.




일단은 정점을 하나 잡아야 하겠다. 트리의 루트를 r이라고 하자. (원본 트리는 사실 unrooted일 것이므로, 임의로 붙이는 셈이다)
r 근처(즉, r에서 거리 2 이하)의 점들이 r로부터 어떤 위치에 있는지를 확실히 판별하고 나면, 그 밑은 DFS로 바로 판별 가능하다.

그러면 r 근처의 위치 관계를 잘 확인하는 것이 중요할 것이다.
r과의 거리가 1인지 2인지를 판별하는 것이 매우매우 중요하다.
이를 위해, 나는 r과의 거리가 1인 점을 하나 찾아냈다. 그 방법에 대해 일단 설명한다.


먼저, r에서 거리 2 이하인 점(즉 입력으로 주어지는 그래프에서 r과 연결된 점)의 집합을 S라고 하자. (r 포함)
S - {r}의 각 정점 v에 대해, 주어진 그래프에서 연결된 인접 정점 중 S에 속하는 정점의 갯수를 세어 이를 각각 c[v]라고 하자.

c[v]가 최대인 v는 대부분의 경우 r과 직접 인접한 점이다. (즉 r과의 거리가 1)
왜냐하면, 깊이 2인 점에서는 자신의 서브트리 쪽 정점만 갈 수 있는데,
그 트리의 깊이 1인 노드(r의 자식)은 거기에 r의 다른 자식들까지도 갈 수 있기 때문이다.
단, r의 자식이 한 개라면 깊이 1이나 2나 같은 값을 가지게 되어 이 가정이 깨지는데, 이는 예외 케이스로 후술하기로 한다.
일단 c[v]가 최대인 v를 잡았고, 이것이 r과의 거리가 1이라고 하자.


이제 r의 직계 자손을 찾았다.
이때, v와 r 모두에서 갈 수 있는 정점들은 다음의 세 가지이다. 그림을 그려서 생각해보자.
1. v의 자식
2. r의 자식 중 leaf인 경우(즉 그 밑에 다른 자식이 없는 경우)
3. r의 자식 중 non-leaf인 경우, 즉 자식이 있는 경우

이 정점들의 집합을 E라고 하겠다.
이것저것 시도하다 보면, 1번과 2번 중 어느 쪽에 속하는지를 구분하기가 어렵고, 또 핵심적이다.
어느 게 어느 쪽인지를 결정하고 나면, 앞에서 말했듯이 그 아래쪽은 DFS로 처리 가능하다.


먼저, 3번 case에 해당하는 정점이 하나라도 있는지는 쉽게 판별 가능하다.
S의 점 중 v와 (입력 그래프에서) 연결되어 있지 않은 점이 있다면, 바로 3번 정점의 자식이다.
그러면, 그 점과 (입력 그래프에서) 연결된 점 중 E에 속하는 것을 찾으면 단 하나가 나올 것이며,
그는 3번 정점에 해당하는 점일 것이다.

3번 경우에 해당하는 점들에 대해서는, 그 아래쪽 서브트리를 모두 DFS로 바로 구할 수 있다.
또한, 1번과 2번 경우도 구분이 모두 되는데, 3번 정점과 (입력 그래프에서) 연결된 점이 2번, 아니면 1번 경우이다.
즉 E에 속하는 모든 정점이 어떤 위치 관계에 놓여 있는지를 모두 확정 가능하고, DFS로 트리를 구축한 뒤 답을 검증하면 된다.


즉 3번 case에 해당하는 점이 하나라도 있다면 1번과 2번이 구별이 되는데, 없다면 또다시 고민이다.
여기서, 1번 정점끼리와 2번 정점끼리는 서로 이어져 있으며, 1번과 2번은 서로 분리되어 있음에 주목했다.
즉 E에 속하는 점들을 서로 연결된 점들끼리 묶을 수 있다.
생각하기 편하게, 두 덩어리가 있다고 하면 하나는 1번, 하나는 2번 경우일 것이다.

그럼 둘중 하나는 v, 하나는 r에 매달면 되는 것일까? 아쉽게도 그렇게 쉽게 끝나지는 않는다.
왜냐하면, 1번 경우의 정점은 자식을 더 가지고 있어도 되고, 2번은 그러면 안 되기 때문이다.
그런데 자식이 있는지 없는지를 알 수가 있나? 주어진 그래프에서 바로 알 수 있는 것은 아닌데?

한 쪽 덩어리를 r에 매달 수 있다면, 나머지는 무조건 v에 달아도 될 것이다. (자식이 있어도 ok, 없어도 ok니까)
r에 매달 수 있는가, 즉 모두 자식이 없도록 r과 연결할 수 있는가?
그 경우, 그 덩어리의 정점 수가 k라면, 그 덩어리의 모든 점들은 주어진 그래프에서 (k+1)개의 간선을 가질 것이다.
같은 덩어리에 속하는 (k-1)개의 점, v, 그리고 r과 연결되어 있으므로.
따라서 이 조건을 만족하는지를 확인해주고, 구분해서 덩어리를 양쪽에 붙인 후 DFS로 트리를 구축한 뒤 답을 검증하면 된다.


답을 검증하는 것은 실제로 모든 거리 2 이하의 정점쌍들을 모두 보면서 입력으로 주어진 것과 일치하는지 확인하면 된다.
모순이 있다면 많아야 주어진 그래프의 E (≤ 1,000,000) 번 돌고 나면 비둘기집의 원리에 의해 모순이 나올 것이기 때문에, TLE는 걱정할 필요가 없다.


생각하지 않은 예외 케이스는, r이 자식을 한 개만 가질 때이다.
그러지 않도록 r을 잘 잡아야 한다는 소리이다.

주어진 그래프에서 degree가 가장 큰 것을 r로 잡으면 어떨까? (←제안받음)
만약 그런데도 r이 자식이 한 개라면, 그 자식으로 움직이면 대부분의 경우
(거리 2 이하로 갈 수 있는 점의 수)가 더 많아지므로 모순이 생길 것이다.

즉 대부분의 경우에는 저렇게 r을 잡으면 자식의 수가 2개 이상이고,
(1-대부분)의 경우는 바로 성게 모양 그래프인데, 이 경우는 입력으로 주어지는 그래프가 완전그래프이며,
루트를 무엇으로 잡고 v를 무엇으로 잡아서 처리하더라도 맞는 그래프가 되므로 문제 없다.



v를 찾는 아이디어(max{ c[v] }), 그리고 1번과 2번 경우를 분류하는 아이디어
이 두 가지가 중요했던 것 같다.
전자는 정말 일찍 갑자기 떠올랐고, 후자는 토론하면서 정립해 나갔다.

케이스 나누기에서의 자잘한 실수들을 하나씩 고쳤다.
눈으로 찾지 못한 DFS 루틴의 치명적인 오류는 DM을 코딩해서 찾았다.
평소에 알고리즘이 틀린 것 같으면 곧잘 파이썬으로 DM을 짜곤 했기 때문에 그 습관이 큰 도움이 되었다.
약 20분 정도 남았을 때 DM을 짜기 시작해서, 틀린 데이터를 찾고, 오류를 찾고, 고쳐서 제출했다.


.......


그렇게 짜낸 5번째 제출이 294분에 AC를 받았고
789 팀은 I번을 푼 유일한 팀이자, 그 덕분에 유일한 11솔브 팀이 되면서
2018 ICPC 서울 리저널 우승을 거머쥐었고, 동시에 2019년 봄 포르투갈에서 개최되는 ICPC 월드 파이널에 참가하는 행운을 얻었다.


아직 실감이 잘 안 난다. 너무나 큰 행운이 찾아온 것 같아 그저 감사할 따름이다. 열심히 해야겠다.



'알고리즘 문제풀기 > 대회 참가기' 카테고리의 다른 글

ICPC Seoul Regional 2018  (4) 2018.11.04
UCPC 2018 후기  (0) 2018.07.30
NYPC 1회 후기  (1) 2016.10.29
Codeforces(618): Wunder Fund Round 2016 후기  (2) 2016.01.30
Codeforces(500): Good Bye 2014 후기  (0) 2014.12.31
  1. md 2018.11.05 13:47 신고

    넘모 멋있어요~~~
    같이 식사해주셔서 영광이에요 ㅎㅎㅎㅎ

  2. ingyu 2018.11.05 14:07 신고

    ♥♡♥♡♥♡♥♡♥♡

  3. Who 2018.11.07 13:58 신고

    너무 멋져요~~

  4. 잉여인간_ 2018.11.09 10:15 신고

    멋져요~~

Ubuntu 16.04 상에서 세팅하는 과정이다.

DB 및 AWS를 운영하는 메인 서버 한 대와, 하위 서버 여러 대로 이루어진 구성이다.
일반적으로는 워커(Worker)를 담당할 채점기 컴퓨터를 따로 두는 편이다. 각각의 채점기 컴퓨터에서는 워커 서비스를 세 개 정도(코어 갯수 - 1) 켜서 사용한다.

또, 참가자(contestant)가 굉장히 많은 경우, 참가자에게 홈페이지를 그려주는 contest web server(CWS) 서버 역시 분리할 필요가 생기기도 한다.
그 경우에도 마찬가지로 CWS를 담당하는 컴퓨터를 따로 둔다.

또, 랭킹을 표시하는 ranking web server(RWS)를 따로, 그리고 여러 개 둘 필요가 생기기도 한다. 채점 및 점수 매기기가 완료될 때마다 모든 RWS 쪽으로 채점 결과를 전송하게 된다.

이외의 서비스, 즉 Postgres DB 서버를 운영하고, 관리자용 admin web server(AWS)를 운영하고, 채점 및 점수 매기는 과정(evaluation service, scoring service)을 총괄하고, 로그를 남기고, 프린팅 등을 처리하는 모든 과정은 하나의 컴퓨터에서 처리할 만 하다.


1.

모든 컴퓨터에서, 필요한 패키지를 설치한다.

sudo apt-get install build-essential openjdk-8-jre openjdk-8-jdk fpc \
    postgresql postgresql-client gettext python2.7 \
    iso-codes shared-mime-info stl-manual cgroup-lite libcap-dev

sudo apt-get install python-dev libpq-dev libcups2-dev libyaml-dev \
libffi-dev python-pip


2.

모든 컴퓨터에서, CMS를 가져오고 prerequisites의 설치를 진행한다.

myungwoo/cms를 가져온다고 하면

<메인 서버>

git clone --single-branch -b koi-cms --recursive https://github.com/myungwoo/cms
cd cms
sudo ./prerequisites.py install

그리고 여전히 메인 서버에서, 모든 하위 서버들의 IP에 대해서 scp로 CMS 폴더를 통째로 보내준다. (git clone보다 빠르기 때문에)

scp ../cms $ip:~/cms -r

이제 각각의 하위 서버에서도 설치를 실행해준다.

<하위 서버>

cd cms
sudo ./prerequisites.py install


3.

모든 서버에서, 파이썬 virtual env를 만들고 CMS의 install을 진행한다.

virtualenv -p python2 ~/venv
source ~/venv/bin/activate
pip install -r requirements.txt
python setup.py install


4.

메인 서버에서, postgres DB를 세팅한다.

<메인 서버>

sudo su - postgres
createuser --username=postgres --pwprompt cmsuser

위의 커맨드에서, DB 접속 비밀번호를 입력한다.

<메인 서버>

createdb --username=postgres --owner=cmsuser cmsdb
psql --username=postgres --dbname=cmsdb --command='ALTER SCHEMA public OWNER TO cmsuser'
psql --username=postgres --dbname=cmsdb --command='GRANT SELECT ON pg_largeobject TO cmsuser'
cmsInitDB

또, Worker나 CWS 등이 이 Postgres에 접속할 수 있어야 하기 때문에, postgres 설정을 바꿔주어야 한다.

<메인 서버>

sudo vim /etc/postgresql/9.5/main/postgresql.conf

59번줄?에, listen_addresses = '127.0.0.1,192.168.0.x'와 같은 부분을, 하위 서버들의 IP 주소로 채운다.
또 HBA 관련 설정을 채워야 한다.

sudo vim /etc/postgresql/9.5/main/pg_hba.conf

모든 하위 서버에 대해서, host cmsdb cmsuser <하위 서버의 IP 주소>/32 md5 와 같은 식으로 한 줄씩 추가해준다.


5.

모든 서버에서, 설정 파일을 수정한다. 이 역시 메인 서버에서 수정하고 그를 scp로 deploy 하는게 편하다.

<메인 서버>

cp config/cms.conf.sample config/cms.conf
vim cms.conf

세팅해야 할 것

5-1. 20-32번줄의 각 서비스의 IP 주소를 설정한다.
Worker(, 그리고 CWS도 분리한다면 CWS)를 제외한 모든 서비스의 IP 주소는 메인 서버의 IP 주소로 설정한다.
포트는 대부분 그대로 쓰되, 한 컴퓨터에서 워커를 여러 대 켜는 경우 각 워커의 포트는 다르게 설정한다.

5-2. DB 접속 스트링 (45번줄)
"database": "postgresql+psycopg2://cmsuser:your_password_here@localhost/cmsdb 라고 되어 있는데,
"database": "postgresql+psycopg2://cmsuser:<4번에서 설정한 비밀번호>@<메인 서버의 IP주소>/cmsdb 가 되도록 바꾼다.

5-3. 81번줄 secret_key
랜덤한 16 bytes hexademical 스트링(즉, 32글자)으로 바꿔 주어야 한다.
다음 커맨드의 결과를 붙여넣자:
python -c "import random;print('%032x'%random.randrange(1<<128))"

5-#. 145번줄 rankings
RWS를 쓸 경우에만 설정한다.
"rankings": ["http://usern4me:passw0rd@localhost:8890/"]
RWS를 호스팅할 서버 주소와 포트를 넣고, 랭킹 서비스에서만 쓸 ID와 비밀번호로 채운다.
이 아이디와 비밀번호는, 대회 서버가 랭킹 서버에게 채점 결과를 전송하는 과정에서의 보안을 담당한다.
여기서, 만약 RWS 앞에 nginx를 놓을 계획이라고 하더라도, 여기에는 백엔드 역할의 서버의 주소와 포트를 넣어야 한다.

5-#. cms.ranking.conf

RWS를 쓸 경우에만 설정한다.

위에서 설정한 랭킹 서비스 전용 아이디와 비밀번호를 채워 넣는다.



수정을 마쳤으면 scp로 각 유저의 ~/cms/config/ 안에 복사해주고,

※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※
※ cms.conf 등을 수정하고 나면, 꼭 다음 커맨드를 써야 반영된다!!!
※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※

sudo ./prerequisites.py install


6.
관리자 계정을 만들고, AWS를 켜서 로그인한다.

관리자 계정에 로그인 할 수 있으면 절대 안 된다는 생각으로, 아이디와 비밀번호를 꼭 정성들여서 만들도록 하자.

<메인 컴퓨터>

cmsAddAdmin -p <패스워드> <아이디>
cmsAdminWebServer 0

AWS에서 컨테스트를 만들어주어야 한다. 그래야 cmsResourceService를 켤 수 있다.


7.
모든 컴퓨터에서 cmsResourceService를 켠다.
Resource Service만 켜면, 그 아이가 각자의 컴퓨터에서 켜야 하는 서비스를 모두 켜 줄 것이다.

cmsResourceService -a <컨테스트 번호>

이제 모든 setup이 끝났다.



번외 1.

nginx 프론트엔드를 세우려면, 먼저 nginx를 설치한다.
그리고 /etc/nginx/sites-enabled/default 의 내용을 싹 지우고, 채워준다.

HTTP 서버만 세우는 건 간단하다.
nginx 설정을 아래와 같이 해준다.

upstream cws {
    ip_hash;
    keepalive 500;
    server :<포트(보통 8888)>;
    server :<포트(보통 8888)>;
# ...
}
upstream aws {
    keepalive 5;
    server :<포트(보통 8889)>;
}
# rws를 안 쓰면 아래 줄은 필요 없다.
upstream rws {
    keepalive 500;
    server :<포트(보통 8890)>;
    server :<포트(보통 8890)>;
# ...
}
server {
    listen 80 default_server;
    server_name <서버 주소>; # cms.asdfzxcv.com, ioi, 혹은 192.168.0.200 등
    location ^~ /aws/ {
        proxy_pass http://aws/;
        include proxy_params;

        proxy_redirect http://$host/ /aws/;
        proxy_redirect https://$host/ /aws/;
        proxy_http_version 1.1;
        proxy_set_header Connection "";
        client_max_body_size 100M;
    }
# rws를 안 쓰면 아래 줄은 필요 없다.
location ^~ /rws/ { proxy_pass http://rws/; include proxy_params; proxy_redirect http://$host/ /rws/; proxy_redirect https://$host/ /rws/; proxy_http_version 1.1; proxy_set_header Connection ""; proxy_buffering off; } location / { proxy_pass http://cws/; include proxy_params; proxy_http_version 1.1; proxy_set_header Connection ""; client_max_body_size 50M; } }


그리고 cms.conf 에서 num_proxies 를 찾아서 1로 만들어주어야 하고,

그 다음에는 또다시 sudo ./prerequisites.py install 을 돌려주어야 한다!!!!

꼭 까먹지 말자.



그리고 방화벽을 세운다.

sudo ufw allow 80
sudo ufw allow 5432
sudo ufw enable

HTTPS를 사용하고 싶다면, 80번을 443번으로 넘겨주는 server{}를 하나 만들고, self-signed certificate를 지정해준 후,
모든 참가자(contestant) 컴퓨터에 해당 CA를 신뢰할 수 있는 인증서로 배포해야 한다.


번외 2. 각종 커맨드 목록

cmsAddAdmin [-p PASSWORD] username
cmsAddParticipation [-c CONTEST_ID] [-i IP] [-d DELAY_TIME] [-e EXTRA_TIME] [-t TEAM] [--hidden] [--unrestricted] [-p PLAINTEXT_PASSWORD | -H HASHED_PASSWORD] [--bcrypt] uesrname
cmsAddUser [-t TIMEZONE] [-l LANGUAGES: comma-separated] [-p PLAINTEXT_PASSWORD | -H HASHED_PASSWORD] [--bcrypt] first_name last_name username
cmsRemoveContest [-c CONTEST_ID]
cmsRemoveParticipation [-c CONTEST_ID] username
cmsRemoveSubmissions [-c CONTEST_ID] [-u USERNAME] [-t TASK_NAME] [-s SUBMISSION_ID]
cmsRemoveTask task_name
cmsRemoveUser username


번외 3. 컴퓨터 환경 세팅

# 유저 추가하기

useradd=저수준이라고 까임
adduser 를 쓰자!

adduser [--home DIR] [--shell SHELL] [--no-create-home] user


# IP 칠 필요 없게 만들기

/etc/hosts에 IP주소와 대명사를 순서대로  한 줄에 띄어쓰기로 구분해서 써주면 된다.
127.0.0.1 대신 localhost를 쓸 수 있는 것도 이 파일 덕분이라고 생각하면 된다.


# 브라우저 홈 페이지 설정

Firefox 홈 페이지 설정 (모든 Firefox를 종료시킨 후에 하자!)

/usr/lib/firefox/mozilla.cfg 에 다음 내용: (첫 줄에 //가 꼭 필요하단다)

//
defaultPref("browser.startup.homepage", "data:text/plain,browser.startup.homepage=http://ioi")
pref("browser.startup.homepage", "http://ioi")

/usr/lib/firefox/defaults/pref/local-settings.js 에 다음 내용:

pref("general.config.obscure_value", 0);
pref("general.config.filename", "mozilla.cfg");

obscure value를 설정하지 않거나 디폴트 값 13으로 두면, mozilla.cfg를 ROT13 해서 읽으려고 하기 때문에 꼭 써주어야 한다.


Chrome 홈 페이지 설정

/opt/google/chrome/master_preferences 에 다음 내용:

{
"homepage": "http://ioi",
"homepage_is_newtabpage": false,
"browser": {
"show_home_button": true
},
"session": {
"restore_on_startup": 4,
"startup_urls": [
"http://ioi"
]
},
"bookmark_bar": {
"show_on_all_tabs": true
},
"sync_promo": {
"show_on_first_run_allowed": false
},
"distribution": {
"import_bookmarks": false,
"import_history": false,
"import_home_page": false,
"import_search_engine": false,
"ping_delay": 60,
"suppress_first_run_bubble": true,
"do_not_create_desktop_shortcut": true,
"do_not_create_quick_launch_shortcut": true,
"do_not_launch_chrome": true,
"do_not_register_for_update_launch": true,
"make_chrome_default": false,
"make_chrome_default_for_user": false,
"suppress_first_run_default_browser_prompt": true,
"system_level": true,
"verbose_logging": true
},
"first_run_tabs": [
"http://ioi"
]
}


얏호

'알고리즘 문제풀기 > 기타' 카테고리의 다른 글

CMS 세팅 (워커 등 분리)  (0) 2018.08.02
Code::Blocks에서의 편한 설정  (0) 2016.01.13

<남남서와 찌끄레기들> 팀으로 참가해, 12문제 중 10문제를 풀고 전체 4등의 결과를 얻었다. 팀 연습을 안 해봤어서 걱정했는데 좋은 결과가 나와서 다행이었다.

대회 준비에 부족한 부분이 있긴 했지만 내가 준비해도 저런 문제가 안 생겼을 거라고는 장담 못 할 것 같다... 주최 분들이 정말 수고하신게 보였다.

내가 푼 문제는 E, K, I였다. 각각 내 풀이를 써본다.


E

배열을 one-based로 사용해 min-heap을 만든다. ($i$번째 노드의 부모가 $\lfloor i/2 \rfloor$가 되는 식으로)
이 때, $1$부터 $N$까지의 수를 어떤 특정 순서로 힙에 삽입해서,
모든 작업이 끝났을 때 $p$번째 위치에 $k$가 적혀 있도록 하는 방법을 아무거나 하나 출력하는 문제이다.

처음에는 방법의 수를 세는 것으로 잘못 읽고는 엄청 어려운 문제라고 생각하고 넘겼는데,
사람들이 많이 풀길래... 현수에게 설명해주면서 보니까 방법을 아무거나 하나 출력하는 문제였고, 그러면 어렵지 않아 보였다.
초반 스퍼트가 끝나가는 타이밍이기도 했고, 급한 마음에 두 번 실수를 거친 끝에 맞았다.


$p$번째 위치 밑($p$번째 위치의 subtree)에는 모두 $k$보다 큰 수가 있어야 하며,
$p$번째 위치 위($p$번째 위치의 조상들)에는 모두 $k$보다 작은 수가 있어야 한다.
양쪽 다 갯수가 맞으면(그만큼 채울 수 있다면) 그런 숫자들로 적당히 채우면 된다.

E 코드 (열기)


K

자연수 $n$과 $m$, 그리고 자연수 수열 $A_i$가 주어졌을 때, 다음 식을 만족하는 자연수 수열 $B_i$를 구하는 문제이다.

$$1+\frac{2^m-1}{n}=\frac{(A_1+B_1)(A_2+B_2)\dots (A_m+B_m)}{B_1 B_2 \dots B_m}$$

너무 하드한 수학문제 같은 인상이라, 처음에는 별로 안 잡으려고 했다.
11분만에 풀어 퍼스트 솔브를 가져간 더민당 팀도 수학을 잘 하는 분이 계시다고 들어서 그런가보다 했었다.
그런데 생각보다 푸는 팀들이 나오고, 내가 맡던 문제들을 다 팀원들한테 준 상태였기 때문에, 이 문제에 대해서 좀 더 고민을 했었다.


먼저 신경쓰인 건, 우변이 $m$개의 값으로 되어 있는데, 좌변에 $2^m-1$이 있는 것이다.
우변을 정리하면 $\left(1+A_i/B_i\right)$들의 곱이기 때문에, 이 항이 하나하나 붙어나가면서 좌변의 값도 만들어나갈 수 있지 않을까 싶었다.

$$\begin{cases}\displaystyle 1+\frac{2^1-1}{n}=\left(1+\frac{A_1}{B_1}\right)? \\ \displaystyle 1+\frac{2^2-1}{n}=\left(1+\frac{A_1}{B_1}\right)\left(1+\frac{A_2}{B_2}\right)? \\ \vdots \\ \displaystyle 1+\frac{2^m-1}{n}=\left(1+\frac{A_1}{B_1}\right)\left(1+\frac{A_2}{B_2}\right)\left(1+\frac{A_3}{B_3}\right) \cdots \left(1+\frac{A_m}{B_m}\right)?\end{cases}$$

그럼 원하는 대로 되기 위해서는 이렇게 되어야 할 것이다...

$$\frac{\displaystyle 1+\frac{2^i-1}{n}}{\displaystyle 1+\frac{2^{i-1}-1}{n}} = 1+\frac{A_i}{B_i}?$$

그런데 이게 좀처럼 예쁘게 풀리지 않았다. $A_i=2^k$ 꼴일 때만 적당한 $B_i$가 존재하게 된다. 그런데 예제를 보면 그렇지 않더라도 멀쩡히 풀고 있었다.

그래서 새로운 시도를 해 봤다. 좌변을 약간 다르게 바꿔보니까...

$$\frac{\displaystyle 1+\frac{2^i-1}{n}}{\displaystyle 1+\frac{2^{i-1}-1}{n/2}} = 1+\frac{A_i}{B_i}$$

만약 이런 식으로 된다면... $n$을 점차 키워나가며 (만들어나가며) 풀 수 있어 보인다.

$$ \frac{n+2^i-1}{n+2^i-2}=1+\frac{A_i}{B_i} \\ \therefore B_i = (n+2^i-2)A_i $$

식이 엄청 간단하게 나왔다. $B_i = (n+2^i-2)A_i $라면 문제의 조건도 만족한다.

그런데.. $n$이 항상 짝수인 것도 아니고. 홀수면 어떻게 되지?
예제 입력 2를 보았다. $n=10$, $m=3$이며,

$$1+\frac{2^1-1}{3} = \left(1+\frac{1}{3}\right) \\ 1+\frac{2^2-1}{5} = \left(1+\frac{1}{3}\right)\left(1+\frac{1}{5}\right) \\ 1+\frac{2^3-1}{10} = \left(1+\frac{1}{3}\right)\left(1+\frac{1}{5}\right)\left(1+\frac{1}{16}\right)$$

좌변에서 $n$이 5에서 10으로 갈 때는 $n+2^3-2=16$이므로 $\left(1+\frac{1}{16}\right)$을 곱해주는 부분이 우리 생각과 꼭 들어맞는 부분인데, 3에서 5로 가는 부분이... 뭔가 신기하다. 뭐지??

뭔가 그럴듯하게 계산을 해보니

$$\frac{\displaystyle 1+\frac{2^m-1}{2n-1}}{\displaystyle 1+\frac{2^{m-1}-1}{n}} = \frac{n}{2n-1} \frac{\displaystyle 2n-1+2^m-1}{\displaystyle n+2^{m-1}-1} = \frac{n}{2n-1} \frac{\displaystyle 2\left(n+2^{m-1}-1 \right)}{n+2^{m-1}-1}=\frac{2n}{2n-1}=1+\frac{1}{2n-1}$$

!!!!!
이렇게 간단하게 정리되는 것이다.
따라서 $n$이 홀수가 될 때는 $B_i = nA_i$를 잡으면 된다.

즉... $n$이 짝수일 때는 $(n/2) \rightarrow n$으로 온 것으로 생각해 $B_i$를 하나 잡아주면, 항이 하나 줄면서 $n$이 절반이 되고,
$n$이 홀수일 때는 $(n+1)/2 \rightarrow n$으로 온 것으로 생각해 $B_i$를 하나 잡아주면, 항이 하나 줄면서 $n$이 거의 절반이 되므로
대충 해결할 수 있...어 보이고,

$m \leq 50$이므로, $m$이 충분히 크다면야 $n$이 무조건 1로 가겠지만, $m$이 너무 작으면 $n$이 1로 가기 전에 쓸 수 있는 $1+\frac{A_i}{B_i}$ 항이 하나 줄지 않나? 싶을 수 있는데,
$m=1$일 때는 그 때의 $n$에 대해서 $B_i=nA_i$를 잡아주면 무조건 $1+\frac{1}{n}=1+\frac{2^1-1}{n}$이 되므로 그 때만 이렇게 처리해주면 된다.

K 코드 (열기)


I

어떤 규칙에 맞게 $N\times N$ 격자를 0 혹은 1로 채운다. 그 조건은...
$a_{ij} + a_{(i+1)j} + a_{i(j+1)} + a_{(i+1)(j+1)} \equiv c_{ij}\text{ mod 2}$ 를 만족해야 한다. $(1\leq i,j \leq N-1)$
즉 모든 2×2 격자에 대해서, 그 격자의 합 mod 2가 되어야 할 값이 정해져 있는 것이다.

여기에, 특정 위치는 반드시 1이라거나, 특정 위치는 반드시 0이라거나 하는 조건들이 여러 개 들어온다. 그것도 들어왔다가 사라졌다가 한다.
이 때 각 시점마다, 지금 들어와있는 조건을 만족하면서 격자를 채우는 방법이 있는가?를 답하는 문제이다.


일단 저 규칙에 대해 생각해보자.
$i=1\textrm{ or }j=1$인 격자들, 즉 ┌ 모양 테두리 부분의 격자들의 값이 정해지면 안쪽 모든 칸들의 값은 저절로 정해질 것이다.
주어진 규칙에 맞게 채워나가면 되니까.
mod 2의 규칙 때문에, 양변에 항을 더하면
$a_{(i+1)(j+1)} \equiv a_{ij} + a_{(i+1)j} + a_{i(j+1)} + c_{ij}\text{ mod 2}$ 로도 쓸 수 있다.
이 식으로 아직 모르는 값을 채워나갈 수 있는 것이다.

반대로 저 격자들의 값은 "자유 변수"의 느낌이다. 안쪽의 "종속 변수"의 값을 결정하는....
예를 들어 $a_{22} = a_{11} + a_{12} + a_{21} + c_{11}$ 이다.
$a_{33} = a_{11} + a_{31} + a_{13} + c_{22}$ 이다.

뭔가 많이 계산을 해보다 보면, 이런 규칙을 알 수 있다.

$$\large a_{ij} = a_{11} + a_{1j} + a_{i1} + \sum _{x<i \\ y<j} c_{xy} \quad \textrm{ for }i,\: j \geq 2$$

각각의 숫자가 어느 위치의 값들에 합해지는지를 보면 규칙을 증명할 수가 있다.
무슨 말이냐면, 예를 들어 $a_{15}$의 값("자유 변수")이 어느 칸들에 더해지는지 생각해보자.
자기 왼쪽 위의 세 칸을 합해 가져오는 규칙 때문에, $a_{25}$에 더해질 것이고,
그걸 가져온 $a_{35}$에도 더해질 것이고, ... 이렇게 $a_{i5}$에는 모두 더해지지만,
$a_{26}$의 경우에는 $a_{15}$와 $a_{25}$를 둘 다 가져오기 때문에 더해지지 않는다. 즉 $a_{15}$가 더해지는 칸들을 1로 나타내면 이런 모양이다.

$$\begin{array}{lr} \cdots & 0 & 1 & 0 & 0 & \cdots \\ \cdots & 0 & 1 & 0 & 0 & \cdots \\ \cdots & 0 & 1 & 0 & 0 & \cdots \\ \quad & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}$$

이런 식으로 각각의 변수들에 대해서 생각하면 위의 규칙 식을 증명할 수 있다.



그러면 우리가 각 시점에 풀어야 할 문제는, 다음과 같은 식이 여러 개 있을 때 모두 만족하도록 "자유 변수"를 정하는 방법이 있는지의 여부이다.

$$\begin{cases}\displaystyle a_{11} + a_{1j} + a_{i1} + \sum _{x<i \\ y<j} c_{xy} \equiv p \\ \displaystyle a_{i1}=p \\ \displaystyle a_{1j}=p \\ \displaystyle a_{11}=p \end{cases}$$

너무 복잡해 보이는데, 일단 첫 번째 식에서 $\sum _{x<i \\ y<j} c_{xy}$ 부분은 다른 조건이랑도 상관 없고, 처음에 입력받은 테이블에서 계산을 마치기만 하면 그 뒤로는 그냥 상수이기 때문에, 그냥 양변에 미리 더해주고 처음부터 $p$에 포함되는 것으로 생각해도 된다. 다시 정리하면

$$\begin{cases}\displaystyle a_{11} + a_{1j} + a_{i1} \equiv p \\ \displaystyle a_{i1}=p \\ \displaystyle a_{1j}=p \\ \displaystyle a_{11}=p \end{cases}$$

각 행 첫 값인 자유 변수를 $A_i$, 각 열 첫 값인 자유 변수를 $B_j$, (1, 1)의 값을 $f$라고 썼을 때

$$\begin{cases}\displaystyle A_i + B_j + f \equiv p \\ \displaystyle A_i=p \\ \displaystyle B_j=p \\ \displaystyle f=p \end{cases}$$

이 문제를 풀려고 보니, 또 $f$가 방해이다.
$f=0$일 때와 $f=1$일 때 중 어느 한 쪽이라도 조건을 만족하게 값을 채울 수 있다면 그 시점의 답은 1일 것이므로,
그냥 같은 알고리즘을 두 번 수행하기로 하고 $f$에 대한 생각을 지울 수 있다.
혹시 $f$를 강제하는 마지막 조건이 들어온다면, 지금 고려하는 $f$와 다르다면 그 시간에는 무조건 불가능하다고 보면 된다.

이제 다음 문제를 풀면 된다.

$$\begin{cases}\displaystyle A_i + B_j \equiv p \\ \displaystyle A_i=p \\ \displaystyle B_j=p \end{cases}$$

$p$의 값에 따라서 이렇게도 쓸 수 있다.

$$\begin{cases}\displaystyle A_i \equiv B_j \\ \displaystyle A_i \not \equiv B_j \\ \displaystyle A_i=p \\ \displaystyle B_j=p \end{cases}$$


이제, 알고스팟의 EDITORWARS 문제(링크)로 유명한 알고리즘을 생각할 수 있다.
union & find(disjoint set 뭐시기라고도 부른다) 알고리즘에서 한 가지 정보를 더 추가하는데, "자신과 같은 집합이 되어서는 안 되는 아이"이다.
그리고 "A와 B는 같은 집합이다" 연산 외에, "A와 B는 다른 집합이다"라는 연산을 추가하는 것이다.
그럼 놀랍게도 각각의 연산에서 "그것은 모순입니다"가 나올 수도 있게 된다.

그 알고리즘을 쓰면, 위와 같은 조건이 여러 개 있을 때 $A_i$ 및 $B_j$들을 집합 관계로 묶어보고,
거기서 모순이 없다면 조건을 만족하는 채우기가 존재한다는 것으로 볼 수 있으므로 해결 가능하다.
$A_i = p$ 꼴의 조건은... 사실 그 절대적인 값은 혼자만 있을 때는 의미가 없고, $A_i=p$였는데 $B_j=p$라면 $A_i$와 $B_j$가 같은 집합으로 묶여야 한다는 것이 중요하다. 모든 값을 뒤집어도 앞의 두 조건의 참거짓은 변하지 않기 때문에, 서로 같은지 여부, 그 관계만이 중요하다. 때문에 "항상 1"을 나타내는 원소를 하나 더 추가해, 여기에 "같다" 혹은 "다르다" 연산을 적용해서 모순을 따지면 된다.


그런데.. 문제는 여기서 끝나지 않는다. 시간에 따라 들어오고 나가는 조건이 있기 때문이다.
이러고 보니 완전히 풀 수 없는 문제처럼 보였는데, 여기서 조금 더 생각을 발전시키면 할 수 있다.

일단, union & find에서 union을 했던 순서의 역순으로 되돌릴 수 있다는 아이디어가 필요하다.
parent 배열이 매번 갱신되는데, 덮어씌우는 것이 아니라 vector에 push_back을 하는 것이다.
그럼 현재값은 back()이고, 되돌릴 때는 pop_back()을 하면 된다.

두 번째 아이디어는...
시간축 방향으로 세그먼트 트리를 만들어보자.
그럼 각각의 쿼리가 $\log T$개의 노드에 들어갈 것이다.

그리고... 이 세그먼트 트리를 DFS해보자.
각각의 노드에 있는 쿼리를 모두 처리해보고, 모순이 있는지 확인하고...
DFS에서 돌아갈 때는 union & find 결과를 모두 되돌려보자.


이제 문제가 풀렸다.

I 코드 (열기)

시간축 방향으로 세그트리를 만들어서, 작업을 되돌리면서 처리하는 아이디어는 처음 생각해봤고, 그것도 대회 중이었기 때문에, 구현에서 실수를 굉장히 많이 했다.

offline dynamic connectivity로 알려져 있는 아이디어라고 한다. 알려진 아이디어를 스스로 생각해냈다는 점이 많이 뿌듯했다.


'알고리즘 문제풀기 > 대회 참가기' 카테고리의 다른 글

ICPC Seoul Regional 2018  (4) 2018.11.04
UCPC 2018 후기  (0) 2018.07.30
NYPC 1회 후기  (1) 2016.10.29
Codeforces(618): Wunder Fund Round 2016 후기  (2) 2016.01.30
Codeforces(500): Good Bye 2014 후기  (0) 2014.12.31

+ Recent posts

티스토리 툴바