Longest Strike 2

Revision en1, by xuanji, 2022-05-16 09:12:06

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English xuanji 2022-05-16 09:12:06 507 Initial revision (published)