TCO09 Qual 3 (완료)

오늘 아침 11시에 있었던 TCO09 퀄 마지막 라운드..
1, 2라운드에서 삽질하다가 결국 3라운드까지 가게됐다..
덕분에 금쪽같은 휴가 쓰고.. 참가하게되었다.. ㅠ_ㅠ
아마도.. 지금까지 참가했던 매치중에 가장 긴장되는 매치였던것 같다..

이미 올라갈 사람은 다 올라갔는지.. 이번에는 약간 한산했다..
무려 1600명 이상 참가했던 Q2에 비해.. Q3은 대략 1200여명 참여했다..

덕분에 모처럼 2문제 풀면서 만족스런 결과를 얻었다..
Q3까지 가는 졸전끝에 간신히 R1 진출~~ (아직 발표는 안났지만)

전체 79등..~ rating도 101점이나 올리면서 4번 연속 하락한걸 한방에 만회했다..~

Level1 - BidirectionalQueue

Problem Statement
     
You are given a bidirectional cyclical queue which contains N elements. You need to extract several elements from this queue. You can do 3 kinds of operations with this queue:
Extract first element. After applying this operation, queue a1, ..., aK becomes a2, ..., aK.
Shift queue elements left. After applying this operation, queue a1, ..., aK becomes a2, ..., aK, a1.
Shift queue elements right. After applying this operation, queue a1, ..., aK becomes aK, a1, ..., aK-1.
You are given the initial number of elements in the queue N and a vector <int> indices which contains the initial (1-based) positions of wanted elements in the queue. Return the minimal number of left and right shifts you'll have to perform to extract the wanted elements in the given order.
Definition
   
Class:
BidirectionalQueue
Method:
extractElements
Parameters:
int, vector <int>
Returns:
int
Method signature:
int extractElements(int N, vector <int> indices)
(be sure your method is public)
   
 
Constraints
-
N will be between 1 and 50, inclusive.
-
indices will contain between 1 and N elements, inclusive.
-
Each element of indices will be between 1 and N, inclusive.
-
All elements of indices will be distinct.
Examples
0)
 
   
10
{1, 2, 3}
Returns: 0
The elements are extracted in the same order as they appear in the queue, so no shifts are required.
1)
 
   
10
{2, 9, 5}
Returns: 8
To extract the first wanted element, 1 left shift is required. After this the next wanted element will be 7th in a queue with 9 elements, so to extract it 3 right shifts are required. Finally, the last wanted element will be 5th in a queue with 8 elements, so either 4 left shifts or 4 right shifts are required.
2)
 
   
32
{27, 16, 30, 11, 6, 23}
Returns: 59
 
3)
 
   
10
{1, 6, 3, 2, 7, 9, 8, 4, 10, 5}
Returns: 14
 
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.

circular 형태로 된 queue가 있다.. 여기에 shift와 extract라는 operation이 있는데 queue를 왼쪽으로 shift 하면 맨 왼쪽에 수가 오른쪽 끝에 가고 오른쪽으로 shift하면 오른쪽 끝에 수가 왼쪽 맨 앞에 붙는다.. extract는 왼쪽 맨 앞에 수를 하나 pop..~ 1부터 N까지 차례로 들어있는 queue에서 원하는 원소를 주어진 순서대로 뽑으려고 할때 최소 shift수 구하기..

greedy로 풀었다.. 왼쪽으로 shift하던 오른쪽으로 shift하던 그 다음 상태가 항상 같아지므로 그냥 적은 비용이 드는 방향으로 shift하면 된다..~ 이 짓을 주어진 원소를 다 뽑을때까지 반복

처음에 원하는 원소를 아무 순서로나 뽑을수 있는지 알고.. 한참 고민했다.. ㅠ_ㅠ 덕분에 시간 대박 낭비..~

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class BidirectionalQueue {
  9 public:
 10
 11 int extractElements(int N, vector <int> indices)
 12 {
 13     int num[100], temp[100];
 14     int size;
 15     int i, j, k;
 16     int cnt1, cnt2;
 17     int sum;
 18     size = indices.size();
 19     for (i = 1; i <= N; i++) {
 20         num[i] = i;
 21     }
 22     sum = 0;
 23     for (i = 0; i < size; i++) {
 24         if (N== 1)
 25             break;
 26         for (j = 1; j <= N; j++) {
 27             if (num[j] == indices[i])
 28                 break;
 29         }
 30         cnt1 = j-1;
 31         for (j = N, k = 0; j >= 1; j--, k++) {
 32             if (num[j] == indices[i])
 33                 break;
 34         }
 35         cnt2 = k+1;
 36 printf("cnt1 = %d, cnt2 = %d\n", cnt1, cnt2);
 37         if (cnt1 < cnt2)
 38             sum += cnt1;
 39         else
 40             sum += cnt2;
 41         for (j = 1, k = cnt1+1; j <= N; k++) {
 42             if (k == N+1)
 43                 k = 1;
 44             if (num[k] == indices[i])
 45                 continue;
 46             temp[j++] = num[k];
 47         }
 48         N--;
 49         for (j = 1; j <= N; j++) {
 50             num[j] = temp[j];
 51         }
 52     }
 53 printf("sum = %d\n", sum);
 54     return sum;
 55 }
 56
 57 };

Level2 - PrettyPrintASpiral

Problem Statement
     
Consider an infinite square grid. Each square in the grid can be represented by a pair of integer coordinates that specify its row and column.
We will fill the entire grid with a spiral of positive integers. We will start by writing the number 1 into the square in row 0, column 0. Then we will write the number 2 into the square in row 0, column 1. From there, the spiral will continue in a counter-clockwise direction. The next few numbers are placed as shown in the scheme below:

Your task will be to return a vector <string> containing a pretty-printed version of a rectangular part of the filled grid.
More precisely, you will be given four ints row1, col1, row2, and col2. Here, row1,col1 will be the coordinates of the top left cell, and row2,col2 the coordinates of the bottom right cell to be displayed.
The returned vector <string> must be formatted according to the following rules:
The vector <string> contains one element for each row of the displayed rectangle. The elements are ordered by the row coordinate they describe.
Each element is a concatenation of space-separated tokens, each describing a cell in the corresponding row. The tokens are ordered by the column coordinates of cells they describe.
All tokens in the entire output have the same length.
The length of a token is minimal, i.e., equal to the number of digits in the largest number displayed.
Tokens that contain numbers with fewer digits are padded from the left using spaces.
Definition
     
Class:
PrettyPrintASpiral
Method:
getWindow
Parameters:
int, int, int, int
Returns:
vector <string>
Method signature:
vector <string> getWindow(int row1, int col1, int row2, int col2)
(be sure your method is public)
   
 
Notes
-
The constraints guarantee that the returned vector <string> will have at most 50 elements, and the length of each element will be at most 50.
Constraints
-
row1 will be between -5,000 and 5,000, inclusive.
-
col1 will be between -5,000 and 5,000, inclusive.
-
row2 will be between -5,000 and 5,000, inclusive.
-
col2 will be between -5,000 and 5,000, inclusive.
-
row2-row1 will be between 0 and 49, inclusive.
-
col2-col1 will be between 0 and 4, inclusive.
Examples
0)
 
   
0
0
0
0
Returns: {"1" }
The spiral starts at coordinates (0,0).
1)
 
   
-1
-2
-1
1
Returns: {"18  5  4  3" }
Note that the single-digit values are now padded with spaces.
2)
 
   
-2
2
0
3
Returns: {"13 30", "12 29", "11 28" }
 
3)
 
   
-3
-3
2
0
Returns:
{"37 36 35 34",
 "38 17 16 15",
 "39 18  5  4",
 "40 19  6  1",
 "41 20  7  8",
 "42 21 22 23" }
 
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차원 좌표계에서 숫자가 반시계방향으로 증가한다.. (row1, col1), (row2, col2) 사이에 수를 차례로 출력하기..

이 문제의 핵심은 (x, y) 좌표가 주어졌을 때, 거기에 해당하는 값을 찾는 방법인데..
나같은 경우 903 - Spiral of Numbers 문제를 미리 풀었기때문에.. 그 코드를 그냥 복.붙 했다.. -_-

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define max(x, y) ((x) > (y) ? (x) : (y))
  8
  9 char temp[1000000];
 10
 11 int get_n(int x, int y)
 12 {
 13     int k, l, m, n;
 14     m = max(abs(x), abs(y));
 15     k = (2*m+1)*(2*m+1);
 16
 17     if (x <= m && y == m) {
 18         l = m - x;
 19         n = k-l;
 20     }
 21     else if (x == -m && y <= m) {
 22         l = m - y;
 23         n = k - (2*m) - l;
 24     }
 25     else if (x <= m && y == -m) {
 26         l = abs(-m - x);
 27         n = k - (4 * m) - l;
 28     }
 29     else {
 30         l = abs(-m - y);
 31         n = k - (6*m) - l;
 32     }
 33     return n;
 34 }
 35
 36
 37 class PrettyPrintASpiral {
 38 public:
 39
 40 vector <string> getWindow(int row1, int col1, int row2, int col2)
 41 {
 42     int i, j, k, l, x, y;
 43     int map[100][100];
 44     int max_digit;
 45     char buf[100];
 46     int len;
 47     vector<string> res;
 48     string str;
 49     max_digit = 0;
 50     for (i = row1, x = 0; i <= row2; i++, x++) {
 51         for (j = col1, y = 0; j <= col2; j++, y++) {
 52             k = get_n(j, i);
 53             sprintf(buf, "%d", k);
 54 printf("(%d, %d) = %d\n", i, j, k);
 55             max_digit = max(max_digit, strlen(buf));
 56             map[x][y] = k;
 57         }
 58     }
 59     for (i = 0; i < x; i++) {
 60         k = 0;
 61         temp[k] = 0;
 62         for (j = 0; j < y; j++) {
 63             sprintf(buf, "%d", map[i][j]);
 64             len = strlen(buf);
 65             if (j != 0) {
 66                 temp[k] = ' ';
 67                 temp[k+1] = 0;
 68                 k++;
 69             }
 70             for (l = 0; l < max_digit-len; l++) {
 71                 temp[k++] = ' ';
 72             }
 73             for (l = 0; l < len; l++) {
 74                 temp[k++] = buf[l];
 75             }
 76             temp[k] = 0;
 77         }
 78         str = temp;
 79         res.push_back(str);
 80     }
 81     return res;
 82 }
 83
 84 };

