Daisy chains#10365

Daisy chains (Editorial)

The solution runs in $O (n^{3})$ O(n^3). Iterate over all possible intervals $[i; j] (0 \leq i \leq j < n)$ [i; j]~(0 \le i \le j < n) and check whether they contain a median flower. For this, there must exist some $p_{k} (i \leq k \leq j)$ p_k~(i \le k \le j) such that

p_{k} = t o t a l P e t a l s / (j - i + 1),

p_k = totalPetals / (j - i + 1),

where $t o t a l P e t a l s$ totalPetals is the total number of petals of the flowers in the interval $[i; j]$ .

Algorithm implementation — $O (n^{3})$ O(n^3)

Declare an array to store the number of petals $p_{i}$ p_i in each flower.

#define MAX 101
int p[MAX];

Read the input data.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &p[i]);

The number of photographs that contain a median flower will be stored in the variable $p h o t os$ .

photos = 0;

Iterate over all possible intervals $[i; j] (0 \leq i \leq j < n)$ [i; j]~(0 \le i \le j < n) and check whether the average number of petals of the flowers in this interval matches the number of petals of at least one of them.

for (i = 0; i < n; i++)
for (j = i; j < n; j++)
{

The variable $t o t a l P e t a l s$ totalPetals stores the total number of petals of the flowers in the interval $[i; j]$ .

  int totalPetals = 0;
  for (k = i; k <= j; k++)
    totalPetals += p[k];

Iterate over the values $p_{k}$ p_k in the interval $[i; j] (i \leq k \leq j)$ [i; j]~(i \le k \le j). If $p_{k}$ p_k is equal to the average number of petals among all flowers in the photograph on the interval $[i; j]$ , then increase the value of $p h o t os$ by $1$ . For this, the following condition must hold:

p_{k} = t o t a l P e t a l s / (j - i + 1)

p_k = totalPetals / (j - i + 1)

  present = 0;
  for (int k = i; k <= j; k++)
    if (p[k] * (j - i + 1) == totalPetals) present = 1;
  if (present) photos++;
}

Print the answer.

printf("%d\n", photos);