TopCoder TCO08 Qualification Round 3(3A)

TCO08 퀄 3라운드 문제를 연습삼아 풀어보았다..
이번 3라운드는 매치도중 시스템이 다운되는바람에 한번 더 열렸다.. -_-;;
그로인해 손해본사람도 있고.. 땡잡은사람도 있고.. ㅋㅋㅋㅋ

다행히 두개 다 연습세션에 추가되었다.. 먼저 열린게 Q3A, 나중에 열린게 Q3..
퀄 라운드 500점짜리는 죄다 DP문제의 연속이었다.. 우웩!!!!!!!!
그러다 마지막에 열린 매치는 DP문제가 떨어졌는지.. 다른 유형의 문제가 나왔다..
어떻게 하루만에 문제를 만들고 테스트케이스까지 만들수 있는지..;; 예비문제를 미리 준비하고있었나..?
아니면 Online Round1에 나올문제가 미리..?? 그렇담 좀 아쉬운데..;;;



[500] RandomNetwork

Problem Statement
     
You are a given a vector <string> network, describing a network. Character j of element i of network is either 'Y' or 'N', indicating whether or not there is a direct path from node i to node j. The number of nodes in the network is equal to the number of elements in network.
A packet begins at node 0. In every step, it travels from its current node to a randomly selected connected node. All random selections are made with equal probability. Return a vector <double>, where the i-th element is the probability that the packet is at node i after taking exactly steps steps.
Definition
   
Class:
RandomNetwork
Method:
probableLocation
Parameters:
vector <string>, int
Returns:
vector <double>
Method signature:
vector <double> probableLocation(vector <string> network, int steps)
(be sure your method is public)
   
 
Notes
-
Each element of the return value must be within 1e-9 absolute or relative error of the actual answer.
-
The network is a directed graph, so a path from i to j does not necessarily mean there is a path from j to i.
Constraints
-
network will contain between 2 and 50 elements, inclusive.
-
Each element of network will contain N characters, where N is the number of elements in network.
-
Each character of each element of network will be either 'Y' or 'N'.
-
The i-th character of the i-th element of network will be 'N'.
-
Each element of network will contain at least one 'Y'.
-
steps will be between 0 and 100, inclusive.
Examples
0)
 
   
{"NYYY", "YNYY", "YYNY", "YYYN"}
0
Returns: {1.0, 0.0, 0.0, 0.0 }
A tetrahedron, with all six edges bidirectional. We start at node 0, and make a single move, equally likely to any of the three other nodes.
1)
 
   
{"NYYY", "YNYY", "YYNY", "YYYN"}
2
Returns:
{0.3333333333333333, 0.2222222222222222, 0.2222222222222222, 0.2222222222222222 }
After 1 move, we have a 1/3 chance of being at any of the other 3 nodes. Each of them carries a 1/3 chance of returning to node 0, for a total of 1/3 * 1/3 + 1/3 * 1/3 + 1/3 * 1/3 = 3/9 = 1/3 chance. There is a 2/3 chance that the packet did not go back to node 0, thus a 2/9 chance of being at any of nodes 1, 2, or 3.
2)
 
   
{"NYY", "NNY", "NYN"}
5
Returns: {0.0, 0.5, 0.5 }
After the first step, we're equally likely to be at node 1 or node 2. After that, each step just bounces the packet back and forth between nodes 1 and 2.
3)
 
   
{"NYYNN", "NNYYN", "NNNYY", "YNNNY", "YYNNN"}
3
Returns: {0.375, 0.125, 0.0, 0.125, 0.375 }
 
4)
 
   
{"NYYY", "NNYY", "NNNY", "YNNN"}
3
Returns: {0.5, 0.1111111111111111, 0.1111111111111111, 0.2777777777777778 }
 
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으로 임의의 graph가 주어진다.. 0번 노드에서 packet을 전송할때 nstep 이후에 각 노드에 packet이 위치할 확률을 구하는 문제..

