After dijkstra from source vertex, you can start a dfs from the destination vertex. Number of shortest paths from source vertex to current vertex = SUM(number of shortest paths from source vertex to children of current vertex (given the child lies in the shortest path)). in dp₁ source vertex is s, in dp₂ source vertex is t

Yes, you should start from the vertex which has 0 in degree.

Okay thanks!

Is Q3 Lehmer's totient problem? Or am I missing something?

Reminder: Registration closes in 45 minutes.

How to solve the fourth problem? I had assumed an unproven claim that the product of gcd of the numbers in the array a[] and some power of 2 should be the sum of numbers in a[]. It somehow worked for all the examples I could come up with during the contest :P

Yeah right ... it did occur to me during the contest. Unfortunately I forgot to incorporate it in the code while coding. Thank you!

Yes the precision is fine ....

Is problem D probability + DP? I am getting WA in pretest 7 and I cant wait to know my mistake. My approach was this. We can see that the architecture of tournament is a complete binary tree. So each game will correspond to a node in this tree. We can also see that expected score for each subtree is independent (that is if the tournament comprised of only those players belonging to the subtree). If we fix the winner of the current subtree, we can independently compute the maximum expected score in each subtree that branch from the path joining the winner node in level 0 to the node corresponding to the current game, and add them to the expected score we get for fixing the current player. Am I being too vague?

Can Div2 D be done somehow with ternary search. We can observe that the required dp expression will be unimodal but not monotonous.

http://codeforces.me/blog/entry/53267?#comment-373035

The problem asks us to find the largest subarray where all the numbers are pairwise co-prime. This means we need the largest subarray where each prime factor occurs only in one number. So for each prime factor of a number we can keep track of index of next number where it occurs as factor. Store the values in a new array.

( Consider the example n = 6 and A = {6, 7, 25, 13, 9, 21}. For number 6 (having prime factors 2 and 3), create store the index of the next number where the prime factors occurs. 2 occurs nowhere but 3 occurs in 9. So store for 6, max{5 (index of 9), 7 (since 2 occurs nowhere)}. That is for each number in A, the corresponding value is the minimum index (greater than current number's index) of the number whose gcd with current number is not 1. Do the same process for each number in A. Create a new array of values. The new 'next' array will look like B = {5, 6, 7, 7, 6, 7} )

After creating the new array, we use DP with dp[i] as length of the longest subarray starting from index i. Its not difficult to see that dp[i] = min {B[j]} for i < j <= n. So the answer is max {dp[1]} for 1 <= i <= n

In case you missed, refer to the following comments in order http://codeforces.me/blog/entry/52653?#comment-367266, http://codeforces.me/blog/entry/52653?#comment-367389

The basic idea is for each i find Nmx[i] — the number of subarrays that will have a[i] number as maximum. Then do final_answer += Nmx[i] * a[i]. Similarly find Nmn[i] — number of subarrays in which a[i] will be the minimum number, and do final_answer -= Nmn[i] * a[i].

Nmx can be found in O(N) time. To find Nmx[i], you have to find Rmx[i] and Lmx[i] such that a[i] is maximum among all numbers in the segment [Lmx[i], Rmx[i]]. Rmx and Lmx arrays can be obtained with a forward sweep and a reverse sweep of the original array.

Similarly find Nmn array.

In problem E, why can't we club p1 and p2, and club c1 and c2, and have dp[u][p1 + 2*p2][c1 + 2*c2], which denotes number of ways to build the graph with the first u vertices, with (p1 + 2*p2) plugs in the previous level, and (c1 + 2*c2) in the current one?