SRM 496

설 연휴 직전에 열렸던 매치..~

근래 있었던 매치와는 다르게 이번 매치는 약간 쉽게 나왔다..

그래도 나는 1개밖에 못풀었지만.. ㅠ_ㅠ

250 을 모처럼 빨리 풀어서 rating 을 쬐금 올렸다..~

level1 을 230 넘긴게 언제인지 가물가물 하군..~!

챌을 시도했으면 좋은 결과가 나왔을텐데..

300등 안에 들것같아서 그냥 현실과 타협한게 좀 아쉬었다..

근데.. 오늘 매치에서 한국인들의 활약이 대단한데..

Level1 - ColoredStrokes

Problem Statement

     

Manao has a bitmap H pixels high and W pixels wide. Initially, each of the pixels is white. Manao draws several (possibly zero) horizontal and/or vertical strokes. A stroke is a line segment 1 pixel thick and 1 or more pixels long. Manao only draws horizontal strokes with red color and vertical strokes with blue. He can paint a one pixel long stroke with either red or blue color, and the stroke will be considered horizontal if red and vertical if blue. Manao never draws two horizontal or two vertical strokes that overlap. If a horizontal stroke and a vertical stroke cross, the pixel at their intersection becomes green.  You're given a vector <string> picture denoting the bitmap after Manao's drawing experiments. The x-th character of the y-th element of picture describes the color of the pixel at coordinates (x, y) of the bitmap, where (0, 0) is the pixel at the top left corner and (W-1, H-1) is the pixel at the bottom right corner. 'R' is red, 'G' is green, 'B' is blue and '.' is white. Return the least possible number of strokes needed to obtain the given picture.

Definition

    

Class:

ColoredStrokes

Method:

getLeast

Parameters:

vector <string>

Returns:

int

Method signature:

int getLeast(vector <string> picture)

(be sure your method is public)

    

 

Constraints

-

picture will contain between 1 and 50 elements, inclusive.

-

Each element of picture will be between 1 and 50 characters long, inclusive.

-

All elements of picture will have equal length.

-

Each character in picture will be 'R', 'G', 'B' or '.'.

Examples

0)

 

    

{"...",

 "..."}

Returns: 0

The picture is blank, Manao made no strokes.

1)

 

    

{"..B.",

 "..B."}

Returns: 1

A single vertical stroke is enough.

2)

 

    

{".BB."}

Returns: 2

Since only vertical strokes are painted with blue color, this picture needs two strokes.

3)

 

    

{"...B..",

 ".BRGRR",

 ".B.B.."}

Returns: 3

One horizontal and two vertical strokes are necessary for this masterpiece.

4)

 

    

{"...B..",

 ".BRBRR",

 ".B.B.."}

Returns: 4

This is the same picture as in the previous case with pixel (3,1) colored blue instead of green. Therefore, a single horizontal stroke won't help.

5)

 

    

{"GR",

 "BG"}

Returns: 4

가로로 칠하면 red, 세로로 칠하면 blue, 겹치면 green 이 될때, 주어진 그림판이 나오려면 최소 몇번을 칠해야하나?

처음에 가로 방향으로 scan => red 다 없애고.. 그담에 세로 방향으로 scan!

  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 ColoredStrokes {

 13 public:

 14

 15 int getLeast(vector <string> pic)

 16 {

 17     int n, m;

 18     int i, j, k;

 19     int cnt;

 20     n = pic.size();

 21     m = pic[0].size();

 22     cnt = 0;

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

 24         for (j = 0; j < m; j++) {

 25             if (pic[i][j] == 'R' || pic[i][j] == 'G') {

 26                 cnt++;

 27                 for (k = j; k < m; k++) {

 28                     if (pic[i][k] == 'R') {

 29                         pic[i][k] = '.';

 30                     }

 31                     else if (pic[i][k] == 'G') {

 32                         pic[i][k] = 'B';

 33                     }

 34                     else {

 35                         break;

 36                     }

 37                 }

 38             }

 39         }

 40     }

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

 42         for (j = 0; j < m; j++) {

 43             if (pic[i][j] == 'B') {

 44                 cnt++;

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

 46                     if (pic[k][j] == 'B') {

 47                         pic[k][j] = '.';

 48                     }

 49                     else {

 50                         break;

 51                     }

 52                 }

 53             }

 54         }

 55     }

 56     return cnt;

 57 }

 58

 59 };