전형적인 DP문제이다..
음.. 은퇴한 이후에 감이 많이 떨어진것같다..(뭐 원래 못하긴했지만) 특히나 DP는 도저히 모르겠다.. ㅠ_ㅠ
DPDPDPDPDPDPDPDPDPDPDPDPDP.... 젠장젠장젠장젠장젠장젠장젠장젠장....


다음과 같은 점화식을 세울 수 있다..

dp[i][j] = i번 step에 packet이 j 위치에 있을 확률이라고 한다면..
dp[0][0] = 1.0
dp[i][j] = sum(dp[i-1][k] / (vertex k의 outdegree)) (k는 0 <= k < n 이고 k->j 의 edge가 있을때)

별로 어렵지않은 문제인데.. 열라 삽질끝에.. 293.33 점에 간신히 submit..! -_-;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class RandomNetwork {
  9 public:
 10
 11 vector <double> probableLocation(vector <string> network, int steps)
 12 {
 13     int graph[100][100];
 14     int n;
 15     int i, j, k, l, cnt;
 16     char buf[100];
 17     double dp[200][200];
 18     vector<double> res;
 19
 20     n = network.size();
 21     memset(graph, 0, sizeof(graph));
 22
 23     for (i = 0; i < n; i++) {
 24         strcpy(buf, network[i].c_str());
 25         for (j = 0; j < n; j++) {
 26             if (buf[j] == 'Y') {
 27                 graph[i][j] = 1;
 28             }
 29         }
 30     }
 31
 32     memset(dp, 0, sizeof(dp));
 33     dp[0][0] = 1.0;
 34     for (i = 1; i <= steps; i++) {
 35         for (j = 0; j < n; j++) {
 36             for (k = 0; k < n; k++) {
 37                 cnt = 0;
 38                 for (l = 0; l < n; l++) {
 39                     if (graph[k][l])
 40                         cnt++;
 41                 }
 42                 if (graph[k][j]) {
 43                     dp[i][j] += dp[i-1][k] / (double)cnt;
 44                 }
 45             }
 46         }
 47     }
 48     for (i = 0; i < n; i++) {
 49         res.push_back(dp[steps][i]);
 50 printf("..%lf\n", dp[steps][i]);
 51     }
 52     return res;
 53 }
 54
 55 };

[500] CableDonation

Problem Statement
     
A local charity is asking for donations of Ethernet cable. You realize that you probably have a lot of extra cable in your house, and make the decision that you will donate as much cable as you can spare.
You will be given a vector <string> lengths indicating the length (in meters) of cables between each pair of rooms in your house. You wish to keep only enough cable so that every pair of rooms in your house is connected by some chain of cables, of any length. The jth character of lengths[i] gives the length of the cable between rooms i and j in your house. A value of '0' (zero) indicates no cable, values of 'a' through 'z' indicate lengths of 1 through 26, and values of 'A' through 'Z' indicate lengths of 27 through 52.
If both the jth character of lengths[i] and the ith character of lengths[j] are greater than 0, this means that you have two cables connecting rooms i and j, and you can certainly donate at least one of them. If the ith character of lengths[i] is greater than 0, this indicates unused cable in room i, which you can donate without affecting your home network in any way.
You are not to rearrange any cables in your house; you are only to remove unnecessary ones. Return the maximum total length of cables (in meters) that you can donate. If any pair of rooms is not initially connected by some path, return -1.
Definition
   
Class:
CableDonation
Method:
cable
Parameters:
vector <string>
Returns:
int
Method signature:
int cable(vector <string> lengths)
(be sure your method is public)
   
 
Constraints
-
lengths will contain between 1 and 50 elements, inclusive.
-
The length of each element of lengths will be equal to the number of elements in lengths.
-
Each character in lengths will be a letter ('a'-'z', 'A'-'Z') or '0' (zero).
Examples
0)
 
   
{ "abc",
  "def",
  "ghi" }
Returns: 40
You can part with the following cables:
length 1 in room 0
length 5 in room 1
length 9 in room 2
length 4 between rooms 0 and 1
length 7 between rooms 0 and 2
length 6 between rooms 1 and 2
length 8 between rooms 1 and 2
for a total of 40 meters.
1)
 
   
{ "a0",
  "0b" }
