Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

iliya_mon's blog

Mashup Contest 3 ! Div 2.5 Style!

By iliya_mon, history, 2 years ago, In English

(سلام ملت) Hello again everyone!

Me (iliya_mon) and my friend E404_Not_Found have been prepared another training round after a long time and we will be so happy if you participate in it! The contest will be held on Thursday, September 29, 2022 at 15:05 UTC+3.5 (Check the time manually in your country from the link).

Here is the link of the contest.

You will be given 7 problems and 120 minutes to solve them.

Also please see the guide of interactive problems if you are not familiar with it.

GL & HF ♥.

Full text and comments »

contest

iliya_mon
2 years ago
5

Editorial of Training Contest 2 !

By iliya_mon, history, 3 years ago, In English

Hello everyone :)

This is the editorial of the second contest of Training contests ! Here's the first training contest, And here's the second one.

Sorry for being late we were so busy these days and couldn't prepare the editorial fast :( Hope now you enjoy the editorial and please write down your opinion about the problems, Thanks :D.

A.Nolimiya loves Shahrad :

Spoiler

B.Find Pair :

Spoiler

C.Mosa and mex :

Spoiler

D.Marapestan :

Spoiler

This problem can be solved easily with dynamic programming.

The answer would always be the count of non-positive numbers in the segment $$$arr[k + 1, n]$$$ + count of the non-negative numbers in the segment $$$arr[1, k]$$$ where $$$1$$$ <= $$$k$$$ < $$$n$$$. All we have to do is to keep track of the occurrences of negative and positive integers till i'th index.

Let's denote the count of negative numbers by $$$neg[1...n]$$$ and $$$pos[1...n]$$$ for positive numbers count. So, the count of non-negative numbers in the segment $$$arr[1, i]$$$ = $$$i$$$ — $$$neg[i]$$$. Similarly, the count of non-positive numbers in the segment $$$arr[i + 1, n]$$$ = $$$n$$$ — $$$i$$$ — $$$pos[n]$$$ + $$$pos[i]$$$.

At last the answer would be min($$$n$$$ — $$$neg[i]$$$ — $$$pos[n]$$$ + $$$pos[i]$$$) for $$$1$$$ <= $$$i$$$ < $$$n$$$.

Code

/*
*   ────────────── •✵•✵• ──────────────
* |         In The Name of *Allah*       |
*   ────────────── •✵•✵• ──────────────
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <math.h>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <iomanip>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
const int maxn = 1e5 + 10;
int dp[maxn], pos[maxn], neg[maxn];
int n, t[maxn];
void solve (){
    cin >> n;
    for (int i = 1; i <= n; i ++){
      cin >> t[i];
    }
    pos[0] = 0, neg[0] = 0;
    for (int i = 1; i <= n; i ++){
      if (t[i] > 0){
        pos[i] = pos[i - 1] + 1;
        neg[i] = neg[i - 1];
      }
      else if (t[i] < 0){
        pos[i] = pos[i - 1];
        neg[i] = neg[i - 1] + 1;
      }
      else {
        pos[i] = pos[i - 1];
        neg[i] = neg[i - 1];
      }
    }
    int ans = INT_MAX;
    for (int i = 1; i < n; i ++){
      ans = min(ans, (n - neg[i] - pos[n] + pos[i]));
    }
    cout << ans;
}
int main () {
  ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tc = 1;
  freopen("input.txt","r",stdin); 
  freopen("output.txt","w",stdout);
  // cin >> tc;
  while (tc --) {
    solve();
  }
  return 0;
}
/* Thanks *Allah* */

E.AHF and alphabet :

Spoiler

Let's first think about what $$$S$$$ < $$$T$$$ can tell us: suppose $$$S$$$ $$$=$$$ $$$abcxyz$$$ and $$$T$$$ = $$$abcuv$$$. Then we know that $$$S$$$ < $$$T$$$ if and only if $$$x$$$ < $$$u$$$ by the definition.

So we can transform the conditions $$$name1$$$ < $$$name2$$$, $$$name2$$$ < $$$name3$$$ ... into the order of letters.

