0442A403's blog

Random problem
By 0442A403, 5 years ago, In English

You have an array $$$arr$$$ with $$$n$$$ elements. Let number $$$i$$$ occurs in multiset $$$Q$$$ $$$arr_i$$$ times. How to get random number from multiset $$$Q$$$ faster than $$$O($$$$$$\log n$$$$$$)$$$?

$$$n$$$ <= $$$1e5$$$, $$$arr_i$$$ <= $$$1e9$$$

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this even solvable?

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

    I think that this one is $$$O(logn)$$$:

    Generate random number from $$$1$$$ to sum of elements of array $$$arr$$$. The answer will be minimum $$$i$$$ such that sum of elements of array $$$arr$$$ from $$$1$$$ to $$$i$$$ is greater than equal to this random number using binary search.

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

You need to clarify this. Why can't I for O(1) take first item from Q? What "get random numner" there means? What multiset is for in this task?

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

    In this task "multiset" is not name of data structure.

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

Try this : https://en.wikipedia.org/wiki/Alias_method

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

Sometimes I wonder what are the trends that determine whether a post would get straight up downvoted or not.

→ Reply