SRM 313 ~ 320

여기까지 푸느라 수고했다 !! 앞으로는 더 힘차게 나아가보자 !!

(2013. 05. 10 ~ 05. 29) - SRM 8개 (DIV 1, 2) / 20일

 

 [ 결과 정리 ]

SRM 번호 / DIV 번호	Easy	Medium	Hard
313 DIV 1	O	ㅡ (미시도 문제)	ㅡ
DIV 2	O	O (DIV 1의 Easy와 같음)	O
314 DIV 1	O	O (DIV 2의 Hard와 같음)	ㅡ
DIV 2	O	O (DIV 1의 Easy와 같음)	X -> △ (editorial 참조)
315 DIV 1	O (DIV 2의 Mid와 같음)	△ (editorial 참조)	ㅡ
DIV 2	O	O	X -> △ (editorial 참조)
316 DIV 1	O (DIV 2의 Mid와 같음)	ㅡ	ㅡ
DIV 2	O	O	O
317 DIV 1	O (DIV 2의 Mid와 같음)	X (안 떠오르는 경우)	ㅡ
DIV 2	O	X -> △ (editorial 참조)	X -> △ (editorial 참조)
318 DIV 1	O (DIV 2의 Mid와 같음)	X -> △ (editorial 참조)	ㅡ
DIV 2	O	△ (editorial 참조)	X -> △ (editorial 참조)
319 DIV 1	O (DIV 2의 Mid와 같음)	X -> △ (editorial 참조)	ㅡ
DIV 2	O	O	O ( System Fail 보고 수정)
320 DIV 1	O (DIV 2의 Mid와 같음)	O (DIV 2의 Hard와 같음)	ㅡ
DIV 2	O	△ (다른 사람 코드 참조)	O

 

 

SRM 313 DIV 1 - Easy

[문제 설명] 단어들의 집합이 주어질 때, 그 집합의 부분집합들 중에 다음 조건을 만족하는 집합의 원소 개수를 구하는 것. (어떤 단어도 다른 단어의 접두사가 되지 않게 하면서, 최대 원소 개수를 갖는 부분집합)     [해결 방법]   어떤 단어 A가 다른 단어 B의 접두사가 되려면, 다음와 같은 조건을 만족해야한다. 1. A의 길이 <= B의 길이 2. A는 B의 부분 단어이다.   집합에 포함된 모든 단어를 사전순으로 정렬해 놓았을 때는, 앞에 있는 단어가 뒤에 있는 단어의 접두사는 될 수 있어도, 그 반대는 불가능하다. (중복 원소 제외) 그 성질을 이용해서, '자기 뒤쪽에 있는 단어들의 접두사가 되지 않는' 단어들의 개수만 세서 반환하면 된다.   중복 원소 처리는, 중복 원소가 n개 이상 있다고 하더라도, 사전순 정렬시 맨 마지막 원소는 같은 단어와 비교되지 않는다. 따라서, 집합에 1개 포함하게 되므로 문제 조건에 맞게 해결이 된다.   [다른 코드를 보고 얻은 팁] 접두사 검사시, substr(0, 길이)을 사용할 것.

 

(SRM 313 DIV 2 - Easy : 쉬움.)

(SRM 313 DIV 2 - MId   : DIV 1의 Easy와 같음)

 

SRM 313 DIV 2 - Hard

[문제 설명]   Parallel Programming 문제이다. 각 작업에 걸리는 시간과 선행 작업들이 주어지며, 선행되야 하는 작업이 존재하는 작업이 있고, 독립적으로 실행할 수 있는 작업이 있다. 선행되야 하는 작업이 없거나 끝난 임의의 두 작업은 동시에 실행될 수 있다.     [해결 방법]   그래프를 이용해서 푸는 문제이다. 선행하는 작업을 시작 노드, 후행하는 작업을 끝 노드로 두고, 그 가중치는 시작 노드(선행 작업)에 걸리는 시간을 가중치로 한다. (최단 경로가 아닌, 최장 경로를 찾아야 하므로 가중치를 음의 부호를 붙여서 넣는다.)   Bellman-Ford 알고리즘을, 모든 노드를 시작점으로 하여 실행한다. 여기서 사이클이 존재하는 경우는 선행 기준이 돌고 돈다는 뜻이므로, -1을 리턴한다.   사이클이 없는 경우에 대해서, 답은, max('최대 경로의 시간 + 마지막 작업의 시간', '독립된 작업의 실행 시간들') 이다. 이유는 다음과 같다.   1. 어차피 독립된 작업들은, 선행 관계가 있는 작업들이 실행되는 동안에 같이 실행될 수 있으므로, 선행 관계가 있는 작업들이 실행되는 시간보다 오래 걸리지만 않는다면 최대 시간에 영향을 주지 않는다.   2. 선행 관계가 있는 작업들의 경우, 이리저리 관계가 복잡하게 꼬여 있는 경우가 많은데, 어떤 경로가 되었든 시간이 가장 많이 걸리는 경로의 작업이 끝나기 전에 다른 경로의 작업이 끝난다.   3. '마지막 작업의 시간' 을 더해 주는 이유는, 마지막 작업의 시간은 이 계산에서 빠지게 되기 때문이다. (간선으로 추가가 되지 않는다는 말이다. 그 시간을 단순히 마지막 upper[] 에 더해주기만 하면 된다.)   두 시간동안 힘들게 푼 문제였다.

 

