mike_wasabi's blog

How to solve this problem ?
By mike_wasabi, history, 6 years ago, In English

Give integer ranges A1, A2, .., AN. Number Ai is called the K-random number of the sequence if in K terms Any sequence of a sequence has at least one term equal to Ai and K is the smallest integer that satisfies this condition. Example: Range 1,2,3,1,2,2. Number 1 is a 3-random number; number 2 is a 3-random number; number 3 is a 4-random number Conditions: N <= 100000 and | Ai | <= 1000.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Run a loop from 1 to N. For each number, remember the last index where you found that number untill now (untill current index). For example, let's say that we are currently at index i. We do the following:

maxi[Ai] = max(maxi[Ai], i — last_index[Ai];

last_index[Ai] = i;

In the end you just calculate this for each number:

maxi[number] = max(maxi[number], N — last_index[number]);

→ Reply