tom's blog

Teasing, unsolvable (?) problem
By tom, history, 7 years ago, In English

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!

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
7 years ago, # |
  Vote: I like it +47 Vote: I do not like it

Bound on n?

→ Reply
»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Define unsolvable? Unless I understand it wrong, it is easily solvable in O(n2).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Then I suppose he meant with a better complexity, like O(N lg N) or O(N lg N sqrt N)

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

Completly misunderstood the problem, please ignore

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    If set is balanced then odd[l - 1] = odd[r] but there can be intervals with odd[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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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??

→ Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it +23 Vote: I do not like it

I have O(nlog2n) 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:

  1. No interesting numbers on the left, no interesting numbers on the right.
  2. There are interesting numbers on the left, no interesting numbers on the right.
  3. No interesting numbers on the left, there are interesting numbers on the right.
  4. There are interesting numbers on both sides.

(Cases 2 and 3 are nearly the same).

Let's find number of intervals if type 1.

For any two numbers i and j cntli + cntri = x and cntlj + cntrj = x. We can rewrite it as cntli + cntri = cntlj + cntrj or cntli - cntlj =  - (cntri - cntrj).

Let's look at some interval [l;r] (m is 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 equation cntli - cntlj =  - (cntri - cntrj)).

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is cntli and cntlr ?

    For suffix [l;m] and prefix [m + 1;r] let's write array of pairs (number;number of its occurrences) — what does it mean? For which prefix/suffix?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      cntli — number of occurrences of number i in 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).

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow! This is brilliant! Thanks!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are welcome ;)

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

      → Reply
»
7 years ago, # |
  Vote: I like it -9 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply