아마 알고리즘 PS(Problem Solving) 분야를 공부하시는 분이라면 한번쯤은 CP(Competitive Programming)에도 참여해보셨을 것입니다. PS가 알려진 알고리즘을 이용해서 프로그래밍 문제를 푸는 것이라고 한다면, CP는 이러한 형태의 문제를 같은 시간대에 여러명이 참여해서 제한시간내에 문제를 풀고 점수를 획득하여 랭킹을 매긴 뒤 Rating을 얻는 방식이라고 할 수 있습니다.

이러한 CP에는 세계적으로 가장 유명한 대학생 대상 프로그래밍 대회인 ACM-ICPC를 비롯하여 온라인에서 자주 이루어지는 Codeforce Contest, AtCoder Contest와 Topcoder Single Round Match 등이 있습니다. 이 외에도 저는 참여해보지 않았지만, Facebook Hacker Cup이나 Hacker Rank같은 것도 비슷한 종류의 대회라고 생각합니다.

어쨋든간 저는 대부분 Codeforce Contest에 참여하곤 했는데 이번에 기회가 되어서 Topcoder SRM에 참여해보려고 했습니다. 인터넷에서 SRM 참여 관련 자료들이 꽤나 있었는데, 옛날 자료이기도 하고 Topcoder 플랫폼 자체가 많이 변해서 자료들과는 조금 다른 점들과 해맨점이 있었습니다.

Codeforce의 경우는 사이트 접속시 직관적인 UI로 쉽게 Contest에 참여할 수 있었는데요 Codeforce의 경우는 알고리즘 문제 해결이 사이트의 주요 목적이다보니 컨테스트 참여와 문제풀이와 같은 UI는 쉽게 익숙해질 수 있었습니다. 하지만 Topcoder의 경우는 SRM 외에도 다양한 많은 기능들을 제공하고 있다 보니 SRM 참여와 SRM 시작 시기를 아는 것이 조금 불편했습니다.

이제 SRM의 참여 방법과 관련된 이야기를 해보려고 합니다.

일단 첫번째로는 Topcoder SRM의 개최 시기를 알아야겠지요? 다음 링크로 이동해봅니다.

https://www.topcoder.com/community/events/

그러면 위와 같은 켈린더를 확인할 수 있는데요, 여기서 하단에 시간대를 보면 "동부 표준시"라는 것을 알 수 있습니다. 이는 구글링 해 보면 
 UTC-05시, 섬머 타임 시에는 UTC-04라는 것을 알 수 있습니다. 한국 표준 시간인 KST의 경우 UTC+09인 것을 감안하면 5+9=14 즉 14시간 정도 차이가 나는 것으로 알 수 있습니다. 즉 구글 캘린더에 나타난 시간에서 14시간을 더해주어야지 한국 시간인 것입니다. 이미지에 나타난 SRM 727의 경우 1월 10일 오후 9시이지만, 한국 시간으로는 1월 11일 오전 11시에 시작했습니다.

이러한 불편함은 다음 링크에 있는 알고스팟 캘린더를 확인하면 간편합니다.

https://algospot.com/calendar/

알고스팟 캘린더의 하단을 보면, 시간 기준이 "서울"로 되어있습니다. 앞에 나와있는 [CF]는 Codeforce의 약자이며, [TC]는 탑코더의 약자입니다. 알고스팟 캘린더는 프로그래밍 콘테스트의 일정이 모여있으므로 훨씬 편리하게 확인할 수 있습니다.

또는 백준저지 캘린더를 확인해도 됩니다. 백준 저지 캘린더에 훨씬 많은 일정들이 빽빽하게 들어있습니다.

https://www.acmicpc.net/calendar

이제 탑코더 사이트로 이동해보도록 하겠습니다.

https://www.topcoder.com

첫 화면 페이지부터 여타 다른 OJ나 CP용 홈페이지와는 조금 다른, 기업용 페이지 같은 모습을 띄고 있습니다. 

일단 화면 중앙의 "I want to join Topcoder" 를 눌러서 회원가입을 했다고 가정하겠습니다.

우측 상단의 Login 버튼을 누르면 중앙에 보이는 것 처럼 두개의 창이 뜨게 됩니다. 이 중 우리의 목적은 SRM을 통한 CP이므로, It's time to compete and win에 맞는 Community log in을 누릅니다.

로그인을 하게 되면 다음과 같은 페이지로 이동하게 되는데, 상단 위젯을 통해서 Competitive Programming을 누릅니다.

그러면 다음과 같은 화면이 나타나게 됩니다. 우측에 나타난 캘린더에서 빨간색으로 표시된 날짜에는 SRM이나 MM(Marathon Match)와 같은 이벤트 등록된 날짜이며, 실제 발생할 시간이 되기 전에는 미리 빨간색으로 나타나지 않는 것으로 보입니다. 따라서 위에서 확인한 구글 캘린더에 있는 아직 시행되지 않은 Round가 보이지 않는다고 해서 불안해 할 필요는 없습니다.

왼쪽부분에는 SRM의 각 Phase 별 시작 시간과 종료 시간에 대해서 설명이 되어 있습니다. 

SRM 라운드 스케쥴과 관련된 설명은 다음 링크에 있습니다.

https://www.topcoder.com/member-onboarding/competing-in-an-algorithm-match-srm/

SRM 등록의 경우 SRM 시작 3시간 전 부터 시작 5분 전까지 가능하다고 쓰여있지만 최근에는 4시간 전 부터 가능한 경우가 많다고 합니다.

다른 포스팅들을 보면 java로 작성된 클라이언트를 다운로드해서 참여해야한다고 나와있지만, 최근에는 업데이트가 되었는지 별도의 프로그램 설치 없이 웹 인터페이스만으로도 대회 참여가 가능합니다. 온라인에서 컴파일 및 TestCase 실행을 해 볼 수 있지만, 반응이 좀 느리고 서버가 약간 불안정했습니다.

대회가 끝나면 다음 링크에 풀이인 Editorial이 올라오는 것으로 보이며, 비공식적으로 코드포스 블로그에 올라오는 경우도 있는것으로 보입니다.

https://www.topcoder.com/community/data-science/data-science-editorials/

혹시 최근에 탑코더 SRM에 입문하실 의향이 있는 분들이 있다면 제 글을 보고 도움이 되기를 바랍니다.

* Topcoder SRM 관련해서 더 읽어볼만한 글들

https://www.acmicpc.net/blog/view/2

https://algospot.com/wiki/read/TopCoder_%ED%8A%9C%ED%86%A0%EB%A6%AC%EC%96%BC

https://www.acmicpc.net/problem/11279

