수요일 밤 12시에 열렸던 매치.. 완전히 삽질한 매치였다.. 역대 최악의 성적을 기록.. ㅠ_ㅠ 방에서 최하위 디비젼 전체에서도 끝에서 두번째를 기록하고말았다.. ㅠ_ㅠ 흠.. 정말 쪽팔리구만..;; 코딩 시간이 끝나자마자 나는 두문제 다 fail할거라는 것을 직감.. 그냥 챌을 많이하려고했는데.. 블챌이 다 실패하고 말았다.. 젠장.. 그냥 가만히 있어도 중간은 가는데.. ㅠ_ㅠ 문제도 정말 짜증나는 셋이 나왔다.. 1000점짜리 문제를 제외하고.. 이런 문제들 진짜 싫다.. rating은 무려 182점 폭락.. 역대 최고의 하락이었다..;; 그래도 아직 div1 유지한게 신기하다..
Level 1 - ArithmeticProgression
Problem Statement
NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.
In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference of any two successive members of the sequence is a constant. For instance, the sequence 3, 5, 7, 9, 11, 13... is an arithmetic progression with common difference 2. An arithmetic sequence can always be represented as an=a0+n*d.
You will be given a sequence seq, where seqi = [ai+1] for some nondecreasing arithmetic sequence a (both indices are 0-based). [x] denotes the floor function (see Notes). The sequence a is defined as a0+i*d. Return the minimal possible value for d. If no possible value exists for d, return -1 instead.
Definition
Notes
-
[x] denotes the floor function of x which returns the highest integer less than or equal to x. For example, [3.4] = 3, [0.6] = 0, [-1.2] = -2 and [-0.6] = -1.
-
Your return value must be accurate to within an absolute or relative tolerance of 1E-9.
Constraints
-
seq will contain between 0 and 50 elements, inclusive.
-
Each element of seq will be between -10^6 and 10^6, inclusive.
-
a0 will be between -10^6 and 10^6, inclusive.
Examples
0)
0
{6, 13, 20, 27}
Returns: 6.75
1)
1
{2, 3, 4, 5, 6}
Returns: 1.0
2)
3
{}
Returns: 0.0
Since the sequence a is nondecreasing, d must be at least 0.
3)
3
{3, 3, 3, 3, 4}
Returns: 0.2
4)
1
{-3}
Returns: -1.0
5)
0
{6, 14}
Returns: -1.0
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.
초항이 a0 이고 공차가 d인 등차수열 A가 주어진다..
수열 seq(i) = floor( A(i+1) ) 이라고 한다..
input으로 수열 a0와 seq가 들어올때 가능한 d의 최소값 구하기.. 가능한 d가 없다면 -1 return..
언듯보면 간단한 문제인것 같기도 하면서.. 또 어려운 문제이다.. 나는 도저히 솔루션이 생각이 안나서 binary search를 시도했다.. 사실 floating point number에 대해서 binary search를 시도하는게 상당히 위험한짓이다.. precision을 높이자니 TLE 날것같고.. precision을 낮추면 WA날것같고.. 나중에 다른사람 소스를 보니 의외로 나처럼 binary search를 시도한 사람이 많았다.. 그사람들 다 system test때 fail했다.. 나를 비롯해서.. ㅠ_ㅠ 다들 TLE에 걸렸나보다..
일단 공차 d = (seq[i] - a0) / (i+1) 중에서 가장 큰 값이 되어야 한다.. 고 한다.. -_- 그래야 최악의 경우도 만족시킬 수 있다.. 그리고 이렇게 구한 d가 정말로 다 맞는지 다음 식을 통해 확인해야 한다.
seq[i] == floor(a0 + (i+1) * d)
문제는 precision error인데 부동소수점을 분모와 분자로 나눠서 두개의 integer로 관리해야한다.. 흠.. 이런 방식은 이론으로만 봤는데.. 실제로 이렇게 풀어야 AC가 나는 경우는 처음이군..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <cmath>
7 using namespace std;
8
9 class ArithmeticProgression {
10 public:
11
12 double minCommonDifference(int a0, vector <int> seq)
13 {
14 int n, i;
15 long long no, den;
16 no = 0;
17 den = 1;
18 n = seq.size();
19 for (i = 0; i < n; i++) {
20 if (no * (i+1) < (seq[i] - a0) * den) {
21 no = seq[i] - a0;
22 den = i+1;
23 }
24 }
25 for (i = 0; i < n; i++) {
26 if (seq[i] != (int)(a0 + (i+1) * no / den))
27 return -1;
28 }
29 return (double)no / (double)den;
30 }
31
32 };
Level2 - InfiniteSequence2
Problem Statement
NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.
Let's consider an infinite sequence A defined as follows:
Ai = 1 for all i <= 0;
Ai = A[i/p]-x + A[i/q]-y for all i >= 1, where [x] denotes the floor function of x. (see Notes)
You will be given n, p, q, x and y. Return the n-th element of A (index is 0-based).
Definition
Class:
InfiniteSequence2
Method:
calc
Parameters:
long long, int, int, int, int
Returns:
long long
Method signature:
long long calc(long long n, int p, int q, int x, int y)
(be sure your method is public)
Notes
-
[x] denotes the floor function of x which returns the highest integer less than or equal to x. For example, [3.4] = 3, [0.6] = 0.
Constraints
-
n will be between 0 and 10^13, inclusive.
-
p and q will both be between 2 and 10^9, inclusive.
-
x and y will both be between 0 and 10^9, inclusive.
Examples
0)
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.
A(i) =
if i <= 0 then 1
else then A(floor((i / p) - x) + A(floor((i / q) - y)
일때 A(n) 을 구하는 문제..
정말 어이없이 틀렸다.. 젠장.. 쉽게 recursion으로 구할수 있는데.. TLE에 걸렸다.. 처음 TLE도 생각해보았는데.. p, q가 2 이상이므로 i가 최소한 1/2로 감소하므로.. 시간이 별로 안걸릴 줄 알았는데.. 내가 너무 과소평가했다.. ㅠ_ㅠ 이문제 역시 같은 이유로 fail한 사람이 무지 많았다.. 이따위 문제를 내다니.. 문제 출제자 도대체 누구야..
정말 드러운 문제이다.. full memorization을 하면 MLE가 나고.. memorization을 안하면 TLE가 난다.. 헐.. 대략 2000000까지만 memorize해서 풀었다..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 int p, q, x, y;
9 long long memo[2000001];
10
11 long long recur(long long u)
12 {
13 if (u <= 0)
14 return 1;
15 if (u > 2000000)
16 return recur((u/p)-x) + recur((u/q)-y);
17 if (memo[u] != -1)
18 return memo[u];
19 return memo[u] = recur((u/p)-x) + recur((u/q)-y);
20 }
21
22 class InfiniteSequence2 {
23 public:
24
25 long long calc(long long n, int P, int Q, int X, int Y)
26 {
27 long long res;
28 p = P;
29 q = Q;
30 x = X;
31 y = Y;
32 memset(memo, -1, sizeof(memo));
33 res = recur(n);
34 return res;
35 }
36
37 };
Level3 - TreeCount
Problem Statement
In graph theory, an independent set or stable set is a set of vertices in a graph such that no two of the vertices are adjacent. That is, it is a set V of vertices such that for every two vertices in V, there is no edge connecting the two.
Similarly, we can define a k-stable set as a set of vertices in a graph such that each vertex in the set has at most k adjacent vertices that are also in the set. So the 0-stable set is the original stable set.
You will be given a vector <string> graph, representing an undirected, acyclic, connected graph. The j-th character of the i-th element of graph will be 'Y' if vertices i and j are connected, or 'N' otherwise. Return a vector <int> containing exactly n elements, where n is the number of elements in graph. The i-th element should be the number of distinct i-stable sets in the graph modulo 112901989, where i is a 0-based index.
Definition
Constraints
-
graph will contain between 1 and 50 elements, inclusive.
-
Each element of graph will contain exactly N characters, where N is the number of elements in graph.
-
Each character in graph will be either 'Y' or 'N'.
-
The j-th character of the i-th element of graph will equal to the i-th character of the j-th element.
-
The i-th character of the i-th element of graph will be 'N'.
-
The graph will represent a tree.
Examples
0)
{"NYY", "YNN", "YNN"}
Returns: {5, 7, 8 }
The tree is 1-0-2. The 5 0-stable sets are {}, {0}, {1}, {2}, {1, 2}. The 7 1-stable sets are all the subsets except {0, 1, 2}. There are 2^3 subsets total, and each one is a 2-stable set.
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.
