탑코더 스름 426 디비젼 1

토->일 넘어가는 새벽 2시에 열린 매치.. 이번 매치는 정말 극악의 매치였다..~
특히 한국사람들은.. 새벽 두시에 졸음을 참으며 열심히 문제를 풀어야했고..
챌린지패이스에서 문제가 생기는바람에 시스템 테스트도 한참 늦게 해줘서..
채점 기다리느라 다들 고생이 많았다..;; 나도 덕분에 날밤 까고 말았다.. =_=;;;
게다가 250점 문제는 쉬운 문제임에도 불구하고 문제 디스크립션이 너무 엉망이라서..
대부분의 사람들이 낮은 코딩점수를 받았다.. (해석을 늦게해서.. -_-;;) 아.. 문제 출제자.. 좀 너무한거 아녀..~
이번 매치에서는 우리방에 챌이 하나도 없었다.. 시도한 사람조차 없었다..;;
남들 코드가 좀 의심가기는 하지만.. 마땅히 fail시킬 수 있는 케이스를 찾는것도 넘 힘들고..
좀 재미없었던 매치..

시스템 테스트도 안되고있고.. 해서 사람들이 매치 끝나고 다들 어드민 방에 모여서 잡담을 하며 놀기도 했다..

Level1 - ShufflingMachine

Problem Statement
     
A card shuffling machine is a device designed to randomize the order of a deck of cards. A particularly poor (but unfortunately relatively common) design of machine works as follows: an integer N is selected uniformly at random between 1 and maxShuffles, inclusive, and a series of N exactly similar deterministic shuffles are performed. A deterministic shuffle is a fixed permutation of the cards. The randomness of the resulting ordering is clearly therefore only dependent on the number of shuffles chosen. After the deck has been shuffled N times, the cards are distributed to the players.
A particularly dishonest player has decided that he wishes to cheat. He has identified K cards in the deck that he wants to receive when the cards are distributed. He has managed to figure out both the fixed shuffle that the machine uses and also the maximum number of shuffles chosen. The fixed shuffle is given in a vector <int> shuffle, in which element i gives the position after the shuffle of the card that was initially in position i (both 0-based). The positions in the deck of the cards the player will receive after they have been shuffled are given in cardsReceived (0-based). Before the cards are shuffled, the player can order them in any way he wishes. Determine the initial ordering that will maximize the expected number of the K desired cards that he will receive and return this expected number.
Definition
   
Class:
ShufflingMachine
Method:
stackDeck
Parameters:
vector <int>, int, vector <int>, int
Returns:
double
Method signature:
double stackDeck(vector <int> shuffle, int maxShuffles, vector <int> cardsReceived, int K)
(be sure your method is public)
   
 
Notes
-
Your return value must be accurate to an absolute or relative tolerance of 1e-9.
Constraints
-
shuffle will contain between 1 and 50 elements, inclusive.
-
shuffle will be a permutation of the numbers between 0 and M-1, inclusive, where M is the number of elements in shuffle.
-
maxShuffles will be between 1 and 100, inclusive.
-
cardsReceived will contain between 1 and M elements, inclusive.
-
Each element of cardsReceived will be between 0 and M-1.
-
The elements of cardsReceived will be distinct.
-
K will be between 1 and M, inclusive.
Examples
0)
 
   
{1,0}
3
{0}
1
Returns: 0.6666666666666666
This deck contains only 2 cards and they swap positions after each shuffle. The cheating player receives first card in the deck after the shuffling is completed and he wants to receive 1 of the cards in the deck. If the deck is shuffled 1 or 3 times, he will receive the card that was initially in position 1. If the deck is shuffled 2 times, he will receive the card in position 0. It is therefore optimal to put the card that he wants in position 1 and he will receive it 2 times out of 3.
1)
 
   
{1,2,0}
5
{0}
2
Returns: 0.8
If he puts the cards he wants in positions 1 and 2, he will receive one of them 4 times out of 5.
2)
 
   
{1,2,0,4,3}
7
{0,3}
2
Returns: 1.0
If he puts the cards in positions 3 and 4, he will receive exactly one of them, regardless of how many shuffles are chosen.
3)
 
   
{0,4,3,5,2,6,1}
19
{1,3,5}
2
Returns: 1.0526315789473684
 
4)
 
   
{3,4,7,2,8,5,6,1,0,9}
47
{6,3,5,2,8,7,4}
8
Returns: 6.297872340425532
 
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.

