# PROBLEM LINK:

**Author:** Avijit Agarwal

**Tester and Editorialist:** Soumik Sarkar

# DIFFICULTY:

CAKEWALK

# PREREQUISITES:

Strings, Sorting

# PROBLEM:

Given a string S find the frequency of each character in the string and check whether they can be rearranged into a sequence F where F_i = F_{i-2} + F_{i-1} holds for all i \ge 3.

# EXPLANATION:

Finding the frequency of each character can be done in linear time. One possible way is below

```
m = empty map
for each character c in S:
if c in m:
m[c] = m[c] + 1
else:
m[c] = 0
F = empty list
for each key, value in m:
append value to F
```

Next we can say that because F_i = F_{i-1} + F_{i-2} and F_{i-2} cannot be 0, F_i > F_{i-1} for all i \ge 3. So it makes sense to sort the array F.

Then we can check if F satisfies the given condition for all i \ge 3. If it does, then the string is dynamic otherwise it is not, right? …But hold on, there is a catch. Indeed F_i > F_{i-1} for all i \ge 3, but what about F_2? The relation between F_2 and F_1 is not specified. So it maybe that F_4 \ne F_2 + F_3 in the sorted order but F_4 = F_1 + F_3. In that case if we can simply swap F_1 and F_2 to get the required sequence and the string is dynamic.

For example: F = (1, 2, 3, 4). Here 3 = 1 + 2 but of course 4 \ne 2 + 3. If we swap 1 and 2 we will get (2, 1, 3, 4) where 3 = 2 + 1 and 4 = 1 + 3.

```
sort F
N = length of F
if N >= 4 and F[4] != F[2] + F[3]:
swap(F[1], F[2])
ok = True
if N >= 3:
for i in [3..N]:
if F[i] != F[i - 1] + F[i - 2]:
ok = False
if ok:
S is dynamic
else:
S is not dynamic
```

# AUTHOR’S AND TESTER’S SOLUTION:

Author’s solution can be found here

Tester’s solution can be found here.