TCO09 Round 1

어제 새벽 2시에 있었던 TCO09 온라인 1라운드..
역시 예상대로 그냥 가볍게 탈락하고 말았다..~ 흑흑.. ㅠ_ㅠ
작년같은경우 -25점이라는 어처구니없는 점수로 탈락했는데..
이번에는 나름 250도 pass하고.. 작년보다는 훨씬 발전했다는 생각이 든다..

이번에 참가하면서 느낀점은..
경쟁이 작년에 비해 엄청나게 치열해졌다는것..
그 결과.. 나름 실력있는 사람들도 고전한 경우가 많았다.. ㅎㅎ

그리고 역시 직장인의 한계를 많이 느낀다..
예전처럼 대회를 위해 올인해서 공부한 경우와..
지금처럼 짬을내서 취미로 하는것은 많은 차이가 있는것 같다.. 쩝

이번 문제셋은 500보다 1000이 더 쉬워보이는데.. 그냥 나만의 착각인가..? ㅋ

500은 도저히 모르겠고 1000 open할까 말까 하다가 열어서 봤는데..

대략 DP 솔루션이 떠올라서 코딩하다가 결국 시간내에 완료하지 못했다..

다른 사람들 보면 대략 500에서 말린 사람들 많은거같은데.. ㅎㅎ

우리 방 사람들인데.. 이렇게 red랑 yellow가 많은 방에서 참가해본게 처음인듯.. ㅋㅋ
특히나 ardiankp나 krzysan은 UVa에서도 매우 유명한 id인데..
게다가 acm-icpc world finalist에 빛나는 한국인 한명도 있다..~~
아.. 잘하는사람들이 도대체 왜이리 많은거야..

Level1 - SequenceSums

Problem Statement
     
Given a number N and a length L, find the shortest list of at least L consecutive non-negative integers whose sum is N. If the length of that list is 100 or smaller, return the sequence as a vector <int> in ascending order. If there is no such sequence or its length is larger than 100, return { }.
Definition
   
Class:
SequenceSums
Method:
sequence
Parameters:
int, int
Returns:
vector <int>
Method signature:
vector <int> sequence(int N, int L)
(be sure your method is public)
   
 
Constraints
-
N will be between 1 and 1000000000, inclusive.
-
L will be between 2 and 100, inclusive.
Examples
0)
 
   
18
2
Returns: {5, 6, 7 }
18 can be expressed as 5 + 6 + 7 or 3 + 4 + 5 + 6. Both of these lists contain more than 2 elements, so you should return the shortest among them.
1)
 
   
18
4
Returns: {3, 4, 5, 6 }
Now the correct answer is 3 + 4 + 5 + 6 because 5 + 6 + 7 contains less than 4 elements.
2)
 
   
18
5
Returns: { }
Both possible presentations of 18 contain less than 5 elements, so there's no answer for this case.
3)
 
   
45
10
Returns: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
 
4)
 
   
1000000000
2
Returns: {199999998, 199999999, 200000000, 200000001, 200000002 }
 
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과 L이 주어질때, 연속된 L개 이상의 수의 합이 N이 되는 최소의 리스트 구하기..

예를들어 N = 18,  L = 2 일때..
18 = 3 + 4 + 5 + 6 도 되고.. 18 = 5 + 6 + 7 도 되는데..
L 보다 크거나 같으면서 크기가 최소인 리스트는 {5, 6, 7} 이 된다

이 문제는 다양한 풀이법이 있는듯 하다..
나같은 경우 길이를 고정시켜놓고 등차수열의 초항을 binary search해서 찾았다..
이런 방법을 parametric search 라고 하는 것 같다..

문제 풀다가 중간에 등차수열의 합 공식이 생각이 안나서.. 예전에 정리해둔 팀노트를 급 찾아보았다..
아.. 중딩 수학이 기억이 안나.. ㅠ_ㅠ;;

n항 까지의 합 = n * (2 * 초항 + (n-1) * 공차) / 2

  1 #include <iostream>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 class SequenceSums {
  9 public:
 10
 11 vector <int> sequence(int N, int L)
 12 {
 13     long long left, right, mid, k;
 14     int i, j, sol;
 15     vector<int> res;
 16     sol = -1;
 17     for (i = L; i <= 100; i++) {
 18         left = 0;
 19         right = N;
 20         while (left <= right) {
 21             mid = (left+right) / 2;
 22             k = ((long long)i*(2*mid+(i-1))) / 2;
 23             if (k == N) {
 24                 sol = mid;
 25                 break;
 26             }
 27             else if (k < N) {
 28                 left = mid+1;
 29             }
 30             else {
 31                 right = mid-1;
 32             }
 33         }
 34         if (sol == -1)
 35             continue;
 36         else
 37             break;
 38     }
 39 printf("sol = %d\n", sol);
 40     res.clear();
 41     if (sol == -1)
 42         return res;
 43     for (j = 0; j < i; j++) {
 44         res.push_back(sol+j);
 45     }
 46     return res;
 47 }
 48
 49 };

Level2 - KthProbableElement

Problem Statement
     
M integers are randomly independently chosen from the interval lowerBound...upperBound, inclusive. Return the probability that the K-th smallest element of the generated set is equal to N. K=1 refers to the smallest element, K=2 refers to the second smallest element, and so on.
Definition
   