Then the question become: do we have a permutation that satisfy those conditions. It is actually the classic topological order question.

One trick in this task is that, if we have something like $$$xy$$$ < $$$x$$$ then there is no solution :).

Code

/*
*   ────────────── •✵•✵• ──────────────
* |         In The Name of *Allah*       |
*   ────────────── •✵•✵• ──────────────
*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()

const int maxn = 1e6 + 10;
int cnt[maxn];
string s[maxn];
vector <int> alphabet, adj[maxn];
bool mark[maxn];

bool check(bool f, int a, int b){
    return (f == 0 && a > b);
}
bool check2(){
    for (int i = 0; i < 26; i ++){
        if (!mark[i]){
            return 0;
        }
    }
    return 1;
}
void dfs(){
    for (int i = 0; i < 26; i ++){
        for (int j = 0; j < 26; j ++){
            if (!mark[j] && !cnt[j]){
                mark[j] = 1, alphabet.pb(j);
                for (auto x : adj[j]){
                    cnt[x] --;
                }
            }
        }
    }
}
void solve (){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> s[i];
    }
    for (int i = 0; i < n - 1; i++){
        bool tom = 0;
        for (int j = 0; j < min(si(s[i]), si(s[i + 1])); j++){
            if (s[i + 1][j] != s[i][j]){
                int u, v;
                u = s[i][j] - 'a', v = s[i + 1][j] - 'a';
                adj[u].pb(v), cnt[v] ++, tom = 1;
                break;
            }
        }
        if (check(tom, si(s[i]), si(s[i + 1]))){
            cout << "Impossible";
            return;
        }
    }
    dfs();
    if (!check2()){
        cerr << ":| ";
        cout << "Impossible";
        return;
    }
    for (auto x : alphabet){
        cout << char('a' + x);
    }
}

int main () {
  ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tc = 1;
  // cin >> tc;
  while (tc --) {
    solve();
  }
  return 0;
}
/* Thanks *Allah* */

F.AHF and Number of Palindromes :

Spoiler

Note: Strings and arrays are considered 0-based in the following solution.

Let $$$isPal[i][j]$$$ be 1 if $$$s[i...j]$$$ is palindrome, otherwise, set it 0. Let's define $$$dp[i][j]$$$ to be number of palindrome substrings of $$$s[i...j]$$$. Let's calculate $$$isPal[i][j]$$$ and $$$dp[i][j]$$$ in $$$O(|S|^{2})$$$. First, initialize $$$isPal[i][i]$$$ = 1 and $$$dp[i][i]$$$ = 1. After that, loop over $$$len$$$ which states length of substring and for each specific $$$len$$$, loop over start which states starting position of substring. $isPal$[start][start + len - 1] can be easily calculated by the following formula:

$$$isPal[start][start+len-1]$$$ = $$$isPal[start+1][start+len-2]$$$ & $$$(s[start] == s[start+len-1])$$$ After that, $$$dp[start][start + len - 1]$$$ can be calculated by the following formula which is derived from Inc-Exc Principle.

$$$dp[start][start+len-1]$$$ = $$$dp[start][start+len-2]$$$ + $$$dp[start+1][start+len-1]$$$ — $$$dp[start+1][start+len-2]$$$ + $$$isPal[start][start+len-1]$$$ After preprocessing, we get queries $$$li$$$ and $$$ri$$$ and output $$$dp[li - 1][ri - 1]$$$. Overall complexity is $$$O(|S|^{2})$$$.

Code