N개의 카드가 있고.. 이 카드를 섞는데.. 섞는 규칙은 shuffle 이라는 1부터 N까지 수의 permutation에 따른다.. 그러나 몇번 섞는지는 알 수 없고 최소 1번에서 최대 maxShuffle번을 섞는다.. 그리고나서 카드를 분배하게되는데.. 나는 cardReceived 번째의 카드들을 받게 된다.. 내가 원하는 카드가 K개이고 맨 처음 모든 카드의 순서를 내 맘대로 바꿀 수 있다.. 내가 받을 수 있는 원하는 카드의 기대값 구하기..

우선 1부터 maxShuffle번까지의 permutation을 다 구한다.. 그중에서 cardReceived column에 있는 수들만 쭉 읽어서 가장 많이 나온 수를 K개 고르면 된다.. 그 수들을 처음에 내가 원하는 곳에 위치시킬 수 있으므로..

코딩은 의외로 깔끔했는데.. 문제 해석이 오래걸려서 125점에 그쳤다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int comp(const void* x, const void* y)
  9 {
 10     int* a = (int*)x;
 11     int* b = (int*)y;
 12     return *b - *a;
 13 }
 14
 15 class ShufflingMachine {
 16 public:
 17
 18 double stackDeck(vector <int> shuffle, int maxShuffles, vector <int> cardsReceived, int K)
 19 {
 20     int m, n;
 21     int i, j, sum;
 22     int perm[200][200];
 23     int cnt[200];
 24     m = shuffle.size();
 25     n = cardsReceived.size();
 26     for (i = 0; i < m; i++) {
 27         perm[0][i] = i;
 28     }
 29     for (i = 1; i < maxShuffles; i++) {
 30         for (j = 0; j < m; j++) {
 31             perm[i][shuffle[j]] = perm[i-1][j];
 32         }
 33     }
 34     memset(cnt, 0, sizeof(cnt));
 35     for (i = 0; i < maxShuffles; i++) {
 36         for (j = 0; j < n; j++) {
 37             cnt[perm[i][cardsReceived[j]]]++;
 38         }
 39     }
 40     qsort(cnt, 200, sizeof(int), comp);
 41     sum = 0;
 42     for (i = 0; i < K; i++) {
 43         sum += cnt[i];
 44     }
 45     return (double)sum / (double)maxShuffles;
 46 }
 47
 48 };

Level2 - CatchTheMice

Problem Statement
     
A fairground operator has designed a new game, called "Catch the Mice". This consists of a set of electronic "mice" that move around on a large board. The contestant controls a square cage, which is initially suspended above the board. The contestant can position the cage anywhere above the board and then drop it, the aim being to enclose some of the mice in the cage. The contestant wins a prize accoring to how many mice he managed to capture. If the contestant captures all of the mice, then he wins the grand prize, which is a sports car. However the fairground operator is not entirely honest, and wants your help to rig the game so that it is impossible to win the grand prize. He wants to make the cage sufficiently small that at no point in time are the mice close enough for it to capture them all.
Consider the mice as a set of points moving in an infinite 2D cartesian plane. Each mouse starts at a known position at time t = 0, then moves with constant velocity in time t ≥ 0. Consider the cage as a perfect square of side length L, that can be positioned anywhere in the plane with its sides parallel to the axes (i.e., the contestant can move, but cannot rotate the cage). The cage can be dropped at any time t ≥ 0 and it will capture a mouse if at that point in time the mouse's position is strictly contained within its boundary (mice exactly on the boundary are not considered to be captured). You should calculate the maximum value of L that doesn't allow all the mice to be captured.
You will be given 4 vector <int>s xp, yp, xv and yv. The position of the mouse with index i is given by (xp[i], yp[i]) and its velocity by (xv[i], yv[i]). The position of the mouse at time t will therefore be (xp[i] + xv[i]*t, yp[i] + yv[i]*t). Return a double giving the length of the side of the largest cage that cannot capture all the mice at any time t ≥ 0.
Definition
   