Class:
KthProbableElement
Method:
probability
Parameters:
int, int, int, int, int
Returns:
double
Method signature:
double probability(int M, int lowerBound, int upperBound, int N, int K)
(be sure your method is public)
     
 
Notes
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
M will be between 1 and 100, inclusive.
-
lowerBound will be between 1 and 1000, inclusive.
-
upperBound will be between lowerBound and 1000, inclusive.
-
N will be between lowerBound and upperBound, inclusive.
-
K will be between 1 and M, inclusive.
Examples
0)
 
   
1
1
10
3
1
Returns: 0.1
The probability that the only chosen number will be equal to 3 is 0.1.
1)
 
   
3
1
2
2
2
Returns: 0.5
There are 8 ways to choose 3 numbers from the interval 1..2:
Numbers | 2nd smallest element
 1 1 1  |  1
 1 1 2  |  1
 1 2 1  |  1
 1 2 2  |  2
 2 1 1  |  1
 2 1 2  |  2
 2 2 1  |  2
 2 2 2  |  2
Exactly 4 of the ways have the 2nd smallest element equal to 2.
2)
 
   
3
1
3
2
2
Returns: 0.48148148148148145
There are 27 ways to choose 3 numbers from the interval 1..3, 13 of them have the 2nd smallest element equal to 2.
3)
 
   
10
1
10
1
10
Returns: 1.0000000000000003E-10
Only one of 1010 ways to choose 10 numbers from the interval 1..10 has 1 as the 10th smallest element.
4)
 
   
4
61
65
62
3
Returns: 0.15200000000000002
 
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.

lowerBound와 upperBound 사이의 수 중에 M개를 뽑을때 (중복순열), K번째 작은 수가 N과 같을 확률 구하기..


to be updated..



Level3 - Unicorn

Problem Statement
     
The unicorn is an exotic chess piece similar to the knight. The difference is that while the knight moves two cells in one direction and one in the other direction, the unicorn moves more than two cells in one direction and more than one in the other direction.
More precisely, each unicorn move looks as follows:
pick up the unicorn;
pick one of the four basic directions, and move the unicorn more than two cells in that direction;
pick one of the two basic directions that are orthogonal to the previous one, and move the unicorn more than one cell in that direction;
put down the unicorn.
We have a chessboard that has R rows times C columns. Each cell of the chessboard contains one of the first L letters of the alphabet. To keep the input small, the content of the cells is randomly generated using the method described below.
You are given the ints R, C, and L described above, an int seed used to generate the letters in the cells, and a string word. You want to trace the string word by taking a unicorn, placing it onto a cell containing the first letter of word, making a valid move that takes it onto a cell that contains the second letter, from there making another move to the third letter, and so on. Return the number of ways in which this can be done, modulo 1,000,000,007.
The content of the cells is generated using the following pseudocode:
x = seed;
d = (65535 div L)+1;
for (int r=0; r<R; r++)
  for (int c=0; c<C; c++) {
    x = (x * 25173 + 13849) modulo 65536;
    chessboard[r][c] = character with ASCII code (65+(x div d));
  }
Definition
   
Class:
Unicorn
Method:
countWays
Parameters:
int, int, int, int, string
Returns:
int
Method signature:
int countWays(int R, int C, int L, int seed, string word)
(be sure your method is public)
   
 
Notes
-
The path of the unicorn can contain the same cell multiple times.
-
In the pseudocode, "A div B" represents the integer part of A/B. For example, 14 div 5 = 2 and 20 div 4 = 5.
-
The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of allowed size within the given limits.
Constraints
-
R will be between 1 and 300, inclusive.
-
C will be between 1 and 300, inclusive.
-
L will be between 1 and 26, inclusive.
-
seed will be between 0 and 65,535, inclusive.
-
word will contain between 1 and 50 characters, inclusive.
-
Each character in word will be an uppercase letter ('A'-'Z').
Examples
0)
 
   
3
4
2
47
"AB"
Returns: 2
When generating the input we will compute d=32768, and then generate the content of the cells. The variable x will have the following values, in order: 17332, 39133, 37242, 14235, 656, 12265, 20598, 6471, 51372, 44853, 44210, and 45363. The generated chessboard looks as follows:
ABBA
AAAA
BBBB
There are only two ways a unicorn can trace the word "AB" on this chessboard. It has to start in one of the two top corners, and then jump into the opposite corner.
1)
 
   
5
5
2
47
"CD"
Returns: 0
No letter C on this board.
2)
 
   
4
4
1
42
"AA"
Returns: 20
The unicorn can start in one of the four corner cells (and then has three possible jumps), or at one of the 8 cells that share a side with a corner cell (and then only have one possible jump). This gives us 4*3 + 8*1 = 20 ways to trace the word.
3)
 
   
4
4
1
42
"AAAAA"
Returns: 172
 
4)
 
   
1
1
5
54321
"ABCDE"
Returns: 0
The board is too small. No word longer than one character can be traced as there is no way to make a valid move.
5)
 
   
8
8
26
226
"TOPCODER"
Returns: 1
The board looks as follows:
AILFPSPF
DZIOMYCE
QOODZARU
YVOTLTRX
LSRIGANL
LCIUUSNF
IWVXKTDE
OVPPNXRD
If we number the rows and columns starting from 0, with (0,0) being the upper left corner cell, the only valid path of the unicorn is (6,5)-(2,1)-(7,3)-(1,6)-(7,0)-(2,3)-(6,7)-(4,2).
6)
 
   
20
20
2
47
"AAAAA"
Returns: 373977054
Do not forget about the modulo; the actual number of paths can be huge.
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.

chess에서 unicorn이 움직이는 방법은 knight의 update버전으로 한방향으로 3칸 이상 그리고 그 직각 방향으로 2칸 이상 움직일 수 있다.. 즉, 주위의 몇칸만을 제외하고 모든 칸을 갈 수 있다는 의미..
input으로 체스판과 string이 주어질때, string 순서대로 unicorn을 이동시킬 수 있는 경우의 수 구하기..
맨 처음에는 아무칸에서 시작할 수 있다..


to be updated..