# PROBLEM LINK:

Author: Shahjalal Shohag

Tester: Ildar Gainullin

Editorialist: Rajarshi Basu

# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Adhoc, Observation

# PROBLEM:

You are given an integer D. You have to find a string S such that the following conditions are satisfied:

- S is non-empty and its length does not exceed 7 \cdot D.
- S contains only lowercase English letters.
- The number of distinct substrings in S minus the number of palindromic substrings in S equals D. Here, when counting palindromic substrings, a substring that occurs multiple times should be counted multiple times.

It can be proved that a solution always exists under the given constraints.

#### Constraints

- 1 \le T \le 100
- 1 \le D \le 10^4
- the sum of D over all test cases does not exceed 10^5

# EXPLANATION:

This is an adhoc constructive problem with multiple possible solutions. I will mention two of them but feel free to mention your own approaches in the comments:

### Approach 1:

- aaaaabbbbb, which is basically D a’s and the D b’s. Here,

- number of distinct substrings is D\times D + D + D.
- number of palindromic substrings is \frac{D \times (D+1)}{2} + \frac{D \times (D+1)}{2}
- Therefore, excess distinct substrings is exactly D as needed.

### Approach 2:

- aaaaabaaaaa, which is basically D a’s then a b and then D a’s again. Try to do the calculations yourself this time

## How I came up with a solution - By Setter

Say we have a string S with length n which doesn’t contain ‘b’. If we append a new letter ‘b’ to S then the difference will be increased by n(number of new distinct substrings( = n + 1) - number of new palindromic substrings (= 1)) . If we append it again, this time it will be increased by (n - 1). So the pattern is like +n, +(n-1), +(n-2), .... +2, +1 (increase in difference is always decreased by 1) after appending it n times.

Initially, the length of S is 0. So if we append a character, let’s say ‘a’, then the pattern will be similar: 0, -1, -2, ...., -(n-2), -(n-1) after appending it n times.

So if we merge them we will have aaa...aaabbb...bbb (n times ‘a’ + n times ‘b’) and the total difference will be n.

# SOLUTION:

## Setter’s Code

```
#include<bits/stdc++.h>
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
assert(1 <= t && t <= 100);
int sum = 0;
while (t--) {
int n; cin >> n;
assert(1 <= n && n <= 10000);
sum += n;
cout << 2 * n << '\n' << string(n, 'n') + string(n, 'o') << '\n';
}
assert(1 <= sum && sum <= 100000);
return 0;
}
```

## Tester’s Code

```
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int d;
cin >> d;
cout << 2 * d + 1 << '\n';
for (int i = 0; i < d; i++) cout << 'i';
cout << 'q';
for (int i = 0; i < d; i++) cout << 'i';
cout << '\n';
}
}
```