(SRM 314 DIV 1 - Easy : DIV 2의 Mid와 같음)

(SRM 314 DIV 1 - Mid : DIV 2의 Hard와 같음)

 

(SRM 314 DIV 2 - Easy : 쉬움)

SRM 314 DIV 2 - Mid

[문제]   사람들의 줄을 세우는 문제이다. 각 사람들 기준으로 자기보다 왼쪽에 있던 사람들 중에서 키 큰 사람들의 수가 주어질 때, 원래 줄의 모습을 복원하여라.   [해결 방법] 키가 가장 작은 사람은 위치를 확정할 수 있다. 가장 작은 사람의 키가 확정되면, 그 다음으로 작은 사람도 위치 확정 가능. 끝까지 반복하면 됨.   단, k번째 빈 칸을(k >= 0) 찾는 코드를 만드는 것이 계속 헷갈려서, 여기서 많은 시간을 먹었다. // 왼쪽으로부터 count 번째 빈 칸의 위치를 찾는 코드(count >= 0) int count = left[i]; for(int iter = 0; iter < n; iter++) { if(line[iter] == 0) { if(count == 0) { line[iter] = i + 1; break; } else count--; } }

SRM 314 DIV 2 - Hard

[문제 설명]   주어진 자연수 집합에서 원소들을 골라서 삼각형을 만들 때 최대 넓이를 구하는 문제이다. 삼각형은 여러 개 만들 수 있으며, 중복 원소도 허용된다.     [시도한 방법] 변을 일일이 선택하는 알고리즘을 만들어보려 했으나, 코드를 짜내지 못했다. Editorial을 참조하니, 그냥 3중 for문으로 해결하면 저절로 되는 문제였다.     [문제 해결] 이 문제는 손을 대지 못하여 에디토리얼을 참조했다. 문제 해결 방식은 DP로, 일일이 값을 만들어보며 최대값을 찾는다. 재귀 함수로 구현해서, 사용한 울타리는 제외하고 나머지 값을 넣어서 또 찾는다.   핵심은, '사용할 수 있는 울타리들' 의 종류가 담긴 vector<int> fences가 2^16개의 종류라는 것이다. 비트마스크 기법 - 알고리즘 2권에 나오지만 아직 보지는 못함 - 을 사용하면, 각 벡터마다 하나의 고유한 번호를 붙일 수 있고, 이를 통해 memoization이 가능하다.(안 쓰면 시간초과)     [Tips] 1. 2^16을 표현할 때, 굳이 계산기 두드리지 말고 1 << 16 이렇게 표현할 수 있다. 캐쉬 크기를 지정할 때 이것을 쓰면 매우 편하다.   2. 정수 3개의 합을 2로 나눈 결과가 실수가 되게 하려면, (double)(a+b+c) / 2 해도 되지만, a+b+c/2.0 하면 된다.   [느낀 점] 하나하나 따져보는 문제를 제대로 풀어본 것은 처음이었다.

 

(SRM 315 DIV 2 - Easy : 쉬움)

(SRM 315 DIV 2 - Mid : 쉬우나, 숫자를 문자로, 문자를 숫자로 변환하는 법을 배우는 문제.

주어진 숫자의 각 자리 숫자를 뽑는 또다른 방법으로는, 10으로 나눠주고 10으로 나눈 나머지를 구하는 방법이 있음.

 

ex. 29743에서 3번째 자리를 구한다 -> 29743을 (3-1)번 10으로 나눠주면 결과는 297.

이 때 이를 10으로 나눈 나머지는 7)

 

 