/*
*   ────────────── •✵•✵• ──────────────
* |         In The Name of *Allah*       |
*   ────────────── •✵•✵• ──────────────
*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
const int maxn = 5e3 + 10;
string s;
bool IsPal[maxn][maxn];
int Query[maxn][maxn], n, q;
void Build (){
  for (int i = 0; i < n; i ++){
    IsPal[i][i] = 1;
  }
  for (int i = n - 1; i >= 0; i --){
    for (int j = i + 1; j < n; j ++){
      IsPal[i][j] = ((s[i] == s[j]) && (j == i + 1 || IsPal[i + 1][j - 1]));
    }
  }
}
void solve (){
  cin >> s;
  n = si(s);
  Build();
  for (int i = 0; i < n; i ++){
    Query[i][i] = 1;
  }
  for (int i = n - 1; i >= 0; i --){
    for (int j = i + 1; j < n; j ++){
      Query[i][j] = Query[i + 1][j] + Query[i][j - 1] - Query[i + 1][j - 1] + IsPal[i][j];
    }
  }
  cin >> q;
  for (int i = 0; i < q; i ++){
    int l, r;
    cin >> l >> r;
    cout << Query[l - 1][r - 1] << '\n';
  }
}
int main () {
  ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tc = 1;
  // cin >> tc;
  while (tc --) {
    solve();
  }
  return 0;
}
/* Thanks *Allah* */

G.AHF's birthday gift :

Spoiler

Since $$${1, 1 ..., 1}$$$ is a pairwise coprime sequence, the maximum element of bi can never greater then $$$2mx$$$ - $$$1$$$. Here mx is the maximum elements in $$$a[i]$$$. So what we need consider is the first a few prime factors. It is not hard to use $$$bitmask-dp$$$ to solve this:

    for (int i = 1 ; i <= n ; i ++) {
      for (int k = 1 ; k < 60 ; k ++) {
        int x = (~fact[k]) & ((1 << 17) - 1);
        for (int s = x ; ; s = (s - 1) & x) {
                if (dp[i - 1][s] + abs(a[i] - k) < dp[i][s | fact[k]]){
                    dp[i][s | fact[k]] = dp[i-1][s] + abs(a[i]-k);
                }
        if (s == 0) break;
            }
      }
    }

Here $$$dp[i][s]$$$: means the first $$$i$$$ items of the sequence, and the prime factor have already existed. And $$$fact[k]$$$ ： means the prime factor set of number $$$k$$$.

Here's a complete editorial for this problem.

Code

/*
*    ────────────── •✵•✵• ──────────────
*  |         In The Name of *Allah*       |
*    ────────────── •✵•✵• ──────────────
*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
const int maxn = 1e2 + 10;
int Primes[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
int Fmask[60], dp[maxn][1 << 16], a[maxn], b[maxn][1 << 16];
void Generate_Sets () {
  for (int i = 1; i <= 58; i ++) {
    Fmask[i] = 0;
    for (int j = 0; j < 16; j ++) {
      if (i % Primes[j] == 0) {
        Fmask[i] |= (1 << j);
      }
    }
  }
}
void solve () {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i ++) {
    cin >> a[i];
  }
  Generate_Sets();
  int Max = (1 << 16) - 1;
  for (int i = 1; i <= n; i ++) {
    for (int j = 0; j < (1 << 16); j ++) {
      dp[i][j] = INT_MAX;
      for (int z = 1; z <= 58; z ++) {
        if ((j & (Fmask[z])) == Fmask[z]) {
          int kom = dp[i - 1][(j ^ Fmask[z])] + abs(a[i] - z);
          if (kom < dp[i][j]) {
            b[i][j] = z;
            dp[i][j] = kom;
          }
        }
      }
    }
  }
  vector <int> B;
  int mask = Max;
  for (int i = n; i >= 1; i --) {
    B.pb(b[i][mask]);
    mask ^= Fmask[b[i][mask]];
  }
  for (int i = n - 1; i >= 0; i --) {
    cout << B[i] << ' ';
  }
}
int main () {
  ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tc = 1;
  // cin >> tc;
  while (tc --) {
    solve();
  }
  return 0;
}
/* Thanks *Allah* */

H.AHF's gems :

Spoiler

Let's reformulate the solution to the form of dynamic programming.

$$$dp[n]$$$ — the number of ways to split the gems so that the total amount of space taken is n.

Then there are obvious transitions of either splitting the last gem or not. $$$dp[n]$$$ $$$=$$$ $$$dp[n − m]$$$ + $$$dp[n − 1]$$$.

And that can be easily rewritten in such a way that matrix exponentiation becomes the solution.

