Editorial of Dytechlab Cup 2022
Difference between en7 and en8, changed 2,511 character(s)
> It has been a wild ride the final 24 hours in the preparation of this contest! And we really hope you liked the problemset we gave today!↵

## [problem:1737A]↵
Author: [user:low_,2022-10-07]↵

<spoiler summary="Tutorial">↵
[tutorial:1737A]↵
</spoiler>↵

<spoiler summary="Solution 
(snippet ( low_ C++)">↵

~~~~~↵
...↵
void execute(int test_number)↵
{↵
  cin>>n>>k>>str;↵
  vector <int> count_char(26, 0);↵
  for (char c: str) count_char[c - 'a']++;↵
  string ans = "";↵
  for (int i = 0; i < min(25, n/k); i++) {↵
    while (k - ans.size() > count_char[i]) {↵
      ans.push_back(i + 'a');↵
    }↵
  }↵

  char c = 'a' + min(n / k, 25);↵
  while (k > ans.size()) {↵
    ans += c;↵
  }↵
  reverse(ans.begin(), ans.end());↵
  cout << ans << "\n";↵
}↵
...↵
~~~~~↵

</spoiler>↵

## [problem:1737B]↵

Author: [user:low_,2022-10-07]↵

<spoiler summary="Tutorial">↵
[tutorial:1737B]↵
</spoiler>↵

<spoiler summary="Solution 
(snippet (low_, C++)">↵

~~~~~↵
...↵
ll l, r;↵

ll bs_sqrt(ll x) {↵
  ll left = 0, right = 2000000123;↵
  while (right > left) {↵
      ll mid = (left + right) / 2;↵
      ↵
      if (mid * mid > x) right = mid;↵
      else left = mid + 1;↵
  }↵
  return left - 1;↵
}↵

// main solution goes here:↵
void execute(int test_number)↵
{↵
  cin >> l >> r;↵
  ll sql = bs_sqrt(l), sqr = bs_sqrt(r);↵
  ll ans;↵
  if (sql == sqr) {↵
    ans = 0;↵
    for (int i = 0; i < 3; i++) {↵
      if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++;↵
    }↵
  } else {↵
    ans = (sqr - sql - 1) * 3;↵
    for (int i = 0; i < 3; i++) {↵
      if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++;↵
      if (l <= sqr * (sqr + i) && sqr * (sqr + i) <= r) ans++;↵
    }↵
  }↵
  cout << ans << "\n";↵
}↵
...↵
~~~~~↵


</spoiler>↵


## [problem:1737C]↵

Author: [user:low_,2022-10-07]↵

<spoiler summary="Tutorial">↵
[tutorial:1737C]↵
</spoiler>↵

<spoiler summary="Solution 
(snippet (low_, C++)">↵

~~~~~↵
...↵
int n;↵
int x[3], y[3];↵
int u, v;↵

pii centralSquare() {↵
  int a = (x[0] == x[1]) ? x[0] : x[2];↵
  int b = (y[0] == y[1]) ? y[0] : y[2];↵
  return {a, b};↵
}↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
  cin>>n;↵
  for (int i=0; i<3; i++) cin>>x[i]>>y[i];↵
  cin>>u>>v;↵

  int cx = centralSquare().first, cy = centralSquare().second;↵

  if ((cx == 1 || cx == n) && (cy == 1 || cy == n)) { // "corner" case, literally↵
    // the crickets can only reach coordinates within the edges that already contains at least 2 crickets,↵
    // which contains the centralSquare of the L↵
    cout << ((u == cx || v == cy) ? "YES\n" : "NO\n");↵
  } else {↵
    if ((cx + cy) % 2 == (u + v) % 2) {↵
      cout << (cx % 2 == u % 2 ? "YES\n" : "NO\n"); ↵
    } else { // can be prove to always reach, since we have ways to align 2 crickets in the same diagonal as target↵
      cout << "YES\n"; ↵
    }↵
  }↵
}↵
...↵
~~~~~↵


</spoiler>↵

## [problem:1737D]↵

Author: [user:low_,2022-10-07]↵

<spoiler summary="Tutorial">↵
[tutorial:1737D]↵
</spoiler>↵

<spoiler summary="Solution (
magnified, C++)">↵

~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵
#define db long double↵
#define ull unsigned long long↵
#define x first↵
#define y second↵
#define mp make_pair↵
#define pb push_back↵
#define all(a) a.begin(), a.end()↵

using namespace std;↵

#define pper(a) cerr << #a << " = " << a << endl;↵

void per() { cerr << endl; }↵
template<typename Head, typename... Tail> void per(Head H, Tail... T) { cerr << H << ' '; per(T...); }↵

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }↵
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }↵