백준저지 11279번 최대 힙 문제입니다.

파이썬이나 C++ STL에서 제공해주는 heap, priority_queue 자료구조를 사용하면 간단하게 풀 수 있지만, 최대힙을 직접 구현하면서 해당 자료구조에 대하여 한번 공부해도록 하겠습니다.

힙이라는 자료구조는 일단 ADT(Abstract Data Type)이기 때문에 직접적으로 메모리상에 어떠한 구조로 나열되든간에, 설계된 대로만 동작하면 맞습니다.

Complete Binary Tree라는 자료구조 특성상 일반 트리 처럼 포인터로 구현을 하기 보다는 배열로 구현하는 것이 편합니다.

저도 이번에 배열로 구현을 할 예정이며 C++ STL에서 제공하는 vector 컨테이너를 사용하겠습니다.

배열로 구현한 Binary Tree는 각 노드 번호 i에 대하여 Left child는 i*2, Right child는 i*2+1의 번호를 갖습니다. 그러기 위해서는 루트노드의 번호를 1부터 새야 하므로 data[0]에는 더미노드를 하나 넣어서 1부터 새도록 구현했습니다.

최대 힙은 두개의 연산을 제공하는데, 새로운 데이터를 넣는 연산과, 힙에서 최대값을 빼내는 연산입니다.

최대 힙의 구조상 부모 노드는 항상 자식 노드보다 값이 크므로, 힙에서 값을 빼내는 연산은 항상 루트 노드의 값을 빼내게 됩니다.

각각의 연산을 push와 pop이라고 명명하겠습니다.

push 연산은 다음과 같은 절차로 이루어집니다.

1. Complete binary tree가 되도록, 마지막 위치에 넣는 값을 집어넣습니다.

2.  직속 부모 노드와 값을 비교하여 자신의 값이 직속 부모 노드 보다 값이 작을 때 까지 부모 노드와 위치를 바꿉니다.

pop 연산은 다음과 같은 절차로 이루어집니다.

1. 리턴할 루트 노드의 값을 따로 빼놓습니다. 그리고 가장 마지막 노드의 값을 루트 노드의 위치로 이동시킵니다.

2. 이동된 노드가 자신의 양쪽 자식 노드와 비교해서 둘 중에 자신보다 큰 값을 가진 노드가 있다면 그 중 가장 큰 노드를 자신의 위치와 바꿉니다. 자신이 모든 직속 자식들보다 값이 클 때 까지 반복합니다.

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MAX_SIZE 100001

class max_heap {
	private:
	vector<int> data;
	public:
	
	max_heap() {
		this->data.push_back(-1); // index 0 means dummy data
	}
	max_heap(int size) {
		this->data.reserve(size);
		this->data.push_back(-1); //index 0 is dummy data
	}
	int pop() {
		if (this->data.size() <= 1) {
			//heap is empty
			return 0;
		}
		int current = 1;
		int left_child = 2;
		int right_child = 3;
		int ret = this->data[current];
		int last = this->data.size() - 1;
		
		swap(this->data[current], this->data[last]);
		this->data.pop_back();
		while (this->data.size() > left_child) { //when left child exist
			int larger_index = left_child;
			if (this->data.size() > right_child) { //when right child exist
				if (this->data[right_child] > this->data[left_child]) {
					larger_index = right_child;
				}
			}
			if (this->data[larger_index] > this->data[current]) {
				swap(this->data[current], this->data[larger_index]);
				current = larger_index;
				left_child = current * 2;
				right_child = left_child + 1;
			} else {
				break;
			}
		}
		return ret;
		
	}
	bool push(int val) {
		this->data.push_back(val);
		int current = data.size() - 1;
		int parent = current/2;
		while (parent > 0 && this->data[current] > this->data[parent]) {
			swap(this->data[current], this->data[parent]);
			current = parent;
			parent = current/2;
		}
	}
};


int main() {
	max_heap heap(MAX_SIZE);
	int n;
	cin >> n;
	for (int i=0; i < n; i++) {
		int tmp;
		cin >> tmp;
		if (tmp > 0) {
			heap.push(tmp);
		} else {
			cout << heap.pop() << endl;
		}
	}
	return 0;
}

https://www.acmicpc.net/problem/1002

백준저지 1002번 터렛 문제이다.

어떤 지점에서 길이가 같은 점들의 집합이 원이므로, 원 두개를 그린 뒤 그 두개의 원의 교점의 개수를 리턴하면 된다.

이는 두 원의 반지름과, 두 원의 중점 사이의 거리와의 관계를 따져서 값을 출력하면 된다.

두 원의 반지름을 r1, r2 (r1 <= r2)이라고 하고, 중점 사이의 거리를 d라고 하자.

소스코드에서는 floating point의 부정확함을 고려하여서 실제 나타난 거리의 제곱수인 정수를 이용하여 비교를 하였다. 따라서 sqrt(Square root)와 같은 함수는 따로 사용할 필요가 없다.

다음 케이스들을 고려해주면 된다.

1. 원이 두 점에서 만나는 경우

r2 - r1 < d < r1 + r2

2. 두 원이 외접하는 경우 (한점에서 만난다)

d = r1 + r2

3. 두 원이 내접하는 경우 (한점에서 만난다)

d = r2 - r1

and

d != 0

4. 하나의 원이 다른 원을 포함하는 경우 (만나지 않는다)

d < r2 - r1

5. 두 원이 멀리 떨어져 만나지 않는 경우

d > r1 + r2

6. 두 원이 일치하는 경우 (무수히 많은 점에서 만난다)

d = 0

r1 = r2

 

#include <iostream>

using namespace std;

typedef long long ll;

int main() {
    int t;
    cin >> t;
    while(t--) {
        ll x1, y1, r1, x2, y2, r2;
        cin >> x1 >> y1 >> r1 >>x2 >>y2 >> r2;
        ll dx = x1-x2;
        ll dy = y1-y2;

        if (r1 > r2) swap(r1, r2);
        ll add = r1 + r2;
        add = add * add;
        ll sub = r2 - r1;
        sub = sub * sub;
        ll d = dx*dx + dy*dy;
        
        if (d < add && d > sub) {
            cout << 2;
        } else if (d == add || (d == sub && d != 0) ) {
            cout << 1;
        } else if (d < sub || d > add) {
            cout << 0;
        } else if (d ==0) {
            if (r1 == r2)
                cout << -1;
            else
                cout << 0;
        }
        cout << '\n';
    }
    return 0;
    
}

팰린드롬인 부분수열 개수 구하기(Counting All Palindromic Subsequences) 알고리즘에 대하여 포스팅을 해 보도록 하겠습니다.

