xuanji's blog

By xuanji, history, 13 months ago, In English

Curious if anyone knows how to solve the following problem faster than $$$O(n^2)$$$.

Given an array $$$a$$$ of length $$$n$$$ and an integer $$$n$$$, find any two numbers $$$l$$$ and $$$r$$$ ($$$l \le r)$$$ such that:

  • Let $$$a'$$$ be the subarray $$$a_l, a_{l+1}, ... a_r$$$. Then for each $$$x$$$ that appears in $$$a'$$$, $$$x$$$ appears in $$$a'$$$ at least $$$k$$$ times (i.e. $$$k$$$ or more array elements are equal to $$$x$$$).
  • The value $$$r-l$$$ is maximized.

Source of problem: I misread https://codeforces.com/contest/1676/problem/F

Full text and comments »

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