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';
}
}