일단 각각의 정의에 대해서 한번 설명을 간단하게 해 보겠습니다.

팰린드롬(Palindrome)은 앞에서부터 읽으나, 뒤에서부터 읽으나 같은 내용인 단어를 뜻합니다. 예를들어 '토마토'라던지 '바밤바', 'level', 'racecar' 등등이 있겠죠.

부분수열(Subsequence)은 원래 수열이나 배열에서 순서는 그대로 두고 일부 원소를 제거한 수열을 뜻합니다. 예를들어 abcdefg 라는 수열(Sequence)가 있다고 할 떄 abc와 bcd 와 같은 녀석들도 부분수열이 되지만, adg와 같은 녀석도 부분수열이 됩니다. 하지만 순서가 바뀌는 cba 같은 녀석은 부분 수열이 안됩니다.

그러면 이제 어떠한 문자열(String)에 대하여 팰린드롬인 부분수열(Palindromic subsequence)의 개수를 세 보도록 하겠습니다. 

일단은 부분수열이 중복이라도, 위치가 다르면 다른 것으로 세는 경우부터 따져보도록 하겠습니다.

즉, 예시로 'aab'의 팰린드롬 부분수열은 { 'a', 'a', 'b', 'aa' }가 되며, 'a'가 2개이지만 문자열의 첫번째 원소와 두번째 원소로 각각 샌 경우입니다.

일단 이 문제에 대해서 풀이법을 스스로 한번 생각해보는 것을 추천한다고 합니다.

다음 GeeksforGeeks 포탈에서 문제를 한번 풀어볼 수 있습니다. 로그인이 필요하긴 합니다만 별도의 개발환경 설정 없이 문제를 풀어볼 수 있습니다.

http://practice.geeksforgeeks.org/problems/count-palindromic-subsequences/1

이 문제 답안의 특징을 살펴보면, 일단 길이가 1인 문자열에 대해서는 팰린드롬 부분수열이 무조건 1개입니다. 그 보다 긴 경우를 고려를 해야 하는데 부분문제로 나누어서 풀이할 수 있습니다. 즉 다이나믹 프로그래밍으로 해결을 할 수 있지요. 아래와 같은 recurrence가 나타납니다.

classic dynamic programming problem, which can be solved using the following recurrence:

• Let $P(L, R)$ be the number of palindromic subsequences in $S[L...R]$, then
• $P(L, R) = \begin{cases} 1 &\text{if } L = R \\P(L + 1, R) + P(L, R - 1) - P(L +1, R - 1) &\text{if } S(L) \neq S(R) \\ P(L + 1, R) + P(L, R - 1) + 1 &\text{if } S(L) = S(R)\end{cases}$

< 출처: csacademy.com >

P(L,R)은 부분문자열 S[L...R]에서 나타나는 팰린드롬 부분수열이고, L과 R은 부분문자열의 시작과 끝 인덱스 번호입니다. L=R인 경우는 길이가 1인 부분 문자열입니다.

S(L) != S(R)인 경우는 왼쪽에서 범위가 1만큼 줄어든 P(L+1, R)과 오른쪽에서 범위가 1만큼 줄어든 P(L, R-1)의 개수를 더한 뒤, 중복으로 더해진 P(L+1, R-1)를 빼 줍니다. P(L+1, R)와 P(L, R-1) 둘 다 P(L+1, R-1)의 범위에서 나타난 정답값을 중복으로 포함하기 때문에 빼 준 것이죠.

S(L) = S(R)의 경우에는 위 경우와 달리 중복으로 더해준 P(L+1, R-1)을 빼지 않고 또 1을 더해줍니다. 

 { P(L+1, R-1)에 해당하는  개수 } = { P(L+1, R-1) 부분수열의 양 끝에 S(L)과 S(R)을 붙인 새로운 팰린드롬 부분수열 개수 }

이기 때문이죠. 그리고 추가적으로 1을 더한 값은 S(L)과 S(R)로만 이루어진 길이가 2인 부분수열의 개수입니다.

이렇게 재귀적인 방법으로 문제를 풀 수 있으며, 재귀 트리를 그려보면 겹치는 부분문제들이 있으므로 이를 메모이제이션(memoization)한 다이나믹 프로그래밍을 이용하여 효율적으로 문제를 해결할 수 있습니다.

Top-Down 방식으로 작성한 DP 솔루션 코드입니다.

 
/*
Please note that it's Function problem i.e.
you need to write your solution in the form of Function(s) only.
Driver Code to call/invoke your function would be added by GfG's Online Judge.*/
int** cps;

int get(int start, int end, string& str);
/*You are required to complete below method */
int countPS(string str)
{
    int ans;
    int len = str.length();
    cps = (int**) calloc(sizeof(int*) , (len+1));
    for (int i=0; i < len+1; i++) {
        cps[i] = (int*) calloc(sizeof(int), (len+1));
    }
    
    
    ans = get(0, len-1, str);
    //free allocated memory
    for(int i=0; i <len+1; i++) {
        free(cps[i]);
    }
    free(cps);
    return ans;
   //Your code here
}

int get(int start, int end, string& str) {
    if (start > end) return 0;
    if (start == end) return 1;
    if (cps[start][end]) return cps[start][end];
    
    if (str[start] == str[end]) {
        cps[start][end] = get(start, end-1, str) + get(start+1, end, str) + 1;
    } else {
        cps[start][end] = get(start, end-1, str) + get(start+1, end, str) - get(start+1, end-1, str);
    }
    return cps[start][end];
}
 

그리고 이제 중복을 허용하지 않는 팰린드롬 부분수열의 개수를 세는 경우를 따져보도록 하겠습니다.

앞선  예시에서 'aab'의 팰린드롬 부분수열은 중복을 허용하는 경우{ 'a', 'a', 'b', 'aa' }가 되며, 중복을 허용하지 않는 경우는 { 'a', 'b', 'aa' } 가 됩니다.

중복을 허용하지 않는 경우 중복을 허용하는 경우 보다 조금 더 까다로운데, dynamic programming의 점화식의 인자가 2개에서 3개로 늘어나게 됩니다. 3번째 인자는 가장 바깥에 감싸고 있는 알파뱃을 나타내는 시그마입니다.

• Let $DP(L, R, \sigma)$ be the number of distinct palindromic subsequences in $S[L..R]$ which are bordered with $\sigma$.
• $DP(L, R, \sigma) = \begin{cases} 0 &\text{if } L > R \\ 1 &\text{if } L = R \ \text{and} \ S(L) = \sigma \\DP(L + 1, R, \sigma) + DP(L, R - 1, \sigma) - DP(L +1, R - 1, \sigma) &\text{if } S(L) \neq \sigma \ \text{or} \ S(R) \neq \sigma \\ 2 + \sum_{\theta \in \{a, b, .., z\}} DP(L + 1, R - 1, \theta) &\text{if } S(L) = S(R) = \sigma \end{cases}$

