$29
Homework 4 Solution
Motivation
A seqence of intergers are given: i_1, i_2, ..., i_n. Define the interval of interest(IOI) with respect to x, parameterized by[l, r] subjected to: gcd(i_l, i_l+1, ..., i_r)=x, where 1<=l<=r<=n.
Gcd here means the greatest common divisor.
Goal
Count all possible intervals with respect to x=x_1, x_2, ..., x_q for the given sequence i_1, i_2, .., i_n.
Input
1. The first line: an integer n, (1 <= n <= 10^5), indicating the length of the given sequence.
2. Next line: n integers separated by space: i_1, i_2, ..., i_n (1<=i_{}<=10^9).
3. The third line: an integer q, (1 <= q <= 3*10^5), indicating the number of xs
4. The forth line: q integers separted by space: x_1, x_2, ..., x_q, (1<=x_{}<=10^9).
Output
For each x, output the number of possible IOIs with respect to x_1, x_2, ...
Sample Input 1
Sample Output 1
5
4
3
15 12 24 64 12
2
4 12
Hint
Observation1: gcd(a, b, c) = gcd(gcd(a, b), c)
Observation2: for the sequence i_1, ..., i_n, define the sequence k_1=i_1, k_j=gcd(k_{j-1},i_{j}) for 2<=j<=n. The number of distinct values in k sequence is no more than 1+log_2^{i_1}.
Hint1: Divide & conquer may be useful:
1. count IOIs at left half(by recursion)
2. count IOIs at right half(by recursion)
3. merge and conut intervals that start from the left half and end at right half(how to count efficiently?, hint: observation 2)
Hint2: try to set a AVL tree / hash, count gcd for all x in one time.
Hint3: the solution of nlogn is possible
Language: C++ Theme: Solarized Light
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Statistic Details
31
Motivation
A student from the School of Life Science and Technology come to ask for help! They sequenced two mice's genes and want to figure out the similarity of these two sequences.
Problem
You have 2 sequences of the gene. Each of them contains 4 different types of nucleotide: A, C, G, T.The similarity of different nucleotides is shown below:
(symbol '-' represent vacancy)
For two known sequences, you may have to figure out a matchup, to maximize their similarity. You may add vacancy into the sequence, but you may not modify the order of the sequence. For example, ACGT and AGG. If you match them as (A, A), (C, G), (G, G), (T, -), the similarity is 5-3+5-1=6. However, if you match them as (A, A), (C, -), (G, G), (T, G), then the similarity is 5-4+5-2=4. For these two sequences, 6 is the best similarity.
Goal
Figure out a matchup to maximize the similarity of the two sequences.
Input
Two lines.
Each line contains an integer, representing the length of the DNA, and a string, representing the gene's sequence.
The length <= 300.
Output
A number indicates the maximize similarity.
Sample Input 1
Sample Output 1
4
ACGT
6
3
AGG
Sample Input 2
Sample Output 2
7
ACAGGTT
12
10 AGGTCCAATT
Hint
Dynamic programming
Motivation
N dragons are attacking the village. M knights come to help you with cost of money.
Problem
Each dragon has hp.
Each knight can be hired with some cost of money.
The cost of knight equals the largest hp of dragon he can defeat.
Minimize the cost and defeat all the dragons.
Input
First line: two integers n, m
Next n lines: n integers indicate the hp of dragons
Next m lines: m integers indicate the cost of knights
n <= m <=50000
Output
Minimal cost or output "you died!" if no solution.
total cost <= 2147483647
Sample Input 1
Sample Output 1
3 5
950
100
300
200
15
150
300
1000
500
Hint
Be greedy
Language: C++ Theme: Solarized Light
1 ▾
2
3
4
5
5. ▾
7 ▾
8
9 ▾
4. ▾
5.
6. ▾
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17. ▾
18.
19.
20.
21.
22.
23. ▾
24. ▾
25.
26.
27.
28.
29.
30.
31.
32.
33.
34. ▾
35. ▾
36.
37. ▾
38.
39.
40.
41.
42.
43.
50 ▾
You have solved the problem Submit
