TopCoder SRM 368 Div 1

이번 매치는 완전.. 역대 최악이었다.. 이보다 더 안좋을수도있을까..?
-25점이란 역대 최악의 점수로 방 꼴찌 전체 508등.. ㅠ_ㅠ
덕분에 rating도 폭락하면서 역대 최저 rating(1086)을 마크했다..
250점짜리는 만만해보였는데.. 500점짜리도 쉬워보여서 더 사람들이 못풀것같은 500점짜리 먼저 시도..
근데 코딩에서 삽질하는바람에 한시간 다 보내고 500점짜리도 망쳐버렸다.. ㅠ_ㅠ
괜히 블챌하다가 25점만 더 잃었다.. 흑흑.. ㅠ_ㅠ;
sysfail과 challenge가 난무했는데도 불구하고.. 난 test case를 구리게 만들어서 실패했다.. 젠장 두고봐!!!!

젠장.. 공동꼴찌.. 완전 굴욕이다..

쭉쭉 폭락하는구나.. DIV1에서 한문제라도 풀려고했지만.. 다음으로 미뤄야겠다.. 우선 상금매치를위해 rating관리 들어가야겠다..

[250] JumpingBoard

Problem Statement
    
You are given a rectangular board where each cell contains either an integer between 1 and 9, inclusive, or a hole.
Place a token into the cell in the upper left corner of the board. Now you can play a simple game. The game consists of moves, and each move looks as follows:
Look at the number X written in the cell where your token is placed.
Choose one of the four basic directions (up, down, left, or right).
Move your token exactly X cells in the chosen direction. You can jump over all intermediate holes in the path.
The game ends after a move that lands the token in a hole or outside the board. Your goal is to make as many moves as possible.
The board is given as a String[] board. Characters '1' to '9' represent cells containing the corresponding integer, and letters 'H' represent holes. The upper left corner of the board corresponds to the first character of the first element of board.
Write a method that will compute the maximum number of moves you can make on the given board. If it is possible to make an arbitrarily large number of moves, your method should return -1.
Definition
   
Class:
JumpingBoard
Method:
maxJumps
Parameters:
String[]
Returns:
int
Method signature:
int maxJumps(String[] board)
(be sure your method is public)
   
 
Constraints
-
board will contain between 1 and 50 elements, inclusive.
-
Each element of board will contain between 1 and 50 characters, inclusive.
-
All elements of board will be of the same length.
-
Each element of board will only contain characters from the string "123456789H" (quotes for clarity).
-
The first character of the first element of board will not be 'H'.
Examples
0)
 
   
{"3942178",
 "1234567",
 "9123532"}
Returns: 5
In the first move you have to move the token to the right. In the second move you have three choices. Moves to the left and to the right would bring you to cells with a 9 and a 7, respectively, forcing you to end the game in the third move. The optimal strategy is to make the second move down, the third one to the right, and the fourth one up or to the left. In the last fifth move you are forced to leave the board.
1)
 
   
{"2H3HH4HHH5"}
Returns: 4
Remember that you are allowed to jump over holes. Only landing in a hole is bad.
2)
 
   
{"3994",
 "9999",
 "9999",
 "2924"}
Returns: -1
Make the first move down, and then you can jump left and right as many times as you wish.
3)
 
   
{"123456",
 "234567",
 "345678",
 "456789"}
Returns: 4
On this board, all moves that don't end the game lead to the right or down. In the best solution, the first three moves are: right, down, right.
4)
 
   
{"9"}
Returns: 1
There is no real choice here. The game will always end after the first move.
5)
 
   
{"2H9HH11",
 "HHHHH11",
 "9HHHH11"}
Returns: 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.

이 문제는 (0,0)에서 시작해서 그 칸에 적혀있는 숫자만큼 위아래좌우로 이동할 수 있다.. 단 H에 빠지면 안되고 밖으로 나가서도 안된다.. 최대 몇번을 이동할 수 있는지 구하는 문제.. cycle이 생기는 경우 -1을 return