S(L)=S(R)=sigma 의 경우는 DP(L+1, R-1, *)를 모두 더하는데, 원래 있던 각각의 부분수열들의 가장 바깥에 σ 글자로 패딩을 입힌 글자들을 셉니다. 그리고 더해주는 2의 경우는 { 'σ' , 'σσ' }의 경우가 됩니다. 기존의 팰린드롬 문자열들은 σ 패딩을 입혔기 때문에 모두 길이가 3 이상이므로, 중복이 될 일은 없습니다.

그러면 약간 헷갈릴 수 있는 부분이, 글자가 σ가 아닌 길이가 1인 팰린드롬 문자열들의 경우는 어떻게 하냐고 할 수 있는데, 해당 항목들은 DP(L, R, σ)가 아닌 닌 곳에서 세고있기에 상관이 없습니다. 

예를 들어서 'aba' 문자열에 대하여 팰린드롬 부분수열은 다음과 같습니다.

{ a, b, aa, aba }

위 Recurrence를 적용해보면

DP(1, 3, a) = DP(2, 2, *) + 2

DP(2, 2, *) = { b }

입니다. 따라서 DP(2, 2, *)에 a로 패딩을 입힌 새로운 팰린드롬 부분수열 { aba } 과, +2에 해당하는 { a, aa }를 합집합 한 결과인 { a, aa, aba }가 DP(1, 3, a)에 해당되고, { b }는 DP(1, 3, b)에 포함됩니다.

따라서 DP(1,3,a) = { a, aa, aba } 이고 / DP(1,3,b) = { b } 이됩니다. 

따라서 글자가 σ가 아닌 길이가 1인 팰린드롬 문자열들의 경우는 DP(L, R, σ)에서 세고 있지 않기에 위의 의문은 해결이 되었습니다.

제가 해당 솔루션을 보고 이해가 가지 않은 부분들을 고심하면서 해결한 내용을 블로그에 포스팅 해 보았는데, 혹시나 궁금하신점이나 의견있으시면 댓글로 달아주시면 내용에 반영하도록 하겠습니다.

[참고]

http://www.geeksforgeeks.org/count-palindromic-subsequence-given-string/

https://csacademy.com/contest/round-57/task/distinct-palindromes/solution/

때는 몇일 전 이었습니다. 여느때 처럼 코드포스와 백준저지를 들락날락하며 새 문제를 풀거나 새 콘테스트가 열리는지 확인하고, 지난 못 푼 문제들 튜토리얼을 읽고 다시 풀어보고 하던 때였습니다. 모르는 사람에게 코드포스 쪽지가 와 있길래 읽어보니 다음과 같은 내용이었습니다.

새로운 온라인 저지 플랫폼인 CS Academy란 것이 있는데, 매 주 콘테스트 라운드를 연다고 합니다. 그리고 제가 코드포스에서 액티브한 유저라서 해당 사이트로 초대를 한다고 하네요..(머쓱) 아직 실력은 갈 길이 멀지만 열심히 한다고 생각해주니 고마웠습니다. 그리고 코드포스 계정과 연동도 가능하다고 하고, 이번주 토요일에 경기가 있으니 한번 참여해보라는 뭐 그런 내용이었습니다. 그래서 한번 방문해 보았습니다.

https://csacademy.com/

사이트 디자인은 마치 안드로이드 폰 UI와 비슷한 형태였습니다. 깔끔하면서도 만든지 얼마 안 된 것 같은 그런 UI이지만 뭐 편리한 기능들은 꽤 많고 다 잘 작동했습니다. 생각보다 공부하기 좋은 기능들이 많이 있는데, 일단 제가 가장 좋아하는 1주일 정도마다 열리는 Round가 있고, 꽤나 자주 열리는 Hourly가 있습니다. 아직 Round를 한번 참여해본 것 말고는 사용을 해 보지 않아서 자세한 이야기는 못 드리겠네요.

콘테스트 외에 주제별로 풀어볼 수 있는 Problem set 기능도 제공합니다. Tasks라고 표현을 하는것 같습니다.

일단 코드포스 보다는 역사가 짧긴 한 것 같습니다. 코드포스가 Contest 번호가 400번대를 넘어섰는데, CS Academy는 58번째 Round를 진행하고 있네요.

Contest Round 외에도 Lesson이라고 해서 주제별로 Computer Science 관련된 자료구조나 알고리즘에 대한 공부 자료들이 있습니다. 그 외에도 그래프나 기하학적인 도형들을 그리는 툴도 있네요. 

그리고 특이했던 것 중 하나가 Contest Round 방식이었습니다. 코드포스와 비슷하게 Division을 1과 2로 나누어서 수준별 차이를 두고, Rating 시스템도 있습니다.

특히나 인상 깊었던 Contest Round 화면입니다. 온라인에서 실시간으로 코딩을 할 수 있고, 컴파일 및 실행과 제출을 한번에 할 수 있습니다. 매번 코드포스에서 문제를 풀 때에는 구름 IDE를 켜서 했던 것에 비해 비교적 간편했습니다.

언어도 다양하게 지원을 합니다. 문제들은 쓸데없는 문장 없이 간결했습니다.

또 특히나 좋았던 점은 아직 사용자가 많지 않아서 그런 것 일수도 있지만 서버 상태가 매우 쾌적했다는 것입니다. 랙이나 시간 지연없이 잘 동작했고, 문제 제출 시 몇번째 Test Case까지 맞았는지와 각각의 실행시간과 메모리 사용량을 알려줍니다.

그리고 콘테스트가 끝나면 Chatting 방에서 해당 라운드에 참여했던 사람들과 이야기를 할 수 있습니다. 그리고 약 15분만 기다리면 튜토리얼(문제에 대한 해설)과 Rating 변동 사항도 알려줍니다.

이번에 처음으로 한번 참여해 보았지만 편리하고 좋은 경험이었습니다. 앞으로도 CS Academy에서 계속 공부를 해 볼 생각입니다.

해당 플랫폼에 대한 더 정갈한 정리는 추후 제가 이 플랫폼을 많이 이용해본 뒤에 올리도록 하겠습니다.

때는 백준 1920번 문제를 풀 때 겪은 일이었습니다.

https://www.acmicpc.net/problem/1920

문제를 보자 마자 C++ STL에 있는 unordered_set을 이용하면 풀리겠거니, 하고 풀었더니 시간초과가 났습니다.

