Zacle07's blog

uVa Frequent values WA. Need help
By Zacle07, history, 9 years ago, In English

Here's the problem . I don't know why I'm getting WA on this problem. Here's my code. Your help will be highly appreciated

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

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

I haven't read all of your code, but this example (or something very similar) will break your code.

Look at the array [1, 1, 1, 2, 2, 2, 2, 3, 3, 3]. In the left half of the array 1 is the most frequent value (with frequency 3), in the right side 3 (with frequency 3). But in total the most frequent element is 2 with frequency 4. So return max(left, right); (line 23) will not work.

Usually this type of problem is solved using Mo's algorithm. I don't think that there is a fast solution using a Segment Tree.

→ Reply