TopCoder SRM 394 Div 1

새벽 1시에 열린 매치.. 완전 안드로메다로 제대로 가버리고 말았다..~ 250점짜리부터 생각보다 빡세서 허우적거리다가.. 결국 어처구니없게 system test에서 fail하고 말았다.. ㅠ_ㅠ 조금만 신경썼으면 충분히 pass할 수 있었는데.. 아쉽군.. 쩝..;; 600점 짜리도 장난아니었고.. 900은 아직 문제도 모름..

Match editorial에 쓰여진 글.. 얼마나 공부해야 페트르처럼 될까..? -_-;;

A healthy turnout of 1500 coders was faced with tough problemsets in both divisions. However, that was no obstacle for Petr to show impressive times on both medium and hard and to win Division 1 achieving the best-ever rating of 3799 (and with such high rating revealing a bug in the rating distribution application, as well :))

방 12등 전체 428등..

완전 제대로 빵점이네.. -_-;; 문제가 어려운 덕분에.. 겨우 2부리그 추락은 막았다..;;;; 600점 이상은 푼사람은 커녕 submit 해본 사람도 없군 이런..;;



[250] RoughStrings

Problem Statement
     
Given a string s, its roughness is calculated as follows: Let c1 be the letter that appears most frequently in s, and let c2 be the letter that appears least frequently (c2 must appear at least once). The roughness of s is the number of occurrences of c1 minus the number of occurrences of c2.
 
You are allowed to modify s by erasing between 0 and n characters, inclusive (see example 1 for clarification). Return the minimum possible roughness that can be achieved by such a modification.
Definition
   
Class:
RoughStrings
Method:
minRoughness
Parameters:
string, int
Returns:
int
Method signature:
int minRoughness(string s, int n)
(be sure your method is public)
   
 
Constraints
-
s will contain between 1 and 50 characters, inclusive.
-
s will contain only lowercase letters ('a'-'z').
-
n will be between 0 and m-1, inclusive, where m is the number of characters in s.
Examples
0)
 
   
"aaaaabbc"
1
Returns: 3
We may remove one 'a' or one 'c' to obtain the minimal roughness of 3.
1)
 
   
"aaaabbbbc"
5
Returns: 0
One of the ways is to remove 'c' and all occurrences of 'a'.
2)
 
   
"veryeviltestcase"
1
Returns: 2
 
3)
 
   
"gggggggooooooodddddddllllllluuuuuuuccckkk"
5
Returns: 3
 
4)
 
   
"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
17
Returns: 0
 
5)
 
   
"bbbccca"
2
Returns: 0
Sometimes you may want to remove less than n characters.
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.

문자열과 integer n 이 주어지고.. 주어진 문자열에서 n개 이하의 문자를 지울 수 있다.. 이때 각 문자별로 남는 최대 개수와 최소 개수의 차를 구하는 문제..

처음에 greedy하게 생각해서 무조건 많은 문자에대해서 지우면 된다고 판단.. 한개씩 지우고 sort하고 다시 지우고 sort하고.. 해보니.. 마지막 case가 답이 나오지 않았다.. OTL.. ㅠ_ㅠ

마지막 케이스:
"bbbccca" => 이때는 a 하나만 지우면 답이 0이 되어서 최소가 된다..

그래서 마땅한 greedy 전략이 생각이 안나서.. backtracking으로 시도.. 적은 수의 문자를 지울때는 그 개수만큼 지우고.. 많은 수의 문자를 지울때는 한개씩 지웠다..

흠.. 맞았다고 생각했는데 결국 time limit으로 fail.. 흑흑.. 설마 time limit이 날까 했는데.. 생각보다 무식한 input이 있었다..;; 근데 time limit으로 fail한 사람이 은근히 많았다..

backtracking전략을 사용하되 pruining 조건을 하나 추가했다.. (적은 수의 문자를 빼다가 일단 많은 수의 문자를 빼기 시작하면 그때부터는 무조건 많은 수의 문자를 뺀다..)