그래서 풀이를 찾아보니 바이너리 서치를 이용해서 풀더군요. 그래서 C++ STL Algorithm 헤더에 있는 binary_search를 이용해서 푸니 똑같이 시간초과가 났습니다.

예전에 C++ STL에 있는 upper_bound와 lower_bound가 O(lgN)이 아니라 선형 시간복잡도를 갖는다는 이야기를 들은적이 있습니다.(틀린 이야기라라고 합니다.) (binary_search는 lower_bound를 이용해서 구현된 것으로 알고 있습니다.) 그래서 vector container에 대한 binary_search를 커스텀으로 구현한 뒤 다시 풀어보니 또 시간초과...

그래서 binary_search를 잘못 구현한 것인가 싶어서 vector<int>::iterator를 이용하지 않고, int형 인덱스로 다시 구현해도 시간초과가 났습니다. 그래서 미뤄두고 있다가 최근 코드포스에서 비슷한 현상을 겪었죠.

http://codeforces.com/contest/892/problem/B

C++로 구현하니 시간초과가 나는데 요즘 공부하는 파이썬으로 짜니 오히려 정답처리가 되는... 그래서 대회가 끝나고 C++로 정답판정을 받은 사람들의 코드를 보니 다음과 같은 코드가 눈에 띄었습니다

 
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin, cout이 scanf, printf에 비해서 속도가 많이 느리다고 하더군요. std::endl보다 '\n'가 훨씬 빠르다는 이야기도 많이 들었지만, 실제 프로그래밍 문제를 풀 때 이러한 것 때문에 애로사항을 겪은적이 없었기 때문에 크게 신경쓰지는 않았었는데 이렇게 겪게 되었습니다.

따지고 보면 입출력 속도 때문에 시간초과가 난 문제 둘 다 최대 입력값 개수가 100만개 이상이었습니다.

찾아보니 여러가지가 자료들이 많았는데 결론적으로는 편리함 때문에 cin, cout을 쓰기 보다는 scanf와 printf를 사용하면 해결될 문제입니다. 그리고 좀 더 빠르게 하겠다면 글자 하나씩 입출력하는 함수들이 더 빠릅니다.(getchar, putchar 등등)

cin, cout을 사용하더라도 sync_with_stdio(false)로 속도를 가속할 수는 있지만, 이는 정공법적인게 아니라 일종의 편법같은 방식이고, 이 방식도 통하지 않는 경우가 있습니다.(그래도 scanf, printf속도로만 정답이 나오는 경우) 그리고 sync_with_stdio를 false로 준 경우, scanf, printf와 같은 C 표준 입출력 함수와 cout, cin같은 C++ 입출력 객체를 섞어 사용하는 경우 오답처리가 날 수 있습니다. 입출력이 코드 작성자가 의도하지 않은 순서로 나타난다던가 하는 일이 일어날 수 있다는 것이죠. 특히 멀티 쓰레드 환경일 경우 sync 값이 true일 때는 Thread safe라서 예상치 못한 값이 나오지 않지만, false를 시킬 경우 Thread unsafe해지기 때문에 예상치 못한 값이 나타날 수 있습니다.

그러므로 굳이 sync_with_stdio(false); 를 이용해서  C++ 입출력 객채를 가속시켜서 사용할 것이라면, scanf와 printf와 섞어서 사용하지 말 것이며, 싱글 쓰레드 환경에서만 사용(알고리즘 문제만 풀 때는 무조건 싱글스레드이므로 상관없지만 실무에선 쓰지말것)하고, 그래도 시간초과가 난다면 C 표준입출력 함수들을 사용하는 것을 추천하는 바입니다.

더 참고할 수 있는 자료들

알고스팟 - 언어별 input method 비교

https://algospot.com/forum/read/2496/

백준저지 -  1920번 문제 질문

https://www.acmicpc.net/board/view/9022

cpp reference - sync_with_stdio

http://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

stackoverflow - sync_with_stdio, cout.tie등에 대한 질문에 대한 답변

https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull

이번 코드포스 콘테스트는 Division 2만 개최되었다. Div1에 해당하는 사람도 참가는 가능하지만, competition은 Div2에 해당하는 사람만 이루어졌다.

풀지 못한 문제도 대회가 끝난 후 읽어보고 Editorial을 읽으면서 계속 공부하려고 해 보았는데, 오랜만에 제대로 공부하는 느낌이 드는 대회였다.

A번 문제

http://codeforces.com/contest/869/problem/A

하나하나 실제로 시뮬레이션 하면 된다. 이미 한번 나왔던 수 인지는 unordered_set으로 확인했다. 그런데 대회가 끝난 후 editorial을 읽어보니, 수학적 증명에 따라서 무조건 짝수개가 나온다고 한다. xor의 수학적 특징때문이다. A xor B = C라면 B xor C = A이라는 뭐 이런 특징때문이라고 한다. A번 문제 쉽다고 생각해서 그냥 풀어버리고 나왔는데, 생각보다 신박한 부분이 있다.

문제가 xi와 yi를 xor한 값이, 2n개의 배열, x1, x2, x3... xn, y1, y2, ... yn의 총 2n개의 배열 안에 들어있으면 카운트를 센다는 것인데, xor한 값이 2n보다 작은지라고 문제를 잘못 이해해서 hack 당한 사람들이 몇 명 있었다.

#include <iostream>
#include <unordered_set>
using namespace std;

int arr[2002][2];
unordered_set<int> s;
int main() {
	int n;
	cin >> n;
	for (int i=0;i < 2; i ++) {
		for (int j=0; j< n; j++) {
			cin >> arr[j][i];
			s.insert(arr[j][i]);
		}
	}
	
	bool even = true;
	for (int i=0; i < n; i++) {
		for (int j=0; j < n; j++) {
			auto& xi = arr[i][0];
			auto& yi = arr[j][1];
			int val = (xi ^ yi);
			if (s.find(val) != s.end()) {
				even = !even;
			}
		}
	}
	
	cout << (even ? "Karen" : "Koyomi") << endl;
}

B번 문제

http://codeforces.com/contest/869/problem/B

죄다 곱해버리면 될 것 같은데, 수가 커서 TLE가 나온다. 그런데 여기서 어차피 마지막 decimal digit을 구할 것이므로, 1의자리수만 고려하면 될 것 같다. 10번마다 주기적으로 회전하므로, 이를 고려하면 된다는 것! 그런데 또 보면 10번을 돈다는 것은, 0이 포함되므로 그냥 0이 나온다는 것이다. 따라서 a와 b의 차이값이 10이상이면 무조건 0이다.    

