TopCoder SRM 409 Div 1 (완료)

어제 밤 12시에 열린 매치.. 엄청나게 많은 사람들이 참가했다.. 총 1706명.. 한국사람은 무려 56명이 참가했다.. 아마 역대 최다가 아닌가 생각된다.. 본격적으로 ACM 시즌 시작인가? ㅎㅎ 덕분에 무지 흥미진진한 매치였다.. 이번에는 평소보다 문제가 쉬웠는데 또 한문제밖에 풀지 못했다.. 아.. 아쉽.. 600점짜리 문제를 다 잘 풀어놓고.. 막판에 결정적인 실수를 하나 하고 말았다.. 요즘 열대야 때문에 다들 밤에 잠을 못이루겠지만.. 나는 이문제 틀려서 억울해서 잠을 못이뤘다.. 젠장.. rating은 6점 상승.. -_- 어쨋든 좋은 경험이었다.. 다음엔 꼭 level2를 풀어주리라..

어마어마한 참가자들.. SRM에서 1700명 넘게 참가한적도 처음보는거같고.. 그중에 한국인이 무려 56명이나 참가했다.. 와.. 탑코더가 점점 유명해지는구나..~

Level1 - OrderedSuperString

Problem Statement
     
A string X is an ordered superstring of the vector <string> words if
Each element of words is a substring of X.
There exists a sequence of indices x_1 <= x_2 <= ... <= x_n, where n is the number of elements in words. For each element k of words, where k is a 1-based index, there is an occurrence of words[k] that starts at the x_k-th letter of X.
For example "abca" is an ordered superstring of {"abc", "ca"}, but "cabc" is not.
Given a vector <string> words, return the length of its shortest ordered superstring.
Definition
   
Class:
OrderedSuperString
Method:
getLength
Parameters:
vector <string>
Returns:
int
Method signature:
int getLength(vector <string> words)
(be sure your method is public)
   
 
Constraints
-
words will contain between 1 and 50 elements, inclusive.
-
Each element of words will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive.
Examples
0)
 
   
{"abc","ca"}
Returns: 4
This is the example from the problem statement. The shortest ordered superstring is "abca". The sequence of indices is {0, 2}. There is an occurrence of "abc" starting at character 0 of "abca", and there is an occurrence of "ca" starting at character 2 of "abca".
1)
 
   
{"a","a","b","a"}
Returns: 3
Although the given words are all substrings of "ab", they do not appear in the proper order. The shortest ordered superstring is "aba".
2)
 
   
{"abcdef", "ab","bc", "de","ef"}
Returns: 6
 
3)
 
   
{"ab","bc", "de","ef","abcdef"}
Returns: 12
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

input으로 여러개의 string이 들어온다.. 이 string을 순서대로 붙여서 만들 수 있는 가장 짧은 string을 구하기.. string을 붙일 때 중첩이 가능하다.. 그러나 이전에 앞에서 붙였던 string의 index보다 더 앞에 붙일수는 없다.. 예를들어 {"abc", "bcd", "de", "f"} => "abcdef" 가 되지만, {"abcd", "de", "bcd"} => "abcdebcd" 가 된다..

코딩은 그냥 greedy하게 앞에서부터 붙였다.. 이때 바로 앞에서 붙였을때의 index와 현재까지 만들어진 string의 길이를 기억해두면 편하다..

음.. 쉬운문제인데 좀 오래걸렸다.. 문제를 이해하는데 좀 오래걸리고.. 코딩하는데도 좀 오래걸렸나..?

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class OrderedSuperString {
  9 public:
 10
 11 int getLength(vector <string> words)
 12 {
 13     int n, i, j, k, len2;
 14     int idx[100], len[100];
 15     char w[100][100];
 16     char str[10000];
 17     n = words.size();
 18     for (i = 0; i < n; i++) {
 19         strcpy(w[i], words[i].c_str());
 20         idx[i] = 0;
 21     }
 22     memset(str, 0, sizeof(str));
 23     strcpy(str, w[0]);
 24     idx[0] = 0;
 25     len[0] = strlen(w[0]);
 26     for (i = 1; i < n; i++) {
 27         len2 = strlen(w[i]);
 28         for (j = idx[i-1]; j <= len[i-1]; j++) {
 29             for (k = 0; k < len2; k++) {
 30                 if (w[i][k] != str[j+k] && j+k < len[i-1]) {
 31                     break;
 32                 }
 33             }
 34             if (k == len2) {
 35                 for (k = 0; k < len2; k++) {
 36                     str[j+k] = w[i][k];
 37                 }
 38                 if (j+k > len[i-1]) {
 39                     len[i] = j+k;
 40                     str[j+k] = 0;
 41                 }
 42                 else {
 43                     len[i] = len[i-1];
 44                 }
 45                 idx[i] = j;
 46                 break;
 47             }
 48         }
 49     }
 50 printf("str = %s\n", str);
 51     return len[n-1];
 52 }
 53
 54 };