Level2 - OneDimensionalBalls

Problem Statement

     

There is an infinite axis with N balls on it. The balls are moving with equal positive velocity, some of them in the positive direction of the axis and some in the opposite. The balls are small enough to be treated as points on the axis. If two balls meet at a point, they do not collide, and instead, they each continue moving in the same direction and at the same speed as before.  Manao is shown a picture of the axis taken at some moment of time. All the balls are at different points in the picture. The balls are numbered from 0 to N-1 and the i-th ball is at point firstPicture[i].  Some time after the first picture is taken, several balls are added to the axis and another picture is taken. Yet again, no two balls share a point in this picture. The balls seem indistinguishable and their coordinates are given in vector <int> secondPicture in ascending order.  For each ball in the second picture, Manao has to guess whether it is present on the first one as well, and if so, say its number. Sometimes, this can't be determined unambiguously, so any valid guess is welcome. A guess is valid if the balls could move in the way described above and appear in the named locations in the second picture. Two guesses are different if there is a ball in the second picture which Manao identifies differently in these guesses. Return the number of valid guesses for the given pictures.

Definition

    

Class:

OneDimensionalBalls

Method:

countValidGuesses

Parameters:

vector <int>, vector <int>

Returns:

long long

Method signature:

long long countValidGuesses(vector <int> firstPicture, vector <int> secondPicture)

(be sure your method is public)

    

 

Constraints

-

firstPicture will contain N elements, where N is between 1 and 50, inclusive.

-

Each element of firstPicture will be between 0 and 100,000,000, inclusive.

-

Elements in firstPicture will be distinct.

-

secondPicture will contain between N and 50 elements, inclusive.

-

Each element of secondPicture will be between 0 and 100,000,000, inclusive.

-

Elements in secondPicture will be in strictly ascending order.

Examples

0)

 

    

{12,11}

{10,11,13}

Returns: 3

There are 2 balls in the first picture at points 12 and 11, respectively. One more ball is added in the second picture. The following three guesses are valid: 1) The ball at point 10 is ball 0, the ball at point 11 is the new one, the ball at point 13 is ball 1. 2) The ball at point 10 is ball 1, the ball at point 11 is ball 0, the ball at point 13 is the new one. 3) The ball at point 10 is ball 1, the ball at point 11 is the new one, the ball at point 13 is ball 0. 

1)

 

    

{1,2,3}

{1,2,3}

Returns: 0

Each picture contains the same number of balls, so they must contain the same set of balls. However, given that some time has passed between the shots, and the balls move with equal positive velocity, there is no way for them to have interchanged positions.

2)

 

    

{1,3}

{1,3}

Returns: 1

If the balls move in opposite directions, they will interchange their positions at some moment.

3)

 

    

{7234}

{6316,689156,689160,689161,800000,1000001}

Returns: 6

Ball 0 could be any of the balls in the second picture.

4)

 

    

{6,2,4}

{1,2,3,4,5,7,8}

Returns: 7

 

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.

first 원소들이 + 또는 - 쪽으로 등속도로 움직일때, first -> second 가 가능한 경우의 수

to be updated..

Level3 - YetAnotherHamiltonianPath

Problem Statement

     

A Hamiltonian path in an undirected graph with N vertices is a sequence of vertices A1, A2, ..., AN such that all Ai are pairwise distinct and for each i (1 < i ≤ N), there is an edge between vertices Ai-1 and Ai. A path starts at vertex A1 and visits each vertex of the sequence in order, ending at vertex AN. The cost of a path is the sum of the weights of the edges connecting the path's consecutive vertices.  You're given a graph where the i-th (0-based) vertex is labeled with string label[i]. There is an edge between each pair of vertices. The cost of the edge between vertices i and j is equal to length^2 (label[i]) + length^2 (label[j]) - length^2 (LCP (label[i], label[j]) ), where "^2" denotes squaring operation, length(X) is the length of string X and LCP(X,Y) is the longest common prefix of strings X and Y.  Return the minimum possible cost of a Hamiltonian path which starts at vertex 0 and ends at vertex 1.