코드를 잘못 내서 hack 당했다.. 중간에 주석처리한 부분을 주석을 해제하면 Hack당한 코드가 된다. 주석 처리해서 지금은 Accept 판정을 받은 코드이다.

#include <iostream>

typedef long long ll;
using namespace std;

int main() {
	ll a, b, ans;
	cin >> a >> b;
	if (b-a >= 10) {
		cout << 0 << endl;
		return 0;
	}
	ans = 1;
	// b %= 10;
	// a %= 10;
	for (ll k = b; k > a; k--) {
		ans *= k;
		ans %= 10;
	}
	cout << ans << endl;
}

C번 문제

http://codeforces.com/contest/869/problem/C

섬 a,b,c에 대하여, a-b, b-c, c-a 연결 시 다리 개수는 모두 독립적이다. a-b 연결 다리 개수는 다리가 0개일때, 1개일때, ... n개일때 모두 고려해서 더하면 된다. n개는 min(a,b) 개이며, a와 b의 섬 개수 중 최소값이다. 다리가 i개 일때는 aCi * bCi * i!의 개수가 나오게 된다. 연결에 참여할 섬들을 고른 뒤 어떻게 연결할 것인지를 곱한 값이다. 팩토리얼과 이항계수는 dp로 구현했다. 메모리가 아슬아슬하다.

#include <bits/stdc++.h>

using namespace std;

#define MOD 998244353

typedef long long ll;

int dp[5001][5001];
int bicof[5001][5001];
int facto[5001];

ll get_facto(int n) {
	if (n <= 1) {
		return 1;
	}
	if (facto[n]) return facto[n];
	ll ret = 1;
	return facto[n] = (n * get_facto(n-1)) % MOD;
}

ll pascal(int n, int r) {
	if (n==r) return 1;
	if (n==0 || r==0) return 1;
	if (bicof[n][r]) return bicof[n][r];
	return bicof[n][r] = ((ll)pascal(n-1, r) + (ll)pascal(n-1, r-1)) % MOD;
}
ll get(int a, int b) {
	if (dp[a][b]) return dp[a][b];
	ll ret = 1;
	int limit = min(a, b);
	for (int i=1; i <= limit; i++) {
		ret += (((pascal(a, i) * pascal(b, i)) % MOD) * get_facto(i)) % MOD;
		ret %= MOD;
	}
	return dp[a][b] = ret;
}
int main() {
	int a, b, c;
	dp[1][1] = 2;
	cin >> a >> b >> c;
	ll ans = 1;
	ans *= get(a,b);
	ans %= MOD;
	ans *= get(b,c);
	ans %= MOD;
	ans *= get(c,a);
	ans %= MOD;
	cout << ans << endl;
}

D번 문제

http://codeforces.com/contest/869/problem/D

실제 대회당시 맞춘사람이 5명인가 밖에 안된다. 등록한사람이 7천명이 가까이되는데 말이다. 출제자가 D번문제와 E번 문제를 바꾸는게 나았을거라고 인정했다. 맞춘 사람 풀이를 보니, 실제로 가능한 경로를 모두 세되, 중복일 경우 최적화를 잘 적용한 것으로 보인다. 나중에 다시 도전해볼 예정이다.

E번 문제

http://codeforces.com/contest/869/problem/E

뭔가 풀 수 있을 것 같은데 못 풀 것 같은 문제이다. 2차원 세그먼트 트리나 쿼드 트리를 사용해야 한다고 한다. 세그먼트 트리와 쿼드 트리를 공부한 뒤 다시 도전할 예정이다.

bits/stdc++.h 헤더 파일이란?

#include <bits/stdc++.h>

간혹 다른사람들이 C++을 이용하여 알고리즘 문제를 푸는 소스코드를 참조했을 때, 위와 같은 헤더가 나타나는 경우가 있습니다. 이 헤더는 어떤 것이고 어떠한 이유로 사용하는 것일까요?

bits/stdc++.h 헤더는 모든 표준 라이브러리가 포함된 헤더입니다. 프로그래밍 대회에서 위 해더를 사용하는 것은 좋은 아이디어 입니다. 문제를 풀 때 마다 #include <iostream> 등등을 작성하는 반복적인 일을 줄여서 시간안배를 도와줍니다. 특히나 문제 푸는 시간이 순위에 결정적인 경우에 더 도움이 될 수 있습니다. 프로그래밍 대회에서는 효율적이고 정확한 알고리즘을 찾는 것이 주가 되어야 하기 때문입니다.

하지만 소프트웨어 공학적인 측면에서는 #include 구문을 줄이는 것이 중요합니다. 많은 필요없는 파일들을 #include 하게 된다면, 컴파일 시간과 프로그램 크기가 쓸데없이 길어지고 커지게 됩니다.

다음은 bits/stdc++ 헤더의 단점들입니다.

- bits/stdc++.h 헤더는 GNU C++ 라이브러리의 표준 헤더가 아니기 때문에, GCC가 아닌 다른 컴파일러로 빌드를 하려고 한다면 실패합니다.

- 쓸대없는 파일들을 추가시켜서 컴파일 시간이 늘어납니다.

- 표준 C++이 아니기 때문에 이식성이 있지도 않고, 컴파일러 종속적입니다.

다음은 bits/stdc++ 헤더의 장점들입니다.

- 프로그래밍 대회에서 쓸데없는 시간낭비를 줄여주므로 사용하면 좋습니다.

- 필요한 헤더 파일 include 구문을 작성하는데 시간을 줄여줍니다.

- STL이나 GNU C++의 모든 함수들을 기억할 필요가 없습니다.

리눅스 머신에서 해당 헤더파일을 한번 열어봤습니다.

// C++ includes used for precompiling -*- C++ -*-

// Copyright (C) 2003-2015 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */

// 17.4.1.2 Headers

// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

헤더파일 길이는 100줄 남짓으로, 헤더치고는 별로 길지 않고, 거의다 쓸만한 헤더파일을 다 넣어버린 내용입니다.

윈도우즈 Visual Studio에서 bits/stdc++.h 헤더 사용하기

그런데 만약 이 헤더파일을 Windows Visual Studio에서 사용을 하고 싶다면 어떻게 하는 게 좋을까요?

일단 이 bits/stdc++.h 헤더파일은 비표준이기때문에 개발 등에서 사용하기엔 좋은 방법은 아닙니다.

하지만 알고리즘 문제해결 등을 할 것이라면, 일반적인 백준이나 코드포스와 같은 온라인 저지에서는 bits/stdc++.h 헤더를 다 지원하기 때문에, 윈도우에서 알고리즘 문제 풀이용으로 헤더를 사용해 보는 것은 나쁘지 않을 수 있습니다.

