Quora.challenge

main.py

import itertools
import sys


def non_increasing_range(items, i, j, _c):
    try:
        d = _c[(i, j)]
        return d
    except KeyError:
        pass
    first, second = items[:2]
    if second > first:
        _c[(i, j)] = False
    else:
        if len(items) > 2:
            _c[(i, j)] = non_increasing_range(items[1:], i+1, j, _c)
        else:
            _c[(i, j)] = True
    return _c[(i, j)]


def non_decreasing_range(items, i, j, _c):
    try:
        d = _c[(i, j)]
        return d
    except KeyError:
        pass
    first, second = items[:2]
    if second < first:
        _c[(i, j)] = False
    else:
        if len(items) > 2:
            _c[(i, j)] = non_decreasing_range(items[1:], i+1, j, _c)
        else:
            _c[(i, j)] = True
    return _c[(i, j)]


def slices(iterable, n):
    if len(iterable) <= n:
        yield iterable
    else:
        for j in xrange(n, len(iterable)+1):
            yield iterable[j-n: j]


def solve(items, k):
    for slc in slices(items, k):
        n_decreasing = 0
        n_increasing = 0
        non_decreasing_c = {}
        non_increasing_c = {}
        for i, j in itertools.combinations(xrange(len(slc)), 2):
            n_increasing += 1 if non_increasing_range(slc[i:j+1], i, j+1, non_increasing_c) else 0
            n_decreasing += 1 if non_decreasing_range(slc[i:j+1], i, j+1, non_decreasing_c) else 0
        yield n_decreasing - n_increasing


def main():
    n, k = map(int, sys.stdin.readline().strip().split(' '))
    items = map(int, sys.stdin.readline().strip().split(' '))
    for result in solve(items, k):
        print result

if __name__ == '__main__':
    main()