class-06.Rmd

---
title: "Class 06: Complete Search III"
date: "01-22-2020"
---

```{r setup, include=FALSE}
htmltools::tagList(rmarkdown::html_dependency_font_awesome())
```

> "Think twice, code once"


<div class="topic">Two pointers</div>

This technique is usually used in an array. We have a pointer to the first
element of the array and to the last. The first pointer will be increasing and
the other one decreasing (you may also find variations of this idea). In practice, intead of using a pointer, a `int`
variable to keep track of the index is usually enough.

Let's see this technique with an example:

**Problem:** You are given an array $a$ of $n$ elements. You should output the
minimum number of intervals $[l_i, r_i] \mid a_i = a_j \forall \, i, j \in [l_i,
r_i]$ \land $[l_1, r_1] \cup [l_2, r_2] \cup \dots \cup [l_m, r_m] = [1, n]$.

$$1 \leq n \leq 10^5$$

**Example:**

**Input:**

$n = 7$

$a = 1\ 1\ 1\ 2\ 2\ 3\ 3$

**Output:**

$1\ 3$

$4\ 5$

$6\ 7$

### First implementation

```c++
vector <pair <int, int>> solution1 (const vector <int>& arr) {
  int n = arr.size();
  vector <bool> vis(n, false);
  vector <pair <int, int>> ret;
  for (int l = 0; l < n; l++) {
    if (vis[l]) continue;
    int L = l;
    int R = l;
    for (int r = l; r < n and arr[l] == arr[r]; r++) {
      vis[r] = true;
      R = r;
    }
    ret.push_back({1 + L, 1 + R});
  }
  return ret;  
}
```

### Second implementation

```c++
vector <pair <int, int>> solution2 (const vector <int>& arr) {
  int n = arr.size();
  vector <pair <int, int>> ret;
  int l = 0;
  while (l < n) {
    int r = l;
    while (r + 1 < n and arr[l] == arr[r + 1]) r++;
    ret.push_back({1 + l, 1 + r});
    l = r + 1;
  }
  return ret;  
}
```

[Full code](./code/class-06/intervals.cpp)

The time complexity of both solutions is $O(n)$.

Let's use this technique in [this problem](https://leetcode.com/problems/two-sum/):

**Problem (2 sum problem):** You are given an array $a$ of $n$ **positive** elements and an integer $target$. You
should output two numbers $i, j \mid i \not = j \land a_i + a_j = target$. It is garantee that a solution always exits.

$$1 \leq n \leq 10^5$$
$$1 \leq target \leq 10^9$$

We can use the same technique and sorting to solve the problem in $O(n \log n)$.

First, let's sort the array and initiate with $l = 0 \land r = n - 1$. $l$ would
just increase and $r$ would just decrease. Then, by the trichotomy property there are
three cases:

* $a[l] + a[r] == target$

  Then, we have and answer and our program can finish

* $a[l] + a[r] < target$

  In this case we need to get a greater sum. Decreasing $r$ the sum may keep
  the same or smaller. Increasing $l$ the sum may keep the same or greater.
  Then, we need to increase $l$.

* $a[l] + a[r] > target$

  Similar to the previous case, we need to decrease the sum, then we decrease
  $r$.

```c++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector <pair <int, int>> arr;
        int index = 0;
        for (int elem: nums) {
            arr.push_back({elem, index});
            index++;
        }
        sort(begin(arr), end(arr));
        int n = nums.size();
        int l = 0, r = n - 1;
        vector <int> ans;
        while (l < r) {
            if (arr[l].first + arr[r].first == target) {
                ans = {arr[l].second, arr[r].second};
                break;
            }
            if (arr[l].first + arr[r].first < target) l++;
            else r--;
        }
        return ans;
    }
};
```

**Extra:** This is another solution using STL + fixing variables in $O(n \log n)$:

```c++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector <int> ans;
        map <int, vector <int>> pos;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            pos[nums[i]].push_back(i);
        }
        for (int x = 0; x < n; x++) {
            int k = target - nums[x];
            if (pos.count(k)) {
                int cnt = 0;
                for (int y: pos[k]) {
                    if (y != x) {
                        ans = {x, y};
                    }
                    cnt++;
                    if (cnt == 2) break;
                }
            }
        }
        return ans;
    }
};
```



