Hello,

I'd like to share a problem with you that me and my friends cannot solve. Statement is really short and simple:

Given a sequence of *n* integers find number of balanced intervals in it. Interval is balanced if all occurring elements have the same number of occurrences, e.g. 1, 2, 2, 1 or 4, 5, 2, 2, 4, 2, 5, 5, 4 or 100, 100

Thanks!

Bound on

n?The larger the better.

Define unsolvable? Unless I understand it wrong, it is easily solvable in

O(n^{2}).Then I suppose he meant with a better complexity, like O(N lg N) or O(N lg N sqrt N)

Completly misunderstood the problem, please ignore

If set is balanced then

odd[l- 1] =odd[r] but there can be intervals withodd[l- 1] =odd[r] that are not balanced (e.g. 1 2 2 2 is not balanced) so your solution gives only upper bound on number of balanced sets.Are you sure you understand the statement correctly?

"1 1 1" is balanced, but your sets aren't equal. "1 1 2 2 2 2" isn't balanced, but your sets are equal.

maybe there is O(n*sqrt(n)) solution to this problem:

first enum the number of times of number occurs in the result

segments:

times from 1 to sqrt(n) and compute the answer:

for every times enum the postion i of array and count the times of

occurence of current number,if this >times , move the previous pointer

u until it ==times if (i-u)==times*kind answer++;

if times >sqrt(n) anyone has some ideas? I have some solution that is not beautiful and perfect,may it can pass..

Do you have link of this problem??

Now I continue to describe when times>sqrt(n) solution

if times>sqrt(n) the number of kind of numbers is <sqrt(n) enum this number

for every kind, enum the position of i, when number of kind

==this_kind, find the position of lu and ru which is on the left of i and lu is left most position num_of_kind==kind and ru is right most postion num_of_kind ==kind, and bs is the hash_value we assume every kind of number occur only once, and hs[i] i from lu to ru is the prefix of hash_value of position i.

every time when kind+1, we update the value hs[j]-j*bs/kind from lu to n-1, and sort them and use vector vec[] to record position of this hash_value,when kind is not change,lu is not move,and we move ru and compute the value of this enum position hs[i]-i*bs/kind and binary search vec[]...

you'd better give the link of the problem and test my solution if it can accept

I have

O(nlog^{2}n) solution, but it's not deterministic because of hashes.Let's solve it using divide-and-conquer algorithm. Suppose, we found number of such intervals, which lies in left or right half of array. Now we should find number of intervals with left border in left half and right border in right half. For such interval let's call number "interesting" if all of it's occurrences lies in one half of array. For example we have array [1, 2, 2, 3, 1, 6] ([1, 2, 2] is a left half). For interval [1, 2, 2, 3, 1] number 2 is interesting, and 1 is not.

Now we can notice, that there are 4 kinds of intervals:

(Cases 2 and 3 are nearly the same).

Let's find number of intervals if type 1.

For any two numbers

iandjcntl_{i}+cntr_{i}=xandcntl_{j}+cntr_{j}=x. We can rewrite it ascntl_{i}+cntr_{i}=cntl_{j}+cntr_{j}orcntl_{i}-cntl_{j}= - (cntr_{i}-cntr_{j}).Let's look at some interval [

l;r] (mis a divide point in divide-and-conquer). For suffix [l;m] and prefix [m+ 1;r] let's write array of pairs (number;number_of_its_occurrences). If we'll sort this two arrays by first element, it's clear that for good interval (and only for good interval) first elements in all pairs are equal and differences of second elements of adjacent pairs are equal by absolute values and have different signs (because of this equationcntl_{i}-cntl_{j}= - (cntr_{i}-cntr_{j})).So we just need to find for each prefix/suffix hash of set of first numbers in pairs and differences of adjacent second elements in pairs. It can be easily done using treaps or any other BST.

Let's move to the second case (and third because of symmetry). Let's again look to array of pairs (

number;number_of_its_occurrences) of left part. Numbers which have maximal number of occurrences are "interesting". We shouldn't add them to hash (because we won't have them in right part), but they shows us, how many occurrences of each element we will have in interval. It's quite easy to calculate hash of all values expect "ineteresting" numbers using treap (for example just store two treaps: one for numbers with maximum number of occurrences and one for all other numbers). But now we should consider, that we know number of occurrences of each number. It's quite easy: we just know, how many occurrences of number with minimal value should we have on the right, so we just store pair (hash;how_many_occurrences_of_minimal_number_on_the_right).Cases 3 and 4 are absolutely similar to 2.

I understand, that my English is terrible and I'm very bad in describing solutions, so feel free to ask if something is hard to understand.

P.S. Looks like we don't even need treaps, simple std::map can do anything we want.

What is

cntl_{i}andcntl_{r}?For suffix [

l;m] and prefix [m+ 1;r] let's write array of pairs (number;numberofitsoccurrences) — what does it mean? For which prefix/suffix?cntl_{i}— number of occurrences of numberiin half of interval, which lies to the left of cut point.For each suffix of left part of array and for each prefix of right half (every interval, which goes through middle point is concatenation of suffix of left half and prefix of right).

Wow! This is brilliant! Thanks!

You are welcome ;)

By the way, this task is very nice. I really enjoyed thinking on it.

I am not :(

oh, it's from IZHO 2016, i think it will be helpful to understand the problem properly.

http://izho.kz/2016/1%20day.%20contest-en.pdf

Day 1, problem c

It's not the same problem. The definition of "good" is different. Although the IZHO one is also very interesting.