template<class U, class V> ↵
ostream& operator<<(ostream& out, const pair<U, V>& a) {↵
  return out << "(" << a.x << ", " << a.y << ")";↵
}↵

template<class U, class V> ↵
istream& operator>>(istream& in, pair<U, V>& a) {↵
  return in >> a.x >> a.y;↵
}↵

template<typename W, typename T = typename enable_if<!is_same<W, string>::value, typename W::value_type>::type>↵
ostream& operator<<(ostream& out, const W& v) { out << "{ "; for (const auto& x : v) out << x << ", "; return out << '}'; }↵

template<class T>↵
void readArr(T from, T to) {↵
  for (auto i = from; i != to; ++i) cin >> *i;↵
}↵

mt19937 mrand(1337); ↵
unsigned int myRand32() {↵
  return mrand() & (unsigned int)(-1);↵
}↵
 ↵
unsigned ll myRand64() {↵
  return ((ull)myRand32() << 32) ^ myRand32();↵
}↵

const int mod = 1000000007;↵

void add(int& a, int b) {↵
  a += b; if (a >= mod) a -= mod;↵
}↵

void dec(int &a, int b) {↵
  a -= b; if (a < 0) a += mod;↵
}↵

int mult(int a, int b) {↵
  return a * (ll)b % mod;↵
}↵

int bp(int a, int b) {↵
  int res = 1;↵
  while (b > 0) {↵
    if (b & 1) res = mult(res, a);↵
    a = mult(a, a);↵
    b >>= 1;↵
  }↵
  return res;↵
}↵

const int N = 507;↵

ll f[N][N];↵

int main(){↵
#ifdef LOCAL↵
freopen("N_input.txt", "r", stdin);↵
//freopen("N_output.txt", "w", stdout);↵
#endif↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵

  int t;↵
  cin >> t;↵

  for (int a = 0; a < t; ++a) {↵

    int n, m;↵
    cin >> n >> m;↵

    for (int i = 0; i < n; ++i) {↵
      for (int j = 0; j < n; ++j) {↵
        f[i][j] = 1e18;↵
      }↵
      f[i][i] = 0;↵
    }↵

    vector<tuple<int, int, int> > ed;↵

    for (int i = 0; i < m; ++i) {↵
      int u, v, w;↵
      cin >> u >> v >> w;↵
      ed.pb(make_tuple(u - 1, v - 1, w));↵
      f[u - 1][v - 1] = 1;↵
      f[v - 1][u - 1] = 1;↵
    }↵

    for (int k = 0; k < n; ++k) {↵
      for (int i = 0; i < n; ++i) {↵
        for (int j = 0; j < n; ++j) {↵
          f[i][j] = min(f[i][j], f[i][k] + f[k][j]);↵
        }↵
      }↵
    }↵

    ll ans = 1e18;↵
    for (auto x : ed) {↵
      int u = get<0>(x);↵
      int v = get<1>(x);↵
      int w = get<2>(x);↵

//      per(ans, u, v, w);↵

      ans = min(ans, (ll) w * (f[0][u] + f[n - 1][v] + 1));↵
      ans = min(ans, (ll) w * (f[0][v] + f[n - 1][u] + 1));↵

  //    per(ans, u, v, w);↵

      for (int i = 0; i < n; ++i) {↵
        ans = min(ans, (ll) w * (f[v][i] + 1 + f[i][0] + f[i][n-1] + 1));↵
        ans = min(ans, (ll) w * (f[u][i] + 1 + f[i][0] + f[i][n-1] + 1));↵
      }↵

    }↵

    cout << ans << '\n';↵

  }↵
}↵
~~~~~↵
</spoiler>↵

## [problem:1737E]↵

Author: [user:ngfam_kongu,2022-10-07]↵

<spoiler summary="Tutorial">↵
[tutorial:1737E]↵
</spoiler>↵

<spoiler summary="Solution 
(C++)">↵