How could you solve the same problem if you need to find three numbers $x, y, z \mid
x \not = y \not = z \land a_x + a_y + a_z = target$ ?

<div class="topic">Recursion</div>

Imagine you have a funtion $f$ that solves a problem in this way:

* When we are in a state with a specific property, we know how to directly solve
  the problem.
* If we are not in a state with the specific property, we can solve the problem
  using different states of $f$.

For example:

$$f(n) = 1 \times 2 \times 3 \times \dots \times n$$

We want to compute $f(n)$ in a recursive way. Then we need:

* Identify a state with a specific property that we can solve easily.

  If $n = 0 \to f(0) = 1$.

* Identify how to solve $f(n)$ using different states of $f$ (that are 'closer'
  to the states with a specific property of the above point). For instance:

$$f(n) = \underbrace{1 \times 2 \times 3 \times \dots \times (n - 1)}_{\text{f(n - 1)}} \times n$$
$$f(n) = n \times f(n - 1)$$

Then, we are basically saying that if $n = 0$ we know how to solve the problem,
else if we have the answer of $f(n - 1)$ we can use it to solve $f(n)$.

In code it is something like this:

```c++
ll f (int n) {
  if (n == 0) return 1;
  return n * f(n - 1);
}
```

What is nice about recursion is that we can think in a recursive way. Thinking
in this way the problem may become easier. For example you can say:

Let $f$ be a function that solves the problem I am trying to solve. Then, you
may say. I have no idea how to solve $f(state)$, but if somehow I would have
the answer of $f(state'), f(state''), f(state'''), \dots$ then I can solve
$f(state)$ and I know how to solve the problem in specific states.

Then, in code, recursive solutions usually have have the form:

```vw
T f(state):
  if (state have a specific property):
    solve the problem for this state and return something
  else:
    get the answer of f(state'), f(state''), f(state'''), ...
    and using these answers compute f(state) and return something
```

For example, let's solve the problem of the towers of Hanoi.

### The tower of Hanoi

<div class="row text-center img-border">
![](./images/class-05/Hanoi.jpeg)

