Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

0442A403's blog

Random problem
By 0442A403, 7 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

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

Is this even solvable?

→ Reply
  • »
    »
    7 years ago, hide # ^ |
     
    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
»
7 years ago, hide # |
 
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
»
7 years ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

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

→ Reply
»
7 years ago, hide # |
 
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