어제 저녁 8시에 열린 매치..
그동안의 부진을 좀 만회하고자 이번에는 좀 정신차리고 했는데.. 또 망쳐버렸다.. ㅠ_ㅠ
250이 열라 코딩이 드러운 문제가 나오면서.. 또 험난한 매치가 되어버렸다..
단순한 코딩 실수를 못찾아서 한참 헤맨게 컸다.. 젠장..
500은 다들 똑같은 DP로 풀었고.. 250은 코드가 다들 개발새발이라 도저히 챌을 할 수가 없었다..
결국 20점 하락 ㅠ_ㅠ;;;;
겨우 삽질해서 한문제 풀었더니.. 이거 허무하구만..
Level1 - T9
Problem Statement
The old fashioned king does not know how to SMS and thus he is having problems sending messages to the queen. In particular, he is having a problem with a feature called T9. In T9, the set of alphabets are partitioned into 9 sets, where the i-th set of characters (1-based) denotes the possible characters that may be typed by pressing digit i. For this problem, we will use strings to denote a set of characters. On a standard modern cell phone, the following partition is used
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
For the partition above, pressing 2 may output 'a', 'b' or 'c'; pressing 3 may output 'd', 'e' or 'f'; and so on. Pressing 223 can give you various outputs of the form "(abc)(abc)(def)" where (XYZ) means that the letter can be either X or Y or Z. For example, a few possible outputs are "ace", "bad" and "bbe". However, not all possible outputs are dictionary words (like "bbe" is not a dictionary word), and thus these outputs do not make sense. The cell phone considers only those outputs which correspond to dictionary words. Suppose that there are only two possible dictionary words from "(abc)(abc)(def)" - namely, "ace" and "bad". Then, the keystrokes 223 gives the output "ace", and the keystrokes 223# gives the output "bad". In general if a certain number (like 223) corresponds to multiple dictionary words, then the number followed by n hashes ('#') is used to type the n-th dictionary word (0-based) from the lexographically sorted list of dictionary words corresponding to the number. Sometimes the number of hashes typed can be quite large. Hence, we have a special character star ('*') which is equivalent to 5 contiguous hashes. The digit 0 is used to type a space. The king needs to type a text using T9. The text is a string that consists of lowercase letters ('a'-'z') and space characters (' '). A word is a maximal contiguous substring of the text that contains only lowercase letters ('a'-'z'). The only way the king can type a word is by first pressing a non-empty sequence of digits ('1'-'9') followed by a (possibly emtpy) sequence of characters '#' and/or '*'. You will be given a vector <string> part whose i-th element (1-based) is the set of alphabets which correspond to the digit i. You will also be given a vector <string> dict that represents a set of all dictionary words, where each element is a single word. Finally, you will be given a vector <string> keystr. Concatenate the elements of keystr in the same order as they are given to obtain a string. This string represents the keystrokes pressed by the king. To help the king, return the text that will result when the given keystrokes are pressed. You may assume that the given keystrokes are valid, i.e. each maximal contiguous substring that doesn't contain '0' characters starts from non-empty sequence of digits ('1'-'9') and then is optionally continued with a sequence of '#' and/or '*' characters. You may also assume that each such substring corresponds to a word from dict.
Definition
Notes
-
A substring of a string is called maximal with respect to some property if it can't be extended to the left or to the right while maintaining the property.
-
A string A is lexicographically less than another string B of the same length if there exists a position i such that each character of A before the i-th position is equal to the character at the corresponding position in B, and A[i] is less than B[i].
-
For the purpose of this problem, a partition of alphabets into 9 sets may contain any number of empty sets.
Constraints
-
part will represent a valid partition of the 26 english alphabets into 9 sets, i.e. it will consist of exactly 9 elements and every letter from 'a' to 'z' will appear exactly once in exactly one of the elements of part.
-
dict will contain between 1 and 50 elements, inclusive.
-
Each element of dict will contain between 1 and 50 characters, inclusive.
-
Each character in dict will be a lowercase letter 'a'-'z'.
-
All elements of dict will be distinct.
-
keystr will contain between 1 and 50 elements, inclusive.
-
Each element of keystr will contain between 1 and 50 characters, inclusive.
-
Each character in keystr will be one of '0'-'9', '#', '*'.
-
The length of the resulting text will be between 1 and 1000, inclusive.
-
The string obtained by concatenating the elements of keystr will represent a valid sequence of keystrokes (as explained in the statement).
Examples
0)
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
{"the", "tie"}
{"0843#000843#000"}
Returns: " tie tie "
There may be leading, trailing and contiguous spaces.
2)
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
{"bad", "ace", "aad", "aae", "aaf", "acf", "acd", "the", "tie"}
{"223#02", "23*#00843#0"}
Returns: "aae bad tie "
Don't forget to concatenate the elements of keystr. Also, "*" is equivalent to "#####".
3)
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
{"the", "tie", "bad", "ace", "aad", "aae", "aaf", "acf", "acd"}
{"84300223#02", "23#*"}
Returns: "the aae bad"
'*' may also appear after the '#'. All that matters is, it is equivalent to "#####".
4)
{"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
{"bad", "ace", "aad", "aae", "tie", "aaf", "acf", "acd", "the"}
{"223#02", "23######"}
Returns: "aae bad"
The king may use '*'. But it is not necessary that he uses it everytime he is allowed to use it.
5)
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.
전화 키패드를 이용해서 문자를 보낸다고 생각하면 되는데.. 각 번호마다 타이핑할 수 있는 알파벳이 있다..
숫자로 뭐라고뭐라고 쳤을때 나오는 결과가 무었일지..
0은 빈칸을 의미하고, # 은 가능한 단어중에 다음거 선택, * 은 가능한 단어중에 5번째꺼 선택 을 의미..
그냥 brute force 로 다 찾으면 된다..
코딩을 거의 잘 해놓고도.. 단순 실수를 못찾아서 헤맸다..
나같은 경우, 일단 dictionary 에 있는 단어들을 encoding 해놓았다..
input 을 parsing 해서 그걸 앞에서 encoding 해둔 map 을 이용해서 계속 찾아나갔다..
아래는 내가 매치중에 짠 코드인데.. 이건 뭐 완전.. -_-;;;;
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <map>
7 #include <set>
8 using namespace std;
9 //#define min(x, y) ((x) > (y) ? (y) : (x))
10 //#define max(x, y) ((x) > (y) ? (x) : (y))
11 //#define INF 999999999
12 //#define EPS 1e-14
13
14 string pp[128];
15 set<string> dd;
16 set<string> ss;
17 map<string, set<string> > ms;
18
19 string find_str(string in, int n)
20 {
21 int i;
22 set<string> temp_set;
23 set<string>::iterator it;
24
25 if (in.size() == 0)
26 return "";
27 temp_set = ms[in];
28
29 n = n % temp_set.size();
30
31 for (it = temp_set.begin(), i = 0; it != temp_set.end() && i < n; it++, i++) {
32 }
33 return *it;
34 }
35
36 class T9 {
37 public:
38
39 string message(vector <string> part, vector <string> dict, vector <string> keystr)
40 {
41 int i, j, k, l;
42 int len, cnt;
43 char ch;
44 string res;
45 string cur;
46 string in, temp;
47 set<string> temp_set;
48
49 for (i = 1; i <= 9; i++) {
50 pp[i] = part[i-1];
51 }
52 dd.clear();
53 for (i = 0; i < dict.size(); i++) {
54 dd.insert(dict[i]);
55 }
56
57 for (i = 0; i < dict.size(); i++) {
58 temp = dict[i];
59 cur = "";
60 for (j = 0; j < temp.size(); j++) {
61 for (k = 1; k <= 9; k++) {
62 for (l = 0; l < pp[k].size(); l++) {
63 if (pp[k][l] == temp[j]) {
64 cur += (char)('0' + k);
65 break;
66 }
67 }
68 if (l < pp[k].size())
69 break;
70 }
71 }
72
73 //printf("found .. %s\n", cur.c_str());
74 if (ms.find(cur) == ms.end()) {
75 temp_set.clear();
76 temp_set.insert(dict[i]);
77 ms[cur] = temp_set;
78 }
79 else {
80 temp_set = ms[cur];
81 temp_set.insert(dict[i]);
82 ms[cur] = temp_set;
83 }
84 }
85
86 res = "";
87 cur = "";
88 in = "";
89 for (i = 0; i < keystr.size(); i++) {
90 in += keystr[i];
91 }
92
93 len = in.size();
94 for (i = 0; i < len; i++) {
95 ch = in[i];
96 if (ch == '*' || ch == '#') {
97 cnt = 0;
98 while (i < len && (in[i] == '*' || in[i] == '#')) {
99 if (in[i] == '*')
100 cnt += 5;
101 else
102 cnt += 1;
103 i++;
104 }
105 i--;
106 temp = find_str(cur, cnt);
107 res += temp;
108 cur = "";
109 continue;
110 }
111 else if (in[i] == '0') {
112 temp = find_str(cur, 0);
113 res += temp;
114 res += " ";
115 cur = "";
116 continue;
117 }
118 else {
119 cur += ch;
120 }
121 }
122
123 if (cur.size() != 0) {
124 temp = find_str(cur, 0);
125 res += temp;
126 }
127 return res;
128 }
129
130 };
Level2 - RoadOrFlightHard
Problem Statement
The king has been out to work for a long time and he wants to go back to his queen as fast as possible. The king is in city 0 and the queen is in city N. There are roads and flights connecting city i to city (i+1) for all i between 0 and N-1, inclusive. The time it takes to travel from city i to city (i+1) by road and by flight is given by the i-th elements of roadTime and flightTime, respectively. roadTime can be generated from the following pseudocode:
roadTime[0] = roadFirst mod roadMod;
for i = 1 to N-1
roadTime[i] = (roadTime[i-1]*roadProd + roadAdd) mod roadMod;
// note that (roadTime[i-1]*roadProd + roadAdd) may overflow a 32-bit integer
flightTime can be generated similarly by using flightFirst, flightProd, flightAdd, flightMod. However, taking a flight risks the life of the king during takeoffs due to the technological limitations in the kingdom. Hence the queen has asked him to ensure that the total number of takeoffs during his entire journey does not exceed K. To minimize the number of takeoffs, the king may choose to take a direct flight from city i to city i+j instead of separate flights from city i to city i+1, then from i+1 to i+2, ... and from i+(j-1) to i+j. The time taken for this flight is the sum of the times taken for the flights from i to i+1, i+1 to i+2, ..., i+(j-1) to i+j. Return the minimum amount of time in which the king can reach his queen.
Definition
Class:
RoadOrFlightHard
Method:
minTime
Parameters:
int, int, int, int, int, int, int, int, int, int
Returns:
long
Method signature:
long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K)
(be sure your method is public)
Constraints
-
N will be between 1 and 400000, inclusive.
-
roadFirst, roadAdd, flightFirst and flightAdd will each be between 0 and 100000, inclusive.
-
roadProd, roadMod, flightProd and flightMod will each be between 1 and 100000, inclusive.
-
K will be between 0 and 40, inclusive.
-
K will be less than or equal to N.
Examples
0)
3
14
1
2
10
18
1
10
17
1
Returns: 14
The pseudocode gives roadTime = {4, 6, 8} and flightTime = {1, 11, 4}. The fastest way to reach the queen is to take the road from city 0 to 1 and 1 to 2, and a flight from city 2 to 3.
1)
3
4
1
2
10
1
1
10
17
2
Returns: 11
roadTime and flightTime are the same as in previous example. But now the king is allowed 2 takeoffs.
2)
3
4
1
2
10
1
1
6
9
1
Returns: 12
roadTime = {4, 6, 8} and flightTime = {1, 7, 4}. Even though roadTime[1] < flightTime[1], it is best to take a direct flight from city 0 to city 3 which takes a total time of 1 + 7 + 4 = 12 units.
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.
to be updated..
Level3 - MallSecurity
Problem Statement
The first mall of the kingdom is about to be inaugurated in a few days. The king wants to make sure that the mall is highly secured. The mall has N floors, numbered 1 to N. Each floor has stations which allow people to enter or leave the floor to which the station belongs. All escalators in the mall begin and end at stations of adjacent floors. To make movement of people easier, super-escalators connect stations in floor 1 to stations in floor N. Each escalator or super-escalator can be used to go upwards as well as downwards. If the i-th floor has Ki stations then the stations are numbered from 1 to Ki. The escalators and super-escalators are constructed in such a way that a person can reach any station from any other station using them. The king wants to have as many guards in the mall as possible to make it secure. Guards can only be placed at stations and at most 1 guard can be placed at a station. Moreover, the people of the kingdom become panicky if they see more than one guard at a time. Hence, there should be no such escalator (or super-escalator) such that guards are placed at both its end stations. You are given a vector <string> escDescription which when concatenated represents a comma (',') separated list of escalators and super-escalators. Every escalator (or super-escalator) is of the form "A B C". If C is less than N, the string represents an escalator from station A of floor C, to station B of floor C+1. If C is equal to N, then the string represents a super-escalator from station A of floor C (= N), to station B of floor 1. Help the king by returning the maximum number of guards he can place in the mall.
Definition
Class:
MallSecurity
Method:
maxGuards
Parameters:
int, vector <string>
Returns:
int
Method signature:
int maxGuards(int N, vector <string> escDescription)
(be sure your method is public)
Constraints
-
N will be between 10 and 50, inclusive.
-
The total number of stations in the mall will not exceed 100.
-
escDescription will contain between 1 and 50 elements, inclusive.
-
Each element of escDescription will contain between 1 and 50 characters, inclusive.
-
The concatenation of the elements of escDescription will be a comma separated list of escalators and super-escalators.
-
Each escalator and super-escalator will be given as "A B C" (quotes for clarity), where A, B and C are positive integers with no leading zeros.
-
In each escalator and super-escalator description, A will be a valid number of station located on floor C.
-
In each escalator and super-escalator description, B will be a valid number of station located on floor C + 1 (or on floor 1, if C = N).
-
In each escalator and super-escalator description, C will be between 1 and N, inclusive.
-
Each floor will have at least 1 station.
-
The stations on each floor will be numbered from 1 to K, inclusive, where K is the total number of stations on this floor.
-
Each pair of stations will be connected with at most one escalator or super-escalator.
-
It will be possible to reach any station from any other station using escalators and super-escalators.
Examples
0)
10
{"1 1 1,1 1 2,1 1 3,1 1 4,1 1 5,1 1 6,1 1 7,1 1 8,1 ",
"1 9,1 1 10"}
Returns: 5
There are 10 floors and each floor has only one station. The stations on adjacent floors are connected with escalators. The stations on floor 1 and on floor 10 are connected with a super-escalator. You can place 5 guards on stations of the following floors: 1, 3, 5, 7 and 9. Another solution is to place them on floors 2, 4, 6, 8, 10.
1)
11
{"1 1 1,1 1 2,1 1 3,1 1 4,1 1 5,1 1 6,1 1 7,1 1 8,1 ",
"1 9,1 1 10"}
Returns: 6
This time there are 11 floors and there's no super-escalator. You can place 6 guards on stations of the following floors: 1, 3, 5, 7, 9, 11.
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.