Definition

    

Class:

YetAnotherHamiltonianPath

Method:

leastCost

Parameters:

vector <string>

Returns:

int

Method signature:

int leastCost(vector <string> label)

(be sure your method is public)

    

 

Notes

-

A prefix of string S is a string that can be obtained by removing zero or more contiguous characters from the end of S.

-

The longest common prefix of two strings A and B is the longest possible string which is a prefix of both A and B.

Constraints

-

label will contain between 2 and 50 elements, inclusive.

-

Each element of label will be between 1 and 50 characters long, inclusive.

-

Each element of label will consist of lowercase letters ('a'-'z') only.

Examples

0)

 

    

{"home", "school", "pub"} 

Returns: 70

The only possible Hamiltonian path from vertex 0 to vertex 1 is 0->2->1. Vertex 0 is labeled "home", and vertex 1 is labeled "pub", so since these two strings have no common prefix, the cost of the edge 0->1 is 4^2+3^2=25. The cost of the edge 2->1 is 45, so the total cost of the path is 70.

1)

 

    

{"school", "home", "pub", "stadium"}

Returns: 167

Of the two possible Hamiltonian paths, the cost of the one that visits "stadium" right after "school" is 1 less than the other one's.

2)

 

    

{"abcd","aecgh","abef","aecd"}

Returns: 91

The cost matrix of this graph is:

-- 40 28 31

40 -- 40 32

28 40 -- 31

31 32 31 --

The optimal path is "abcd"->"abef"->"aecd"->"aecgh".

3)

 

    

{"canada", "cyprus", "croatia", "colombia", "chile", "china", "cameroon"}

Returns: 509

 

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.

두 string 사이의 거리는 lenth(s1)^2 + length(s2)^2 - (longest common prefix of s1 and s2)^2 일때,

s0 -> s1 으로 가는 최소 거리 구하기 

문제의 요점은 shortest path 를 찾는것인데.. cost 가 최소가 되도록 하려면

최대한 lcp 가 큰 쪽으로 가야한다.. 그렇게 하려면 sort 한 다음에 순서대로 가면 되겠다..

문제는 원하는 답은 0번에서 시작해서 1번에서 끝나야하는데.. sort 한 결과는 항상 그렇지 않다는 점이다..

그러나 식을 조금만 고쳐서 원하는 결과를 얻을 수 있는데..

sort 한 처음 node 와 끝 node 의 cost 관계를 적용하고..

원래 0번 node 와 1번 node 의 cost 를 끊어주면 된다..

왜 그렇게 되는지 증명은.. 쩝.. 어려움.. ㅠ_ㅠ;;

  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 lcp(string s1, string s2)

 13 {

 14     int i;

 15     i = 0;

 16     while (i < s1.size() && i < s2.size()) {

 17         if (s1[i] != s2[i])

 18             break;

 19         i++;

 20     }

 21     return i;

 22 }

 23

 24 class YetAnotherHamiltonianPath {

 25 public:

 26

 27 int leastCost(vector <string> label)

 28 {

 29     int n;

 30     int i, k;

 31     int sum;

 32     int c1, c2;

 33     n = label.size();

 34     sum = 0;

 35     sum += label[0].size() * label[0].size();

 36     sum += label[1].size() * label[1].size();

 37     for (i = 2; i < n; i++) {

 38         sum += 2 * label[i].size() * label[i].size();

 39     }

 40     c1 = lcp(label[0], label[1]);

 41     sort(label.begin(), label.end());

 42     c2 = lcp(label[0], label[n-1]);

 43     for (i = 1; i < n; i++) {

 44         k = lcp(label[i-1], label[i]);

 45         sum -= k * k;

 46     }

 47     sum += c1 * c1;

 48     sum -= c2 * c2;

 49     return sum;

 50 }

 51

 52 };