~~~~~↵
#include<iostream>↵
#include<fstream>↵
#include<cstdio>↵
#include<algorithm>↵
#include<cmath>↵
#include<vector>↵
#include<deque>↵
#include<set>↵
#include<map>↵
#include<bitset>↵
#include<ctime>↵
#include<queue>↵
using namespace std;↵
#define ll long long↵
#define pii pair <ll, ll>↵
#define ld long double↵
#define XX first↵
#define YY second↵
#define mattype ll↵
#define matrix vector <vector <mattype> >↵
 ↵
// constants:↵
const int mn = 1000005;↵
const int mod = 1000000007;↵
const long long inf = 4444444444444444444;↵
const int sminf = 1111111111;↵
const bool is_multitest = 1;↵
const bool is_interactive = 0;↵
 ↵
// i/o methods:↵
const bool input_from_file = 0;↵
const bool output_to_file = 0;↵
#define filename ""↵
#define in_extension "inp"↵
#define out_extension "out"↵
 ↵
// debug functions↵
void debug_vector(string name, vector <ll> v) {↵
  cerr << name << " @size=" << v.size() << ": [";↵
  for (int x: v) cerr << x << " ";↵
  cerr << "]\n";↵
}↵
 ↵
void debug_2d_vector(string name, vector <vector<ll> > v) {↵
 ↵
  cerr << name << " @size=" << v.size() << ": {\n";↵
  for (int i = 0; i < v.size(); i++) {↵
    cerr << "\t";↵
    debug_vector(name + "[" + to_string(i) + "]", v[i]);↵
  }↵
  cerr << "}\n";↵
}↵
 ↵
// data preprocessing: (e.g.: divisor generating, prime sieve)↵
ll POW2[mn];↵
void preprocess()↵
{↵
  POW2[0] = 1;↵
  for (int i = 1; i < mn; i++) POW2[i] = POW2[i &mdash; 1] * 2 % mod;↵
}↵
 ↵
// global variables:↵
ll n;↵
 ↵
ll POW(ll u, ll v) {↵
  if (v == 0) return 1;↵
  ll mid = POW(u, v / 2);↵
  mid = (mid * mid) % mod;↵
  return (v & 1) ? (mid * u % mod) : mid;↵
}↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
  cin>>n;↵
 ↵
  if (n == 1) {↵
    cout << "1\n";↵
    return;↵
  }↵
  vector <ll> ans(n + 1, 0), sufsum(n + 1, 0);↵
  sufsum[n] = ans[n] = POW(POW2[(n &mdash; 1) / 2], mod &mdash; 2);↵
  for (int i = n &mdash; 1; i > 1; i--) {↵
    ans[i] = POW(POW2[(i + 1) / 2], mod &mdash; 2);↵
    if (2 * i <= n) ans[i] = ans[i] * (1 &mdash; sufsum[i * 2] + mod) % mod;↵
    sufsum[i] = (sufsum[i + 1] + ans[i]) % mod;↵
  }↵
  for (int i = 1; i <= n; i++) cout << ans[i] << "\n";↵
 ↵
}↵
// REMEMBER TO CHOOSE TEST METHODS↵
// PLEASE REMOVE cout AND cerr DEBUG LINES BEFORE SUBMITTING PROBLEMS↵
// Solution by low_↵

signed main()↵
{↵
#ifdef lowie↵
    if (!is_interactive)↵
    {↵
        freopen("test.inp", "r", stdin);↵
        freopen("test.out", "w", stdout);↵
    }↵
#else↵
    if (input_from_file) freopen(filename"."in_extension, "r", stdin);↵
    if (output_to_file) freopen(filename"."out_extension, "w", stdout);↵
#endif↵
    if (!is_interactive)↵
    {↵
        ios_base::sync_with_stdio(0);↵
        cin.tie(0);↵
        cout.tie(0);↵
    }↵
 ↵
    preprocess();↵
    int ntest;↵
    if (is_multitest) cin >> ntest;↵
    else ntest = 1;↵
 ↵
    for (int testno = 1; testno <= ntest; testno++)↵
    // use for instead of while to serve facebook hacker cup test format↵
    {↵
        execute(testno); // only start coding in this function, not in main↵
    }↵
}↵
// Template by low_↵
// Contact me via mail: [email protected]
// ...or codeforces: www.codeforces.com/profiles/low_↵
// ...or if you're interested in food: www.instagram.com/lowie.exe/↵
snippet (low_, C++)">↵

