## Sunday, August 4, 2013

### [TopCoder] SRM 586 DIV 2, 500p, 1000p, Solution

Problem Statement

F is a function that is defined on all real numbers from the closed interval [1,N]. You are given a vector <int> Y with N elements. For each i (1 <= i <= N) we have F(i) = Y[i-1]. Additionally, you know that F is piecewise linear: for each i, on the interval [i,i+1] F is a linear function. The function F is uniquely determined by this information. For example, if F(4)=1 and F(5)=6 then we must have F(4.7)=4.5.

As another example, this is the plot of the function F for Y = {1, 4, -1, 2}.

You are also given a vector <int> query. For each i, compute the number of solutions to the equation F(x) = query[i]. Note that sometimes this number of solutions can be infinite.

Return a vector <int> of the same length as query. For each i, element i of the return value should be -1 if the equation F(x) = query[i] has an infinite number of solutions. Otherwise, element i of the return value should be the actual number of solutions this equation has.
Definition

 Class: PiecewiseLinearFunctionDiv2 Method: countSolutions Parameters: vector , vector Returns: vector Method signature: vector countSolutions(vector Y, vector query) (be sure your method is public)

Constraints
-
Y will contain between 2 and 50 elements, inclusive.
-
Each element of Y will be between -1,000,000,000 and 1,000,000,000, inclusive.
-
query will contain between 1 and 50 elements, inclusive.
-
Each element of query will be between -1,000,000,000 and 1,000,000,000, inclusive.
Examples
0)

 {1, 4, -1, 2} {-2, -1, 0, 1}
Returns: {0, 1, 2, 3 }
 This is the example from the problem statement. The detailed information about the queries is: There is no such x that F(x) = -2 is satisfied. F(x) = -1 is only true for x = 3. F(x) = 0 has two roots: 2.8 and 10/3. F(x) = 1 has three roots: 1, 2.6 and 11/3.
1)

 {0, 0} {-1, 0, 1}
Returns: {0, -1, 0 }
 This function's plot is a horizontal segment between points (1, 0) and (2, 0). F(x) = 0 is satisfied for any x between 1 and 2 and thus the number of solutions is infinite. For any other value on the right-hand side, it has no solutions.
2)

 {2, 4, 8, 0, 3, -6, 10} {0, 1, 2, 3, 4, 0, 65536}
Returns: {3, 4, 5, 4, 3, 3, 0 }
3)

 {-178080289, -771314989, -237251715, -949949900, -437883156, -835236871, -316363230, -929746634, -671700962} {-673197622, -437883156, -251072978, 221380900, -771314989, -949949900, -910604034, -671700962, -929746634, -316363230}
Returns: {8, 6, 3, 0, 7, 1, 4, 8, 3, 4 }
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.

[Thoughts]

[Code]
``````1:  #include<vector>
2:  using namespace std;
3:  class PiecewiseLinearFunctionDiv2
4:  {
5:  public:
6:       vector <int> countSolutions(vector <int> Y, vector <int> query)
7:       {
8:            vector<int> result;
9:            for(int i =0; i< query.size(); i++)
10:            {
11:                 int searchNum = query[i];
12:                 int start = 0;
13:                 int solution=0;
14:                 if(searchNum == Y[start]) solution++;
15:                 for(int j =1; j< Y.size(); j++)
16:                 {
17:                      if(max(Y[start], Y[j]) > searchNum && min( Y[start], Y[j]) < searchNum)
18:                      {
19:                           solution++;
20:                      }
21:                      if(searchNum == Y[j])
22:                      {
23:                           if(searchNum == Y[start])
24:                           {
25:                                solution =-1;
26:                                break;
27:                           }
28:                           solution++;
29:                           //j++;
30:                      }
31:                      start = j;
32:                 }
33:                 result.push_back(solution);
34:            }
35:            return result;
36:       }
37:  };
``````

### Problem Statement  1000P

In this problem, all strings consist of uppercase English letters only. That is, there are 26 distinct letters.

The weight of a string S can be computed as follows: for each letter that occurs at least once in S, its leftmost and rightmost occurrences L and R are found and the weight is increased by R-L.

For example, if S="ABCACAZ", the weight of S is (5-0) + (1-1) + (4-2) + (6-6) = 7. (The leftmost occurrence of 'A' is at the index L=0, the rightmost one is at R=5, so 'A' contributes 5-0 = 5 to the weight of S. The only 'B' contributes 0, the pair of 'C's adds 2, and the only 'Z' adds 0.)

You are given a int L. Consider all strings of length L. Compute the weight of each of these strings. The strings with the minimum weight among all of them are called light. Your task is to count the number of light strings of length L. Since this count may be very large, return it modulo 1,000,000,009.

### Definition

 Class: StringWeightDiv2 Method: countMinimums Parameters: int Returns: int Method signature: int countMinimums(int L) (be sure your method is public)

### Constraints

- L will be between 1 and 1000, inclusive.

### Examples

0)

 `1`
`Returns: 26`
 Any string of length 1 has weight equal to 0.
1)

 `2`
`Returns: 650`
 We can divide strings of length 2 into two classes: the strings with distinct first and second letter, and the strings with two equal letters. The strings composed of two equal letters have weight 1. All the other strings have weight 0. Thus, the number of strings of minimum weight is 26*26-26=650.
2)

 `50`
`Returns: 488801539`

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.

[Thoughts]

ABC
ACB
BAC
BCA
CAB
CBA

AABC 权重1
ABBC 权重1
ABCC 权重1

C(L-1, 25) * P(26, 26) = (L-1)!/(  (L-26)! *  (25!) )  * 26! = P(L-1, 25) *26

[Code]
``````1:  int mod = 1000000009;
2:  class StringWeightDiv2
3:  {
4:  public:
5:       long Permutation(int n, int m)
6:       {
7:            long result=1;
8:            for(int i =0; i< m; i++)
9:            {
10:                 result*=n;
11:                 result%=mod;
12:                 n--;
13:            }
14:            return result;
15:       }
16:       int countMinimums(int L)
17:       {
18:            if(L<=26) return Permutation(26, L);
19:            else
20:                 return Permutation(L-1, 25)*26%mod;
21:       }
22:  };
``````