Overall complexity: $$$O(m^{3}⋅ logn)$$$.

Code

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define MOD 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define bolt ios::sync_with_stdio(0)
#define light cin.tie(0);cout.tie(0)
#define forr(i,p,n) for(ll i=p;i<n;i++)
#define MAXN 1000003
typedef long long ll;
using namespace std;
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
ll fpow(ll n, ll k, ll p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = MOD){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}

ll bin[103][103];

void mult_mat(ll m, ll ans[][100], ll bin[][100]){
    ll mult[m][m];
    forr(i,0,m){
        forr(j,0,m){
            mult[i][j]=0;
            forr(k,0,m){
                mult[i][j]+=ans[i][k]*bin[k][j];
                if(mult[i][j]>=MOD){
                    mult[i][j]%=MOD;
                }
            }
        }
    }
    forr(i,0,m){
        forr(j,0,m){
            ans[i][j]=mult[i][j];
        }
    }
}

void pow_mat(ll n, ll fin[][100], ll m){
    ll ans[m][100];
    ll b[m][100];
    forr(i,0,m){
        forr(j,0,m){
            ans[i][j]=bin[i][j];
            b[i][j]=bin[i][j];
        }
    }
    n--;
    while(n>0){
        if(n%2==1){
            mult_mat(m,ans,b);
            n--;
        }else{
            n=n/2;
            mult_mat(m,b,b);
        }
    }
    forr(i,0,m){
        forr(j,0,m){
            fin[i][j]=ans[i][j];
        }
    }
}

int main(){
    bolt;
    ll n,m;
    cin>>n>>m;
    bin[0][0]=1;
    bin[0][m-1]=1;
    for(ll i=1;i<m;i++){
        bin[i][i-1]=1;
    }
    if(n<m){
        cout<<1<<"\n";
    }else{
        ll fin[m+1][100];
        pow_mat(n-m+1,fin,m);
        ll ans=0;
        forr(i,0,m){
            ans+=fin[0][i];
            if(ans>=MOD){
                ans-=MOD;
            }
        }
        cout<<ans<<"\n";
    }
}

Full text and comments »

editorial

iliya_mon
3 years ago
1

Mashup Contest 2 ! Div3 Style!

By iliya_mon, 3 years ago, In English

Hello again everyone !

Me (iliya_mon) and my friend E404_Not_Found have been prepared another training round and we will be so happy if you participate in it ! The contest will start Tuesday, February 8, 2022 at 18:05 UTC+3.5.

Here is the link of the contest.

You will be given 8 problems and 150 minutes to solve them.

GL & HF everyone :D.

UPD1 : Congrats to the winners :

1- akifpathan

2- corrupt

3- [user : Enigma_]

UPD2 : Editorial will be published asap.

UPD2 : The link of the editorial !

Full text and comments »

mashup

iliya_mon
3 years ago
7

Editorial of Training Contest 1

By iliya_mon, history, 3 years ago, In English

Hi all ! Here's the editorial of our training contest, Some of the problems had editorial before and we put the links there, But some of them didn't and we wrote editorial for them, Hope you liked the problems and had fun :)

Magic Time :

Spoiler

AHF's Sum ! :

Spoiler

An efficient solution is while traversing the array, store sum so far in currsum. Also, maintain the count of different values of currsum in a map. If the value of currsum is equal to the desired sum at any instance increment count of subarrays by one. The value of currsum exceeds the desired sum by currsum – sum. If this value is removed from currsum then the desired sum can be obtained. From the map find the number of subarrays previously found having sum equal to currsum-sum. Excluding all those subarrays from the current subarray, gives new subarrays having the desired sum. So increase count by the number of such subarrays. Note that when currsum is equal to the desired sum then also check the number of subarrays previously having a sum equal to 0. Excluding those subarrays from the current subarray gives new subarrays having the desired sum. Increase count by the number of subarrays having sum 0 in that case.

Code

// C++ program to find number of subarrays
// with sum exactly equal to k.
#include <bits/stdc++.h>
using namespace std;