Returns: -1
The two rooms are not connected.
2)
 
   
{ "0X00",
  "00Y0",
  "0000",
  "00Z0" }
Returns: 0
You have no unnecessary cable.
3)
 
   
{ "Az",
  "aZ" }
Returns: 105
 
4)
 
   
{ "0top",
  "c0od",
  "er0o",
  "pen0" }
Returns: 134
 
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.

각 room을 연결하는 chain의 길이가 주어진다.. 모든 room이 연결된 상태를 유지하기위해 뺄수있는 chain의 길이의 합을 최대화하는 문제..

별다른 응용이 없는 단순 MST 문제이다.. -_-;;

매치도중 많은사람들이 fail했는데.. 아마도 문제파악을 잘 못하고 greedy 접근방법으로 시도한 것 같다..
접근방법만 잘 찾았다면 쉽게 풀수 있었을듯..

나는 그냥 내꺼 MST 라이브러리 갖다 붙이고.. 조금 코딩해서 submit하니깐.. 411.97 점..
 

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <string>
  5 #include <vector>
  6 using namespace std;
  7
  8 typedef struct _edge {
  9     int v1, v2;
 10     int dist;
 11 } EDGE;
 12 EDGE edge[1000000];
 13 int union_no[1000];
 14 int edge_cnt, n;
 15
 16 int comp(const void* a, const void* b)
 17 {
 18     EDGE* x, *y;
 19     x = (EDGE*)a;
 20     y = (EDGE*)b;
 21     if (x->dist < y->dist)
 22         return -1;
 23     else if (x->dist > y->dist)
 24         return 1;
 25     return 0;
 26 }
 27 int union_find(int u)
 28 {
 29     int temp = u;
 30     while (union_no[temp] != temp)
 31         temp = union_no[temp];
 32     return temp;
 33 }
 34
 35 class CableDonation
 36 {
 37 public:
 38
 39 int cable(vector <string> lengths)
 40 {
 41     int i, j;
 42     char buf[1000];
 43     int r1, r2;
 44     int sum, cnt;
 45     n = lengths.size();
 46
 47     for (i = 1; i <= n; i++) {
 48         union_no[i] = i;
 49     }
 50
 51     edge_cnt = 0;
 52     sum = 0;
 53     for (i = 0; i < n; i++) {
 54         strcpy(buf, lengths[i].c_str());
 55         for (j = 0; j < n; j++) {
 56             if (buf[j] == '0')
 57                 continue;
 58             else if (buf[j] >= 'a' && buf[j] <= 'z') {
 59                 edge[edge_cnt].v1 = i;
 60                 edge[edge_cnt].v2 = j;
 61                 edge[edge_cnt].dist = buf[j] - 'a' + 1;
 62                 sum += edge[edge_cnt].dist;
 63             }
 64             else {
 65                 edge[edge_cnt].v1 = i;
 66                 edge[edge_cnt].v2 = j;
 67                 edge[edge_cnt].dist = buf[j] - 'A' + 27;
 68                 sum += edge[edge_cnt].dist;
 69             }
 70             edge_cnt++;
 71         }
 72     }
 73     qsort(edge, edge_cnt, sizeof(EDGE), comp);
 74     cnt = 0;
 75     for (i = 0; i < edge_cnt; i++) {
 76         r1 = union_find(edge[i].v1);
 77         r2 = union_find(edge[i].v2);
 78         if (r1 == r2)
 79             continue;
 80         else if (r1 > r2)
 81             union_no[r2] = r1;
 82         else
 83             union_no[r1] = r2;
 84         cnt++;
 85         sum -= edge[i].dist;
 86     }
 87     if (cnt != n-1)
 88         return -1;
 89     return sum;
 90 }
 91
 92 };

나같은경우 Q1에서 통과하는바람에 Q2, Q3은 참여를 못했는데..
Q2랑 Q3은 Q1과 다르게 상당히 많은 contestant가 참여했고.. 완전 피튀기는 전쟁이었다..

내일 Online Round가 시작된다..
어휴.. 완전 ㅎㄷㄷㄷ 이던데.. 과연 잘할수있을까.. ;;;;