Hardstone's hard problem

Правка en4, от dfsof, 2023-08-17 06:02:41

Prof. hardstone gives you an integer array $$$A$$$. The length of $$$A$$$ is $$$n$$$ and there are $$$m$$$ distinct numbers in $$$A$$$. Count the number of tuple $$$(l, r)$$$, $$$1 \leq l \leq r \leq n$$$, such that:

Numbers that appear in the interval $$$a[l...r]$$$ appear the same number of times.

For example, $$$A=[1,2,1,2]$$$, then there are $$$8$$$ legal tuples: $$$(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (3, 4), (1, 4)$$$.

This is an open problem with brain storm. $$$O(n^2m)$$$ brute force using the prefix sum and $$$O(n2^m)$$$ brute force using bitmasks and hashtable are easy to come up with. I am looking for a $$$O(nmlog^k)$$$ solution. Are there any smart data structures?

Note that when $$$A = [1,2,3]$$$, all intervals are legal. For example, $$$[1, 2]$$$ is legal, as both $$$1$$$ and $$$2$$$ appear once. We do not care about $$$3$$$ because $$$3$$$ does not appear.

amenotiomoi proposes a genius randomized $$$O(n^2)$$$ idea, and I formalize his idea here: Similar to the Zobrist hashing, we assign a random value to each distinct integer. We record the prefix sum of the hash values. Then, we fix $$$l$$$ and count the number of $$$r$$$ with respect to this $$$l$$$. For each $$$l$$$, we denote $$$p(l, j)$$$ be the first place $$$j$$$ appears after $$$l$$$ (inclusive), somehow like std::string.find(j, l). If $$$j$$$ never appears after $$$l$$$, we let $$$p(l, j) = \infty$$$. For example, if $$$A=[4,1,2,3]$$$, then $$$p(2, 1)=2, p(2,2)=3, p(2,3)=4, p(2,4) = \infty$$$.

Теги data structures, string, array

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский dfsof 2023-08-17 10:52:07 7 Tiny change: 'fter $l$, we let $p(l, j) ' -> 'fter $l$, $p(l, j) '
en17 Английский dfsof 2023-08-17 06:48:21 10
en16 Английский dfsof 2023-08-17 06:44:25 2 Tiny change: '2,2,3]$, $r=1$, $2 \l' -> '2,2,3]$, $l=1$, $2 \l'
en15 Английский dfsof 2023-08-17 06:26:34 5 Tiny change: '= O(n(mlogm + mlogn +nlogmlogn' -> '= O(n(mlogn + mlogm+nlogmlogn'
en14 Английский dfsof 2023-08-17 06:23:56 0 (published)
en13 Английский dfsof 2023-08-17 06:23:51 5 Tiny change: 'could be find via bina' -> 'could be fould via bina' (saved to drafts)
en12 Английский dfsof 2023-08-17 06:22:37 0 (published)
en11 Английский dfsof 2023-08-17 06:22:30 36 (saved to drafts)
en10 Английский dfsof 2023-08-17 06:19:31 15 Tiny change: 'r$ be the hash value of $a[1..' -> 'r$ be the prefix sum of hash values of $a[1..'
en9 Английский dfsof 2023-08-17 06:18:58 0 (published)
en8 Английский dfsof 2023-08-17 06:18:53 1 Tiny change: ' $O(mlogm). For two ' -> ' $O(mlogm)$. For two ' (saved to drafts)
en7 Английский dfsof 2023-08-17 06:17:52 0 (published)
en6 Английский dfsof 2023-08-17 06:17:45 691
en5 Английский dfsof 2023-08-17 06:10:29 739
en4 Английский dfsof 2023-08-17 06:02:41 86
en3 Английский dfsof 2023-08-17 06:02:04 542 (saved to drafts)
en2 Английский dfsof 2023-08-17 05:34:18 185
en1 Английский dfsof 2023-08-17 05:13:45 695 Initial revision (published)