solved.ac Grand Arena #3

Solution 1

Let's decide on the two fruits that will be used. After that, we look for the longest continuous subsequence of those two fruits. This can be done by using the split method (if your language supports it) or by maintaining a cnt variable and traversing the list from the front. If the current element is one of the chosen types of fruits, add $1$ to cnt . Otherwise, reset cnt to $0$. Find the maximum possible cnt value.

Supposing there are $d = 9$ types of fruits, there are $\frac{d(d-1)}{2} = 36$ ways to choose two of them, and each of the choices $O(N)$ time. Total time complexity is $O(d^2N)$.

Code (C++20)

#include <iostream>
#include <ranges>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> S(N);
    for (int &s : S)
        cin >> s;
    int ans = 0;
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j < i; j++)
        {
            auto v = S | views::transform([&](int x)
                                          { return x == i || x == j; });
            for (auto w : views::split(v, false))
                ans = max(ans, (int)distance(w.begin(), w.end()));
        }
    cout << ans << endl;
}

Code (Python)

import re


def main():
    input()
    s=''.join(input().split())
    ans = 0
    for i in range(1, 10):
        for j in range(1, i):
            ans = max(ans, max(map(len, re.split(f'[^{i}{j}]', s))))
    print(ans)


if __name__ == "__main__":
    main()

Code (Rust)

use std::io::*;
use std::iter::FromIterator;

fn main() {
    stdin().read_line(&mut String::new()).unwrap();
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    let s = String::from_iter(s.chars().filter(|&x| !x.is_ascii_whitespace()));
    let mut ans = 0;
    for i in '1'..='9' {
        for j in '1'..i {
            ans = ans.max(
                s.split(|x| x != i && x != j)
                    .map(|x| x.len())
                    .max()
                    .unwrap_or_default(),
            );
        }
    }
    println!("{}", ans);
}

Solution 2

Let's denote using $R_l$, the rightmost point of the longest continuous sequence of two or less types of fruits starting from $S_l$. That is, there are always two or less types of fruits in $S_l, S_{l+1}, \cdots, S_{R_l}$. Removing $S_l$ from the sequence, there are still two or less types of fruits in $S_{l+1}, \cdots, S_{R_l}$ so $R_{l+1}$ is always larger than or equal to $R_l$. Therefore, $R_l$ increases with $l.

Supposing $R_{l-1}$ was calculated, and since we know $R_l$ to be larger than or equal to $R_{l-1}$, we can use a naive solution using a loop from $r = R_{l-1}$ increasing $r$ by $1$ each iteration looking for the maximum $r$ such that there are two or less types of fruits in $S_{l}, \cdots, S_r$. Since $r$ increases by $N$ in the loop, the number of iterations does not exceed $O(N)$.

Now we just need to find the types of fruits in $S_l, \cdots, S_r$ fast. This can be done by maintaining a cnt array of length $10$ in which we store the count of each type of fruit in the current range $S_l, \cdots, S_r$, and if we also store the number of types of fruits with more than $1$ fruit, this can be solved in $O(1)$ time. Total complexity is $O(N)$.

Variable r is used to maintain $R_l + 1$ in the below code.

Code (C++)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<int> S(N);
    for (int &s : S)
        cin >> s;
    int ans = 0, r = 0, non_zero = 0;
    vector<int> cnt(10);
    for (int l = 0; l < N; l++)
    {
        while (r < N)
        {
            int nxt_non_zero = non_zero + (cnt[S[r]] == 0 ? 1 : 0);
            if (nxt_non_zero <= 2)
            {
                cnt[S[r]]++;
                r++;
                non_zero = nxt_non_zero;
            }
            else
                break;
        }
        ans = max(ans, r - l);
        cnt[S[l]]--;
        if (cnt[S[l]] == 0)
            non_zero--;
    }
    cout << ans << endl;
}

Code (Python)

def main():
    N = int(input())
    S = map(int, input().split())

    ans = r = non_zero = 0
    cnt = [0]*10

    for l in range(N):
        while r < N:
            nxt_non_zero = non_zero + (1 if cnt[S[r]] == 0 else 0)
            if nxt_non_zero <= 2:
                cnt[S[r]] += 1
                r += 1
                non_zero = nxt_non_zero
            else:
                break
        ans = max(ans, r - l)
        cnt[S[l]] -= 1
        if cnt[S[l]] == 0:
            non_zero -= 1

    print(ans)


if __name__ == "__main__":
    main()

Code (Rust)

use std::io::*;

fn main() {
    let n = read_vec()[0];
    let s = read_vec();

    let mut ans = 0;
    let mut r = 0;
    let mut non_zero = 0;
    let mut cnt = [0; 10];

    for l in 0..n {
        while r < n {
            let nxt_non_zero = non_zero + if cnt[s[r] as usize] == 0 { 1 } else { 0 };
            if nxt_non_zero <= 2 {
                cnt[s[r]] += 1;
                r += 1;
                non_zero = nxt_non_zero;
            } else {
                break;
            }
        }
        ans = ans.max(r - l);
        cnt[s[l]] -= 1;
        if cnt[s[l]] == 0 {
            non_zero -= 1;
        }
    }

    println!("{}", ans);
}

fn read_vec() -> Vec<usize> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}