SRM 315 DIV 2 - Hard

풀지 못하고, 결국  Editorial을 참조하여 풀었음.   [문제 설명] JOSEPHUS문제의 변형판이다.   [시도 방법] 처음에 벡터를 만들어서 시뮬레이션을 돌려 보았으나, 구현을 전혀 하지 못했다. 각 변수의 값이 어떨 때 어떻게 되어야 하는 지를 모르겠어서, 매우 힘들었다. 계속 구현하다가 실패하여, 예전에 저장해 둔 [n번째 빈 칸 찾기] 소스 코드를 참조하여 이를 사이클 형태로 변형하니, 일단 구현에는 성공하였다. (StandInLine 문제의 잘 푼 사람의 코드를 스크릔샷으로 찍어 사용하였다.)   그러나 이것으로도 풀리지는 않았다. 시간 제한이 초과되었기 때문이다. 이 문제는 시뮬레이션을 돌리면 약 O(NM)의 시간복잡도를 갖는데, 둘 다 5십만이므로 시간 내에 불가능하다. 다르게 푸는 방법은, 시뮬레이션 대신에 숫자로 이를 대응시켜서 푸는 것이었다.     http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm315   여기에서 유용하게 볼 것은, 하나를 지우고 다음 지울 것의 위치를 찾는 코드가 바로 curIndex = (curIndex -1 + m + (n) - 1) % n + 1 이라는 것이다. (1-based임. 앞의 (n)은 생략 가능.) 연필로 써서 하나하나 해 본 결과, 이것이 성립하리라는 것을 알 수 있었다.   0 - based의 경우는, 다음과 같은 소스 코드가 된다. // 1 - based 코드. struct KidsGame{ int kthKid(int n, int m, int k) { int currentIdx = (0 - 1 + m ) % n + 1; int beforeK = k - 1; int nr = 1; while( currentIdx != beforeK + 1) { if( currentIdx < beforeK + 1) beforeK--; n--; nr++; currentIdx = (currentIdx - 1 + m - 1) % n + 1; } return nr; } }; // 0 - based 코드. struct KidsGame{ int kthKid(int n, int m, int k) { int currentIdx = (0 - 1 + m ) % n; int beforeK = k - 1; int nr = 1; cout << currentIdx << endl; while( currentIdx != beforeK ) { if( currentIdx < beforeK ) beforeK--; n--; nr++; currentIdx = (currentIdx - 1 + m ) % n; cout << currentIdx << endl; } return nr; } };

 

( SRM 315 DIV 1 - Easy : DIV 2의 Mid와 같음)

 

SRM 315 DIV 1 -  Mid

[문제 설명] 스도쿠 채우는 경우의 수를 묻는 문제. 실제 스도쿠는 매우 경우의 수가 많아서, 축소시켜서 4 x 4 크기로 나왔다.   [시도 방법] 모든 경우를 하나하나 만들어보며 풀었다. 4^16이라 많을 것 같지만, 실제로는 그렇지가 않아서 금방 풀린다. 주어진 판에서 행, 열 순으로 가장 빠른 빈 칸을 찾고, 가로, 세로, 사각형에 특정 문자가 들어갈 수 있는지 여부를 판단하여 만일 들어갈 수 있는 경우라면, 판에 그 수를 넣은 뒤에 재귀적으로 돌렸다. 완성된 경우 1을, 완성할 수 없는 경우 0을 반환하여, 모든 경우의 수를 더해서 반환했다.   [틀렸던 부분] - 스도쿠에서, 처음에 16개의 판을 모두 채워서 줄 수도 있다는 것을 알았고, - 내가 빈 칸에 숫자들을 모두 채울 수 있다고 하더라도, 이 판이 틀릴 수 있다.   예를 들면 아래와 같다.  1 3 2 1  1 2 3 4  2 1 4 3  3 4 1 -  => 이 경우, 2를 채우면 가로/세로/사각형 검사는 만족하지만, 전체 판은 그렇지 않다. - 즉, 주어진 판 자체가 조건을 벗어나는 것이 있는지를 먼저 검사해야 했다.

 

(SRM 316 DIV 2 - Easy : 구현만 잘 생각해보면 쉬움. 속도가 문제....)

 

SRM 316 DIV 2 - Mid

[문제 설명] 최소 클릭 수로 메일함의 메일들을 지우는 문제.   [문제 해결] 그냥 하나하나 경우를 따져보고 최소값을 찾으면 된다.   [고쳐야 할 점] 내가 테스트 케이스를 보고서야 틀린 곳이 어딘지 알게 됨. 내 스스로 어디가 틀렸고 어디서 예외가 생길지를 미리 예측하지 못했음. 테스트 케이스를 하나하나 보면서 좀 더 주의깊게 읽을 것.   [나의 코드와, 모범 코드 비교] // 1. 나의 코드 #define INF 987654321 struct InboxCleanup { int fewestClicks(string msg, int low, int high){ int n = msg.size(); int ret = INF; for(int shown = low; shown <= high; shown++) { // num of pages which shows email as much as 'int shown' int pages = n / shown; int minClick = 0; if(n > shown) minClick = pages - 1; else minClick = 0; printf("pages / minClick(only pages) : %d\n", pages, minClick); for(int i = 1; i <= pages; i++) { int method1, method2; // method 1. click 'D's individually and delete // method 2. select All and deselect '.'s and delete int numOfD = 0; for(int mail = (i-1)*shown; mail < i * shown; mail++) { cout << msg[mail] << " "; if(msg[mail] == 'D') numOfD++; } if(numOfD != 0) { method1 = numOfD + 1; method2 = shown - numOfD + 2; } else method1 = method2 = 0; printf("shown / method1 / method2 : %d %d %d\n", shown, method1, method2); cout << minClick << endl; // minClick += min(method1, method2); minClick = minClick + min(method1, method2); cout << minClick << endl; } // for the last page if(n % shown != 0) { int lastPagesShown = (n - 1 + shown) % shown + 1; if(n > pages) minClick++; int method1, method2; // method 1. click 'D's individually and delete // method 2. select All and deselect '.'s and delete int numOfD = 0; for(int mail = n - lastPagesShown; mail < n; mail++) { if(msg[mail] == 'D') numOfD++; } if(numOfD != 0) { method1 = numOfD + 1; method2 = lastPagesShown - numOfD + 2; } else method1 = method2 = 0; printf("LastPagesShown / method1 / method2 : %d %d %d\n", lastPagesShown, method1, method2); minClick += min(method1, method2); } printf("이 단계에서의 minClick : %d\n", minClick); ret = min(ret, minClick); } return ret; } };   2. 모범 코드 ( 아이디 K208 )     같은 알고리즘인데도 길이 차이가 엄청나게 심하다... 이 길이 차이가 결국 점수의 차이로 이어진다. 500점짜린데 나는 199점. 이 사람은 499.99점.....분발하자!!   이 코드와 똑같이 다시 짜 보려고, 외운 뒤에 똑같이 짜려고 해 보았는데 생각처럼 간단하지 않았다. 정말 이런 좋은 코드를 짜는 습관을 내가 갖겠다.

 

 

SRM 316 DIV 2 - Hard

[문제 설명] 회사에서 비상연락망을 제작한다. 트리 구조로 상하 관계가 이루어진다고 할 때, 모든 구성원이 연락받는 데 걸리는 시간을 구해라.     [문제 해결] 여기서의 핵심은, 자기 직속 부하들 중에, 연락하는 데 제일 오래 걸리는 사람에게 먼저 연락을 해야한다는 것. 그렇게 하고 나면, 여기서는 트리 구조의 특징인 재귀 함수로 풀 수 있다.   [배운 점] 나는 매우 복잡하게 struct Node 를 사용해서 트리 노드를 직접 만들었는데, 알고 보면 그것은 필요가 없었다. 그냥 그때그때마다 자식 노드를 찾아서 값만 계산해주면 되는 것이었다. vector temp; int timeSet(int v) { vector childTime; for(int i = 0; i < temp.size(); i++) if(temp[i] == v) childTime.push_back(timeSet(i)); int ret = 0; sort(childTime.begin(), childTime.end(), greater()); for(int i = 0; i < childTime.size(); i++) ret = max(ret, childTime[i] + i + 1); return ret; } class SpreadingNews { public: int minTime(vector supervisors); }; int SpreadingNews::minTime(vector s) { temp = s; return timeSet(0); }

 

 

(SRM 317 DIV 2 - Easy : 어렵지는 않았지만, substr을 이용하면 엄청 쉽게 풀 수 있는 문제였다.

Substr의 사용법을 확실하게 익히게 되었다.)

 

 

SRM 317 DIV 2 - Mid : 풀지 못하고, 에디토리얼과 다른 사람의 소스를 참조해서 풀었음.

[문제 설명] 주어진 숫자 구간에서 펠린드롬의 개수를 구하는 문제.   [틀린 이유] 입력이 크기 때문에, 주어진 구간에 대해 모두 숫자를 만들어보고 펠린드롬의 개수를 세는 것은 시간이 100% 초과된다. 나는 그 이외에 다른 알고리즘이 없을 것이라 생각했는데, 아니었다.   [문제 해결 방법] 핵심은 펠린드롬이 되는 숫자를 '직접' 만드는 것이다. 실제 펠린드롬의 개수는 얼마 되지 않고, 예를 들어 숫자 23으로 만들 수 있는 펠린드롬은 2332 와 23 이다. 즉, 9자리의 펠린드롬 숫자가 필요하면, 1부터 99999까지로 위와 같이 만들어서 세면 된다. N의 크기가 10억에서 10만으로 줄었기 때문에, 할 만 하다.   stringstream 을 이용해서 숫자를 문자로, atoi(c_str)    을 이용해서 문자를 다시 숫자로 바꾼다.   그렇게 하면 이제 이 펠린드롬이 범위 내에 들어가는지를 알 수 있다. #include #include #include #include #include // for atoi. #include // for stringstream. using namespace std; #define INF 987654321 int lo, hi; int makePalin(string s) { int n = s.size(); int count = 0; // i == 0 : even, i == 1 : odd for(int i = 0; i < 2; i++) { int number = 0; string s1, s2; s1 = s; s2 = s.substr(0, n-i); reverse(s2.begin(), s2.end()); s1 += s2; number = atoi(s1.c_str()); if(number >= lo && number <= hi) { cout << number << endl; count++; } } return count; } struct PalindromicNumbers{ int countPalNums(int lower, int upper){ int count = 0; lo = lower, hi = upper; // generating palindrome numbers for(int num = 1; num <= 99999; num++) { stringstream tmp; tmp << num; string s = tmp.str(); count += makePalin(s); } return count; } }; 앞으로 펠린드롬 문제는 왠만하면 다 할 수 있을 것 같다. ㅋㅋ

 

 

SRM 317 DIV 2 - Hard : 못 풀고 Editorial과 다른 코드 참조해서 품.

[문제 설명] 위상 정렬할 수 있는 경우의 수를 구하여라.   [문제 해결] 도저히 어떻게 할 방법이 떠오르지가 않아서, Editorial을 봤더니, 집합의 Free한 원소를 하나하나씩 비어있는 첫 칸에 넣어가면서, 완성되면 1을 더하고. 아니면 0을 더해주면 경우의 수를 셀 수 있다고 했다.   아이디어만 나와있어서 직접 구현을 하기 위해, 현재 집합을 vector<int> 로 삼아서 구현했다. 캐쉬를 쓰기 위해서, 주어진 벡터에 대해서, 각각의 원소가 있으면 그 위치의 비트를 1, 없으면 0으로 하여 벡터의 고유 번호를 계산하는 함수를 만들었다. 그리고, 집합의 원소를 택했을 경우, 벡터에서 그 원소를 찾고 erase를 사용하여 지운 뒤에 재귀 함수를 호출하는 방식으로 만들었다. 그러나 이는 시간 초과가 났다...... 출력 없애고 이렇게 저렇게 줄이려 해 보았으나 계속 걸렸다.   결국 시간 제한을 넘지 못하고, chronotable의 소스를 보고 풀 수 있게 되었다. 시간을 줄이는 답은, 벡터가 아니라 '하나의 수'로 상태를 표시하는 데에 있었다. 어차피 20개의 원소를 20개의 비트로 표현할 수 있다면, 굳이 벡터를 넘겨서 연산하지 않아도 되는 것이다. 코드는 아래와 같다. #include #include #include #include #include using namespace std; #define INF 987654321 int adj[20][20]; long long int cache[(1 << 20) + 10]; int n; struct OrderingCount{ long long countOrderings(vector req){ n = req.size(); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) adj[i][j] = (req[i][j] == 'Y'); memset(cache, -1, sizeof(cache)); return dfs((1 << n) - 1); } long long int dfs(int state) { printf("current state : %0X\n", state); long long int& ret = cache[state]; if(ret != -1) return ret; if(state == 0) return 1; ret = 0; for(int i = 0; i < n; i++) { if((state >> i) & 1) { bool isFree = true; for(int j = 0; j < n; j++) { if( adj[j][i] && ((state >> j) & 1)) { isFree = false; break; } } if(isFree) ret += dfs(state ^ (1 << i)); } } return ret; } };   충격이었다. '비트마스크를 제대로 사용하면 엄청나게 시간을 줄일 수 있구나' 라는 것을 깨달았다. 마지막으로 고생했던 것은, 최대 20 x 20 , 모두 'N' 인 경우의 시간이었는데, 여기서 계속 걸렸다. 한참 해멨는데도 풀리지 않고, 통과한 소스 코드와 비교해도 다른 점을 찾기가 어려웠다. 그런데 테스트용으로 넣었던 printf() 구문을 빼자, 놀랍게도 엄청 빠르게 성공했다.... 테스트용 코드는 반드시 없애놓고 제출해야겠다.

 

