TopCoder Open 2011 시작!!
작년에 TCO10 때 휴가까지 쓰고 참가했는데도 불구하고 Qual round 도 통과못한 아쉬움이 있었는데..
올해도 상황을 보니 작년과 비슷하게 진행되고 있다.. -_-
맞았다고 생각한 500 이 의외로 fail 하면서 637 등.. 간발의 차이로 탈락했다.. 젠장!!!!
500 이 fail 한 이유는 특정 케이스에 대해서 TLE 가 나는거였는데.. 나와 같은 이유로 fail 한 사람이 많았다..
이런 xx 같은 경우가 다 있다니..!!
Level1 - MinimumLiars
Problem Statement
There is a group of N people numbered from 0 to N-1. Each of them is either an honest person or a liar. You wish to know how many liars are in the group. To do this, you have asked the same question to every person in the group: "What is the number of liars in this group?". The people in the group themselves know the exact number of liars, but since you are a foreigner in the group, they have not told it to you exactly. Instead, the i-th person answered you as follows: "There are at least claim[i] liars in the group." It is known that statements by honest persons are always true. However, statements by liars are always false. So, if a liar claims that there are at least X liars in the group, then in fact there are less than X liars. Now, given a vector <int> claim containing the N answers that you received, you would like to determine the number of liars in the group. Unfortunately, there's another twist that makes this problem more complicated. The people in the group speak a different language than you, so you might have misunderstood some of their answers. The answers in claim are how you understood them, but they might not match what the people actually told you. If you definitely misunderstood at least one of the answers, return -1. Otherwise, assuming that you understood all answers correctly, return the minimum number of liars that could be in the group.
Definition
Class:
MinimumLiars
Method:
getMinimum
Parameters:
vector <int>
Returns:
int
Method signature:
int getMinimum(vector <int> claim)
(be sure your method is public)
Constraints
-
claim will contain between 2 and 50 elements, inclusive.
-
Each element of claim will be between 0 and 100, inclusive.
Examples
0)
{1,1,1,2}
Returns: 1
It would be impossible for all the members of the group to be honest because in that case, all of their answers would be 0. It is, however, possible that only the last person is a liar and each of the first three persons is honest. Therefore the correct answer is 1.
1)
{7,8,1}
Returns: 2
The first two people claim that there are at least 7 and 8 liars, respectively, which is impossible as the group only has three people. Thus, they must be lying. The third person claims there is at least one liar, and this is definitely true since we have already identified two liars, so this person is honest.
2)
{5,5,5,5,5}
Returns: -1
Everybody agrees that there are at least 5 liars in the group. The group contains exactly 5 people, so in fact all of them claim that everybody is a liar. We can't assume that some person is honest because this person definitely wouldn't have claimed him/herself as being a liar. We also can't assume that all of them are liars because in this case it will appear that all their statements are true. Every scenario we can try leads to a contradiction, so you must have misunderstood at least one of the answers.
3)
{0,0,0,4,3,0}
Returns: 2
4)
{4,7,5}
Returns: 3
Every claim made is impossible. Therefore all three people in the group must be lying.
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.
i번째 사람이 liar 라면 claim[i] 는 전체 liar 수보다 크고, i번째 사람이 liar 가 아니라면 claim[i] 는 전체 liar 수보다 작거나 같다.. 최소 가능한 liar 수 구하기
liar 수를 0 ~ n 까지 넣고 시도해보았다..
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 //#define INF 999999999
10 //#define EPS 1e-14
11
12 class MinimumLiars {
13 public:
14
15 int getMinimum(vector <int> claim)
16 {
17 int n;
18 int i, j;
19 int cnt;
20 n = claim.size();
21 for (i = 0; i <= n; i++) {
22 cnt = 0;
23 for (j = 0; j < n; j++) {
24 if (claim[j] <= i) {
25 }
26 else {
27 cnt++;
28 }
29 }
30 if (cnt == i) {
31 return i;
32 }
33 }
34 return -1;
35 }
36
37 };
Level2 - FoxListeningToMusic
Problem Statement
Fox Jiro is going to listen to some music. He has N songs, numbered 0 to N-1, inclusive. The lengths of the songs are given in the vector <int> length, where the i-th element is the length in seconds of song i.
The music player he uses has a shuffle feature. Using this feature, he can listen to the songs in random order. More precisely, first the player chooses one song among all songs with equal probability and plays it. When the song ends, the player chooses the next song in the same fashion and plays it immediately. Note that the player may choose the same song more than once in a row.
You are given an int T. Return a double[] P, where P[i] indicates the probability that the player is playing the i-th song T+0.5 seconds after Jiro starts listening to the music in shuffle mode.
Definition
Class:
FoxListeningToMusic
Method:
getProbabilities
Parameters:
vector <int>, int
Returns:
vector <double>
Method signature:
vector <double> getProbabilities(vector <int> length, int T)
(be sure your method is public)
Notes
-
Each element of the returned array must have an absolute or relative error less than 1e-9.
Constraints
-
length will contain 1 and 50 elements, inclusive.
-
Each element of length will be between 1 and 80,001, inclusive.
-
T will be between 0 and 80,000, inclusive.
Examples
0)
{1, 2}
1
Returns: {0.25, 0.75 }
There are three possible scenarios that lead up to time 1.5:
song 0 -> song 0 (with probability 1/4)
song 0 -> song 1 (with probability 1/4)
song 1 (with probability 1/2)
1)
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.
각 음악의 재생 길이가 나오고.. random play 를 할때, T+0.5 초 순간에 i 번째 음악이 play 될 확률 구하기..
전형적인 DP 로 풀었다..
P[i][j] = i 초에 j 음악이 play 될 확률이라고 놓고 풀었다..
최악의 경우 loop 가 2억번 돌아서 약간 불안했는데.. tc 를 50개 다 넣어봐도 잘 돌아가길래 submit
근데 특정 case 에서 fail 했다.. ㅠ_ㅠ;
double 값이 너무 작아지면 연산 속도가 갑자기 떨어지는 것 같다.. ㅠ_ㅠ;; (링크)
그래서 너무 작은값이 나올때 무시하고 돌렸다..
문제 출제자.. 이건 좀 너무하잖아!!
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 //#define INF 999999999
10 //#define EPS 1e-14
11
12 int n;
13 int tt;
14 double P[100001][51];
15
16 class FoxListeningToMusic {
17 public:
18
19 vector <double> getProbabilities(vector <int> length, int T)
20 {
21 int i, j, k;
22 int temp;
23 double p;
24 vector<double> res;
25 n = length.size();
26 tt = T;
27 p = 1.0 / (double)n;
28 for (i = 0; i < n; i++) {
29 res.push_back(0);
30 }
31 for (i = 0; i <= T; i++) {
32 for (j = 0; j < n; j++) {
33 P[i][j] = 0.0;
34 }
35 }
36 for (i = 0; i < n; i++) {
37 if (length[i] > T)
38 res[i] += p;
39 else
40 P[length[i]][i] = p;
41 }
42 for (i = 1; i <= T; i++) {
43 for (j = 0; j < n; j++) {
44 temp = i+length[j];
45 for (k = 0; k < n; k++) {
46 if (P[i][k] > 1e-15) {
47 if (temp > T)
48 res[j] += P[i][k] * p;
49 else
50 P[temp][j] += P[i][k] * p;
51 }
52 }
53 }
54 }
55 return res;
56 }
57
58 };
Level3 - SquareSeries
Problem Statement
Taro and Brus are playing a new game called Square Series. The game involves placing a non-empty sequence of black and white squares following a couple of rules:
The first square has side length 1.
For i > 1, if the color of square i (1-indexed) is different than the color of square i-1, its side length will be equal to the side length of the previous square plus 1. If the colors are the same, then the side length will be equal to the previous side length minus 1. Note that a side length of 0 would make the shape not a square, so it is not legal to repeat the color after a length 1 square.
Taro wants to prepare new challenges for Brus and would like you to make a program that will generate valid square series such that it matches string pattern and the length of the last square is equal to lastLength. The pattern contains 'W' and 'B' representing white and black squares respectively and exactly one '?' character. To generate a sequence of strings that matches the pattern, replace the '?' character with a (possibly empty) sequence of white and black squares. Given the pattern and lastLength, if there is no valid sequence of squares that follows the aforementioned rules, matches the pattern and finishes with a square of side length equal to lastLength, then return "..." (quotes for clarity). Otherwise, return the shortest possible sequence that matches the pattern and finishes with a square of the appropriate side length. In case there is more than one sequence with a length equal to the shortest possible, return the lexicographically first of them.
Definition
Class:
SquareSeries
Method:
completeIt
Parameters:
string, int
Returns:
string
Method signature:
string completeIt(string pattern, int lastLength)
(be sure your method is public)
Notes
-
The lexicographically earlier of two strings of the same length is the one that has the earlier character (using ASCII ordering) at the first position at which they differ.
Constraints
-
lastLength will be between 1 and 100, inclusive.
-
pattern will contain between 1 and 50 characters, inclusive.
-
Each character in pattern will be 'W', 'B' or '?'.
-
pattern will contain exactly one '?' character.
Examples
0)
"W?B"
2
Returns: "WB"
It is possible to replace the '?' character with an empty sequence. The sequence "WB" is the shortest one that matches the pattern and ends with a square of length 2.
1)
"?"
5
Returns: "BWBWB"
Any sequence can match the "?" pattern. "BWBWB" and "WBWBW" are the shortest sequences possible that end with a square of size 5. "BWBWB" is the lexicographically earlier of the two.
2)
"BWBBBBW?WB"
10
Returns: "..."
Every sequence that begins with BWBBBB is invalid because it will require an invalid square of size 0 at position 6 (1-based).
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.