역시 젤 만만한 문제였다.. longest path를 구하는문제.. dfs로 search하면서 각 노드에서 갈수있는 최대 길이를 memorization했다.. 그러고보니 교내 프로그래밍 경진대회때 내가 낸 문제랑 비슷하군.. 물론 이게 더 어렵다..
근데.. 왜케 코드가 길지.. -_-;

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 int n, m;
      9 int is_cycle;
     10 int dp[51][51];
     11 char map[51][51];
     12 char check[51][51];
     13
     14 int dfs(int u, int v)
     15 {
     16     int i, j, k;
     17     int max1 = 1;
     18
     19     k = map[u][v] - '0';
     20     if (v+k < m && map[u][v+k] != 'H') {
     21         if (check[u][v+k] == 1) {
     22             is_cycle = 1;
     23             return -1;
     24         }
     25         if (dp[u][v+k]) {
     26             max1 = max(max1, dp[u][v+k]+1);
     27         }
     28         else {
     29             check[u][v+k] = 1;
     30             dp[u][v+k] = dfs(u, v+k);
     31             max1 = max(max1, dp[u][v+k]+1);
     32             check[u][v+k] = 2;
     33         }
     34     }
     35     if (v-k >= 0 && map[u][v-k] != 'H') {
     36         if (check[u][v-k] == 1) {
     37             is_cycle = 1;
     38             return -1;
     39         }
     40         if (dp[u][v-k]) {
     41             max1 = max(max1, dp[u][v-k]+1);
     42         }
     43         else {
     44             check[u][v-k] = 1;
     45             dp[u][v-k] = dfs(u, v-k);
     46             max1 = max(max1, dp[u][v-k]+1);
     47             check[u][v-k] = 2;
     48         }
     49     }
     50     if (u-k >= 0 && map[u-k][v] != 'H') {
     51         if (check[u-k][v] == 1) {
     52             is_cycle = 1;
     53             return -1;
     54         }
     55         if (dp[u-k][v]) {
     56             max1 = max(max1, dp[u-k][v]+1);
     57         }
     58         else {
     59             check[u-k][v] = 1;
     60             dp[u-k][v] = dfs(u-k, v);
     61             max1 = max(max1, dp[u-k][v]+1);
     62             check[u-k][v] = 2;
     63         }
     64     }
     65     if (u+k < n && map[u+k][v] != 'H') {
     66         if (check[u+k][v] == 1) {
     67             is_cycle = 1;
     68             return -1;
     69         }
     70         if (dp[u+k][v]) {
     71             max1 = max(max1, dp[u+k][v]+1);
     72         }
     73         else {
     74             check[u+k][v] = 1;
     75             dp[u+k][v] = dfs(u+k, v);
     76             max1 = max(max1, dp[u+k][v]+1);
     77             check[u+k][v] = 2;
     78         }
     79     }
     80     return dp[u][v] = max1;
     81 }
     82
     83 class JumpingBoard {
     84 public:
     85
     86 int maxJumps(vector<string> board)
     87 {
     88     int i, j, max1;
     89     m = board[0].size();
     90     n = board.size();
     91     for (i = 0; i < n; i++) {
     92         strcpy(map[i], board[i].c_str());
     93     }
     94     memset(dp, 0, sizeof(dp));
     95     memset(check, 0, sizeof(check));
     96
     97     is_cycle = 0;
     98     check[0][0] = 1;
     99     dfs(0, 0);
    100     if (is_cycle)
    101         return -1;
    102
    103     max1 = 0;
    104     for (i = 0; i < n; i++) {
    105         for (j = 0; j < m; j++) {
    106             max1 = max(max1, dp[i][j]);
    107         }
    108     }
    109     return max1;
    110 }
    111
    112 };

이방법 말고 Bellman-Ford를 이용하는 기발한 방법이 여기 설명되어 있다..




[500] PolylineUnion

Problem Statement
    
A polyline is a sequence of line segments such that each segment starts at the point where the previous segment ended.
If two polylines have a common point, we say that they belong to the same picture. The common point does not have to be an endpoint of a line segment.
Your method will be given a vector <string> polylines. Concatenate the elements of polylines to get a space-separated list of polyline descriptions. Each polyline description consists of one or more point descriptions, separated by single dashes ('-'). Each point is described by its two non-negative integer coordinates, separated by a comma (',').
Return the number of pictures in the union of all the given polylines.
Definition
   
Class:
PolylineUnion
Method:
countComponents
Parameters:
vector <string>
Returns:
int
Method signature:
int countComponents(vector <string> polylines)
(be sure your method is public)
   
 
Notes
-
The point sequence that defines a polyline may contain the same point more than once, and even consecutive points are allowed to be equal.
-
A polyline may be just a single point.
Constraints
-
polylines will have the format described in the problem statement.
-
polylines will contain between 1 and 50 elements, inclusive.
-
Each of the elements in polylines will contain between 0 and 50 characters, inclusive.
-
Each coordinate of each point specified in polylines will be between 0 and 10000, inclusive.
-
The point coordinates in polylines will not contain unnecessary leading zeros.
Examples
0)
 
   
{"0,0-10,10 0,10-10,0"}
Returns: 1
Two intersecting line segments form a single picture.
 
1)
 
   
{"0,0-10,5 5,0-15,5-10,10-5,5"}
Returns: 2
Two non-intersecting polylines.
 
2)
 
   
{"1","3,0-5,5 4,0-4,20"}
Returns: 2
Note that you first have to concatenate the elements of polylines and only then parse the resulting string.
3)
 
   
{"10,0-10,1-9,2-9,3-8,4 ","8,2-9,2-10,3 ","12,2-11,2-9,1"}
Returns: 1
Together, these three polylines form a single picture. From a graph theoretical point of view, this picture can be seen as a tree with 11 vertices. (Ten of them are the given points and one is the intersection of 10,1-9,2 and 11,2-9,1.)
 
