지난주 수요일 밤 12시에 열린 매치.. 오랜만에 div1에서 했는데.. 결과적으로 성적이 안좋았다.. ㅠ_ㅠ
간신히 하나 풀어서 서밋까지는 했는데 system fail.. ㅠ_ㅠ 250은 사실 좀 어이가 없었다..;
rating은 하락했지만.. 그래도 div1은 지켜냈다..;
Level1 - EquilibriumPoints
Problem Statement
There are N points situated on a straight line. The i-th point is located at coordinate x[i] and has a mass of m[i]. The locatıon of each point is strongly fixed and cannot be changed by any forces. Coordinates of all points are distinct.
When another point P is added on the line and its position is not fixed, the point falls under the impact of gravitational forces from each of the given N points. Points located to the left of P force it to the left, and points located to the right of P force it to the right. When two points are located a distance of d apart and have masses m1 and m2, the value of gravitational force between them is F = G * m1 * m2 / d^2, where G is some positive constant.
Point P is said to be an equilibrium point if the vector sum of gravitational forces from all points on P equals zero. In other words, the sum of the values of gravitational forces between P and all the points located to the left of P must be the same as the sum of the values of gravitational forces between P and all the points located to the right of P.
It is known that there always exist exactly N-1 equilibrium points. Return a vector <double> containing their coordinates sorted in ascending order.
Definition
Class:
EquilibriumPoints
Method:
getPoints
Parameters:
vector <int>, vector <int>
Returns:
vector <double>
Method signature:
vector <double> getPoints(vector <int> x, vector <int> m)
(be sure your method is public)
Notes
-
Each element of your return value must have an absolute or relative error less than 1e-9.
-
You don't need to know the mass of point P and the value of constant G to solve the problem.
Constraints
-
x will contain between 2 and 50 elements, inclusive.
-
m will contain the same number of elements as x.
-
Each element of x will be between 1 and 1000, inclusive.
-
Each element of m will be between 1 and 1000, inclusive.
-
x will be sorted in strictly ascending order.
Examples
0)
{1, 2}
{1, 1}
Returns: {1.5 }
When two points have the same mass, the equilibrium point is located exactly halfway between them.
1)
{1, 2}
{1, 1000}
Returns: {1.0306534300317156 }
When two points have distinct masses, the equlibrium point is located closer to the point with lesser mass.
2)
{1, 2, 3}
{1, 2, 1}
Returns: {1.4060952084922507, 2.5939047915077493 }
There are two equilibrium points located symmetrically with respect to the middle point of the input points.
3)
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.
이 문제는 equilibrium point를 찾는 문제이다..(????) 어떤 물체들이 일직선 상에 놓여있을때(1차원으로 가정) 오른쪽으로 발생하는 중력의 힘의 합과 왼쪽으로 발생하는 중력의 힘의 합이 같은 지점이 equilibrium point이다. 두 물체 사이에 작용하는 힘은 (질량1*질량2) / 거리^2 이다..!
갑자기 쌩뚱맞게 왠 equilibrium ??? 뭔 영화제목도 아니고.. -_-;
나는 이 문제를 다 읽자마자 바로 binary search (bisection method) 접근방법이 생각났다.. 그런데 전에도 한번 floating point number에 대해 binary search 시도했다가 time limit exceeded 난 적이 있어서.. 쉽게 시도를 못하고 삽질하다가.. 아무리 생각해도 모르겠고.. 그래서 포기하고 500점 보다가.. 500점은 더 어려운거같고.. ㅠ_ㅠ 결국 이판사판으로 250점 다시 열고 binary search를 시도했다..
챌 타임때 보니.. 다른사람도 다 나랑 같은방법으로 짠걸 보고.. 맞았구나.. 생각했는데.. 젠장.. system fail..!! 아니나다를까.. precision error로 틀린것이었다.. 이런 젠장!!! 오차범위를 10^-12로 했는데도 틀리다니!! 탑코더 정말 까다롭구만..! 다행히도 나와 같은 실수를 해서 fail한 사람이 좀 있었다..
여기서 얻을 수 있는 교훈은..?
나올 수 있는 답의 범위를 우선 찾고.. 그 사이에대해서 답을 binary search 했다..
You are organizing a party and have bought several pieces of cake for it. The weights of these pieces are given in the vector <int> weights, where each element corresponds to the weight of a single piece.
After looking at the pieces more carefully, you became worried that they have different weights and decided to make these differences smaller. In order to do this, you can make at most maxCuts cuts. With each cut you can choose one of the pieces you currently have and divide it into two distinct pieces. Note that each of these two pieces can be chosen again when making subsequent cuts.
Your goal is to produce cuts in such way that the difference between the maximal and the minimal pieces' weights becomes as small as possible. Find the best way of making cuts and return the optimal difference.
Definition
Class:
CakesEqualization
Method:
fairDivision
Parameters:
vector <int>, int
Returns:
double
Method signature:
double fairDivision(vector <int> weights, int maxCuts)
(be sure your method is public)
Notes
-
Your return value must have an absolute or relative error less than 1e-9.
Constraints
-
weights will contain between 1 and 50 elements, inclusive.
-
Each element of weights will be between 1 and 1,000,000,000, inclusive.
-
maxCuts will be between 1 and 100,000, inclusive.
Examples
0)
{1, 3}
2
Returns: 0.0
First, choose the piece with weight 3 and cut it into pieces with weights 1 and 2. Then, choose the piece with weight 2 and cut it into two pieces with weight 1. Now all pieces have the same weight, so the answer is 0.
1)
{1, 1, 1, 1, 1}
4
Returns: 0.0
Even though you are allowed to make 4 cuts, there is no sense in making any of them.
2)
{1, 3}
1
Returns: 0.5
The same case as in example 0, but now you are allowed to make only one cut. The best thing to do is to cut the piece with weight 3 into two pieces with weights 1.5.
3)
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으로 케익 조각의 크기가 vector로 주어지고 maxCut이 주어진다. 케익을 최대 maxCut만큼 자를 수 있다. 한번 자른 케익 조각을 또 자를 수 있다. 이렇게 해서 가장 큰 조각과 가장 작은 조각의 차이를 최소로 하고싶다. 그 최소값 구하기
이 문제는 일종의 greedy로 해결할 수 있다..
우선 가장 큰 케익을 자르는것을 원칙으로하는데.. 그렇다고 무조건 2등분을 하는것은 아니다.
예) {100, 300}, 2 => 300을 3등분을 해야 답이 나온다..
모든 케익 C[i] 에 대해서 각각 P[i] 등분을 한다고 생각하면 된다..
그래서 C[i] / P[i] 값이 가장 큰것에 대해서 P[i] 값을 1씩 증가시켜주면 된다..
구현은 매 iteration마다 sort해도 되고.. PQ 비스무리한 자료구조를 써도 된다..~
그리고.. precesion error에도 주의해야한다.. OTL
사실 Live 3635 - Pie 문제와 비스무리한데.. 저 문제를 풀어놓고도 못풀다니.. ㅠ_ㅠ
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <set>
7 #include <cmath>
8 using namespace std;
9 #define min(x, y) ((x) > (y) ? (y) : (x))
10
11 typedef struct _d {
12 int no, den;
13 } DATA;
14
15 bool operator < (const DATA& a, const DATA& b)
16 {
17 double x, y;
18 x = (double)a.no / (double)a.den;
19 y = (double)b.no / (double)b.den;
20 return y < x;
21 }
22
23 class CakesEqualization {
24 public:
25
26 double fairDivision(vector <int> weights, int maxCuts)
27 {
28 int size, i;
29 double min1, x, y;
30 DATA d1;
31 multiset<DATA> s;
32 multiset<DATA>::iterator it;
33
34 size = weights.size();
35 for (i = 0; i < size; i++) {
36 d1.no = weights[i];
37 d1.den = 1;
38 s.insert(d1);
39 }
40 it = s.begin();
41 x = (double)it->no / (double)it->den;
42 it = s.end();
43 it--;
44 y = (double)it->no / (double)it->den;
45 min1 = x - y;
46 for (i = 0; i < maxCuts; i++) {
47 it = s.begin();
48 d1 = *it;
49 s.erase(it);
50 d1.den++;
51 s.insert(d1);
52 it = s.begin();
53 x = (double)it->no / (double)it->den;
54 it = s.end();
55 it--;
56 y = (double)it->no / (double)it->den;
57 min1 = min(min1, fabs(x - y));
58 }
59 return min1;
60 }
61
62 };
Level3 - TeamManagement
Problem Statement
You are the manager of a newly formed football club and want to buy some players for your club. You identified that there are N potentially interesting players on the market and numbered them 0 to N-1. You don't have enough money to buy all these players, so you want to buy only K of them.
It appears however that buying players is not always easy. Some of the players are loyal to your club. To buy such a player you can just pay money for him. Other players are not loyal, and you can buy such a player A only if you have previously bought some player B, who is a friend of player A.
You are given a string loyalty, where the i-th character is 'Y' if the i-th player is loyal to your club, and is 'N' otherwise. You are also given a vector <string> friends, which describes which pairs of players are friends of each other. Each element has the format "A B", where A and B are the numbers of two players who are the friends of each other.
Friendship is symmetrical (if A is a friend of B, then B is a friend of A) and not necessarily transitive (if A is a friend of B and B is a friend of C, then C is not necessarily a friend of A). It is known that friends contains exactly N-1 elements and that for any two players A and B there exists a chain of players with numbers I0=A, I1, ..., Ik-1, Ik=B (k >= 1), where every two players consecutive in the chain are friends of each other (we'll call this property a connectedness of friendship relation). It is guaranteed that each player has at most 3 friends and that at least one player is loyal to your club.
A subset of K players is called possible if you can buy all players from this subset and only these players, in some order. You decided to choose some possible subset and to buy all players from it. If there are many such subsets, you choose one at random (all subsets have the same probability of being chosen).
You are now interested in the probability of buying each of the players. Return a vector <double> containing N elements, where the i-th element is the probability of buying the i-th player.
Definition
Class:
TeamManagement
Method:
getDistribution
Parameters:
int, int, vector <string>, string
Returns:
vector <double>
Method signature:
vector <double> getDistribution(int N, int K, vector <string> friends, string loyalty)
(be sure your method is public)
Notes
-
Each element of your return value must have an absolute or relative error less than 1e-9.
Constraints
-
N will be between 1 and 50, inclusive.
-
K will be between 1 and N, inclusive.
-
loyalty will contain exactly N characters.
-
Each character of loyalty will be 'Y' or 'N'.
-
At least one character of loyalty will be 'Y'.
-
friends will contain exactly N-1 elements.
-
Each element of friends will be formatted "A B" (quotes for clarity), where A and B are distinct integers between 0 and N-1, inclusive, with no extra leading zeros.
-
The friendship relation will be connected (see the statement for precise definition).
-
Each player will have at most 3 friends.
Examples
0)
5
3
{"0 1", "1 2", "2 3", "3 4"}
"NNYNN"
Returns:
{0.33333333333333337, 0.6666666666666667, 1.0, 0.6666666666666667, 0.33333333333333337 }
There are three possible subsets: {0, 1, 2}, {1, 2, 3} and {2, 3, 4}.
1)
4
3
{"2 0", "2 1", "2 3"}
"NNYN"
Returns: {0.6666666666666667, 0.6666666666666667, 1.0, 0.6666666666666667 }
All subsets that include player 2 are possible.
2)
6
4
{"4 3", "3 1", "3 0", "0 2", "0 5"}
"NNNNYY"
Returns:
{0.8571428571428572, 0.4285714285714286, 0.4285714285714286, 0.8571428571428572,
0.7142857142857143, 0.7142857142857143 }
The following 7 subsets are possible in this case: {1, 3, 4, 5}, {0, 3, 4, 5}, {0, 2, 4, 5}, {0, 2, 3, 5}, {0, 2, 3, 4}, {0, 1, 3, 5}, {0, 1, 3, 4}.
3)
6
1
{"3 0", "0 2", "0 4", "4 1", "2 5"}
"YYYNNN"
Returns: {0.33333333333333337, 0.33333333333333337, 0.33333333333333337, 0.0, 0.0, 0.0 }
When you wish to buy only one player, it must be a loyal player.
4)
7
7
{"3 1", "1 5", "5 4", "4 0", "4 6", "5 2"}
"NNNNNNY"
Returns: {1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0 }
Here you wish to buy all available players.
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.