Class:
CatchTheMice
Method:
largestCage
Parameters:
vector <int>, vector <int>, vector <int>, vector <int>
Returns:
double
Method signature:
double largestCage(vector <int> xp, vector <int> yp, vector <int> xv, vector <int> yv)
(be sure your method is public)
   
 
Notes
-
Your return value must be accurate to an absolute or relative tolerance of 1e-9.
Constraints
-
xp, yp, xv and yv will contain between 2 and 50 elements, inclusive.
-
xp, yp, xv and yv will contain the same number of elements.
-
Each element of xp, yp, xv and yv will be between -1000 and 1000, inclusive.
-
At no point in time t ≥ 0 will any two mice occupy the same point in space.
Examples
0)
 
   
{0,10}
{0,10}
{10,-10}
{0,0}
Returns: 10.0
A cage with side length greater than 10 would be able to catch both the mice at any time before t = 1.
1)
 
   
{0,10,0}
{0,0,10}
{1,-6,4}
{4,5,-4}
Returns: 3.0
At time t = 1, the mice are at positions (1, 4), (4, 5) and (4, 6). At this point in time any cage with an edge length larger than 3 would be able to catch them. This is the point in time when the mice are closest together.
2)
 
   
{50,10,30,15}
{-10,30,20,40}
{-5,-10,-15,-5}
{40,-10,-1,-50}
Returns: 40.526315789473685
 
3)
 
   
{0,10,10,0}
{0,0,10,10}
{1,0,-1,0}
{0,1,0,-1}
Returns: 10.0
 
4)
 
   
{13,50,100,40,-100}
{20,20,-150,-40,63}
{4,50,41,-41,-79}
{1,1,1,3,-1}
Returns: 212.78688524590163
 
5)
 
   
{0,10}
{0,0}
{5,5}
{3,3}
Returns: 10.0
 
6)
 
   
{-49,-463,-212,-204,-557,-67,-374,-335,-590,-4}
{352,491,280,355,129,78,404,597,553,445}
{-82,57,-23,-32,89,-72,27,17,100,-94}
{-9,-58,9,-14,56,75,-32,-98,-81,-43}
Returns: 25.467532467532468
 
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.

쥐들의 x, y 좌표가 주어지고 x방향 y방향 속도가 각각 주어진다.. t초 후의 번 쥐의 위치는 (xp[i]+xv[i]*t, yp[i]+yv[i]*t) 가 된다. 이때, 모든 순간에 대해서 모든 쥐를 다 포함할 수 없는 가장 큰 직사각형 구하기.. 경계선에 걸치는것은 포함되지 않는것으로 간주..

이 문제는 ternary search를 이용해서 풀 수 있다.. 

예를들어 쥐들이 처음에는 좀 멀리 떨어져있다가 시간이 흘러서 어느 특정 시점에 서로 가장 가까워지고

그 시점이 지나면 다시 멀어진다는 가정이 맞아야 한다..

직관적으로 생각해보면 맞는것 같기도하고.. ㅇ.ㅇ;;

따라서  f(x) = 시간 x에 대해 모든 쥐를 잡을 수 있는 가장 작은 사각형의 side

라고 정의하면 f(x)는 unimodal 형태가 되므로 ternary search 적용이 가능하다..

ternary search에 대한 더 자세한 내용은 알고스팟 강좌를 참조하자..

  1 #include <iostream>

  2 #include <cstdio>

  3 #include <algorithm>

  4 #include <vector>

  5 #include <string>

  6 using namespace std;

  7 #define INF 999999999.0

  8 #define min(x, y) ((x) > (y) ? (y) : (x))

  9 #define max(x, y) ((x) > (y) ? (x) : (y))

 10

 11 typedef struct _p {

 12     double x, y;

 13 } POINT;

 14

 15 POINT pt[100], dt[100];

 16 int n;

 17

 18 double f(double p)

 19 {

 20     double minx, miny, maxx, maxy;

 21     double x, y;

 22     int i;

 23     minx = miny = INF;

 24     maxx = maxy = -INF;

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

 26         x = pt[i].x + dt[i].x * p;

 27         y = pt[i].y + dt[i].y * p;

 28         minx = min(minx, x);

 29         miny = min(miny, y);

 30         maxx = max(maxx, x);

 31         maxy = max(maxy, y);

 32     }

 33     return max(maxx-minx, maxy-miny);

 34 }

 35 double t_search(double left, double right)

 36 {

 37     int it;

 38     double a, b;

 39     it = 200;

 40     while (it--) {

 41         a = (left * 2.0 + right) / 3.0;

 42         b = (left + right * 2.0) / 3.0;

 43

 44         /* f(): 감소 -> 증가 */

 45         if (f(a) > f(b))

 46             left = a;

 47         else

 48             right = b;

 49     }

 50     return f((left + right) * 0.5);

 51 }

 52

 53 class CatchTheMice {

 54 public:

 55

 56 double largestCage(vector<int> xp, vector<int> yp, vector<int> xv, vector<int> yv)

 57 {

 58     int i;

 59     n = xp.size();

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

 61         pt[i].x = xp[i];

 62         pt[i].y = yp[i];

 63         dt[i].x = xv[i];

 64         dt[i].y = yv[i];

 65     }

 66     return t_search(0, 1000000);

 67 }

 68

 69 };

