I wrote (out of the contest, unluckily) a binary search which checks every edge and his right neighbour in the path a->b: you can handle all cases except the case in which time_a = time_a' and time_b = time_b' (where time_a is the optimal time to fill from a his part of tree and time_a' is the same thing from the next edge etc), but in both cases (if you decide to go right or left in your binary search) it gets 100 points, lol. That's strange D:

My code: http://pastebin.com/tenyL8CR

Define P[n][k] as the probability to get exactly k "heads" throwing n coins. Now if you can do a O(N²) DP like this: - if n == 1, P[1][0] = 1-p and P[1][1] = p - else, P[n][k] = p * P[n-1][k-1] + (1-p) * P[n-1][k]

The remaining part of the problem can be solved using linearity of expectations.

During the contest i solved B casting every integer in the range [a, b] into a string (using std::to_string()) and then iterating the string with a range based for, and I got TLE (code here).

Then I removed the std::string conversion and did the same thing extracting every digit from the number, using the same complexity [ O(b — a) ], and got AC in 15 ms (code here).

Now on my pc the first solution, with the 1 1000000 tc, works in 130ms while the second one takes 40ms (I haven't got any kind of supercomputer or quantum computer and I compile with the same flags of Codeforces (C++11)). Now the question is: does codeforces hate std::string? is std::to_string() very very slow?

I got 3 TLEs for this :(

I solved it using topological sort on a graph where an edge i->j means that I have to remove i before j. The long thing is to create the graph but it can be done in O(N^2) comparing every pair of segments in O(1) [ here is the long thing, you have to consider some corner cases where the segments are vertical lines ]. Relation is transitive, i.e. if i < j and j < k --> i < k , that's why topological sort works (where a < b means that I have to remove a before b).

I submitted a solution more than 30 minutes ago and still nothing... Website is completely unavailable o:

lol I've just solved that problem and I think you've only over-complicated the task. Do you really need LDC[ x ]? And why do you use a segment tree when it is slower and worse to code than a BIT? After calculating the LIS terminating at every indexyou can just find super numbers in linear time.

Hint: Suppose you're at index i of the array A and you already know that number A[ j ] (where j>i) is a super number. What can you say about A[i], looking at A[i], A[j], Lis[j] and Lis[i] ? Try on paper, I found algorithm in that way :)

yeah i was talking about the problem "Almost Equal" not "Almost Equal Advanced", sorry

I've solved it using hashing (Rabin Karp, 2 different hashes to have less collisions) And binary search for every query. Using Rabin Karp during preprocess you can get every hash in O(1) And then just binary search the different char between the two substrings And check the other two parts to be equal.

I know man, I always make silly mistakes caused by pressure/stress. Last example: I took part in code jam 1C and I could have scored 55 points (and I could be advanced to round 2) but I made a very silly mistake in the big A so I got only 33 points (the small tests) :(

Can someone better explain the proof of the upper bound of O(N * sqrt(N)) of the second approach to problem F? I came up with the same solution but at the beginning I thought it was tle...

I missed the big case of C only because I forgot to transform to long long a single variable !!! So, you're not the only one :')

You don't even need suffix automata, I think you can do it in O(N) just with tree DFS and kmp :)

Sorry my fault, my code was right but I thought roads in input were correct (i.e. a is closer to the root than b) so it was going on infinite loop. lol

I solved it that way but I keep getting TLE on 7th test case. My solution--> http://codeforces.me/contest/519/submission/10136461

I think the solution with trie is better than the hashing one. I haven't perfectly analized your code but maybe the bug is that your hashing is not perfect so I suggest you to implement the trie solution, which is much easier

There's a simple O(N^2) solution (N^2 is an upper bound, actually it is faster I think):

• For every node i, do a dfs (max depth 2) using i as root

• During dfs, for every node j that you reach using 2 edges, update cnt[j] (where cnt[j] is the number of ways to reach j using 2 edges) PS: clearly you stop dfs when you use 2 edges

• At the end of the dfs, iterate from node 1 to N and for every node j update result in this way:

  1. if cnt[j] < 2, do nothing
  1. else: ris += (cnt[j] * (cnt[j]-1))/2 --> This is a "reduct" form of binomial coefficient (I want to consider all rhombs starting to i and ending at j, so I can take all combination of 2 intermediate nodes)

At the end of the whole process you'll obtain the answer :)

Nice problems but server is always busy!!! I submitted the code for A-Bits 10 minutes ago and it's still in queue

Thanks !!! Finally, after "number of graham" submissions, i got AC!!! PS: This is my first comment to comment :D