Subtask 1: Due to the small value of $N$, we can just brute force all possible subsets of cows and all permutations of them.
#include <algorithm> #include <iostream> #include <vector> int main() { int t; std::cin >> t; for(int cn = 1; cn <= t; cn++) { int n; std::cin >> n; std::vector<int> v(n); for(auto& x: v) std::cin >> x; std::sort(v.begin(), v.end()); int ret = 1; do { for(int len = 1; len <= n; len+=2) { bool valid = true; for(int i = 0; valid && 2*i+1 < len; i++) { valid = v[i] == v[len-1-i] && v[i] < v[i+1]; } if(valid) ret = std::max(ret, len); } } while(std::next_permutation(v.begin(), v.end())); std::cout << ret << "\n"; } }
Subtask 2: Assume that Farmer John wants the picture to have a cow with every height from $1$ to $10$. What is the maximum number of cows that can be in the picture?
It is not hard to see that the only valid arrangement is to have cows with heights $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]$. In general, if multiple heights exist, then the middle cow must be the tallest, and then two cows of the next-tallest height must get placed on each end, and progressively shorter cows are placed on each end.
We can therefore brute force all $\mathcal{O}(2^{10})$ subsets of heights that could appear and see if we can construct such a photo.
#include <algorithm> #include <iostream> #include <vector> int main() { int t; std::cin >> t; for(int cn = 1; cn <= t; cn++) { int n; std::cin >> n; std::vector<int> f(n+1); for(int i = 0; i < n; i++) { int x; std::cin >> x; f[x]++; } int ret = 1; for(int mask = 1; mask < (1<<std::min(n,10)); mask++) { bool valid = true; bool seen = false; for(int i = std::min(n,10); valid && i > 0; i--) { if(mask&(1<<(i-1))) { if(f[i] == 0) valid = false; if(!seen) seen = true; else if(f[i] < 2) valid = false; } } if(valid) ret = std::max(ret, 2*__builtin_popcount(mask)-1); } std::cout << ret << "\n"; } }
Full credit: Consider an optimal picture. If the middle cow is not the tallest one, we can safely replace the middle cow with the tallest cow. From then, consider the cows in decreasing height. If it is possible to take taller cows and replace a pair of non-adjacent cows of smaller height, then we can do so without affecting the optimality of the picture.
Therefore, we have the following algorithm for constructing an optimal picture:
This gives us a linear-time algorithm - all that we need to efficiently simulate this is that we track for a given height $H$ how many cows have that height.
Nick Wu's C++ solution:
#include <iostream> #include <vector> int main() { int t; std::cin >> t; for(int cn = 1; cn <= t; cn++) { int n; std::cin >> n; std::vector<int> f(n+1); for(int i = 0; i < n; i++) { int x; std::cin >> x; f[x]++; } int ret = 0; bool seen = false; for(int i = n; i > 0; i--) { if(f[i] == 0) continue; if(!seen) ret++; else if(f[i] >= 2) ret += 2; seen = true; } std::cout << ret << "\n"; } }
Benjamin Qi's Python solution:
from collections import Counter T = int(input()) for _ in range(T): N = int(input()) A = map(int, input().split()) c = Counter(A) max_key = max(c.keys()) print(sum(2 * (v >= 2) for v in c.values()) + (c[max_key] == 1) - (c[max_key] >= 2))