어제 저녁 9시에 열린 매치.. 오랜만에 참여했다.. 시간대도 좋았고..
이번매치에는 문제가 좀 tricky한게 많아서 챌린지의 향연이었다..
나도 간신히 250은 pass했는데.. 챌에서 삽질한게 좀 아쉽다..
사람들이 많이 fail해서그런지.. rating은 생각보다 많이 안떨어졌다..;
Level1 - LampsGrid
Problem Statement
Jack has bought a rectangular table containing a grid of lamps. Each lamp is initially either "on" or "off". There is a switch underneath each column, and when the switch is flipped, all the lamps in that column reverse their states ("on" lamps become "off" and vice versa).
A row in the grid is considered lit if all the lamps in that row are "on". Jack must make exactly K flips. The K flips do not necessarily have to be performed on K distinct switches. His goal is to have as many lit rows as possible after making those flips.
You are given a vector <string> initial, where the j-th character of the i-th element is '1' (one) if the lamp in row i, column j is initially "on", and '0' (zero) otherwise. Return the maximal number of rows that can be lit after performing exactly K flips.
Definition
Class:
LampsGrid
Method:
mostLit
Parameters:
vector <string>, int
Returns:
int
Method signature:
int mostLit(vector <string> initial, int K)
(be sure your method is public)
Constraints
-
initial will contain between 1 and 50 elements, inclusive.
-
Each element of initial will contain between 1 and 50 characters, inclusive.
-
Each element of initial will contain the same number of characters.
-
Each element of initial will contain only the digits '0' and '1'.
-
K will be between 0 and 1000, inclusive.
Examples
0)
{"01",
"10",
"10"}
1
Returns: 2
Here, Jack must flip exactly one switch. If he flips the switch for the second column, the bottom two rows become lit.
1)
{"101010"}
2
Returns: 0
2)
{"00", "11"}
999
Returns: 0
No row can be lit after exactly 999 flips.
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.
0 또는 1로 채워져있는 2차원 matrix가 주어진다.. 임의의 row에 대해서 모든 column의 값이 1이면 그 row의 상태를 on 이라고 한다. 각 column에 대해서 column 전체 값을 뒤집는 operation을 K번 해야할 때 최대 몇개의 row를 on 인 상태로 만들 수 있을까?
정말 삽질끝에 풀어냈다.. 첨에 아이디어가 잘 생각이 안나서.. 그냥 포기할까 했는데.. 끝까지 물고늘어져서.. 기어코 pass했다.. 오호.. 요즘 컨디션이 좀 괜찮나..?
우선 각 row에 대해서 0이 몇개인지 센다.. 0의 개수가 K보다 크거나 K와 parity가 다르면 절대 그 row는 on이 될 수 없다.. 또한 다른 row와 독립적이어서 그냥 지워버리고 생각하면 된다.. 그리고 남은 row에 대해서 똑같은 row가 가장 많은것을 on 시키는 전략으로 하면 된다..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <map>
7 using namespace std;
8 #define max(x, y) ((x) > (y) ? (x) : (y))
9
10 class LampsGrid {
11 public:
12
13 int mostLit(vector <string> initial, int K)
14 {
15 int n, m;
16 int i, j;
17 int temp, max1;
18 int row_sum[100];
19 int check[100];
20 char board[100][100];
21 map<string, int> dup;
22 n = initial.size();
23 m = initial[0].size();
24 memset(board, 0, sizeof(board));
25 for (i = 0; i < n; i++) {
26 strcpy(&board[i+1][1], initial[i].c_str());
27 }
28 memset(row_sum, 0, sizeof(row_sum));
29 for (i = 1; i <= n; i++) {
30 for (j = 1; j <= m; j++) {
31 row_sum[i] += board[i][j] - '0';
32 }
33 }
34 memset(check, 0, sizeof(check));
35 for (i = 1; i <= n; i++) {
36 temp = m - row_sum[i];
37 if (temp > K) {
38 check[i] = -1;
39 }
40 if ((temp & 1) != (K & 1)) {
41 check[i] = -1;
42 }
43 }
44 max1 = 0;
45 for (i = 1; i <= n; i++) {
46 string s = &board[i][1];
47 if (check[i] == -1)
48 continue;
49 if (dup.find(s) == dup.end()) {
50 dup[s] = 1;
51 }
52 else {
53 dup[s]++;
54 }
55 temp = dup[s];
56 max1 = max(max1, temp);
57 }
58 return max1;
59 }
Level2 - GroupedWord
Problem Statement
A word is grouped if, for each letter in the word, all occurrences of that letter form exactly one consecutive sequence. In other words, no two equal letters are separated by one or more letters that are different. For example, the words "ccazzzzbb" and "code" are grouped, while "aabbbccb" and "topcoder" are not.
A grouped word was divided into several parts. You are given all the parts in random order as a vector <string>. Reconstruct the original word and return it. If there is more than one possible answer, return "MANY" instead. If no grouped word could have resulted in the given parts, return "IMPOSSIBLE" instead (all quotes for clarity).
Definition
Constraints
-
parts will contain between 1 and 50 elements, inclusive.
-
Each element of parts will contain between 1 and 20 characters, inclusive.
-
Each element of parts will contain only lowercase letters ('a' - 'z').
Examples
0)
{"aaa", "a", "aa"}
Returns: "aaaaaa"
These parts could only have come from the word "aaaaaa", which is a grouped word.
1)
{"ab", "bba"}
Returns: "IMPOSSIBLE"
The only possible original words are "abbba" and "bbaab", and neither of them are grouped words.
2)
{"te", "st"}
Returns: "stte"
3)
{"te", "s", "t"}
Returns: "MANY"
The initial word could be either "stte" or "ttes".
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.
여러개의 문자열 조각들이 input으로 들어온다.. 이 문자열들을 모두 붙여서 하나의 문자열을 만드는데.. 규칙은 같은 문자는 모두 연속되어야 한다.
예)
ccazzzzbb <--- (O)
aabbbccb <--- (X)
이렇게 문자열을 붙일수 있는 경우가 하나면 만들어진 문자열을 리턴하고 답이 여러개면 "MANY" 불가능하면 "IMPOSSIBLE"을 리턴..
to be updated..
Level 3 - BuildersCountry
Problem Statement
There's a far away country where only builders live. They have built a number of cities already, and some of them are connected with bidirectional roads. The existing roads are given in the vector <string> g, where the j-th character of the i-th element is 'Y' if there's a bidirectional road connecting cities i and j, and 'N' otherwise. Each city contains a number of houses, given in the vector <int> before, where the i-th element is the number of houses in city i. Exactly one builder lives in each house.
The country will go through a two-phase building process. In the first phase, new bidirectional roads will be built so that every pair of cities will be connected by some path. When a road is built between two cities, every builder from both cities will be involved and each builder will be paid roadCost units of money.
In the second phase, new houses will be built. You are given a vector <int> after, where the i-th element is the number of houses that must exist in city i after this phase is complete. In other words, after[i] - before[i] new houses must be built in city i during this phase. When a house is built, all builders in that city and all its neighboring cities will be involved and each one will be paid houseCost[i] units of money. Two cities are neighboring if they are directly connected by a road. After each house is built, a new builder will immediately live in that house. Houses can be built in any order.
Return the minimal possible cost required to finish both phases of the building process.
Definition
Class:
BuildersCountry
Method:
minCost
Parameters:
vector <int>, vector <int>, vector <int>, vector <string>, int
Returns:
long long
Method signature:
long long minCost(vector <int> before, vector <int> after, vector <int> houseCost, vector <string> g, int roadCost)
(be sure your method is public)
Constraints
-
before will contain between 1 and 50 elements, inclusive.
-
Each element of before will be between 1 and 100000, inclusive.
-
after will contain the same number of elements as before.
-
The i-th element of after will be between the i-th element of before and 100000, inclusive.
-
houseCost will contain the same number of elements as before.
-
Each element of houseCost will be between 1 and 100000, inclusive.
-
g will contain the same number of elements as before.
-
Each element of g will contain exactly n characters, where n is the number of elements in g.
-
Each element of g will contain only uppercase letters 'Y' and 'N'.
-
The i-th character of the i-th element of g will always be 'N'.
-
The i-th character of the j-th element of g will always be equal to the j-th character of the i-th element of g.
-
roadCost will be between 1 and 100000, inclusive.
Examples
0)
{2, 1, 3, 5}
{2, 1, 3, 5}
{4, 5, 3, 2}
{"NNNN", "NNNN", "NNNN", "NNNN"}
1000
Returns: 13000
We can build roads from city 1 to all other cities for a total cost (1+2)*1000 + (1+3)*1000 + (1+5)*1000 = 13000. All houses are already built.
1)
{1, 1, 1, 1}
{1, 3, 1, 2}
{8, 5, 3, 2}
{"NYNN", "YNYN", "NYNY", "NNYN"}
100000
Returns: 39
We don't need to add any roads. If we build one house in city 1, we need to pay 5*(1+1+1). After that, build one house in city 3 for a cost of 2*(1+1). Then, build another house in city 1. This time, the cost will be 5*(1+2+1) since 2 workers now live in city 1. The total cost is 15+4+20=39.
2)
{9, 11}
{10, 11}
{5, 1}
{"NN", "NN"}
15
Returns: 400
Build one road and build one house.
3)
{1}
{1000}
{2}
{"N"}
888
Returns: 999000
Build 999 houses. Total cost is (1+2+...+999)*2 = 999000.
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.
