TopCoder SRM 365 Div 1

음.. 이번 match는 완전.. -_-;;
누구의 말따라.. bloodthristy match였다.. 매우 tricky한 문제들로인해.. challenge가 난무했다..
역배점이라서 1000점이 젤 쉬운문제라는 말도 있었는데.. 결과를 보니.. 꼭 그렇지도 않았다.. 완전..;;
뭐랄까.. 완전 낚인느낌.. challenge time에서 살아남은 사람들도.. 결국 system judge에서 다 fail했다.. ㅠ_ㅠ

1000점짜리 문제를 보니 topological sort 비스무리해서.. 한번 시도해봤는데.. 결국 system fail..;; 문제가 tricky하다는 것은 알고있었는데.. 나도 fail이었을줄은 몰랐다.. ㅠ_ㅠ

이 처참한 현장이 보이는가..!

더더욱 놀라운것은.. 나는 그럼에도불구하고 rating이 올랐다는거..;; -_-; 아 놔.. 이러면 다음에도 DIV1이잖아!!


[300] PointsOnCircle

Problem Statement
     
You are given the radius r of a circle centered at the origin. Your task is to return the number of lattice points (points whose coordinates are both integers) on the circle. The number of pairs of integers (x, y) that satisfy x^2 + y^2 = n is given by the formula 4*(d1(n) - d3(n)), where di(n) denotes the number of divisors of n that leave a remainder of i when divided by 4.
Definition
   
Class:
PointsOnCircle
Method:
count
Parameters:
int
Returns:
long
Method signature:
long count(int r)
(be sure your method is public)
     
 
Constraints
-
r will be between 1 and 2*10^9, inclusive.
Examples
0)
 
     
1
Returns: 4
The only lattice points on the circle are (0, 1), (1, 0), (-1, 0), (0, -1).
1)
 
   
2000000000
Returns: 76
 
2)
 
   
3
Returns: 4
The number of lattice points on the circle of radius 3 is the same as the number of integer solutions of the equation x^2 + y^2 = 9. Using the formula from the problem statement we can calculate this number as 4*(d1(9) - d3(9)). It is easy to see that d1(9) = 2 (divisors 1 and 9) and d3(9) = 3 (divisor 3). So the answer is 4*(2 - 1) = 4.
3)
 
   
1053
Returns: 12
 
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.



 

원의 반지름이 들어오고 이 원 둘레에 놓이는 lattice point(x, y 좌표가 다 정수)의 개수를 구하는 문제..
문제에 보면 공식이 나와있다.. 공식은 r^2의 약수중에 4n+1 꼴의 약수의 개수에서 4n+3꼴의 약수의 개수를 빼면 된다.. 근데.. 계산하기 만만치 않을거같은데.. 우선 다른사람 소스를 보면서 이해해보아야겠다..

match editorial을 참고했다..

Note that we don't care about even divisors so divide r by 2 while r is even.
Find all the divisors of r using standard O(r1/2) algorithm and store them in an array v.
Note that a divisor of r2 has a form a*b where both a and b are the divisors of r.
Motivated by the third step, iterate through all pairs of elements of v (a, b) and check if we already encountered a divisor a*b (we store all previously encountered divisors in a set lookup). If not, check its remainder upon division by 4, increment respective counter (either for remainder 1, or remainder 3), and insert this divisor in lookup.

우리가 원하는 것은 r^2의 약수인데.. 그것을 구하기위해 우선 r의 약수들을 구한다 (sqrt(r)까지만 나눠보면 된다)..
이어서 "r^2의 약수 = 임의의 r의 약수 * 임의의 r의 약수" 라는 성질을 이용해서 r^2의 약수를 다 찾는다..
알고나면 간단한데.. 왜 문제풀땐 생각이 안날까.. ㅠ_ㅠ

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <set>
      6 using namespace std;
      7
      8 class PointsOnCircle {
      9 public:
     10
     11 long long count(int n)
     12 {
     13     int i, j, size;
     14     long long cnt1, cnt3, temp;
     15     vector<long long> vt;
     16     set<long long> s;
     17     set<long long>::iterator it;
     18     for (i = 1; i*i <= n; i++) {
     19         if (n % i == 0) {
     20             vt.push_back(i);
     21             if (n / i != i)
     22                 vt.push_back(n/i);
     23         }
     24     }
     25     size = vt.size();
     26     for (i = 0; i < size; i++) {
     27         for (j = 0; j < size; j++) {
     28             s.insert(vt[i]*vt[j]);
     29         }
     30     }
     31     cnt1 = cnt3 = 0;
     32     for (it = s.begin(); it != s.end(); it++) {
     33         temp = *it;
     34         if (temp % 4 == 1)
     35             cnt1++;
     36         else if (temp % 4 == 3)
     37             cnt3++;
     38     }
     39     return 4 * (cnt1 - cnt3);
     40 }
     41
     42 };