~~~~~↵
...↵
// data preprocessing: (e.g.: divisor generating, prime sieve)↵
ll POW2[mn];↵
void preprocess()↵
{↵
  POW2[0] = 1;↵
  for (int i = 1; i < mn; i++) POW2[i] = POW2[i &mdash; 1] * 2 % mod;↵
}↵
 ↵
// global variables:↵
ll n;↵
 ↵
ll POW(ll u, ll v) {↵
  if (v == 0) return 1;↵
  ll mid = POW(u, v / 2);↵
  mid = (mid * mid) % mod;↵
  return (v & 1) ? (mid * u % mod) : mid;↵
}↵
// main solution goes here:↵
void execute(int test_number)↵
{↵
  cin>>n;↵
 ↵
  if (n == 1) {↵
    cout << "1\n";↵
    return;↵
  }↵
  vector <ll> ans(n + 1, 0), sufsum(n + 1, 0);↵
  sufsum[n] = ans[n] = POW(POW2[(n &mdash; 1) / 2], mod &mdash; 2);↵
  for (int i = n &mdash; 1; i > 1; i--) {↵
    ans[i] = POW(POW2[(i + 1) / 2], mod &mdash; 2);↵
    if (2 * i <= n) ans[i] = ans[i] * (1 &mdash; sufsum[i * 2] + mod) % mod;↵
    sufsum[i] = (sufsum[i + 1] + ans[i]) % mod;↵
  }↵
  for (int i = 1; i <= n; i++) cout << ans[i] << "\n";↵
 ↵
}↵
...

~~~~~↵
</spoiler>↵

## [problem:1737F]↵

Author: [user:351F44,2022-10-07]↵

<spoiler summary="Tutorial">↵
Observation: Assume that x is composite number and divisor of n. Among all the multiples of x, the number of the divisor of n must be less than or equal to m/2.↵

First, factorize n. Assume that w is divisor of n. If w is in the form of a^4, a^3b^2, or a^2b^2c^2, it can be proved that there is no answer. Otherwise, there can be two cases.↵

If the possible maximum exponent of prime factor is 2, place the divisors like this: 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a. And expand the sequence as follows:↵

1. Repeat the current sequence twice &mdash; 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a 1 a^2 a.↵
2. Multiply the odd-indexed elements of first half and the even-indexed elements of second half by the new prime factor. Index 1 is exception &mdash; 1 a^2b^2 bc a^2b b^2c ab a^2c ab^2 ac c a^2b^2c b a^2bc b^2 abc a^2 ab^2c a / 1 a^2 ab b a^2b a.↵
3. If more prime factor exists, jump to "Otherwise".↵

Otherwise, place the divisors like this: 1 a^3 a a^2 / 1 a. Now the exponents of other prime factors are all 1, and we can expand the sequence as follows: ↵

1. Repeat the current sequence twice &mdash; 1 a^3 a a^2 1 a^3 a a^2 / 1 a 1 a.↵
2. Multiply the even-indexed elements of first half and the odd-indexed elements of second half by the new prime factor &mdash; 1 a^3b a a^2b b a^3 ab a^2 / 1 ab b a.↵
3-1. If the maximum exponent is 3, swap a and b &mdash;  1 a^3b b a^2b a a^3 ab a^2↵
3-2. Otherwise, swap b and ab &mdash; 1 b ab a.↵

Like this, we can expand the sequence↵
</spoiler>↵

<spoiler summary="Solution (C++)">↵
~~~~~↵
#import<bits/stdc++.h>↵
#define endl '\n'↵
using namespace std;↵

int m, t, b[18], check[18], cnt[5];↵
vector<int>v;↵
vector<vector<int>>a;↵

void initialize(int m)↵
{↵
fill(b, b + m + 1, 0);↵
fill(check, check + m + 1, 0);↵
fill(cnt, cnt + 5, 0);↵
v.clear();↵
a.clear();↵
}↵
void insert1(int p1, int c1)↵
{↵
v[p1] = c1;↵
a.push_back(v);↵
}↵
void insert2(int p1, int p2, int c1, int c2)↵
{↵
v[p1] = c1;↵
v[p2] = c2;↵
a.push_back(v);↵
}↵

