Bear and Colors (Codeforces 643A)
Tags: Implement, implementation

Bear Limak has n colored balls, arranged in one long row. Balls are numbered 1 through n, from left to right. There are n possible colors, also numbered 1 through n. The i-th ball has color ti.For a fixed interval (set of consecutive elements) of balls we can define a dominant color. It's a color occurring the biggest number of times in the interval. In case of a tie between some colors, the one with the smallest number (index) is chosen as dominant.There are  non-empty intervals in total. For each color, your task is to count the number of intervals in which this color is dominant.

Input: The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — the number of balls.The second line contains n integers t1, t2, ..., tn (1 ≤ ti ≤ n) where ti is the color of the i-th ball.

Output: Print n integers. The i-th of them should be equal to the number of intervals where i is a dominant color.

Note: In the first sample, color 2 is dominant in three intervals:  An interval [2, 2] contains one ball. This ball's color is 2 so it's clearly a dominant color.  An interval [4, 4] contains one ball, with color 2 again.  An interval [2, 4] contains two balls of color 2 and one ball of color 1. There are 7 more intervals and color 1 is dominant in all of them.

Sample Inputs:
4
1 2 1 2

3
1 1 1

Sample Outputs:
7 3 0 0

6 0 0

Solution (Python):
n = int(input())
arr = [int(q) - 1 for q in input().split()]
ans = [0] * n
for i in range(n):
    cnt = [0] * n
    best = 0
    for j in arr[i:]:
        cnt[j] += 1
        if cnt[j] > cnt[best] or (j < best and cnt[j] == cnt[best]):
            best = j
        ans[best] += 1
print(*ans)

Solution (Python):
n = int(input())
t = [int(q) - 1 for q in input().split()]
k = [0] * n
for i in range(n):
    s = [0] * n
    b = 0
    for a in t[i:]:
        s[a] += 1
        if s[a] > s[b] or (a < b and s[a] == s[b]):
            b = a
        k[b] += 1
print(*k)

Solution (Python):
from sys import stdin
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
no_of_ocuur = [0] * n
no_of_times = [0] * n
for start in range(n):
    index_of_last_maxx = a[start] - 1
    for end in range(start, n):
        no_of_ocuur[a[end] - 1] += 1
        if no_of_ocuur[index_of_last_maxx] < no_of_ocuur[a[end] - 1]:
            index_of_last_maxx = a[end] - 1
        if no_of_ocuur[index_of_last_maxx] == no_of_ocuur[a[end] - 1]:
            index_of_last_maxx = min(index_of_last_maxx, a[end] - 1)
        no_of_times[index_of_last_maxx] += 1
    no_of_ocuur = [0] * n
print(*no_of_times)