[500] ArithmeticPrograssions

Problem Statement
     
You are given a vector <string> numbers containing a set of distinct non-negative integers (no leading zeroes). Let m be the smallest integer in numbers, and let M be the largest integer in numbers. An arithmetic progression of integers a+id, a+(i+1)d, ..., a+(j-1)d, a+jd is called proper if it satisfies all of the following conditions:
It contains at least 3 distinct integers from numbers.
All of the numbers in the progression are integers between m and M, inclusive.
If it were extended in either direction, condition 2 would no longer be satisfied. In other words, neither a+(i-1)d nor a+(j+1)d are between m and M, inclusive. (See example 0 for further clarification.)
Given a proper arithmetic progression, let a be the number of integers in the progression that are contained in numbers, and let b be the total number of integers in the progression. The aptitude of the progression is defined as a divided by b. Given numbers, return the maximal aptitude of a proper arithmetic progression as a vector <string> containing exactly 2 elements representing 2 integers (with no leading zeroes), first of which divided by the second equals the maximal aptitude. The first and the second elements of vector <string> you return must represent non-negative integers which do not have common divisors greater than 1. Return {"0", "1"} if no proper arithmetic progression exists.
Definition
   
Class:
ArithmeticProgressions
Method:
maxAptitude
Parameters:
vector <string>
Returns:
vector <string>
Method signature:
vector <string> maxAptitude(vector <string> numbers)
(be sure your method is public)
   
 
Constraints
-
numbers will contain between 1 and 50 elements, inclusive.
-
Each element of numbers will contain between 1 and 18 characters, inclusive.
-
Each character of every element of numbers will be a digit ('0'-'9').
-
No element of numbers will contain '0' (zero) as its first character.
-
All elements of numbers will be distinct.
Examples
0)
 
   
{"1", "3", "5", "8"}
Returns: {"3", "4" }
We have two proper arithmetic progressions here: 1, 2, 3, 4, 5, 6, 7, 8 and 1, 3, 5, 7. Both of them can not be extended since neither 0, nor 9 lies in [1; 8] in the first case and neither -1, nor 9 lies in [1; 8] in the second case. 4 elements of the first progression belong to numbers and so its aptitude is 4/8 = 1/2. 3 elements of the second progression belong to numbers and so its aptitude is 3/4, which is highest possible in this case.
1)
 
   
{"1", "3", "5", "7", "9", "11", "13", "15", "17", "19"}
Returns: {"1", "1" }
The elements of numbers form a proper arithmetic progression, hence its aptitude is 1.
2)
 
     
{"1", "999999999999999999"}
Returns: {"0", "1" }
There are not enough elements in numbers to form a proper arithmetic progression.
3)
 
   
{"1", "7", "13", "3511", "1053", "10", "5"}
Returns: {"3", "391" }
The elements of numbers are not necessarily sorted.
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.

이 문제는 아직 읽어보지않았다.. 나중에 시간나면..



[1000] RelabelingOfGraph

Problem Statement
     
Given a directed graph on n vertices, your task is to label its vertices as follows:
Each vertex must be labeled with a distinct number between 0 and n-1, inclusive.
For every edge in the graph from vertex v1 to vertex v2, v2's label must be greater than v1's label.
You are given a vector <string> m containing the adjacency matrix of the original graph. The j-th character of the i-th element of m is '1' (one) if there is an edge in the graph from the i-th vertex to the j-th vertex, or '0' (zero) otherwise.
 
Return the labeling as a vector <int>, where the i-th element of the vector <int> is the label of the i-th vertex. If there is more than one possible labeling, return the one that comes first lexicographically. If there is no valid way to label the vertices, return an empty vector <int>.
Definition
   
