화요일 저녁 8시에 열렸던 매치.. 이번에는 한번 두문제 풀어보나 했지만.. 역시 실패했다.. ㅠ_ㅠ 가까스로 서밋까지는 했는데.. 어이없는 케이스에 챌당했다..;; 흠.. 예전에는 이런 케이스에는 안당했는데..;; 어쨋든 문제가 트리키에서 여러명 fail하고.. 덕분에 rating도 약간 올랐다.. 현재 1353점으로.. 탑코더 전체 rated member 9529명중에 2008등을 달리고있다.. -_- 음.. 그래도 2008년에 2008등 한번 해보네..
Level1 - OlympicCandles
Problem Statement
To celebrate the upcoming Thought Challenge Olympics, you are going to follow tradition and light candles. On the first night of the event, you will light one candle. At the end of the night, you will extinguish the candle. On each subsequent night, you will light one more candle than you did on the previous night, so that on the n-th night (indexed from 1) you will light n candles (and extinguish them all in the morning). Each night that you light a candle, its height will decrease by 1 inch; once its height reaches 0 inches, you cannot use it anymore. You are given a vector <int> candles, the i-th element of which is the height of the i-th candle that you own. Return the maximum number of nights you can celebrate the event without going to the store to get more candles. For example, if you have three candles of height 2, you can light one the first night, the other two on the second night, and then all three candles on the third night. Definition
Class: OlympicCandles Method: numberOfNights Parameters: vector <int> Returns: int Method signature: int numberOfNights(vector <int> candles) (be sure your method is public)
Constraints - candles will contain between 1 and 50 elements, inclusive. - Each element of candles will be between 1 and 100, inclusive. Examples 0)
{2, 2, 2} Returns: 3 The example from the statement. 1)
{2, 2, 2, 4} Returns: 4 With an extra candle we are able to use the candles for four nights. 2)
{5, 2, 2, 1} Returns: 3
3)
{1, 2, 3, 4, 5, 6} Returns: 6
4)
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} Returns: 4
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.
초가 여러개 있고 각각의 초의 길이가 주어진다.. 첫날은 촛불을 하나 켜야하고 둘째날은 두개를 켜야하고.. 등등이다.. 하루에 초는 1cm씩 탈때 최대 몇일동안 촛불을 켤수 있을까?
그냥 greedy 하게 풀었다.. 무조건 가장 킨 초를 사용하여 불을 켜고.. 초의 개수가 모자를때 break.. 구현은 일단 가장 큰 값 k개를 뽑아내고 그 값을 변경후 다시 넣어야하므로.. heap 비스무리한 자료구조인 multiset을 쓰려고하였으나.. 생각해보니 초의 총 개수가 50밖에 안되므로 그냥 매번 sort했다..;;
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <string> 6 #include <set> 7 using namespace std; 8 9 class OlympicCandles { 10 public: 11 12 int numberOfNights(vector <int> candles) 13 { 14 int n, cnt; 15 int i, j; 16 multiset<int> c; 17 multiset<int>::iterator it; 18 cnt = 1; 19 while (1) { 20 sort(candles.begin(), candles.end()); 21 n = candles.size(); 22 if (n < cnt) 23 break; 24 for (i = n-1, j = 0; j < cnt; i--, j++) { 25 if (candles[i] <= 0) 26 break; 27 candles[i] -= 1; 28 } 29 if (j < cnt) 30 break; 31 cnt++; 32 } 33 return cnt-1; 34 } 35 36 };
Level2 - CandyGame
Problem Statement
Your brother is playing a new game he received for his birthday. The game takes place on an acyclic, undirected graph, with pieces of candy located on some of the nodes. On each turn, your brother picks a node with at least 2 pieces of candy on it. He then picks up 2 pieces of candy from that node, eats one piece, and places the other piece on an adjacent node. If at any time there is a piece of candy on the target node, then the game is over and your brother wins. If he cannot put candy on that node through any sequence of moves, he loses. Your brother is smart, and so if there is a winning sequence of moves he will find it. You enjoy frustrating your brother and want to make him lose the game. The graph will be given as a vector <string>. The j-th character of element i will be 'Y' if nodes i and j are connected in the graph; otherwise, it will be 'N'. Return the maximum number of pieces that can be placed on the board without your brother being able to win; if more than 2,000,000,000 pieces can be placed on the board without your brother winning, return -1 instead. Definition
Class: CandyGame Method: maximumCandy Parameters: vector <string>, int Returns: int Method signature: int maximumCandy(vector <string> graph, int target) (be sure your method is public)
Constraints - graph will contain N elements, where N is between 1 and 50, inclusive. - Each element of graph will contain exactly N characters. - Each character in graph will be either 'Y' or 'N'. - In graph, the j-th character of element i will equal the i-th character of element j. - The i-th character of the i-th element of graph will be 'N'. - The graph represented by graph will have no cycles. - target will be between 0 and N-1, inclusive. Examples 0)
{"NYN", "YNY", "NYN"} 1 Returns: 2 The graph is a straight line: 0-1-2 With node 1 as the target, we can only put one piece of candy each on nodes 0 and 2. If you place a second piece on either, your brother can eat one and move the other to node 1. 1)
{"NYN", "YNY", "NYN"} 2 Returns: 3 The same graph as example 0, but now node 2 is the target. The optimal strategy places 3 pieces of candy on node 0. 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.
undirected acylic graph가 주어진다.. 임의의 vertex에 여러개의 캔디가 있을때 그 중 2개를 집어서 하나는 먹고 하나는 이웃한 (edge로 연결된) vertex로 보낼 수 있다. 이런식으로 해서 최적의 전략으로 주어진 target vertex에 캔디를 최소 한개 놓고싶다.. 이때 target vertex에 캔디를 놓지 못하게 하면서 최대로 많이 캔디를 몇개너 놓을수 있을까? 답이 20억이 넘으면 -1 return
아쉽게 풀지 못했다.. DFS 탐색하면서 해당하는 값을 찾는 방식으로 접근했는데.. 솔루션에 문제가 있었나보다.. 그리고 connected component가 아니면 답은 -1이다.. 어처구니없게도 챌 당했다.. -_-;
editorial을 참조하여 풀었다.. 우선 target을 제외한 모든 노드에 캔디 하나씩 놓는다.. 더 이상 캔디를 추가하면 target에 도달하는 조건이 만족한다.. 이 상태에서 각 캔디를 target과 가장 먼 노드로 다 밀어버린다.. 길이 n을 이동하려면 캔디가 2^n 개 필요하다는 것은 쉽게 생각해낼 수 있다.. 참 신선한 문제이군..
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <string> 6 using namespace std; 7 #define max(x, y) ((x) > (y) ? (x) : (y)) 8 9 int map[100][100]; 10 int depth[100]; 11 int n; 12 13 void dfs(int u, int len) 14 { 15 int i; 16 depth[u] = len; 17 for (i = 0; i < n; i++) { 18 if (map[u][i] && depth[i] == -1) { 19 dfs(i, len+1); 20 } 21 } 22 } 23 24 int max_depth(int u) 25 { 26 int i, r, max1; 27 max1 = depth[u]; 28 for (i = 0; i < n; i++) { 29 if (map[u][i] && depth[i] > depth[u]) { 30 r = max_depth(i); 31 if (r > max1) 32 max1 = r; 33 } 34 } 35 return max1; 36 } 37 38 class CandyGame { 39 public: 40 41 int maximumCandy(vector <string> graph, int target) 42 { 43 int i, j, k; 44 long long sum; 45 n = graph.size(); 46 if (n == 1) 47 return 0; 48 memset(map, 0, sizeof(map)); 49 for (i = 0; i < n; i++) { 50 for (j = 0; j < n; j++) { 51 if (graph[i][j] == 'Y') 52 map[i][j] = 1; 53 } 54 } 55 memset(depth, -1, sizeof(depth)); 56 dfs(target, 0); 57 for (i = 0; i < n; i++) { 58 if (depth[i] == -1) 59 break; 60 } 61 if (i != n) 62 return -1; 63 sum = 0; 64 for (i = 0; i < n; i++) { 65 if (i == target) 66 continue; 67 k = max_depth(i); 68 sum += 1LL << (max_depth(i) - depth[i]); 69 if (sum > 2000000000) 70 return -1; 71 } 72 return (int)sum; 73 } 74 75 };
Level3 - TournamentSeeding
Problem Statement
The Total Conquest soccer league is about to begin its season ending tournament next week. The tournament will be a single elimination tournament, meaning that a team that loses is immediately eliminated from the tournament. To set up the tournament, each team will be assigned a unique seed prior to the start of the tournament (starting from 0); the number of teams in the tournament will be a power of 2. The following algorithm in pseudocode is then used to determine pairings: SetSeeds(vector <string> Teams) { LET N = the number of teams left IF(N==1) The tournament is over ELSE Pair all teams such that their seeds sum to N-1. Assume the lower seeded team wins each game. Call SetSeeds(Winners) } For example, in an 8 team tournament, the first round games would be between 0-7, 1-6, 2-5, and 3-4. In the second round, the games would be between 0-3 and 1-2, with the winners meeting in the final. Due to the format of the tournament, it is possible for a second round game to be played before all first round games have finished; a game may be started as long as both teams have advanced to the correct round. In the above tournament, for instance, if teams 0 and 3 win their opening round games, they may play their second round game prior to the game between 2-5. You have been given a list of the teams in the tournament; you should concatenate the elements of teams to form a single space separated list of teams in the tournament with no leading or trailing spaces. You also will be given games; this should be concatenated to form a single space separated list representing the games played. Each game will be represented by two words; the first will be the name of the winning team, and the second will be the team that lost that game. The games may be listed in any order, but all games that have been played in the tournament so far will be listed. You know that all games played in the tournament will be won by the team with the lower numbered seed. Assign the seeds to teams consistent with the games played; if there is more than one way to do this, select the lexicographically first among them (see Notes). Return a vector <string> containing the same number of elements as seeds; the i-th element in the return should correspond to the team name of the team that has been assigned seed seeds[i]. If the games listed in games do not represent a valid set of games in a tournament, return an empty vector <string>. Definition
Notes - An assignment of teams A is lexicographically earlier than B if, for some seed i, A[i] < B[i], and for all seeds j < i, A[j]=B[j]. - When comparing two strings, digits ('0'-'9') come before letters. - A string C is less than D if C is a prefix of D, or if, for some character at index i, C[i] < D[i], and for all j < i, C[j]=D[j]. Constraints - teams will contain between 1 and 50 elements, inclusive. - Each element of teams will contain between 1 and 50 characters, inclusive. - teams will contain only uppercase letters ('A'-'Z'), digits ('0'-'9') and spaces (' '). - The number of teams listed in teams will be a non-negative power of 2. - There will be no duplicate team names in teams. - teams will be formatted as described in the statement. - Each name in teams will contain between 1 and 20 characters, inclusive. - games will contain between 0 and 50 elements, inclusive. - Each element of games will contain between 1 and 50 characters, inclusive. - When concatenated, games will contain a single space separated list of names from teams, with no leading or trailing spaces. - When concatenated, games will contain an even number of team names. - No team will play against itself in games. - There will be no repeated game listed in games. - seeds will contain between 1 and 50 elements, inclusive. - Each element of seeds will be between 0 and N-1, inclusive, where N is the number of teams in teams. Examples 0)
{"CELTICS ", "LAKER", "S SPURS PISTONS"} {"CELTICS LAKERS CELTICS PISTONS LAKERS SPURS"} {0, 1, 2, 3} Returns: {"CELTICS", "LAKERS", "SPURS", "PISTONS" } The final rounds of the 2008 NBA playoffs. The first round games were CELTICS-PISTONS and LAKERS-SPURS, and the CELTICS beat the LAKERS in the final. 1)
{"GIANTS PATRIOTS CHARGERS PACKERS"} {"PATRIOTS CHARGERS"} {3, 2, 1, 0} Returns: {"PACKERS", "CHARGERS", "PATRIOTS", "GIANTS" } Here is an incomplete tournament with only one game played. There are several possible seedings, but the lexicographically earliest seeding is: 0) GIANTS 1) PATRIOTS 2) CHARGERS 3) PACKERS 2)
{"REDSOX PHILLIES METS DODGER", "S ORIOLES BLUEJAYS CUBS AN", "GELS"} {"METS ANGELS", " METS CU", "BS ORIO", "LES ANGELS"} {0, 1, 2, 3, 4, 5, 5, 5} Returns: { } In a single elimination tournament, it is impossible for the ANGELS to lose twice. 3)
{"REDSOX PHILLIES METS DODGER", "S ORIOLES BLUEJAYS CUBS AN", "GELS"} {"METS ANGELS", " METS CU", "BS CU", "BS DODGERS REDSOX PHILLIES"} {0, 1, 2, 3, 4, 5, 6, 7} Returns: {"BLUEJAYS", "METS", "CUBS", "REDSOX", "PHILLIES", "DODGERS", "ANGELS", "ORIOLES" } In this tournament, the second round game between the METS and CUBS was played before the BLUEJAYS-ORIOLES game from the first round. 4)
{"A B C D E F 8 H I 3 9 L 4 N O P"} {"P A B H D C D E E N"} {0, 2, 0, 0, 3, 4, 7, 2} Returns: {"3", "8", "3", "3", "D", "E", "P", "8" } Note that the same seed may be requested multiple times. 5)
{"A B C D E F G H"} {"A B C D A C E F"} {0, 1, 2, 3, 4, 5, 6, 7} Returns: {"A", "E", "G", "C", "D", "H", "F", "B" }
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.
