ArenaRating

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 11 to cnt . Otherwise, reset cnt to 00. Find the maximum possible cnt value.

Supposing there are d=9d = 9 types of fruits, there are d(d1)2=36\frac{d(d-1)}{2} = 36 ways to choose two of them, and each of the choices O(N)O(N) time. Total time complexity is O(d2N)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 RlR_l, the rightmost point of the longest continuous sequence of two or less types of fruits starting from SlS_l. That is, there are always two or less types of fruits in Sl,Sl+1,,SRlS_l, S_{l+1}, \cdots, S_{R_l}. Removing SlS_l from the sequence, there are still two or less types of fruits in Sl+1,,SRlS_{l+1}, \cdots, S_{R_l} so Rl+1R_{l+1} is always larger than or equal to RlR_l. Therefore, RlR_l increases with $l.

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

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

Variable r is used to maintain Rl+1R_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() }