void f1(int x)↵
{↵
int n = a.size();↵
for(int i = 0; i < n; i++)a.push_back(a[i]);↵
for(int i = 0; i < n; i += 2)↵
{↵
a[i + 1][x] = 1;↵
a[i + n][x] = 1;↵
}↵
swap(a[n / 2], a[n]);↵
}↵
void f2(int x)↵
{↵
int n = a.size();↵
for(int i = 0; i < n; i++)a.push_back(a[i]);↵
for(int i = 1; i < n; i += 2)↵
{↵
a[i + 1][x] = 1;↵
a[i + n][x] = 1;↵
}↵
a[n][x] = 1;↵
}↵
void f3(int x)↵
{↵
int n = a.size();↵
for(int i = 0; i < n; i++)a.push_back(a[i]);↵
for(int i = 0; i < n; i += 2)↵
{↵
a[i + 1][x] = 1;↵
a[i + n][x] = 1;↵
}↵
swap(a[n], a[2 * n &mdash; 1]);↵
}↵

int main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
for(cin >> t; t--;)↵
{↵
cin >> m;↵
for(int i = 1; i <= m; i++)↵
{↵
cin >> b[i];↵
cnt[min(b[i], 4)]++;↵
}↵
if(cnt[4] || cnt[3] >= 2 || cnt[3] && cnt[2] || cnt[2] >= 3)↵
{↵
cout << -1 << endl;↵
initialize(m);↵
continue;↵
}↵

for(int i = 1; i <= m; i++)v.push_back(0);↵
a.push_back(v);↵

if(cnt[2])↵
{↵
int p1 = -1, p2 = -1;↵
for(int i = 1; i <= m; i++)↵
{↵
if(b[i] == 2)↵
{↵
if(~p1)p2 = i - 1;↵
else p1 = i - 1;↵
}↵
}↵
if(~p2)↵
{↵
insert2(p1, p2, 2, 2);↵
insert2(p1, p2, 0, 1);↵
insert2(p1, p2, 2, 1);↵
insert2(p1, p2, 0, 2);↵
insert2(p1, p2, 1, 1);↵
insert2(p1, p2, 2, 0);↵
insert2(p1, p2, 1, 2);↵
insert2(p1, p2, 1, 0);↵
check[p1 + 1] = check[p2 + 1] = 1;↵
}↵
else↵
{↵
insert1(p1, 2);↵
insert1(p1, 1);↵
check[p1 + 1] = 1;↵
}↵
for(int i = 1; i <= m; i++)↵
{↵
if(check[i])continue;↵
if(a.size() % 2)f2(i - 1);↵
else f3(i - 1);↵
}↵
}↵
else↵
{↵
if(cnt[3])↵
{↵
int p = 0;↵
for(int i = 1; i <= m; i++)↵
{↵
if(b[i] == 3)p = i - 1;↵
}↵
insert1(p, 3);↵
insert1(p, 1);↵
insert1(p, 2);↵
check[p + 1] = 1;↵
}↵
else↵
{↵
insert1(0, 1);↵
check[1] = 1;↵
}↵
for(int i = 1; i <= m; i++)↵
{↵
if(!check[i])f1(i - 1);↵
}↵
}↵

for(auto &v: a)↵
{↵
if(*max_element(v.begin(), v.end()))↵
{↵
for(auto &p: v)cout << p << ' ';↵
cout << endl;↵
}↵
}↵
initialize(m);↵
}↵
}↵
~~~~~↵
</spoiler>↵

## [problem:1737G]↵

Author: [user:magnified,2022-10-07]↵

<spoiler summary="Tutorial">↵
[tutorial:1737G]↵
</spoiler>↵

<spoiler summary="Solution (C++)">↵
[submission:175031734]↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English magnified 2022-10-08 04:03:04 0 (published)
en9 English magnified 2022-10-08 04:02:09 8 Tiny change: 'ssion:175031734]\n</spoil' -> 'ssion:175061586]\n</spoil' (saved to drafts)
en8 English low_ 2022-10-07 22:09:11 2511 Tiny change: '"Solution (low_, C+' -> '"Solution snippet (low_, C+'
en7 English low_ 2022-10-07 21:59:52 0 (published)
en6 English magnified 2022-10-07 21:28:26 14
en5 English magnified 2022-10-07 21:28:04 33
en4 English magnified 2022-10-07 21:27:03 66
en3 English magnified 2022-10-07 21:25:26 11181
en2 English magnified 2022-10-07 20:28:00 3444
en1 English magnified 2022-10-03 06:14:08 34 Initial revision (saved to drafts)