Class:
RelabelingOfGraph
Method:
renumberVertices
Parameters:
vector <string>
Returns:
vector <int>
Method signature:
vector <int> renumberVertices(vector <string> m)
(be sure your method is public)
   
 
Notes
-
vector <int> a comes before vector <int> b lexicographically if a[i] < b[i] , where i is the first position in which a and b differ.
Constraints
-
m will contain between 1 and 50 elements, inclusive.
-
Each element of m will contain exactly n characters, where n is the number of elements in m.
-
Each character in each element of m will be '1' (one) or '0' (zero).
-
The i-th character of the i-th element of m will be '0'.
Examples
0)
 
   
{"0100", "0010", "0001", "0000"}
Returns: {0, 1, 2, 3 }
A chain consisting of 4 vertices.
1)
 
   
{"010", "001", "100"}
Returns: { }
We have a cycle of 3 vertices and hence can not enumerate the vertices in the desired fashion.
2)
 
   
{"00001", "00010", "00000", "00001", "00100"}
Returns: {0, 1, 4, 2, 3 }
 
3)
 
   
{"0"}
Returns: {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.

graph가 주워지고 labeling하는 문제.. labeling하는 규칙은 우선순위가 높은것부터 하고 같은경우 숫자가 낮은 vertex부터 labeling한다.

UVa 11060 - Beverages 문제와 비슷한거같아서 소스를 조금 고쳐서 submit했는데.. system test에서 fail했다.. 음.. 내 생각에는 다 맞는거 같은데.. 뭐가 틀린것인가..?


음.. 뭐가 문제인지 찾아냈다..;;
서로 관계가 없는 vertex간에는 번호가 낮은 vertex를 먼저 labeling하는 줄 알았는데.. 그게 아니라 결과를 쭉 나열했을 때, 그게 lexicographically smallest가 되어야 한다는 것이었다..
결국 문제를 잘못 이해한거였다.. ㅠ_ㅠ 어쩐지.. UVa에서 AC받은게 fail일리 없지.. ㅠ_ㅠ

match editorial을 참조하여 풀었다..

우선 floyd warshall을 이용하여 transitive closure를 구하고 cycle이 있느지를 체크한다..

있으면 labeling을 할 수 없으므로 {} 을 return한다..

그 이외의 경우는 DFS를 통해서 역으로 호출하는데..

임의의 vertex u 에 대해서 v -> u 가 있으면 v 를 호출해가는 식이다..

이러한짓을 낮은 번호부터 하면 lexy smallest로 labeling이 된다..

  1 #include <iostream>

  2 #include <string>

  3 #include <cstdio>

  4 #include <map>

  5 #include <algorithm>

  6 #include <vector>

  7 using namespace std;

  8 //#define INF 99999999

  9

 10 int n;

 11 int graph[100][100];

 12 int check[100];

 13 int tcnt;

 14

 15 void dfs(int u)

 16 {

 17     int i;

 18     for (i = 0; i < n; i++) {

 19         if (graph[i][u] && check[i] == -1)

 20             dfs(i);

 21     }

 22     check[u] = tcnt++;

 23 }

 24

 25 class RelabelingOfGraph {

 26 public:

 27

 28 vector<int> renumberVertices(vector <string> m)

 29 {

 30     int i, j, k;

 31     char buf[100];

 32     vector<int> res;

 33

 34     res.clear();

 35     n = m.size();

 36     memset(graph, 0, sizeof(graph));

 37

 38     for (i = 0; i < n; i++) {

 39         strcpy(buf, m[i].c_str());

 40         for (j = 0; j < n; j++) {

 41             graph[i][j] = buf[j] - '0';

 42         }

 43     }

 44

 45     for (k = 0; k < n; k++) {

 46     for (i = 0; i < n; i++) {

 47     for (j = 0; j < n; j++) {

 48         if (graph[i][k] && graph[k][j])

 49             graph[i][j] = 1;

 50     }

 51     }

 52     }

 53

 54     for (i = 0; i < n; i++) {

 55         if (graph[i][i])

 56             return res;

 57     }

 58

 59     tcnt = 0;

 60     memset(check, -1, sizeof(check));

 61

 62     for (i = 0; i < n; i++) {

 63         if (check[i] == -1) {

 64             dfs(i);

 65         }

 66     }

 67

 68     for (i = 0; i < n; i++) {

 69         res.push_back(check[i]);

 70     }

 71     return res;

 72 }

 73

 74 };