(SRM 318 DIV 2 - Easy : Just test all cases, and find max value)

 

SRM 318 DIV 2 - Mid : Finally Solved, but my answer was not elegant.

[Problem]  A person is going home. S/He can jump or walk at any time. Return the minimum time required to get home.  - Walking speed is 1 unit / 1 sec.  - Jumping needs fixed move distance / fixed required time. (i.e. we can jump only exactly 5 unit / 3 secs)   [Solving] It was hard to analyze what this problem says. The key point is, we don't have to jump in the direction which directly reaches home. For example. Jump unit = 3, and total Distance = 5, we can get home with only 2 jumps because 3 + 3 > 5.   [Thought & Tips Found]  - By seeing some other's code, I realized that my code is not clean, and has so many 'if - expression's.  - In problems like this case, it is very useful to use ceil(X)  / floor(X).     Code became much cleaner than before.

 

SRM 318 DIV 2 - Hard : Did not solved. Solved after reading editorials.

[Problems] Throwing darts - 2 points for short distance, 3 points for long distance. Probability that a dart is successful is given. Two cases have each success probability. If we want to get (not less than) W points in N tries, return the probabilty to win.   [What was hard for me to solve] At first, I misunderstood the problem : I thought that the answer should be the sum of all probability to win. However, it wasn't.  Understanding problem was so hard, because the term 'winning probability' in this problem was quite different from well-known 'winning probability'. In this problem, every 'lower probability to win' is not added to the total winning probability.   [Tips]  - We can write this code for two method - ( iterative / recursive)  - When using cache, if we need to deal with the case that the index is negative,    we can try the method shown below.   double p1, p2; double prob[MAX_W][MAX_N]; struct SimplifiedDarts{ double get(int i, int j) { if(i < 0) return prob[0][j]; else return prob[i][j]; } double tryToWin(int W, int N, int P1, int P2) { p1 = P1 / 100.0; p2 = P2 / 100.0; // prob[W][N]. if (W > 0 and N == 0) -> prob == 0 for(int i = 1; i <= W; i++) prob[i][0] = 0.0; // prob[W][N]. if (W == 0 and N >= 0) -> prob == 1 for(int i = 0; i <= N; i++) prob[0][i] = 1.0; for(int i = 1; i <= W; i++) for(int j = 1; j <= N; j++) prob[i][j] = max(p1*get(i-2, j-1) + (1-p1)*get(i, j-1), p2*get(i-3, j-1) + (1-p2)*get(i, j-1)); return prob[W][N] * 100; } };

 

 

SRM 318 DIV 1 - Mid : Failed. Referred from Editorials and others' codes.

