Round #283 (Div. 2) D. Tennis Game

http://codeforces.com/contest/496/problem/D Crucial insight: Given t, there are at most \[\frac{n}{t}\] total sets. (We want to minimize the size of each set and the size of each size >=t) Finding the winner of each set and the starting position of the next set can be done in O(1) by using the following information: Let p_index[k] be the index of k-th serve won by Petya in a[], p_index[k]=n if k> total number of servers won by Petya. p_near[i] be the index of the next serve won by Petya starting from the position of i+1, p_near[i]=n if there does not exist such serve. p_count[i] be the total number of serves won by Petya in a[0..i]. Let g_index[],g_near[],g_count be the similar arrays of Gena. It’s easy to see that all these information can be calculated in O(n) Suppose the starting point of the current set is at position i. Let p_next be the smallest index such that Petya is able to win this set, g_next be the smallest index such that Gena is able to win this set. Case 1: a[i]=1 p_next=p_index[p_count[i]+t-1] g_next=g_index[g_count[g_near[i]]+t-1] Case 2: a[i]=2 g_next=g_index[g_count[i]+t-1] p_next=p_index[p_count[p_near[i]]+t-1] Petya won this set if p_next<g_next, Gena won this set if g_next<p_next, t is invalid if p_next=g_next or p_next>=n or g_next>=n Therefore we can count the number of sets won by Petya and Gena respectively in O(\[\frac{n}{t}\]) for each t. Note that if the number sets won by Petya=the number sets won by Gena, t is invalid. Also note that the player who won the last serve should won the entire match, otherwise t is invalid. Time Complexity \[\sum\limits_{t=1}^n \frac{n}{t}=O(n\log n)\] Solution https://github.com/hujiewang/Programming-Contests/blob/master/codeforces/%23283/d.cpp