Image taken from [Wikipedia](https://en.wikipedia.org/wiki/Tower_of_Hanoi#/media/File:Tower_of_Hanoi.jpeg)
</div>

**Problem:** You have 3 rods, and a pile of $n$ disks in one rod. Each disk have different
diameter, the disks are in order in the stack, the greatest in the button and
the smallest on the top. We want to move all the disks to another rod. We can
only move the top disk of a stack to another rod if the other rod is empty or
the diameter of its top element is greater that the one we are moving. Can you
give a sequence of movements to solve this problem ?

Let's say we have the function $f$ such that $f(source, target, pivot, n)$ moves
the $n$ disks that are in the `source` rod to the `target` rod. Then, we can
say:

If I want to move the $n$ disks from `source` rod to the `target` rod, first
I need to move $n - 1$ disks from `source` to `pivot`, then I move the last
disk in `source` to target. After that, we need to move the $n - 1$ disks  in
`pivot` to `target` and we are done. Moreover, if there is only one disk we can
direcly move it to `target`. Then, we can write $f$ in this way:

```bw
void f(source, target, pivot, n):
  if n == 1:
    move the disk in source to target
    return
  # move the top n - 1 disks in source to pivot
  f(source, pivot, target, n - 1)
  # move the last disk in source to target
  f(source, target, pivot, 1)
  # move the n - 1 disks in pivot to target
  f(pivot, target, source, n - 1)
```

And that's all. It solves the problem!

### Exercises

Write recursive functions to compute:

  * $fib(n)$

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemfib" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemfib" class="collapse">

```c++
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll fib (int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

int main () {
  int n = 40;
  cout << fib(n) << '\n';
  return (0);
}
```

  </div>
  <!-- ends code -->

  * Sum of digits of a number $n$

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemsum-digits" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemsum-digits" class="collapse">

```c++
#include <bits/stdc++.h>

using namespace std;

int sumOfDigits (int n) {
  if (n == 0) return 0;
  return (n % 10) + sumOfDigits(n / 10);
}

int main () {
  int n = 999;
  cout << sumOfDigits(n) << endl;
  return (0);
}
```

  </div>
  <!-- ends code -->

  * $C(n, k)$

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemcombinatorics" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemcombinatorics" class="collapse">

```c++
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll comb (int n, int m) {
  if (m == 0) return 1;
  if (n == m) return 1;
  return comb(n - 1, m - 1) + comb(n - 1, m);
}

int main () {
  cout << comb(4, 2) << '\n';
  return (0);
}
```

  </div>
  <!-- ends code -->

  * Determinant of a matrix


  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemdeterminant" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemdeterminant" class="collapse">

```c++
// This is your challenge
```

  </div>
  <!-- ends code -->

<div class="topic">Modular arithmetic</div>

When we are doing a division we are basically computing:

$$a = b \cdot \lfloor a / b \rfloor + r$$
$$0 \leq r < b$$

Now, we say:

$$a \equiv r \mod b \lor r \equiv a \mod b$$

That is $x \equiv y \mod m$ iff $(x - y) | m$.

**Note:** $r$ is what we get when we compute $a \% b$.

When working with modular arithmetic, that set of values our numbers can take
is $0, 1, 2, \dots, m - 1$, where $m$ is a constant. So each number $x$ is
represented as $x \mod m$.

For example, if $m = 12 \to x = 20$ is represented as $x \mod 12 = 8$.

In some problems you will be asked to output the answer module $m$. For doing
this you may just solve your problem and in the end output $your\_answer \% m$.
Nevertheless, what happend if $m= 10^9 + 7$ and you have:

```c++
int m = 1e9 + 7; // 10^9 + 7
long long a = 1e10; // 10^10
long long your_answer = (a * a) % m;
```

Althought we know that the $\%$ operator will give us a result less than $m$,
$a * a$ can not fit in a `long long` ($10^{20} > 2^{63}$), so we have `overflow`. In
order to fix that, we can use the properties of modular arithmetic:

$$(x + y) \mod m = (x \mod m + y \mod m) \mod m$$
$$(x - y) \mod m = (x \mod m - y \mod m) \mod m$$
$$(x \times y) \mod m = (x \mod m \times y \mod m) \mod m$$
$$x^n \mod m = (x \mod m)^n \mod m$$

So, we can fix the above code in this way:

```c++
long long your_answer = ((a % m) * (a % m)) % m;
```

From the above properties we have:

$x \mod m = x \mod m + 0 = x \mod m + m \mod m = (x + m) \mod m$

The last equation will be useful because in C++ the result of $\%$ can be
 in $(-m, m)$. For example:

```c++
cout << (-4) % 5 << '\n'; // -4
```

Then, the subtraction should be:

$$(x - y) \mod m = ((x \mod m - y \mod m) \mod m + m) \mod m$$

Now, the result will always be in $[0, m)$.

<div class="topic">Binary exponenciation</div>

$a^b$ can be expressed in a recursive way.

$$
    \text{power}(a, b) =
    \begin{cases}
        1       & \quad \text{If } b = 0 \\
        \text{power}(a, \lfloor b / 2 \rfloor) ^ 2  & \, \text{if } b \mod 2 = 0 \\
        a \times \text{power}(a, \lfloor b / 2 \rfloor) ^ 2 & \, \text{if } b \mod 2 = 1
    \end{cases}
$$

Moreover, from the properties of modular arithmetic, we can get $a^b \mod m$
as:

$$
    \text{binpow}(a, b) =
    \begin{cases}
        1       & \quad \text{If } b = 0 \\
        \text{binpow}(a, \lfloor b / 2 \rfloor) ^ 2 \mod m & \, \text{if } b \mod 2 = 0 \\
        (a \times \text{binpow}(a, \lfloor b / 2 \rfloor) ^ 2) \mod m & \, \text{if } b \mod 2 = 1
    \end{cases}
$$

In code:

```c++
const ll m = 1e9 + 7;

ll binpow (ll a, ll b) {
  if (b == 0) return 1;
  a %= m;
  ll res = binpow(a, b / 2);
  res = (res * res) % m;
  if (b % 2 == 1) res = (a * res) % m;
  return res;
}
```

The above code compute $a^b \mod m$ in $O(\log b)$.

This function will be really useful, but before using it, we need to know one
theorem.

### Fermat's little theorem

If $m$ is prime and $0 < a < m$, we have:

$$a^{m - 1} \equiv 1 \mod m$$

Moreover, we say the the inverse of $a$ is $b$ if:

$$ab \equiv 1 \mod m$$

$b$ is written as $a^{-1}$.

And as $a^{m - 1} = a \cdot a^{m - 2}$

Using Fermat's little theorem we have that the inverse of $a$ is $a^{m - 2}$ if $m$ is prime.

Now, we can mention one more property of modular arithmetic (if $b^{-1}$ exists).

$$\frac{a}{b} \mod m = ((a \mod m) \times (b^{-1} \mod m)) \mod m$$

Let's see how it is useful in [this problem](https://vjudge.net/problem/Gym-247724E).

**Problem:** Compute $S = (1 + a + a^2 + a^3 + \dots + a^k) \mod m$.

$$m = 10^9 + 7 \text{ (is prime)}$$
$$1 \leq a \leq 10^{18}$$
$$1 \leq k \leq 10^{18}$$

If $a = 1 \to S = (k + 1) \mod m$

If $a > 1 \to S = \frac{a^{k + 1} - 1}{a - 1} \mod m$

Then, we can use the above properties to compute that.

```c++
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll m = 1e9 + 7;

ll add (ll a, ll b) { return ((a % m) + (b % m)) % m; }
ll sub (ll a, ll b) { return (((a % m) - (b % m)) + m) % m; }
ll mul (ll a, ll b) { return ((a % m) * (b % m)) % m; }

ll binpow (ll a, ll b) {
  if (b == 0) return 1;
  a %= m;
  ll res = binpow(a, b / 2);
  res = mul(res, res);
  if (b % 2 == 1) res = mul(a, res);
  return res;
}

ll inverse (ll a) { return binpow(a, m - 2); }

int main () {
  ll a, k;
  cin >> a >> k;
  if (sub(a, 1) == 0) {
    cout << add(k, 1) << '\n';
  } else {
    cout << mul(sub(binpow(a, k + 1), 1), inverse(a - 1)) << '\n';
  }
  return (0);
}
```

Recommended readings:

* Concrete Mathematics - Knuth. Chapter 1
* [Modular Arithmetic for Beginners](https://codeforces.com/blog/entry/72527)
* [Competitive Programmer’s Handbook, chapters 5, 8 y 21](https://jadi.net/wp-content/uploads/2017/07/competetive-programmers-handbook.pdf)
* Principles of Algorithmic Problem Solving, sections 15.6 y 15.7
* [Learn Data Structures and Algorithms, section Basic Recursion](https://www.codechef.com/certification/data-structures-and-algorithms/prepare)
* [E-maxx Binary Exponentiation](https://cp-algorithms.com/algebra/binary-exp.html)

<div class="topic" id="contest">Contest</div>

You can find the contest [here](https://vjudge.net/contest/353470).


<!-- Begins problem A -->
<div class="card" id="A">
<div class="collapsed solution-title" type="button" data-toggle="collapse" data-target="#collapseProblemA" aria-expanded="false" aria-controls="collapseTwo">
<!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">A: Brutality</p>
</div>
<!-- begin body -->
<div id="collapseProblemA" class="collapse">
<div class="card-body solution-body">

### <a href="https://codeforces.com/problemset/problem/1107/C" target="_blank">Brutality</a>

The optimal strategy is to take equal consecutive elements and take
the $k$ highest values. We can implement this idea with two
pointers and sorting in $O(n \log n)$.

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemA" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemA" class="collapse">

```c++
#include <bits/stdc++.h>

#define all(X) begin(X), end(X)

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  ll n, k;
  cin >> n >> k;
  vector <ll> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  string s;
  cin >> s;
  ll ans = 0;
  for (int i = 0; i < n;) {
    vector <ll> tmp;
    tmp.push_back(a[i]);
    int j = i + 1;
    while (j < n and s[i] == s[j]) tmp.push_back(a[j]), j++;
    sort(rbegin(tmp), rend(tmp));
    int cnt = 0;
    for (ll elem: tmp) {
      if (cnt == k) break;
      ans += elem;
      cnt++;
    }
    i = j;
  }
  cout << ans << endl;
  return (0);
}
```

  </div>
  <!-- ends code -->

</div>
</div>
</div>
<!-- ends problem A -->





<!-- Begins problem B -->
<div class="card" id="B">
<div class="collapsed solution-title" type="button" data-toggle="collapse" data-target="#collapseProblemB" aria-expanded="false" aria-controls="collapseTwo">
<!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">B: Fox and Snake</p>
</div>
<!-- begin body -->
<div id="collapseProblemB" class="collapse">
<div class="card-body solution-body">

### <a href="https://codeforces.com/problemset/problem/510/A" target="_blank">Fox and Snake</a>

There is a pattern every four rows.

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemB" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemB" class="collapse">

```c++
#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;
     
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int r = 0; r < n; r++) {
    if (r % 4 == 0 or r % 4 == 2) {
      cout << string(m, '#') << '\n';
    } else if (r % 4 == 1) {
      cout << string(m - 1, '.') + '#' << '\n';
    } else {
      cout << '#' + string(m - 1, '.') << '\n';
    }
  }
  return (0);
}
```

  </div>
  <!-- ends code -->

</div>
</div>
</div>
<!-- ends problem B -->




<!-- Begins problem C -->
<div class="card" id="C">
<div class="collapsed solution-title" type="button" data-toggle="collapse" data-target="#collapseProblemC" aria-expanded="false" aria-controls="collapseTwo">
<!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">C: Counting Chaos</p>
</div>
<!-- begin body -->
<div id="collapseProblemC" class="collapse">
<div class="card-body solution-body">

### <a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2284" target="_blank">Counting Chaos</a>

Just try all options.

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemC" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemC" class="collapse">

```c++
#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;

bool isPalindrome (int hh, int mm) {
  int val = hh * 100 + mm;
  string s = to_string(val);
  string rs = s;
  reverse(all(rs));
  return s == rs;
}

int val (char ch) { return ch - '0'; }

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    string s;
    cin >> s;
    int hh = val(s[0]) * 10 + val(s[1]);
    int mm = val(s[3]) * 10 + val(s[4]);
    do {
      mm++;
      if (mm == 60) mm = 0, hh++;
      if (hh == 24) hh = 0;
    } while (!isPalindrome(hh, mm));
    cout << setfill('0') << setw(2) << hh << ":";
    cout << setfill('0') << setw(2) << mm << "\n";
  }
  return (0);
}
```

  </div>
  <!-- ends code -->

</div>
</div>
</div>
<!-- ends problem C -->




<!-- Begins problem D -->
<div class="card" id="D">
<div class="collapsed solution-title" type="button" data-toggle="collapse" data-target="#collapseProblemD" aria-expanded="false" aria-controls="collapseTwo">
<!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">D: Mirror, Mirror</p>
</div>
<!-- begin body -->
<div id="collapseProblemD" class="collapse">
<div class="card-body solution-body">

### <a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2284" target="_blank">Mirror, Mirror</a>

Just implement what the problem says. Be careful with the implementation.

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemD" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemD" class="collapse">

```c++
#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;

vector <string> rotate90 (const vector <string>& a) {
  int n = sz(a);
  vector <string> b = a;
  for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
      b[c][n - 1 - r] = a[r][c];
    }
  }
  return b;
}

vector <string> reflect (const vector <string>& a) {
  int n = sz(a);
  vector <string> b = a;
  for (int r = 0; 2 * r < n; r++) {
    swap(b[r], b[n - 1 - r]);
  }
  return b;
}

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc = 0;
  int n;
  while (cin >> n) {
    vector <string> a(n);
    vector <string> b(n);
    for (int r = 0; r < n; r++) cin >> a[r] >> b[r];
    cout << "Pattern " << ++tc << " was ";
    if (a == b) {
      cout << "preserved.\n";
      continue;
    }
    int rotate = 0;
    vector <string> cur = a;
    for (int i = 1; i < 4; i++) {
      cur = rotate90(cur);
      if (cur == b) {
        rotate = 90 * i;
        break;
      }
    }
    if (rotate != 0) {
      cout << "rotated " << rotate << " degrees.\n";
      continue;
    }
    rotate = 0;
    cur = reflect(a);
    if (cur == b) {
      cout << "reflected vertically.\n";
      continue;
    }
    for (int i = 1; i < 4; i++) {
      cur = rotate90(cur);
      if (cur == b) {
        rotate = 90 * i;
        break;
      }
    }
    if (rotate != 0) {
      cout << "reflected vertically and rotated " << rotate << " degrees.\n";
      continue;
    }
    cout << "improperly transformed.\n";
  }
  return (0);
}
```

  </div>
  <!-- ends code -->

</div>
</div>
</div>
<!-- ends problem D -->




<!-- Begins problem E -->
<div class="card" id="E">
<div class="collapsed solution-title" type="button" data-toggle="collapse" data-target="#collapseProblemE" aria-expanded="false" aria-controls="collapseTwo">
<!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">E: Fractal</p>
</div>
<!-- begin body -->
<div id="collapseProblemE" class="collapse">
<div class="card-body solution-body">

### <a href="http://poj.org/problem?id=2083" target="_blank">Fractal</a>

You can create a matrix filled with spaces, select a position and start doing
the recursion to store the fractal in the matrix. The choice or the initial
position and how to do the transition can be obtained by getting a pattern with the
first values of $n$.

  <!-- begin code -->
  <div class="collapsed code-title" type="button" data-toggle="collapse" data-target="#codeProblemE" aria-expanded="false" aria-controls="collapseTwo">
  <!-- title -->
  <i class="fas fa-caret-right"></i> <p class="title">Code</p>
  </div>
  <div id="codeProblemE" class="collapse">

```c++
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

vector <string> grid;
int DR[] = {-1, -1, 1, 1, 0};
int DC[] = {1, -1, 1, -1, 0};

void print () {
  for (int i = 0; i < grid.size(); i++) {
    string& row = grid[i];
    int j = row.size() - 1;
    while (row[j] == ' ') row.erase(row.begin() + j);
    cout << row << endl;
  }
  cout << '-' << endl;
}

void rec (int r, int c, int step) {
  if (step == 0) {
    grid[r][c] = 'X';
    return;
  }
  for (int d = 0; d < 5; d++) {
    rec(r + DR[d] * step, c + DC[d] * step, step / 3);
  }
}

int main () {
  int n;
  while (cin >> n, n != -1) {
    int gridSize = int(pow(3, n - 1));
    grid = vector <string> (gridSize, string(gridSize, ' '));
    int initial = (n == 1) ? 0 : gridSize / 3 + gridSize / 6; 
    int step = gridSize / 3;
    rec(initial, initial, step);
    print();
  }
  return (0);
}
```

  </div>
  <!-- ends code -->

</div>
</div>
</div>
<!-- ends problem E -->

<p style="float: none; clear: both;"></p>

<div style="float: right;" class="pt-3">
  <a class="continue-link" href="./class-07.html" 
     data-toggle="tooltip" title="Complete Search IV">
  Next
  </a>
</div>

<div class="pt-3">
  <a class="continue-link" href="./class-05.html"
     data-toggle="tooltip" title="Complete Search II">
  Previous
  </a>
</div>

<script>
  $('#all-classes').collapse('show');
  $('#class-06').addClass('active');
  const cur_class = document.getElementById('class-06');
  cur_class.scrollIntoView({
    behavior: 'smooth',
    block: 'center'
  });
</script>