새벽 2시에 열린 매치.. 두문제를 안정적(?)으로 푼 덕분에 작년 9월 이후로 처음으로 blue로 복귀했다.. 휴우..; 역시.. 탑코더는 새벽 2시에 해야.. 등급이 오르는군..
방 3등 전체 51등..
흠.. 500을 푸는데 좀 오래걸렸다.. 좀더 빨리풀수있었는데..
blue로 복귀.. 오랜만에 다시 1군에 올라간다.
[250] TrophyShelf
Problem Statement
You have several trophies sitting on a shelf in a straight line. Their heights are given in a vector <int> trophies, from left to right. The shelf is positioned so that whenever people enter your room, they see it directly from the left side. In other words, the leftmost trophy is completely visible to the viewer, the next trophy in line is directly behind it, and so on. Unfortunately, tall trophies near the left side of the shelf might block the view of other trophies. A trophy is visible only if every trophy in front of it (from the viewer's perspective) is strictly shorter than it is. You wonder if rotating the shelf 180 degrees would increase the number of visible trophies. Return a vector <int> containing exactly two elements. The first element should be the number of trophies visible when viewing the shelf directly from the left side, and the second element should be the number of trophies visible when viewing the shelf directly from the right side.
Definition
Constraints
-
trophies will contain between 1 and 50 elements, inclusive.
-
Each element of trophies will be between 1 and 100, inclusive.
Examples
0)
{1,2,3,4,5}
Returns: {5, 1 }
When viewed from the left, each trophy is taller than all the trophies in front of it. However, when viewed from the right, the first trophy blocks the view of all the other trophies.
1)
{5,5,5,5}
Returns: {1, 1 }
Since all trophies have the same height, only the first is visible when viewed from each direction.
2)
{1,2,5,2,1}
Returns: {3, 3 }
This trophy shelf is symmetric.
3)
{1,4,2,5,3,7,1}
Returns: {4, 2 }
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.
숫자들이 주어지고.. 각각은 trophy의 높이를 말한다.. 왼쪽에서 보았을때 보이는 trophy와 오른쪽에서 보았을때 보이는 trophy의 개수 구하기..
앞에서부터 읽어서 구하고 다시 뒤에서부터 읽으면서 구했다.. 별다른 알고리즘이 필요없는.. -_-;
나름대로 빨리 이해해서 코딩했는데.. 그래도 남들보다 많이 늦었다.. 다들 왜이리 코딩속도가 빠른겨..;;
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 class TrophyShelf {
9 public:
10
11 vector <int> countVisible(vector <int> trophies)
12 {
13 int n, i;
14 int cnt1, cnt2, max1;
15 vector<int> res;
16 n = trophies.size();
17 cnt1 = 0;
18 max1 = -1;
19 for (i = 0; i < n; i++) {
20 if (max1 < trophies[i]) {
21 max1 = trophies[i];
22 cnt1++;
23 }
24 }
25 max1 = -1;
26 cnt2 = 0;
27 for (i = n-1; i >= 0; i--) {
28 if (max1 < trophies[i]) {
29 max1 = trophies[i];
30 cnt2++;
31 }
32 }
33 res.push_back(cnt1);
34 res.push_back(cnt2);
35 return res;
36 }
37
38 };
[500] CandidateKeys
Problem Statement
A database table consists of a set of columns called attributes, and a set of rows called entries. A superkey is a set of attributes such that each entry's values for those attributes forms a unique ordered set. That is, for any superkey, each pair of entries differs in at least one of the attributes contained within the superkey. A candidate superkey is a superkey such that no proper subset of its attributes forms a superkey. Return a vector <int> with exactly two elements. The first element should be the number of attributes in the smallest candidate superkey of the table, and the second element should be the number of attributes in the largest candidate superkey of the table. If there is no valid candidate superkey, return an empty vector <int> instead. The input is described by a vector <string> table. Each string in table represents one entry, while characters contained in the string are attribute values for that entry.
Definition
Notes
-
A proper subset of a superkey is a set of attributes that is formed by removing one or more attributes from the superkey.
Constraints
-
table will contain between 2 and 50 elements, inclusive.
-
Each element of table will contain between 1 and 10 characters, inclusive.
-
Each element of table will contain the same number of characters.
-
Each character in table will be an uppercase letter ('A'-'Z').
Examples
0)
{
"ABC",
"ABC",
"ABC"
}
Returns: { }
Since all entries are the same, there is no set of attributes that can differentiate between them. Therefore, this table has no candidate superkeys.
1)
{
"ABC",
"ABD",
"ABE"
}
Returns: {1, 1 }
There are four superkeys here: {column 0, column 1, column 2} {column 0, column 2} {column 1, column 2} {column 2} Note that the fourth superkey is a subset of all the other superkeys, so it is the only candidate superkey.
2)
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.
DB에 해당하는 table이 주어지고 여러개의 attribute를 조합해서 superkey를 만들고 싶을때 어떻게 조합해야 하는지.. 이때 최대 크기의 candidate key와 최소 크기의 candidate key 구하기..
candidate key가 되기위한 조건은 attribute set의 subset이 candidate key가 되면 안된다..
흠.. 위의 설명이 맞는지 잘 모르겠다.. 오랜만에 DB때 배웠던 지식이 나왔는데 하나도 기억이 안나는군.. ㅠ_ㅠ
super key와 candidate key 등을 다시한번 찾아봐야겠다..
attr의 개수가 최대 10개밖에 안되므로.. 가능한 모든 subset을 다 구했다.. (2^m) 그래서 얻은 값이 key가 될수있는지 전쌍 비교를 통해 무식하게 판단 (n^2)하고.. key로 가능한 경우.. 이전에 구한 다른key들의 subset인지를 또 판단했다.. 그래서 최종적으로 통과한 key를 후보에 넣고.. attr의 개수의 최대, 최소를 구했다..
attr의 subset은 bit연산을 통하여 하나의 integer로 표현하였다..
다른사람의 솔루션도 다 비슷한 듯..
이문제 코딩하다가 코딩이 너무 짜증나서 그냥 때려치고 1000점 짜리 문제를 열고 해석했는데.. 앞으로 그런짓은 하지말아야겠다.. ㅠ_ㅠ 오히려 시간만 낭비한꼴이되었다..
음.. 참고로 이문제는 SRM 366 GuitarConcert 문제랑 푸는방법이 비슷한거같기도 하다..
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 #define max(x, y) ((x) > (y) ? (x) : (y))
9
10 int check_subset(int u, int v)
11 {
12 if ((u & v) == v)
13 return 1;
14 return 0;
15 }
16
17 class CandidateKeys {
18 public:
19
20 vector <int> getKeys(vector <string> table)
21 {
22 int n, m, size;
23 int i, j, k, l;
24 int cnt, fl, bt;
25 int min1, max1;
26 char str[100][100];
27 char temp[100][100];
28 int candi[10000];
29 vector<int> res;
30
31 n = table.size();
32 m = table[0].size();
33 for (i = 0; i < n; i++) {
34 strcpy(str[i], table[i].c_str());
35 }
36 size = (1 << m);
37 cnt = 0;
38 for (i = 1; i < size; i++) {
39 l = 0;
40 for (k = 0; (1<<k) <= i; k++) {
41 bt = (1 << k);
42 if (bt & i) {
43 for (j = 0; j < n; j++) {
44 temp[j][l] = str[j][k];
45 temp[j][l+1] = 0;
46 }
47 l++;
48 }
49 }
50 //printf("i = %d\n", i);
51 fl = 1;
52 for (j = 0; j < n; j++) {
53 for (k = j+1; k < n; k++) {
54 //printf("temp[%d] = %s, temp[%d] = %s\n", j, temp[j], k, temp[k]);
55 if (!strcmp(temp[j], temp[k])) {
56 fl = 0;
57 break;
58 }
59 }
60 }
61 if (fl == 0) {
62 continue;
63 }
64 for (j = 0; j < cnt; j++) {
65 if (check_subset(i, candi[j]))
66 break;
67 }
68 if (j == cnt)
69 candi[cnt++] = i;
70 }
71 /*
72 printf("cnt = %d\n", cnt);
73 for (i = 0; i < cnt; i++) {
74 printf("candi[%d] = %d\n", i, candi[i]);
75 }
76 */
77 res.clear();
78 if (cnt == 0)
79 return res;
80 min1 = 1000000;
81 max1 = -1;
82 for (i = 0; i < cnt; i++) {
83 k = 0;
84 for (j = 1; j <= candi[i]; j*=2) {
85 if (candi[i] & j) {
86 k++;
87 }
88 }
89 min1 = min(min1, k);
90 max1 = max(max1, k);
91 }
92 res.push_back(min1);
93 res.push_back(max1);
94 printf("min1= %d, max1 = %d\n", min1, max1);
95 return res;
96 }
97
98 };
[1000] LittleTree
Problem Statement
In a rooted tree, a vertex V is at level L if the length of the shortest path between the root and V is L. Vertex U is said to be the parent of vertex V if U and V are connected by an edge, V is at level L, and U is at level L-1. A vertex U is an ancestor of vertex V if U lies along the shortest path from the root vertex to V. More formally, U is an ancestor of V if there exists a sequence of vertices U = W1, W2 ,..., Wk = V, such that Wi is the parent of Wi+1 for every 1 <= i < k. You're given a rooted tree and you wish to perform several augmentation operations on it. An augmentation operation consists of the following steps:
Choose a non-root vertex V.
Choose a vertex U, which is an ancestor of V.
Erase the edge from V to its parent.
Draw an edge from U to V so that U becomes the parent of V.
If V and U are at levels L1 and L2, respectively, then the cost of the augmentation operation described above is L1 - L2 - 1. A tree has height K if there exists some vertex at level K and no vertex is at level K+1. Given a tree and an int height, return the smallest total cost required to perform a sequence of augmentations on the tree such that the height of the resulting tree is less than or equal to height. For example, the following diagram illustrates augmenting the subtree rooted at vertex 2, which is augmented such that vertex 2 becomes a child of vertex 0 (which is the root vertex). This is also the cheapest way of transforming this tree of height 3 into a resulting tree of height 2.
0 0
\ / \
1 2 1
\ => / \
2 3 4
/ \
3 4
The tree contains exactly N vertices, and is described by a vector <string> edges. Concatenate the elements of edges to form a single-space separated list of strings of the form "parent,child" (quotes for clarity). Here, parent and child are integers with no leading zeros and are between 0 and N-1, inclusive, which represents that vertex child is a child of vertex parent. Each vertex will have exactly one parent except for the root vertex. Node 0 is the root vertex.
Definition
Class:
LittleTree
Method:
minCost
Parameters:
int, vector <string>, int
Returns:
int
Method signature:
int minCost(int N, vector <string> edges, int height)
(be sure your method is public)
Constraints
-
N will be between 2 and 100, inclusive.
-
height will be between 1 and N-1, inclusive.
-
edges will be formatted as described in the problem statement.
-
edges will contain between 1 and 50 elements, inclusive.
-
Each element of edges will contain between 1 and 50 characters, inclusive.
-
There will be exactly N-1 tree edges contained in edges.
-
edges will represent a tree.
Examples
0)
5
{"0,1 1,2 2,3 2,4"}
2
Returns: 1
This is the example from the problem statement.
1)
5
{"0,1 1,2 2,3 2,4"}
1
Returns: 3
The tree is the same from above, but we must get a resulting tree of height 1. One way to achieve this is to augment vertices 3 and 4 to become children of vertex 0, then augment vertex 2 to become a child of vertex 0, for a total cost of 5. However, we can do better by first augmenting the subtree rooted at vertex 2 to become a child of vertex 0, then augmenting vertices 3 and 4 to become children of vertex 0, for a total cost of 3.
2)
3
{"0,1 1,2"}
2
Returns: 0
This tree already has a height of 2, so we don't need to perform any augmentations.
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.
tree가 주어진다.. 이 tree의 height를 height로 바꾸고싶을때 얼마의 비용이 드는지 구하는 문제.. U를 root로 하는 subtree를 떼어다 V의 자식으로 붙일때 드는 비용은 Level(V)-Level(U)-1 이다..