Level2 - MagicalSpheres

Problem Statement
     
Once upon a time, there lived a powerful wizard who created spheresCount magical spheres. These spheres, when connected together, were a source of unimaginable power. To prevent anyone else from using them, the wizard created fakeSpheresCount spheres that are indistinguishable from the real ones, but don't hold any magical power.
You are determined to find out which spheres are real, and use them to rule the world. To accomplish this, you want to gather a team of gnomes to try every combination of spheresCount spheres out of (spheresCount + fakeSpheresCount) spheres, even if it takes centuries. You will assign combinations to each gnome beforehand, and you will not test any combination more than once. Unfortunately, the gnomes have a labor union that won't allow some gnomes to have more work than others. Therefore, you must select a team size that will allow you to assign an equal number of combinations to each gnome.
Return the maximum possible team size less than or equal to gnomesAvailable that allows even distribution of the work.
Definition
   
Class:
MagicalSpheres
Method:
divideWork
Parameters:
int, int, int
Returns:
int
Method signature:
int divideWork(int spheresCount, int fakeSpheresCount, int gnomesAvailable)
(be sure your method is public)
   
 
Constraints
-
spheresCount will be between 1 and 1,000,000,000, inclusive.
-
fakeSpheresCount will be between 1 and 1,000,000,000, inclusive.
-
availableGnomes will be between 1 and 100000, inclusive.
Examples
0)
 
   
3
1
3
Returns: 2
We have a total of four spheres, lets call them {a,b,c,d}. We need to check all triplets to find which of them are real. The different triplets are: {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}. Since there are four possibilities to check, we can divide it between two gnomes, by assigning two to each of them.
1)
 
   
3
3
50
Returns: 20
With three fake spheres, there are 20 triplets to check. You can use 20 gnomes and assign one of the triplets to each of them.
2)
 
   
4
3
4
Returns: 1
 
3)
 
   
15634
456
5000
Returns: 4990
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

문제는 진짜 magical sphere가 몇개 있고.. 가짜도 몇개 있고.. gnome이 이중에 몇번을 .. 어쩌구.. 설명하자면 복잡하고.. 간단히 nCr 을 나눌 수 있는 g보다 작은 수 중 가장 큰수 구하기 이다.. 여기서 n = s+f, r = s 가 된다..

우선 1부터 g까지 루프를 돌면서 그 수가 nCr 을 나눌 수 있는지 판단한다..
어떤수로 나눠지는지 아닌지 알려면 factoring(소인수분해)을 하고 각 factor의 개수를 비교하면 된다..
nCr의 factor를 구하기 위해서 다음과 같이 바꾼다.. nCr = n! / ((n-r)! * r!)
어떤 n! 에 소인수 k가 몇번 들어가있는지는 이미 잘 알려진 공식에 의해 쉽게 구할 수 있다..
이 내용들을 대략 조합해서 풀면 된다.. ㅎㅎ

이 문제는 정말 아쉽게 fail 했다.. 접근 방법까지 잘 찾았는데.. 결국 코드에 약간의 문제가 있었다.. 비슷한 코드가 좀 있어서 마구 copy & paste를 남발했는데.. 결국 붙여놓고 고쳐야 할 부분을 깜빡하고 말았다.. ㅠ_ㅠ 결국은 system fail..

근데 매치 끝나고 고쳐서 서밋해보니 딱 하나의 case에서 TLE가 났다.. 이건 뭥미.. prime factor들의 개수를 다 저장하고 나중에 넘치는지 모자르는지 구했는데.. 그것보다 각 prime factor에 대해서 개수를 구하고 개수가 모자르면 바로 break 하는 방법으로 고쳤다.. 그리고 나도 남들처럼 prime factor 개수 구하는부분을 함수로 만들어 보았다..;;

참고로 이문제는 UVa 10139 - Factovisors 문제와 연관이 있다.. 좋은 문제..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 char is_prime[100001];
  9 int prime[10000];
 10 int prime_cnt;
 11
 12 void sieve()
 13 {
 14     int i, j;
 15     prime_cnt = 0;
 16     memset(is_prime, -1, sizeof(is_prime));
 17     is_prime[0] = is_prime[1] = 0;
 18     for (i = 2; i <= 100000; i++) {
 19         if (is_prime[i]) {
 20             for (j = 2; i * j <= 100000; j++)
 21                 is_prime[i*j] = 0;
 22             prime[prime_cnt++] = i;
 23         }
 24     }
 25 }
 26
 27 int n_div(int a, int b)
 28 {
 29     int cnt;
 30     long long temp;
 31     cnt = 0;
 32     temp = b;
 33     while (temp <= a) {
 34         cnt += (a / temp);
 35         temp *= b;
 36     }
 37     return cnt;
 38 }
 39
 40 class MagicalSpheres {
 41 public:
 42
 43 int divideWork(int s, int f, int g)
 44 {
 45     int i, cnt, n;
 46     long long temp;
 47     sieve();
 48     for (n = g; n > 1; n--) {
 49         temp = n;
 50         for (i = 0; i < prime_cnt && prime[i] <= n; i++) {
 51             if (temp % prime[i] == 0) {
 52                 cnt = 0;
 53                 while (temp % prime[i] == 0) {
 54                     cnt++;
 55                     temp /= prime[i];
 56                 }
 57                 if (n_div(s+f, prime[i]) - n_div(s, prime[i]) - n_div(f, prime[i]) - cnt < 0) {
 58                     goto X;
 59                 }
 60             }
 61         }
 62         return n;
 63 X: ;
 64     }
 65     return 1;
 66 }
 67
 68 };

