//testing Ai Code
#include "triplepeaks.h"
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
// Part I: Count mythical triples
long long count_triples(vector<int> H) {
int N = H.size();
long long count = 0;
// For each middle peak j
for (int j = 1; j < N - 1; j++) {
// Count pairs (i, k) where i < j < k
// Heights are (H[i], H[j], H[k])
// Distances are (j-i, k-j, k-i)
// Use a map to count occurrences of each height on the left
map<int, int> left_count;
for (int i = 0; i < j; i++) {
left_count[H[i]]++;
}
// For each k > j
for (int k = j + 1; k < N; k++) {
int d1 = k - j; // distance from j to k
// For a mythical triple, we need heights to match distances
// Distances are: (j-i, k-j, k-i) = (j-i, d1, j-i+d1)
// Case 1: H[j] = j-i, so j-i = H[j], thus i = j - H[j]
// Then we need {H[i], H[k]} = {d1, j-i+d1} = {d1, H[j]+d1}
if (j - H[j] >= 0) {
int i = j - H[j];
if (i < j) {
// Check if {H[i], H[k]} matches {d1, H[j] + d1}
if ((H[i] == d1 && H[k] == H[j] + d1) ||
(H[i] == H[j] + d1 && H[k] == d1)) {
count++;
}
}
}
// Case 2: H[j] = d1 (distance j to k)
// Then we need {H[i], H[k]} to match {j-i, k-i}
// If H[k] = j-i, then j-i = H[k], so i = j - H[k]
if (j - H[k] >= 0 && j - H[k] < j) {
int i = j - H[k];
int d2 = j - i; // = H[k]
int d3 = k - i; // = d2 + d1
if (H[j] == d1 && H[i] == d3) {
count++;
}
}
// Case 3: H[j] = k-i
// Then k-i = H[j], distances are (j-i, d1, H[j])
// We need {H[i], H[k]} = {j-i, d1}
// If H[i] = j-i, then i such that j-i = H[i]
// If H[k] = j-i, then we need to check
int d3_target = H[j]; // k - i should equal H[j]
int i_candidate = k - d3_target;
if (i_candidate >= 0 && i_candidate < j) {
int d2 = j - i_candidate;
if ((H[i_candidate] == d2 && H[k] == d1) ||
(H[i_candidate] == d1 && H[k] == d2)) {
count++;
}
}
}
}
// The above counts each triple multiple times, need to fix
// Actually, let me rewrite with correct logic
count = 0;
for (int i = 0; i < N - 2; i++) {
for (int j = i + 1; j < N - 1; j++) {
for (int k = j + 1; k < N; k++) {
int d1 = j - i;
int d2 = k - i;
int d3 = k - j;
vector<int> heights = {H[i], H[j], H[k]};
vector<int> distances = {d1, d2, d3};
sort(heights.begin(), heights.end());
sort(distances.begin(), distances.end());
if (heights == distances) {
count++;
}
}
}
}
return count;
}
// Part II: Construct mountain range with many mythical triples
vector<int> construct_range(int M, int K) {
// Strategy: Create patterns that generate many mythical triples
// Pattern 1: Repeating sequence that creates many triples
// A simple pattern: use heights that are small and repeat
// Heights like [1, 2, 1, 2, 1, 2, ...] can create triples
// Better pattern: Use arithmetic progressions
// For large M, we want to maximize triples
vector<int> H;
if (M <= 100) {
// Small case: use pattern [1, 2, 3, 1, 2, 3, ...]
int pattern_len = min(M, 10);
for (int i = 0; i < M; i++) {
H.push_back((i % pattern_len) + 1);
}
} else {
// Large case: use a pattern that maximizes triples
// Pattern: mostly 1s and 2s which create many small distance triples
int n = min(M, 200000);
for (int i = 0; i < n; i++) {
if (i % 3 == 0) H.push_back(1);
else if (i % 3 == 1) H.push_back(2);
else H.push_back(1);
}
}
// Ensure heights are valid (between 1 and N-1)
int N = H.size();
for (int i = 0; i < N; i++) {
if (H[i] >= N) H[i] = N - 1;
if (H[i] < 1) H[i] = 1;
}
return H;
}
