BOJACK - Editorial

PROBLEM LINK:

Contest

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 :wink:
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';
  }
}
22 Likes

This Q is will not let me sleep.

38 Likes

How are people able to think of such type of logic?

15 Likes

This one is gonna scare me in my dreams :cold_face: :cold_face:

13 Likes

Should I cry? After seeing the solution. Shame on myself.

14 Likes

I’m devastated.

6 Likes

what the

4 Likes

Wow, beautiful! :neutral_face:

1 Like

:frowning:

6 Likes

@rajarshi_basu

but what the heck is this SOLUTION
Can u pls explain

4 Likes

I still didn’t get how those values came?

3 Likes

I’m sad.

2 Likes

same feeling bro :frowning:

1 Like

:sob:

KIng of adhoc problems.
Whenever humanity will talk about adhoc problems this problem will be remembered.

39 Likes

He has created string of type
aaaabbbbbccccdddd where repetitions of each of ‘a’,‘b’,‘c’ and ‘d’ are calculated to fit the conditions.

can anyone explain the formula,

the logic, why is it so?

5 Likes

My solution https://www.codechef.com/viewsolution/35812640 gave wa during the contest, but the same passed later https://www.codechef.com/viewsolution/35817679
what happened?

I also checked my program for all possible values of d, it seems to be correct.

1 Like

They are identical

Checker has a problem.