4)
 
   
{"0,0-10,0-0,0 20,0-8,0-20,0"}
Returns: 1
The union of these two polylines is the line segment 0,0-20,0.
5)
 
   
{"1,1 2,2 3,3 4,4 3,3-4,4"}
Returns: 3
A single point is a special case of a polyline.
6)
 
   
{"10,10-20,10 20,10-15,18 15,18-10,10"}
Returns: 1
A triangle.
7)
 
   
{"1,1 1,1"}
Returns: 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.

인풋으로 점또는 선분 또는 서로 이어진 선분(polyline)이 들어온다.. 총 몇개의 picture로 구성되어있는지 구하는 문제.. 즉, connected component가 몇개인지..

선분교차를 구현한게 있어서 거져먹기위해 이문제를 덥석 물었다.. 헐.. 근데 코딩하다가 꼬이더니.. 결국 못풀었다.. 답이 이상하게 나오길래.. 나중에 확인해보니 '=' 을 '=='으로 잘못쓴게있었다.. OTL .. ㅠ_ㅠ;;
고쳐서 submit해봤는데 역시 아직도 sysfail이다.. 뭐.. 고치기는 귀찮고.. 아마도 input parsing을 잘못한듯 싶다..

결국 선분교차 알고리즘을 이용하여 해결..~

1) single point로 주어진 경우 (x1, y1) - (x1, y1) 이라는 선분으로 생각하면 쉽다..

2) parsing이 열라 짜증나는데.. strtok 를 이중으로 쓰면 안되더군.. 새로운사실..?



[1000] BinaryCodes

Problem Statement
    
Given a finite alphabet S, a binary code over this alphabet S is a function that maps each element of S to some (possibly empty) string over the alphabet {0,1}.
An example of such a code for S={a,b,c,d} is the function f defined by f(a)=1, f(b)=1010, f(c)=01, f(d)=10101.
Any binary code can be naturally extended to encode strings over the alphabet S simply by concatenating the codes of the string's letters, in order. For example, using the code mentioned above we can encode cac as f(cac)=01101.
A code is called ambiguous if there are two different strings over S that have the same encoding. Obviously, in practice we want to avoid using an ambiguous code.
A code is called really ambiguous if there are three different strings over S that have the same encoding. For example, the code from the above example is really ambiguous: the strings ba, acc, and d are all encoded to 10101.
You will be given a vector <string> code containing the strings over {0,1} used to encode letters of some alphabet S. Your method should check whether this code is really ambiguous. If it is really ambiguous, find a shortest string over {0,1} that is an encoding of (at least) three different strings over S, and return its length. If the given code is not really ambiguous, return -1.
Definition
   
Class:
BinaryCodes
Method:
ambiguous
Parameters:
vector <string>
Returns:
int
Method signature:
int ambiguous(vector <string> code)
(be sure your method is public)
   
 
Notes
-
Your method does not need to know the actual elements of S, and the size of S is obviously equal to the number of elements in code.
Constraints
-
code will contain between 2 and 30 elements, inclusive.
-
Each element of code will contain between 0 and 50 characters, inclusive.
-
Each element of code will only contain the characters '0' (zero) and '1' (one).
Examples
0)
 
   
{"1","1010","01","10101"}
Returns: 5
This is the example from the problem statement, and the string 10101 is the shortest string that can be decoded in three different ways.
1)
 
   
{"0","1"}
Returns: -1
This code is obviously not ambiguous.
2)
 
   
{"0","11","11","11"}
Returns: 2
This is clearly a really ambiguous code, as there are three different one letter strings over S that are encoded to 11.
3)
 
   
{"0000","001","01001","01010","01011"}
Returns: -1
This code is a prefix code, i.e., no code word is a prefix of another code word. If a code has this property, it is guaranteed that it is not ambiguous, but the other direction is not true.
4)
 
   
{"1","10","00"}
Returns: -1
This is not a prefix code, but it can easily be shown that this code is not ambiguous.
5)
 
   
{"","01101001001","111101011"}
Returns: 0
Having an empty code word is a great way how to design a really ambiguous code.
6)
 
   
{"00011011","000110","11","0001","1011","00","011011"}
Returns: 8
The shortest proof that this code is really ambiguous is 00011011. Note that this string can in fact be decoded in four different ways.
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.

각 문자를 나타내는 2진 코드가 주어진다. 어떤 encoding된 코드가 3개 이상의 문자열로 decoding된다면 "really ambiguous"라고 한다. "really ambiguous"한 가장 짧은 코드를 찾는 문제

음.. 모르겠다.. -_-;;