CF #88

Solved A, WA on B, TLE on C.

A. A simulation problem, since t_i <= 10^8, you can run time from 0 to 10^8, then solve each person when their t_i matches current time. Of course you need to sort them by their t_i so that you can get them in O(1) time. B. Recognizing constraints. a and b can both be 10^9 so enumerating even one of them is a bad idea. But mod is only 10^7. So you can try all possible numbers for the first person, i=0 to min(a, mod-1), since if some other choice, say k makes first win, then k%mod would make it win as well. The first wins if i*10^9 + j !=0 % mod for all j=0 to b. In other words -i*10^9 % mod >= b+1
Last catch is integer overflow when you do the multiplication.

C. Tournament. First thing is to realize that brute force will not work. Checking all path of length 2 would be n^3 and n=5000, so you need something better. For tournament, wiki tells you that if a tournament has a cycle, then it has a cycle of length 3. And draw a picture you will see a ways to find the length-3 cycle. Now the rest is easy. Do a DFS or BFS, find any cycle, then find a length-3 cycle out of that cycle.
For DFS you need to remember parent[node] for each node to be able to reconstruct the cycle.

Last but not least, the input can be huge, as large as 2.5MB. So cin will kill you. Use scanf instead.

D. TODO

E. TODO

Summary: When div1 and div2 are together in the same round, the problem is usually easier.
rank 470, rating 1669 (-6)