please give me basic approch to solve that ques
CodeChef Streak Explained
Theory
The problem asks, given 2 sequences (A and B) each with n integers (where n is the number of days Om’s and Addy’s streaks were observed), which sequence has the longest sub-sequence of nonzero integers (if both are the same, then its a draw). The sequences contain integers in the range 0 \le A_i, B_i \le 10^9 where A_i and B_i denote the number of problems solved by Om and Addy on day (i + 1) (zero index) respectively. Since a day with 0 problems solved is not considered in the streak, we want the length of the longest sub-sequence of nonzero integers in each sequence. Let’s call this \text{maxln}. Procedure:
- Calculate the \text{maxln} of A and B. Let’s denote these as \text{maxln}_A and \text{maxln}_B
- Check which is greater \text{maxln}_A or \text{maxln}_B
- Output the name of the person with the greater \text{maxln} or “Draw” if both have the same \text{maxln}
Calculating \text{maxln} of A and B
The main part of this problem is to calculate such a sub-sequence. This can trivially be accomplished by iterating from i = 0...N and checking the value of the i-th element. Let’s denote \text{curr}_a and \text{curr}_b as the length of the current nonzero sub-sequence. The reason this denoted as “current” is because we don’t know if we’ll find larger sub-sequence later on or if the maximum already occurred. As we iterate through both sequences, if we find that A_i = 0, then we set \text{maxln}_a = max(\text{maxln}_a, \text{curr}_a). The same happens for B_i. This is because, if we find that A_i or B_i is 0, then the current sub-sequence cannot be extended. However, this current sub-sequence could have started as a result of another prior 0 which may had have another longer sub-sequence than \text{curr}_a or \text{curr}_b, before it. Hence, we have 2 variables, one that keeps track of the current sub-sequence length and one that keeps up with the overall maximum sub-sequence length. Before assigning a new value to the length of the overall maximum, we check if the current length is greater than the one already stored. Then we set the “current” variables to 0 since a new sub-sequence starts. Note that this sub-sequence checking happens independently, hence the two separate current and maximum variables. If A_i or B_i is nonzero, then we can increment the value of \text{curr}_a or \text{curr}_b by one. At the end we again compute \text{maxln}_a and \text{maxln}_b with the final current sub-sequences as the last stretch may have been the maximum.