// Function to find number of subarrays
// with sum exactly equal to k.
int findSubarraySum(int arr[], int n, int sum)
{
  // STL map to store number of subarrays
  // starting from index zero having
  // particular value of sum.
  unordered_map<int, int> prevSum;

  int res = 0;

  // Sum of elements so far.
  int currsum = 0;

  for (int i = 0; i < n; i++) {

    // Add current element to sum so far.
    currsum += arr[i];

    // If currsum is equal to desired sum,
    // then a new subarray is found. So
    // increase count of subarrays.
    if (currsum == sum)
      res++;

    // currsum exceeds given sum by currsum
    // - sum. Find number of subarrays having
    // this sum and exclude those subarrays
    // from currsum by increasing count by
    // same amount.
    if (prevSum.find(currsum - sum) != prevSum.end())
      res += (prevSum[currsum - sum]);

    // Add currsum value to count of
    // different values of sum.
    prevSum[currsum]++;
  }

  return res;
}
int main()
{
  int arr[] = { 10, 2, -2, -20, 10 };
  int sum = -10;
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << findSubarraySum(arr, n, sum);
  return 0;
}

Nolimiya and Powers of two :

Spoiler

First of all, let's analyze how can we calculate the minimum number of powers of two needed to get $$$n$$$ as the sum. We can use binary representation of $$$n$$$: each bit in it, which is equal to $$$1$$$, becomes a summand in the answer.

Firstly, if the number of summands is greater than $$$k$$$ then the answer is NO. Okay, what if we don't have enough summands? Every summand $$$x$$$ $$$>$$$ $$$1$$$ can be broken down into two summands equal to $$$x / 2$$$ Let's maintain all summands greater than $$$1$$$ somewhere (stack, array, queue, multiset, anything you want), and pick an arbitrary summand and break it into two until we have exactly $$$k$$$ summands. If $$$n$$$ $$$≥$$$ $$$k$$$, then this process will terminate since we will have some summand to pick until all of them are equal to $$$1$$$.

Code

/*
*   ────────────── •✵•✵• ──────────────
* |         In The Name of Allah         |
*   ────────────── •✵•✵• ──────────────
*/
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <iomanip>
#define pb push_back
#define si(s) s.size()
#define all(a) a.begin(), a.end()
typedef long long ll;
using namespace std;
int n, k;
ll sum;
vector <int> a;
bool f = false;

// If you submit this solution with other C++ versions except C++20 you will get ACC 
// But can you tell why it will get MLE on test 1 if you submit it with C++20? 

bool check(int n, int k){
    a.clear();
    sum = k;
    for (int i = 0; i < k; i++){
        a.pb(1);
    }
    for (int i = k - 1; i >= 0; i --){
        while (sum + a[i] <= n){
            sum += a[i];
            a[i] *= 2;
        }
    }
    if (sum != n) f = false;
    else f = true;
}
void get_input() {
    cin >> n >> k;
}
void solve() {
    check(n, k);
}
void output() {
    if (f == false){
        cout << "NO";
        return;
    }
    else {
        cout << "YES" << '\n';
        for (auto x: a){
            cout << x << ' ';
        }
    }
}
int main () {
  ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t --) {
    get_input(), solve(), output();
  }
  return 0;
}
/* Thanks Allah */

AHF's Contest :

Spoiler

Because of the low constraints, this problem can be solved by complete search over all problem sets (there are $$$2^{n}$$$ of them).

For every potential problem set (which can be conviniently expressed as bit mask) we need to check if it satisfies all needed criteria. We can simply find the sum of problem complexities and also the difference between the most difficult and the easiest problems in linear time, iterating over the problems that we included in our current set/bitmask. If this problem set can be used, we increase the answer by one.

The time Complexity of the solution is $$$O(2^{n} * n)$$$.

If you don't know what's bitmask read this blog.

Bonus : Find another solution without bit mask and write it down in the comments!

Code