Level3 - GridColoring

Problem Statement
     
Given a rectangular grid where all the cells are initially white, you perform the following procedure K times:
Select a cell from the grid at random, and call it A
Select a cell from the grid at random, and call it B
Color all the cells in the rectangle bounded by A and B
Each cell is selected at random, with uniform distribution, and each selection is independent from the other selections. It's possible that A and B correspond to the same cell.
For example, the image below shows a 5x7 grid where the selected pairs could have been (row, column):
(0,1); (3,2)
(3,6); (4,0)
(0,6); (0,5)
Resulting in a grid with 22 colored cells and 13 white cells.

You are given ints rows and cols, the dimensions of the grid. Return the expected number of colored cells after K steps.
Definition
   
Class:
GridColoring
Method:
area
Parameters:
int, int, int
Returns:
double
Method signature:
double area(int K, int rows, int cols)
(be sure your method is public)
     
 
Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
K will be between 0 and 100, inclusive.
-
rows will be between 1 and 1000, inclusive.
-
cols will be between 1 and 1000, inclusive.
Examples
0)
 
   
1
2
1
Returns: 1.5
The grid has two cells. The probability that both of them will get colored is 0.5, and the probability that only one of them will get colored is 0.5. So the expected value is 0.5 * 2 + 0.5 * 1 = 1.5.
1)
 
   
2
2
1
Returns: 1.875
With the same grid as in the previous example, but two selections, the expected value rises to 1.875.
2)
 
   
1
2
2
Returns: 2.25
 
3)
 
   
3
5
7
Returns: 19.11917924647044
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

row by col 의 grid가 주어지고.. grid안의 두점을 random하게 선택해서 그 점으로 만들어지는 사격형을 모두 칠한다.. 이러한짓을 k번 반복할때.. 결국 한번도 안칠해지는 사각형 개수의 기대값 구하기..

에디토리얼을 참조해서 풀었다..

일단 임의의 cell (x, y)가 칠해질 확률을 구하면

col에 대해서 선택하는 두 점의 x좌표가 왼쪽 점은 x보다 작거나 같아야하고 오른쪽 점은 x보다 크거나 같아야 한다.. 따라서 경우의 수는 (x+1)*(col-x)가 된다.. 그러나 오른쪽을 선택하고 왼쪽을 선택하는 경우와 왼쪽을 선택하고 오른쪽을 선택하는 경우 두가지가 다르므로 * 2 를 해야한다.. 그러나 선택한 두 점이 같은경우가 있으므로 - 1 을 해야한다.. 따라서..

col에 대해서 x가 선택될 확률 px =  (2 * (x+1)*(col-x) -1 ) / (col*col)

row에 대해서 y가 선택될 확률 py = (2 * (y+1)*(row-y) - 1) / (row*row)

cell (x, y) 가 칠해질 확률 p(x, y) = px * py

이 짓을 k번 하는데.. k번을 했는데도 (x, y)가 안칠해지 확률 q = (1 - p(x, y))^k

결국 각 cell이 칠해질 확률은 한번도 안칠해지지만 않으면 되므로 1 - q가 된다..

따라서 모든 cell에 대해서 구한 1 - q를 다 더해주면 된다..

아.. 확률은 어렵구만..~

  1 #include <iostream>

  2 #include <cstdio>

  3 #include <algorithm>

  4 #include <vector>

  5 #include <string>

  6 #include <cmath>

  7 using namespace std;

  8

  9 double get_p(double x, double y, double rows, double cols)

 10 {

 11     double px, py;

 12     px = 2 * (x+1) * (rows-x) - 1;

 13     py = 2 * (y+1) * (cols-y) - 1;

 14     return px * py / (rows * rows * cols * cols);

 15 }

 16

 17 class GridColoring {

 18 public:

 19

 20 double area(int K, int rows, int cols)

 21 {

 22     int i, j;

 23     double sum, temp;

 24     sum = 0;

 25     for (i = 0; i < rows; i++) {

 26         for (j = 0; j < cols; j++) {

 27             temp = get_p(i, j, rows, cols);

 28             sum += 1.0 - pow(1.0-temp, (double)K);

 29         }

 30     }

 31     return sum;

 32 }

 33

 34 };