그러면 간단하게, 윈도우에서 적용되도록 비쥬얼 스튜디오 include 헤더들이 저장되는 디렉토리에 bits라는 폴더를 하나 만들고, 그 폴더 하위에 stdc++.h라는 이름의 파일을 집어넣으면 됩니다.

일단 윈도우즈 비쥬얼 스튜디오의 include 파일들이 저장되는 디렉토리를 찾아봅시다.

제 컴퓨터의 경우는 다음 경로가 include 디렉토리입니다.

C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.12.25827\include\

물론 Visual Studio 버전과, 설치된 드라이브 명에 따라 조금씩 경로는 다를 수 있습니다.

이 경로에 bits라는 디렉토리를 하나 만들어 준 뒤, 그 하위 경로에 stdc++.h라는 텍스트 파일을 하나 만들어 줍시다.

(아마 해당 경로에는 바로 텍스트 파일을 만들기에는 관리자 권한이 필요할 수 있으므로, 바탕화면 등에 만든 뒤 드래그 앤 드롭으로 옮기는 식으로 하시는 편이 편합니다.)

즉 결과적으로 경로는

C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.12.25827\include\bits\stdc++.h

가 되게 됩니다.

stdc++.h파일의 내용은 아래에 있습니다.

복사를 하시려면, 우측 하단의 view-raw를 누른 뒤 복사하시면 됩니다. 

한국정보올림피아드 2015년도 초등부 문제 풀이 포스팅입니다.

https://www.acmicpc.net/category/detail/1353

1번 사과문제입니다.

https://www.acmicpc.net/problem/10833

apple수를 사람수로 나누면 1인당 지급되는 사과수가 됩니다.

#include <iostream>

using namespace std;

int main() {
	int N;
	cin >> N;
	
	int ans = 0;
	while(N--) {
		int std, apple;
		cin >> std >> apple;
		int cnt = apple/std;
		int total = cnt * std;
		ans += apple - total;
	}
	cout << ans << endl;
}

2번 벨트문제입니다.

https://www.acmicpc.net/problem/10834

정수로 떨어지게 되어있으므로 그냥 계산하면 됩니다.

#include <iostream>

using namespace std;

int main() {
	int M;
	bool direction = false;
	int rot = 1;
	cin >> M;
	
	while (M--) {
		int a, b;
		int dir;
		cin >> a >> b >> dir;
		rot *= b;
		rot /= a;
		if (dir == 1) {
			direction = !direction;
		}
	}
	cout << (direction == true ? "1" : "0") << " " << rot << endl;
}

3번 카드문제입니다.

https://www.acmicpc.net/problem/10835

완전탐색을 하면 시간 초과가 난다. O(3^n)이 된다. 하지만 중복탐색되는 부분을 줄이면, 즉 Memoziation원리를 적용한 Dynamic programming으로 풀 시에는 나타나는 좀더 효율적으로 풀 수 있다. dp[왼쪽남은카드수][오른쪽남은카드수]로 한다면 최악의경우 O(n^2)이므로 2000^2 = 400만으로 1초안에 풀 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> L, R;
int n;

int dp[2001][2001];
bool chk[2001][2001];

int get(int l, int r) {
	if (l <= 0 || r <= 0) {
		return 0;
	}
	if (chk[l][r]) return dp[l][r];

	int ret;
	
	ret = max(get(l-1, r-1), get(l-1, r));
	int left_top_card_val = L[n-l];
	int right_top_card_val = R[n-r];
	if (left_top_card_val > right_top_card_val) {
		ret = max(ret, get(l, r-1) + right_top_card_val);
	}
	chk[l][r] = true;
	return dp[l][r] = ret;
}
int main() {
	cin >> n;
	L.reserve(n);
	R.reserve(n);

	for (int i=0; i < n; i++) {
		int tmp;
		cin >> tmp;
		L.push_back(tmp);
	}
	for (int i=0; i < n; i++) {
		int tmp;
		cin >> tmp;
		R.push_back(tmp);
	}
	cout << get(n, n) << endl;
}

4번 여왕별 문제입니다.

https://www.acmicpc.net/problem/10836

dfs로는 Time out이 납니다.. 그러므로 더 좋은 성능의 방법을 찾아봐야 합니다.

숫자가 감소하지 않는 방향이라고 했으니 규칙을 잘 보면, 왼쪽 끝과 위쪽 끝을 제외하고 내부쪽은 결과적으로 위쪽 값과 같은 값을 갖게 됩니다.

이러한 규칙을 이용하면 O(MN)으로 해결 가능합니다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> border;

int main() {
	int M, N;
	cin >> M >> N;
	int len = M*2 - 1;
	border.resize(len, 1);
	while(N--) {
		int zero, one, two;
		cin >> zero >> one >> two;
		for (int i=zero; i < zero + one; i++) {
			border[i]++;
		}
		for (int i = zero+one; i < len; i++) {
			border[i] += 2;
		}
	}
	
	for (int i=0; i < M; i++) {
		for (int j=0; j < M; j++) {
			if (j==0) {
				cout << border[M-i-1] << ' ';
			} else {
				cout << border[M+j-1] << ' ';
			}
		}
		cout << endl;
	}
}

한국정보올림피아드 2016년도 초등부 문제 풀이 포스팅입니다.

문제들은 백준저지에서 참고하고 풀이했습니다.

https://www.acmicpc.net/category/detail/1526

총 4문제로 이루어지며, 뒤쪽 문제로 갈 수록 난이도가 어려워집니다.

1번 방 배정 문제입니다.

https://www.acmicpc.net/problem/13300

학년 별 인원수에 맞는 방을 배정한 뒤 모두 더해주면 됩니다.

방에 4명씩 있을 수 있다면, 실제 인원에 +3을 해준 뒤, 4로 나누어주면 각 학년 및 성별별로 필요한 방의 수가 나옵니다. C++에서 정수끼리 나눗셈을 할 시, 소수점 이하는 자동으로 버려지기 때문입니다.

예를들어 방에 5명이 있을 수 있고, 인원이 5명이라고 하면 5+4을 해서 9을 만든 뒤 5로 나누면 1.8이 되는데 소수점 버림으로 인하여 1이 됩니다. 5명일 시에는 방이 1개 필요한 것입니다.

비슷한 원리로 방에 5명이 있을 수 있고, 인원이 6명일 경우 6+4을 해서 10를 만든 뒤 5로 나누면 2가 됩니다.  6명이 묵기 위해서는 2개의 방이 필요한 것입니다.

#include <iostream>

#define GIRL 0
#define BOY 1
using namespace std;

