SRM498 - div2 - level two

srm498_div2_level2.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-

"""SRM498 - div2 - level two

Fox Ciel likes sequences. One day, she invented 
a new type of sequence and named it the fox sequence. 
A sequence seq containing N elements is called a fox 
sequence if and only if there exist four integers 
a, b, c and d such that 0 < a < b <= c < d < N-1 
and the following five conditions are met:

    * seq[0], seq[1], ... , seq[a] forms an arithmetic 
      progression with a positive common difference. 
      An arithmetic progression is a sequence where 
      the difference between successive elements is equal. 
      The difference between successive elements is called 
      the common difference. Note that 0 is neither 
      positive nor negative.
    * seq[a], seq[a+1], ... , seq[b] forms an arithmetic 
      progression with a negative common difference.
    * seq[b], seq[b+1], ... , seq[c] are all equal.
    * seq[c], seq[c+1], ... , seq[d] forms an arithmetic 
      progression with a positive common difference.
    * seq[d], seq[d+1], ... , seq[N-1] forms an arithmetic 
      progression with a negative common difference.

You are given a sequence seq. Return "YES" if it is a fox 
sequence, or 'NO' if it is not (all quotes for clarity).

Definition:
    Class: FoxSequence
    Method: isValid
    Parameters: int[]
    Returns: String
    Method signature: String isValid(int[] seq)
"""

class FoxSequence(object):
    """Fox Sequence

    Constraints:
        - seq will contain between 1 and 50 elements, inclusive.
        - Each element of seq will be between 1 and 2,000, inclusive.

    >>> fox = FoxSequence()
    >>> print fox.isValid([1,3,5,7,5,3,1,1,1,3,5,7,5,3,1,])
    YES
    >>> print fox.isValid([1,2,3,4,5,4,3,2,2,2,3,4,5,6,4,])
    YES
    >>> print fox.isValid([3,6,9,1,9,5,1,])
    YES
    >>> print fox.isValid([1,2,3,2,1,2,3,2,1,2,3,2,1,])
    NO
    >>> print fox.isValid([1,3,4,3,1,1,1,1,3,4,3,1,])
    NO
    >>> print fox.isValid([6,1,6,])
    NO
    """

    def __init__(self):
        pass

    def isValid(self, seq):
        a, b, c, d = 0, 0, 0, 0

        for i in range(len(seq)-1):
            if seq[i]>=seq[i+1]:
                a = i
                break

        for i in range(a+1, len(seq)-1):
            if seq[i]<=seq[i+1]:
                b = i
                break

        for i in range(b+1, len(seq)-1):
            if seq[i]!=seq[i+1]:
                c = i
                break

        for i in range(c+1, len(seq)-1):
            if seq[i]>=seq[i+1]:
                d = i
                break

        # Check a
        if(a <= 0):
            return 'NO'

        diff = (seq[a]-seq[0]) / a
        for i in range(a-1):
            if seq[i+1]-seq[i] != diff:
                return 'NO'

        # Check b
        diff = (seq[b]-seq[a]) / (b-a)
        for i in range(a+1, b-1):
            if seq[i+1]-seq[i] != diff:
                return 'NO'

        # Check c
        diff = 0;
        for i in range(b+1, c-1):
            if seq[i+1]-seq[i] != diff:
                return 'NO'

        # Check d
        diff = (seq[d]-seq[c])/(d-c)
        for i in range(c+1, d-1):
            if seq[i+1]-seq[i] != diff:
                return 'NO'

        diff = (seq[len(seq)-1]-seq[d])/((len(seq)-1)-d)
        for i in range(d, (len(seq)-1)-1):
            if seq[i+1] - seq[i] != diff:
                return 'NO'
        return 'YES'


if __name__ == '__main__':
    import doctest
    doctest.testmod()