[Problem] Roll a dice. Move to cells according to the die. Each cell has own value. Values can be negative or 0 or positive. Values are added to my score. (Repeat) Player can stop the game whenever he/she wants to. In this situation, calculate the maximum expected score that player can get.   [What was hard for me] At first, I could not understand the problem... After some times passed, I realized that threr is a recurrence relation in this problem. However, could not find the "Ending condition - when I should end this program".   [Solution] The idea to solve this, was that   - "Just throw the dice many, times!! Expected value will be closer and closer to the answer."  I was shocked. The ending condition was that - no much try is left.  Because there can be 'Errors' in floating point calculations, and so the calculated value, in most cases, never can be exactly same with the real answer. That was the key. Just make the approximation of answer, but make errors very small.   [Source] vector s; double cache[15][5000]; int n; struct CyclicGame{ double estimateBank(vector cells){ s = cells; for(int i = 0; i < 15; i++) for(int j = 0; j < 5000; j++) cache[i][j] = -1; n = cells.size(); return getProb(0, 5000); } // 현재 위치가 pos일 때, throws번 던져서 얻는 기대값을 반환한다. double getProb(int pos, int throws) { if(throws == 0) return 0; double& ret = cache[pos][throws]; if(ret != -1) return ret; double ans = 0; for(int i = 1; i <= 6; i++) { ans += (1/6.0) * ( s[(pos + i) % n] + getProb((pos + i) % n, throws - 1)); } return ret = (ans < 0) ? 0 : ans; } };

 

 

 

SRM 319 DIV 2 - Easy

[Problem] Count the number of changes of elements in a matrix to make the given matrix as a 'skew matrix'.   [Solving] Easy. Just convert to 'int' matrix and count that matrix[i][j] != -matrix[j][i].   [Tips] Very Useful Tips!!! - To extract numbers from the string like "1 2 -3 5 -112", use stringstream. string s = "11 -12 153 154 662"; stringstream ss; int num[5]; ss << s; // put string into stringstream for(int i = 0; i < 5; i++) ss >> num[i]; // store each numbers to 'int's

 

(SRM 319 DIV 2 - Mid : Just code it. Easy.)

 

SRM 319 DIV 2 - Hard

[Problem]  Find the values which satisfy the BST characteristics.   [Point]  - Do not actually implement the tree, but use arrays instead. (something like heap)  - If someone wants to find whether this tree is BST or not, check values recursively.       - This is stjepan's code. It checks whether the values of children are in the right interval, recursively.     (At first calling, we use it by calling rec( idx_of_root, minimum_value, maximum_value) )   [Tips / Notes]  - This checking is actually a DFS technique.

 

 

SRM 319 DIV 1 - Mid : Got RTE and saw editorial & others' codes.

[Problem]  A Binary serach tree is given. However, we have only the 'structure' of the tree, not the exact value.  This BST is formed from a string, by some specific rule. (complex)  In this case, calculate all string that makes this BST.   [My tries]  At first I thought this problem as 'counting the cases of 'topological sort'. (Like SRM 317 DIV 2 - Hard)  So, I tried to make all possible strings, and used bitmasks.  However, visiting 2^26 states were not possible in 2 seconds. Also, '2^26' long long ints exceed memory limit.  (I think It could have been possible if the number of state is less than 2^20)  I used memoization for 2^22 states, however, the execution time could not be more reduced.  So I gave up after two hours' combat, and read editorials.  Surprisingly, it was an combinatorial problem - which I never have tried.   [How to Solve]  In the string, root node should be in first position.  The key of this problem is, in the string, values that make left and right subtree do not limit each other.  Let's denote that T : root / L : values that make left subtree / R : values ~ right subtree.  For example, if we have one root, and 3 nodes in left subtree, one node in right subtree,  possible strings are : T L L L R / T L L R L / T L R L L / T R L L L  => 4.  => The number of interleaving (interleaving - 섞는 것) is => 4 choose 1 (4 C 1)  => Exact number of interleaving is : (numOfLeftDescendent + numOfRIghtDescendent) choose (numOfLeftDescendent)    Most important thing is, we can recursively calculate this number and multiply all values.  That could be answer - since in all independent events, the number of entire cases can be made  by multiplying number of all cases in each event.)    [Tips]  - When declaring a function, SPECIFY the exact role / return value / input arguments !     : Especially for RECURSIVE functions !!  - Before writing a program, carefully think the TIME COMPLEXITY.     : I used almost 2 hours to reduce execution time.  - Binomial Coefficients    - See the exact Definiton : http://en.wikipedia.org/wiki/Binomial_coefficient#Definition_and_interpretations    - Codes #define N 10 long long int bino[N+1][N+1]; int main(void) { // --------------------------------------------------------------- // 아래 3개의 for문을 를 합쳐서 한꺼번에 쓰면, 다음과 같다. memset(bino, 0, sizeof(bino)); for(int i = 1; i <= N; i++) for(int j = 0; j <= N; j++) bino[i][j] = (j == 0) ? 1 : bino[i-1][j-1] + bino[i-1][j]; // --------------------------------------------------------------- /* memset(bino, 0, sizeof(bino)); for(int i = 0; i <= N; i++) // for all n >= 0, n_C_0 = 1; bino[i][0] = 1; // memset을 한 이상, 이 세팅은 필요가 없다. // for(int j = 1; j <= N; j++) // for all k > 0, 0_C_k = 0; // bino[0][j] = 0; for(int i = 1; i <= N; i++) for(int j = 1; j <= i; j++) bino[i][j] = bino[i-1][j-1] + bino[i-1][j]; */ // --------------------------------------------------------------- printf("\n이항계수 계산을 모두 다 구하지 않고, \n한 값만 구하는 다른 방법!\n"); int a = 5; int b = 2; // we want to calculate 5 choose 3. long long int result = 1; for(int j = 0; j < b; j++) { result = result * (a-j) / (j+1); // 직접 계산식에 따라 계산하는 방법임. // 뒤쪽 j+1을 b-j와 같이 써서는 안 된다. int형끼리의 게산이므로, 정수끼리 정확히 약분되야만 한다. // result * (a-j) 은 반드시 (j+1)로 나누어 떨어진다. 왜 그런지 생각해보자. } printf(" => %d Choose %d = %lld\n", a, b, result); return 0; }

 

(SRM 320 DIV 2 - Easy : 쉬움)

 

 

SRM 320 DIV 2 - Mid

[Problem]  Compare the given numbers in two strings which are consisted of numbers and factorials.  (ex. 6!! vs 876, 0! vs 1, 9! vs 99999999 )   [Key Point]  - Carefully deal with the all cases,  : especially [0(!...!) vs 1(!...!)] and [0 vs 1(!..!)] and ... etc.   [Experiences]  - Before writing the code, think all possible cases. Do Not Write the code before thinking!!  - Do not submit the code even if it passed all test cases.    - Statistically, it will probably be more dangerous & harmful to my score.    - Implement "enough" new test cases.       + Test the cases that even if it strongly be seems to work fine.   [Tips]  - When comparing two values, if we have to make duplicated codes     as almost same operations are needed, "swapping" the two values are very useful.  - If we have to compare 'Factorial' values, it won't be able to get the exact value if the number is LARGE.     -> However, there is a way :         (Ex. 1677886162 >? 1*2*3*4*5* ... * (22) ) we can compare with the 중간값s.     -> If 중간값 is bigger than other number, the result will also be.  - Here is the code.   [Another solution]  - http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm320     : But I cannot understand why the condition in while(...) should be x<=15. Why 15??

 

 

SRM 320 DIV 2 - Hard

I'll skip the problem statement. This problem is easy. Just code it.  This problem is almost same with "Getting the maximum length of Longest Increasing Sequence".   [Tips]  - I solved this problem usign recursive function. (DP) // global variables int n; vector< pair, double> > tp; double cache[51]; struct ContestSchedule{ double expectedWinnings(vector con){ n = con.size(); for(int i = 0; i < n; i++) { long long int s, t; int p; stringstream ss(con[i]); ss >> s >> t >> p; tp.push_back(make_pair(make_pair(s, t), p/100.0)); } sort(tp.begin(), tp.end()); for(int i = 0; i <= n; i++) cache[i] = -1; return solve(-1); } double solve(int pos) { double &ret = cache[pos+1]; if(ret != -1) return ret; long long int end = 0; if(pos != -1) end = tp[pos].first.second; double ans = tp[pos].second; for(int next = pos + 1; next < n; next++) { if(end <= tp[next].first.first) ans = max(ans, tp[pos].second + solve(next)); } return ret = ans; } };    - But also, there was another implementation (Kankuro's code) // global variables int n; vector, double> > tp; double res[50]; struct ContestSchedule{ double expectedWinnings(vector con){ n = con.size(); for(int i = 0; i < n; i++) { long long s, t, p; stringstream ss(con[i]); ss >> s >> t >> p; tp.push_back(make_pair(make_pair(s, t), p/100.0)); } sort(tp.begin(), tp.end()); double ans = 0; for(int i = 0 ; i < n; i++) { double cur = 0; for(int j = 0; j < i; j++) if(tp[j].first.second <= tp[i].first.first) cur = max(cur, res[j]); res[i] = cur + tp[i].second; ans = max(res[i], ans); } return ans; } };   [Tips]  - At First, I used two vectors : vector<pair<startTime, endTime>> and vector<pair<startTime, probability>>     I expected that sorting two vectors respectively will give me same order, although two vectors are different.     (because two vector have the same order of 'first' element.)     However, it didn't. While sorting the 'pair', if the 'first' element is same, it compares the second element.     Therefore I got failed to pass system test (at the last case).