다른사람 코드는 간단하던데.. 내꺼는 왜이렇지.. ㅠ_ㅠ;;;
뭔가 다른 쉬운 방법이 있는것 같다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define min(x, y) ((x) > (y) ? (y) : (x))
  8
  9 int min1;
 10
 11 int comp(const void* x, const void* y)
 12 {
 13     int* a = (int*)x;
 14     int* b = (int*)y;
 15     return *b - *a;
 16 }
 17
 18 void dfs(int n, int* cnt, int fl)
 19 {
 20     int i, j;
 21     int temp_cnt[26];
 22     if (min1 == 0)
 23         return ;
 24     qsort(cnt, 26, sizeof(int), comp);
 25     if (n < 0)
 26         return ;
 27     for (j = 25; j >= 0; j--) {
 28         if (cnt[j] != 0)
 29             break;
 30     }
 31     if (j < 0) {
 32         min1 = 0;
 33         return ;
 34     }
 35     min1 = min(min1, cnt[0]-cnt[j]);
 36
 37 //printf("cnt[0] = %d, cnt[%d] = %d\n", cnt[0], j, cnt[j]);
 38
 39     if (n <= 0)
 40         return ;
 41     for (i = 0; i < 26; i++) {
 42         temp_cnt[i] = cnt[i];
 43     }
 44     if (temp_cnt[j] <= n && fl == 0) {
 45         temp_cnt[j] = 0;
 46         dfs(n-cnt[j], temp_cnt, 0);
 47     }
 48     temp_cnt[j] = cnt[j];
 49     temp_cnt[0]--;
 50     dfs(n-1, temp_cnt, 1);
 51 }
 52
 53 class RoughStrings {
 54 public:
 55
 56 int minRoughness(string s, int n)
 57 {
 58     int cnt[26];
 59     int i, j, len;
 60     int a, b;
 61     char buf[100];
 62     strcpy(buf, s.c_str());
 63     len = strlen(buf);
 64     memset(cnt, 0, sizeof(cnt));
 65     for (i = 0; i < len; i++) {
 66         cnt[buf[i] - 'a']++;
 67     }
 68     qsort(cnt, 26, sizeof(int), comp);
 69     a = cnt[0];
 70     for (j = 25; j >= 0; j--) {
 71         if (cnt[j] != 0)
 72             break;
 73     }
 74     b = cnt[j];
 75     min1 = a - b;
 76     dfs(n, cnt, 0);
 77     printf("min1 = %d\n", min1);
 78     return min1;
 79 }
 80
 81 };

[600] CentersOfSymmetry

Problem Statement
     
We have n straight lines drawn in the Cartesian plane each described by two distinct points (x1[i], y1[i]) and (x2[i], y2[i]) lying on it. A center of symmetry is such a point that under a symmetry centered at this point the given configuration of lines goes into itself (i.e., the image of every given line under this symmetry is again one of the given lines). Return the number of centers of symmetry that the given system of lines has. Return -1 if there are infinitely many centers of symmetry.
Definition
   
Class:
CentersOfSymmetry
Method:
lineConfigurations
Parameters:
vector <int>, vector <int>, vector <int>, vector <int>
Returns:
int
Method signature:
int lineConfigurations(vector <int> x1, vector <int> y1, vector <int> x2, vector <int> y2)
(be sure your method is public)
   
 
Notes
-
A symmetry centered at point X works as follows. The image of a point A is such a point B that X is the midpoint of the line segment AB (note that if A = X, then also B = X). The image of a line is the union of images of all points on this line.
Constraints
-
x1 will contain between 1 and 50 elements, inclusive.
-
x1, y1, x2, y2 will all contain the same number of elements.
-
All the elements of x1, y1, x2 and y2 will be between -50 and 50, inclusive.
-
For each i either x1[i] and x2[i] or y1[i] and y2[i] will be distinct (i.e., two points defining a line will be distinct).
-
All the lines defined by (x1[i], y1[i]) and (x2[i], y2[i]) will be distinct.
Examples
0)
 
   
{0, 0}
{0, 0}
{1, -1}
{1, 1}
Returns: 1
A configuration of two intersecting lines has a single center of symmetry - their intersection point.
1)
 
   
{0, 0, 0, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 0, 0, 0, 0, 0, 0}
{1, 1, 1, 1, 1, 1, 1, 1, 1}
{1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 1
All the lines pass through the origin.
2)
 
   
{0, 1, 2}
{0, 1, -1}
{1, 2, 0}
{1, -1, 0}
Returns: 0
 
