CF - Longest k-Good Segment

Authors: Sofia Yang, Mohammad Nour Massri, Neo Wang

Edit This Page

Official Editorial (C++)

Explanation

We can binary search for the largest valid segment size. If this segment is valid, update the current value of ret\texttt{ret} with our indices ii and jj. Rather than using a map, we instead opt to use a presized HashTable for faster O(1)\mathcal{O}(1) query operations.

Implementation

Time Complexity: O(Nlog⁡N)\mathcal{O}(N \log N)

C++

 Code Snippet: C++ Short Template (Click to expand)


 Code Snippet: HashTable (Click to expand)


const int mx = 5e5 + 1;


int n, k;
int v[mx];
pi ret;

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9, MAX_Ai = 1e6 + 9;
int n, k;
int a[N];
int frequency[MAX_Ai];  // frequency of each number in the window
int maxSegment, leftMaxSegment,
    rightMaxSegment;  // max size of the segment and its ends


int main() {

Java

import java.io.*;
import java.util.*;
public class KGood {
 	Code Snippet: Kattio (Click to expand)


	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int N = io.nextInt();
		int K = io.nextInt();
		int difVal = 0;  // Number of different values in the window.

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum