Codeforces Round #361 (Div. 2)

http://codeforces.com/contest/689

Problems :
pA : http://codeforces.com/contest/689/problem/A
pB : http://codeforces.com/contest/689/problem/B
pC : http://codeforces.com/contest/689/problem/C
pD : http://codeforces.com/contest/689/problem/D
pE : http://codeforces.com/contest/689/problem/E

My Solution :
pA : http://codeforces.com/contest/689/submission/18922621
pB : http://codeforces.com/contest/689/submission/18924209
pC : http://codeforces.com/contest/689/submission/18932251
pD : http://codeforces.com/contest/689/submission/18932696
pE : http://codeforces.com/contest/689/submission/19054541

pA :
I use the concept of vector & brute force.
First, I give all the digits a coordinate. '0' is (2,1), '1' is (1,4), ... etc.
Then, I think that if there's another way to do the finger movements, the first digits must be different. So I try all digits as the first, and then try the movements the problem gave. During the process, if the coordinate is out of range, then it fails.

Time complexity : O(1)

pB :
I use BFS(Breadth-First-Search).
If you got a new point x, you should update x-1, x+1, and a[x].

Time Complexity : O(n)

pC :
I use binary search.
It's obvious that the greater m is, the greater n is. So you can do binary search on the n, from 8 to 5*10^15(when m = 10^15, the answer is about 4.949 * 10^15).
But how can we know the m when we get an n? First, the sequences are geometric sequence, so we can infer that the maximum number is a1*r^3, which a1 is the first number of geometric sequence and r is the ratio(2nd number / 1st number). So, we try every possible r that a1*r^3 < n , then we can quickly count the number of a1 by n/r^3.

Time Complexity : O(10^5 * log10^15)

pD :
Binary Search again. lol
First, we build a segment tree on array a and b. Let's call them seg_a and seg_b. For every i, 1<=i<=n, if a[i]>b[i], then it's impossible to find any possible answers. If a[i] == b[i], then we can do binary search on a & b that max(a) or min(b) changes first. We can query the value using seg_a & seg_b. If a[i]<b[i], then we can also do binary search! Think it clearly, min(b)-max(a) is increasing! So when min(b)-max(a) = 0. Then we got the answer. We can query the val using seg_a & seg_b, too.

Time Complexity : O(n lgn lgn)

pE :
First, we build dp saving C(n,k). Then we can quickly calculate that if there are i elements in [l,r], the answer should add (r-l+1) * dp[i]. So, we can sort all the input by the first value and build a minimum heap. When the input's first number is smaller than the top of the heap, we can update the value, ans so on. You can see my code. ^_^

Another round that solve all the questions. Happy~~