3)
 
   
{-10, 10}
{10, -10}
{-10, 10}
{-10, 10}
Returns: -1
Two parallel lines produce infinitely many centers of symmetry.
4)
 
   
{-50, -50, -50, -50}
{-50, -49, -48, -46}
{50, 49, 48, 46}
{50, 50, 50, 50}
Returns: 0
4 parallel lines with no centers of symmetry.
5)
 
   
{10, -35, -8, 7, -5, -8, -9, -50, -17, -18, -17, -26, -5, 23, 18, -7, -8, -6,
 -8, -12, 22, -7, 17, -48, -6, -16, -12, -14, 13, 30, 11, 17, -3, -5, -27, -30}
{-27, -25, -17, -26, -3, -19, -20, -33, -22, -21, -23, -38, -2, -32, -27, -8, -2, -5,
 -21, -7, -15, -15, -5, -27, 0, -19, -25, 1, -22, -11, -13, -38, -1, -6, -17, -32}
{16, -32, -11, 11, -3, -9, -8, -45, -16, -15, -19, -29, -2, 20, 24, -1, 4, -7,
 -5, -13, 16, -9, 29, -43, 2, -17, -15, -15, 17, 24, 23, 14, -7, -3, -24, -33}
{-35, -23, -26, -32, -3, -21, -18, -30, -20, -15, -27, -42, -5, -28, -35, 2, -5, -6,
 -15, -7, -13, -19, -9, -24, -12, -21, -34, 1, -28, -9, -17, -34, -9, 0, -15, -36}
Returns: 1
 
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.

to be updated..




[900] PseudoRandomKingdom

Problem Statement
     
There are n cities in a kingdom, numbered 0 through n-1. Some pairs of cities are connected by bidirectional roads in such a way that one can traverse all the cities in the kingdom by following these roads. There are exactly n-1 roads. The configuration of the roads is given as a vector <string> g, where the i-th element is a single-space separated list of the cities connected to city i by direct roads.
 
A spendthrift king devised the following scheme for taxing the roads: Each road is assigned a random integer between 0 and cost, inclusive, where each such integer is equally likely. This integer is the cost in dollars of traversing the road. John lives in one of the cities in the kingdom, and he is not happy to learn about these taxes. His fiancee Mary lives in another city, and he wants to go visit her. However, he only has savings dollars to spend on taxes. Return the probability that John will be able to reach Mary, regardless of where they each live. In other words, return the probability that the cost of travel between any two cities in the kingdom will not be greater than savings.
Definition
     
Class:
PseudoRandomKingdom
Method:
probabilityOfHappiness
Parameters:
vector <string>, int, int
Returns:
double
Method signature:
double probabilityOfHappiness(vector <string> g, int cost, int savings)
(be sure your method is public)
   
 
Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
g will contain n elements, where n is between 2 and 50, inclusive.
-
Each element of g will contain between 0 and 50 characters, inclusive.
-
Each element of g will be a single-space seperated list of distinct integers with no leading zeroes, each of which will be between 0 and n - 1, inclusive.
-
i will not appear in the list g[i].
-
i will appear in the list g[j] if and only if the number j will appear in the list g[i].
-
g will represent a graph with the properties described in the problem statement.
-
cost will be between 1 and 10, inclusive.
-
savings will be between 0 and 500, inclusive.
Examples
0)
 
   
{"1 2",
 "0",
 "0 3",
 "2"}
1
2
Returns: 0.875
This is a path of length 3 so no more than two roads can have cost 1. We have 8 possible graphs in all and only the one where every road has a cost of 1 does not suit us. Thus the answer is 7/8.
1)
 
   
{"1 2 3 4 5 6",
 "0",
 "0",
 "0",
 "0",
 "0",
 "0"}
10
19
Returns: 0.903158288086044
Almost all graphs satisfy us.
2)
 
   
{"1 2 3 4 5 6",
 "0",
 "0",
 "0",
 "0",
 "0",
 "0"}
10
0
Returns: 5.644739300537775E-7
Now John does not have any savings at all.
3)
 
   
{"1",
 "0"}
10
500
Returns: 1.0000000000000002
 
4)
 
   
{"9 6",
 "6 4",
 "8",
 "5",
 "7 1",
 "8 3",
 "1 0 8",
 "4",
 "2 5 6",
 "0"}
9
26
Returns: 0.350862063
 
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.

to be updated..