Level3 - MismatchedStrings

Problem Statement
     
Well-parenthesized strings are defined using the following rules:
The empty string is well-parenthesized.
If S is a well-parenthesized string, then (S) is a well-parenthesized string.
If S and T are well-parenthesized strings, then ST is a well-parenthesized string.
Every well-parenthesized string can be created using the previous rules only.
In this problem we will deal with the complement of this set of strings: The strings that consist only of the characters '(' and ')', but are not well-parenthesized. We will call these strings mismatched.
You are given an int N and a long long K. All mismatched strings of length N can be ordered lexicographically, and numbered sequentially, starting with zero. Return the string that will get the number K in this order. If there is no such string, return the empty string instead.
Definition
   
Class:
MismatchedStrings
Method:
getString
Parameters:
int, long long
Returns:
string
Method signature:
string getString(int N, long long K)
(be sure your method is public)
   
 
Notes
-
Given two different strings S and T of equal length, S is lexicographically smaller than T if it has a smaller character at the first position where they differ.
-
The ASCII value of '(' is less than the ASCII value of ')'.
Constraints
-
N will be between 1 and 50, inclusive.
-
K will be between 0 and 2^N - 1, inclusive.
Examples
0)
 
   
4
0
Returns: "(((("
For any length, the lexicographically smallest mismatched string consists of '(' characters only.
1)
 
   
4
4
Returns: "())("
There are 14 mismatched strings of length 4. The first five are "((((", "((()", "(()(", "()((", and "())(". Note that we use a 0-based index, hence K=4 corresponds to the fifth mismatched string.
2)
 
   
6
63
Returns: ""
There are less than 64 mismatched strings of length 6.
3)
 
   
7
13
Returns: "((())()"
 
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의 string 중에서 lexicographically K-th mismatched string 구하기

귀찮은 관계로.. -_- 알고스팟 에디토리얼을 그냥 펌..;;

-- 풀이 --

 

기본 아이디어는 우선 empty string에서 시작해서..

'(' 를 붙여보고 앞으로 나올 수 있는 mismatched가 몇개인지 세봅니다

'('를 붙여서 K-th smallest string을 만들 수 없다고 판단되면 대신 ')' 를 붙입니다..

')'를 붙일 경우 '('를 붙였을 때 만들 수 있는 string의 개수 만큼을 건너뛰게 되므로 K 값에서 빼주면서 진행합니다..

 

이 문제를 풀기 위해 먼저 다음과 같은 table을 구해두면 편합니다

 

match[i][j] = 길이 i 이면서 j개의 '(' 가 아직 닫히지 않은 string의 개수

                   (또는 j개의 '('를 닫을 수 있는 string의 개수??)

 

 

long long match[60][60];

int n;

 

long long get_cnt(string str)

{

    int i, j, len;

    long long cnt;

    len = str.size();

    cnt = 1LL << (n-len);

    j = 0;

    for (i = 0; i < len; i++) {

        if (str[i] == '(')

            j++;

        else

            j--;

        if (j < 0)

            return cnt;

    }

    return cnt - match[n-len][j];

}

 

class MismatchedStrings {

public:

 

string getString(int N, long long K)

{

    int i, j;

    long long cnt;

    string res;

    n = N;

    memset(match, 0, sizeof(match));

    match[0][0] = 1;

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

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

            match[i][j] = match[i-1][j+1];

            if (j-1 >= 0)

                match[i][j] += match[i-1][j-1];

        }

    }

    res = "";

    if (K >= (1LL << N) - match[N][0]) {

        return res;

    }

    for (i = 0; i < N; i++) {

        res += '(';

        cnt = get_cnt(res);

        if (cnt <= K && K) {

            K -= cnt;

            res[res.size()-1] = ')';

        }

    }

    return res;

}

 

};

 

이상 tomek의 솔루션 이었습니다..

틀린점이 있으면 알려주세요.. ㅎㅎ;;