/*
*   ────────────── •✵•✵• ──────────────
* |         In The Name of *Allah*       |
*   ────────────── •✵•✵• ──────────────
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <math.h>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <iomanip>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
const int maxn = 20;
int a[maxn], ans, n, x, l, r;
void solve (){
  cin >> n >> l >> r >> x;
  for (int i = 0; i < n; i ++){cin >> a[i];}
  for (int i = 0; i < (1 << n); i ++){
    ll cost = 0;
    int mini = 1e9, maxi = 0, kom = 0;
    for (int j = 0; j < n; j ++){
      if (i & (1 << j)){
        ++ kom;
        mini = min(mini, a[j]), maxi = max(maxi, a[j]), cost += a[j];
      }
    }
    if (cost >= l and cost <= r and maxi - mini >= x and kom >= 2){
      ++ ans;
    }
  }
  cout << ans;
}
int main () {
  ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tc = 1;
  // cin >> tc;
  while (tc --) {
    solve();
  }
  return 0;
}
/* Thanks *Allah* */

Nolimiya's Phone Numbers :

Spoiler

Let's use map from string to vector of strings to simplify implementation. The map keys is friend names, and the values — list of phone numbers.

At first let's put all input data in map, but if vector for a current friend already contains a current number we should not put this number in the vector (for example, we can check it with help of set).

After that we need only to remove for each friend the numbers which are the suffixes of other number of that friend. The time limit allows to make it in time equals to square of phone number count for a current friend.

Now we need to iterate through map key set (it will be names of all Nolimiya's friends) and print all remaining phone numbers for each friend.

Code

/*
*    ────────────── •✵•✵• ──────────────
*  |         In The Name of *Allah*       |
*    ────────────── •✵•✵• ──────────────
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <math.h>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <iomanip>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
map <string, set <string>> a;
int n;
const int maxn = 1000;
bool mark[maxn];
bool issuf(string a, string b) {
  string kom = "";
  if (si(b) < si(a)) {
    return false;
  }
  kom = b.substr(si(b) - si(a), si(a));
  return (kom == a);
}
void RemovSufs(vector <string> kom) {
  fill(mark, mark + maxn, 0);
  for (int i = 0; i < si(kom); i ++) {
    for (int j = 0; j < si(kom); j ++) {
      if (i != j) {
        if (issuf(kom[j], kom[i])) {
          mark[j] = 1;
        }
      }
    }
  }
  vector <string> ans;
  for (int i = 0; i < si(kom); i ++) {
    if (!mark[i]) {
      ans.pb(kom[i]);
    }
  }
  cout << si(ans) << ' ';
  for (auto x : ans) {
    cout << x << ' ';
  }
}
void solve () {
  cin >> n;
  for (int i = 0; i < n; i ++) {
    string kom;
    cin >> kom;
    int m;
    cin >> m;
    for (int j = 0; j < m; j ++) {
      string x;
      cin >> x;
      a[kom].insert(x);
    }
  }
  cout << si(a) << '\n';
  for (auto x : a) {
    cout << x.first << ' ';
    vector <string> k;
    for (auto y : x.second) {
      k.pb(y);
    }
    RemovSufs(k);
    cout << '\n';
  }
}
int main () {
  ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int tc = 1;
  // cin >> tc;
  while (tc --) {
    solve();
  }
  return 0;
}
/* Thanks *Allah* */

Interactive Cows ! :

Spoiler

Good bye for now (◕ᴗ◕)

Full text and comments »

editorial

iliya_mon
3 years ago
5

Mashup Training Contest for Newbies, Pupils, Specialists !

By iliya_mon, history, 3 years ago, In English

Hello everyone !

Me (iliya_mon) and my friend E404_Not_Found have been prepared a training round and we will be so happy if you participate in it ! The contest will start Saturday, February 5, 2022 at 18:05 UTC+3.5.

You will be given 6 problems and 150 minutes to solve them and one of the problems is interactive please read the guide of interactive problems.

Here is the link of the contest.

GL & HF everyone :D.

The round is finished :) Congrats to the winners :

1- Lyde

2- suhail.loya

3- Mr.Farahmand

UPD2 : The link of the editorial.

Full text and comments »

mashup

iliya_mon
3 years ago
6