Editorial of Training Contest 1

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	jiangly	3578
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	tourist	3565
8	maroonrk	3531
9	Radewoosh	3521
10	Um_nik	3482

#	User	Contrib.
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
8	SecondThread	146
10	pajenegod	145

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 (◕ᴗ◕)