Level3 - LongStraightRoad

Problem Statement
     
You are driving on a long, straight road, on your way to a place whose name is given in destination. After a while, you lose track of how far you've driven and realize that you may even have driven past your destination without noticing. "Don't worry!" says your friend, who is in the car with you, "I have an excellent memory and can remember not only what was written on every road sign that we have passed, but also what order they were in. Let's continue until we see the next road sign and maybe we'll be able to work out how far we still have to go." You agree to his plan, but don't quite trust his memory as much as he clearly does. You decide that you'll believe what he says as long as it is entirely consistent, otherwise you'll try to find somewhere that you can buy a map.
The information written on each sign is a semi-colon separated list, where each element of the list is the name of a place and the distance to that place from the sign separated by a space. For example, if sign i contained "A 10;B 15" (quotes for clarity) and the sign were located a distance of S[i] units down the road, then the place called "A" would be located P["A"] = S[i] + 10 units down the road and the place called "B" would be located P["B"] = S[i] + 15 units down the road. The distances will never be negative, so only places that are at least as far along the road as the sign can be listed. Note that the values in S[] and P[] need not be integers and that places will have distinct names. You are given the information written on sign i as your friend remembers it in signs[i]. Your friend claims to remember the order of the signs too, so if you wrote down the values of S[i] for each sign, they would be in strictly increasing order (no two signs were colocated).
You are currently at the same position as the sign given in the last element of signs. If the information given in signs is consistent, you can determine the remaining distance to your destination and this distance is non-negative, then return this distance. Otherwise, if there is no way that the data given in signs could represent a set of signs and places as described above, or you cannot determine the distance to your destination from the information in the signs, or you have already driven past your destination, return -1 instead.
Definition
   
Class:
LongStraightRoad
Method:
distanceToDestination
Parameters:
vector <string>, string
Returns:
int
Method signature:
int distanceToDestination(vector <string> signs, string destination)
(be sure your method is public)
   
 
Notes
-
While no two signs were at the same position on the road, places may be legitimately colocated with other places and with the signs.
Constraints
-
A place is a string containing betweeen 1 and 50 uppercase letters ('A' - 'Z'), inclusive.
-
A distance is an integer between 0 and 10000, inclusive, formatted without leading zeros.
-
signs will contain between 1 and 50 elements, inclusive.
-
Each element of signs will contain between 1 and 50 characters, inclusive.
-
Each element of signs will be a semicolon-separated list, each item of which will be a place and a distance, separated by a space.
-
No element of signs will contain the same place more than once.
-
signs will contain no more than 100 distinct places.
-
destination will be a place.
Examples
0)
 
   
{"COLCHESTER 5;GLASTONBURY 25;MARLBOROUGH 13"
,"MARLBOROUGH 2"}
"GLASTONBURY"
Returns: 14
The first sign tells you that GLASTONBURY is 12 units further than MARLBOROUGH. Since you're now 2 units from MARLBOROUGH, you must be 14 units from GLASTONBURY.
1)
 
   
{"COLCHESTER 5;GLASTONBURY 25;MARLBOROUGH 13"
,"GLASTONBURY 13;MARLBOROUGH 2"}
"GLASTONBURY"
Returns: -1
The distance between GLASTONBURY and MARLBOROUGH has changed between the first and second signs, so they're inconsistent. Even though you are standing next to a sign that tells us how far you are from your destination, return -1.
2)
 
   
{"A 25;B 15"
,"A 2"}
"B"
Returns: -1
You've driven past your destination by 8 units.
3)
 
   
{"YVO 60;J 62"
,"K 45"
,"K 40;MV 17"
,"K 37;YVO 44;HY 48;CC 69;D 77;YXF 80"
,"YVO 30;B 37;RB 59"}
"MV"
Returns: 0
You're standing right at your destination.
4)
 
   
{"A 200;B 150"
,"C 45;D 100;E 150"
,"C 25;E 130"
,"F 80;G 65"
,"G 35;H 160"
,"A 160"
,"H 130"}
"F"
Returns: -1
There is no way the signs could be in this order.
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.

to be updated..