int people[2][7];
int main() {
	int N, K;
	int ans = 0;
	int bias;
	cin >> N >> K;
	
	bias = K - 1;
	
	for (int i=0; i < N; i++) {
		int S, Y;
		cin >> S >> Y;
		people[S][Y]++;
	}
	for (int s = 0; s < 2; s++) {
		for (int y = 1; y < 7; y++) {
			if (people[s][y]) {
				ans += (people[s][y] + bias) / K;
			}
		}
	}
	cout << ans << endl;
	
}

2번 타일 장식물 문제입니다.

https://www.acmicpc.net/problem/13301

가로 세로 길이가 늘어나는 패턴이 짝수번째 홀수번째마다 규칙성을 갖고 연속됩니다. 이 규칙성만 찾으면 간단하게 해결할 수 있습니다.

#include <iostream>

using namespace std;
typedef long long ll;
int main() {
	ll x = 1, y = 1;
	int N;
	cin >> N;
	for (int i = 1; i < N; i++) {
		if (i & 1) {
			y += x;
		} else {
			x += y;
		}
	}
	
	cout << ((x+y)<<1) << endl;
}

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>

#define MIN(a,b) ((a) < (b) ? (a) : (b))
using namespace std;

vector<int> holiday;
vector<bool> day;
int total_day, absent_day;
int cost[101][101];

int count = 0;
int count_mem = 0;
int find_cost(int start_day, int num_coupon) {
	count ++;
	int min_cost = 987654321;
	int temp, a,b;
	temp = 987654321;
	if (start_day > total_day) {
		//basis case
		return 0;
	} else if (!day[start_day]) {
		
		for (int i=start_day+1; i<=total_day; i++) {
			if (day[i]) {
				return find_cost(i, num_coupon);
			}
		}
		return 0;
	}
	
	if (cost[start_day][num_coupon] == 0) {
		if ( start_day <= total_day - 2 && day[start_day+1] && day[start_day+2] ) {
			
		} else {
			min_cost = MIN(min_cost, find_cost(start_day + 1, num_coupon) + 10000 );
		}
		
		if (min_cost != temp) {
			temp = min_cost;
			a = start_day + 1;
			b = num_coupon;
		}
		
		if ( start_day <= total_day - 5 && day[start_day+1] && day[start_day+2] && day[start_day+3] && day[start_day+4]) {
		} else {
			min_cost = MIN(min_cost, find_cost(start_day + 3, num_coupon + 1) + 25000 );
		}
		
		if (min_cost != temp) {
			temp = min_cost;
			a = start_day + 3;
			b = num_coupon + 1;
		}
		
		min_cost = MIN(min_cost, find_cost(start_day + 5, num_coupon + 2) + 37000 );
		
		if (min_cost != temp) {
			temp = min_cost;
			a = start_day + 5;
			b = num_coupon + 2;
		}
		
		if (num_coupon >= 3) {
			min_cost = MIN(min_cost, find_cost(start_day + 1, num_coupon - 3) );
			
			if (min_cost != temp) {
				a = start_day + 1;
				b = num_coupon - 3;
			}

		}
		cost[start_day][num_coupon] = min_cost;
		return min_cost;
	} else {
		count_mem++;
		return cost[start_day][num_coupon];
	}
	
	
}
int main() {
	int temp;
	int answer;
	
	scanf("%d %d\n", &total_day, &absent_day);
	holiday.reserve(absent_day);
	day.resize(total_day + 1, true);

	for (int i=0;i<absent_day; i++) {
		scanf("%d ", &temp);
		holiday.push_back(temp);
	}
	
	for (int i=0;i<absent_day; i++) {
		day[holiday[i]] = false;
	}
	
	answer = find_cost(1, 0);
	cout << answer;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

typedef struct {
	int x, yl, yh;
} barPos;

typedef pair<int, int> meta;
bool operator<(barPos a, barPos b) {
	return a.x < b.x;
}

vector<barPos> barriers;
vector<int> answer;
set<meta> subp;
void dump_barrier() {
	cout << " --------------------------------------" << endl;
	for (int i=0; i < barriers.size(); i++) {
		cout << barriers[i].x << " " << barriers[i].yl << " " << barriers[i].yh << endl;
	}
	cout << " --------------------------------------" << endl;
}
void dump_subp() {
	for (set<meta>::iterator ptr = subp.begin(); ptr != subp.end(); ptr++) {
		cout << ptr->first << ", " << ptr->second << endl;
	}
}
int find_min_y() {
	int min_val = 98754321;
	for (set<meta>::iterator ptr = subp.begin(); ptr != subp.end(); ptr++) {
		min_val = min(min_val, ptr->second);
	}
	return min_val;
}
void set_answers(int min_val) {
	for (set<meta>::iterator ptr = subp.begin(); ptr != subp.end(); ptr++) {
		if (ptr->second == min_val) {
			answer.push_back(ptr->first);
		}
	}
}
int main() {
	int N;
	int srcY, finX;
	
	cin >> N >> srcY >> finX;
	barriers.reserve(N);
	
	for (int i=0; i < N; i++) {
		int x, yl, yh;
		
		cin >> x >> yl >> yh;
		barPos tmp;
		tmp.x = x;
		tmp.yl = yl;
		tmp.yh = yh;
		barriers.push_back(tmp);
	}
	sort(barriers.begin(), barriers.end());
	subp.insert(make_pair(srcY, 0));
	vector<set<meta>::iterator> delete_candidate;
	for (int i=0; i < N; i++) {
		auto upper_bound = barriers[i].yh;
		auto lower_bound = barriers[i].yl;
		delete_candidate.clear();
		int minl = 987654321;
		int minh = 987654321;
		for (set<meta>::iterator ptr = subp.lower_bound(make_pair(lower_bound, 0)); ptr != subp.upper_bound(make_pair(upper_bound, 0)); ptr++) {
			delete_candidate.push_back(ptr);
			minl = min(minl, ptr->second + (ptr->first - lower_bound));
			minh = min(minh, ptr->second + (upper_bound - ptr->first));
		}
		for (int j=0; j < delete_candidate.size(); j++) {
			subp.erase(delete_candidate[j]);
		}
		if (delete_candidate.size() > 0) {
			delete_candidate.clear();
			subp.insert(make_pair(upper_bound, minh));
			subp.insert(make_pair(lower_bound, minl));
		}
	}
	
	int min_y_val = find_min_y();
	set_answers(min_y_val);
	
	cout << finX + min_y_val << endl << answer.size();
	for (int i=0; i < answer.size(); i++) {
		cout << ' ' << answer[i];
	}
	cout << endl;
}