Записи в блоге

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Блог пользователя tourist

Code Weekend #1

Автор tourist, 6 месяцев назад, По-русски

Всем привет!

Мы, команда RGBTeam (qwerty787788, Romka и tourist) очень любим эвристические соревнования по программированию и очень грустим из-за того, что с каждым годом их становится всё меньше и меньше. И вот, как-то однажды мы подумали, что хватит это терпеть, и решили организовать своё соревнование :) Несмотря на то, что часто такие идеи остаются лишь идеями, в этот раз мы были полны решимости довести дело до конца и сейчас хотим пригласить вас всех поучаствовать в первом и, хочется надеяться, не последнем Code Weekend #1!

Соревнование пройдёт в формате, довольно близком к ICFPC/Hashcode — будет дана одна задача и несколько десятков тестов к ней. Участникам нужно будет отправить на каждый тест наилучшее (согласно правилам задачи) решение данного теста, которое может быть получено любыми алгоритмами, написанными на любом языке и работающими любое время. В середине соревнования условие задачи будет расширено, а также добавлены новые тесты.

Соревнование начнётся 7 июня в 21:00 UTC и продлится 48 часов. Через сутки после начала, 8 июня в 21:00 UTC будет выложена вторая, расширенная версия условия вместе с набором тестов для неё. Соревнование заканчивается ещё через сутки после опубликования второй версии условия, 9 июня в 21:00 UTC. Расширенная версия условия будет надмножеством базовой версии. То есть, если предположить, что задача звучит как "дана шахматная позиция, найдите лучший ход", то в базовой версии условия могут быть только пешки, слоны и кони, а в расширенной версии появятся ладьи и ферзи.

Участие в соревновании подразумевается командное, размер команды не ограничен, но мы постарались сбалансировать задачу так, чтобы у больших команд не было сильного преимущества над маленькими командами, поэтому рекомендованный размер команды — 1-4 человека.

В отличие от ICFPC, упор в соревновании будет сделан на эвристические алгоритмы, а не на функциональное программирование (хотя в последние годы и на ICFPC не было ничего про ФП).

Внимание! Соревнование пройдет на отдельном сайте https://codeweekend.dev, на котором нужно зарегистрироваться (один раз на команду). Все объявления во время контеста будут делаться в дискорд-чате, так что вступайте в него по ссылке https://discord.gg/M6pG5zp3DF. Обязательно зовите поучаствовать друзей, подруг, друзей подруг и всех остальных, кому это может быть интересно :)

UPD. Наш контест любезно согласились проспонсировать TON Foundation, за что им огромное спасибо!

В связи с этим, в соревновании будут разыграны следующие призы.

1-е место — 400 TON
2-е место — 300 TON
3-е место — 200 TON
4-е место — 100 TON

Дополнительно:

1-е место по итогам первого дня соревнования — 111 TON
В конце каждой минуты соревнования текущий лидер (если есть хотя бы одна команда с ненулевым результатом) получает 0.1 TON.
300 TON будут распределены поровну за лучшее решение каждого теста по итогам соревнования. Например, если всего будет 10 тестов, по первым трём лучший результат будет у команды А, а по остальным семи у команды В, то команда А получит 300/10*3 = 90 TON, а команда В — 300/10*7 = 210 TON.

В случае равенства баллов выше располагается команда, набравшая свои очки ранее.

Таким образом, суммарный призовой фонд соревнования составит более $10000 по текущему курсу.

Полный текст и комментарии »

contest, heuristics

+1034

tourist
6 месяцев назад
31

Codeforces Round #850 Editorial

Автор tourist, 21 месяц назад, По-русски

1786A2 - Чередующаяся колода (сложная версия)

Problem author: KAN

Explanation

Code by KAN

NT = int(input())
 
for T in range(NT):
	n = int(input())
	answer = [0, 0, 0, 0]
	first_card = 1
	for it in range(1, 20000):
		who = 0 if it % 4 == 1 or it % 4 == 0 else 1
		cnt = it
		if n < cnt:
			cnt = n
		cnt_white = (cnt + first_card % 2) // 2
		cnt_black = cnt - cnt_white
		answer[who * 2 + 0] += cnt_white
		answer[who * 2 + 1] += cnt_black
		first_card += cnt
		n -= cnt
		if n == 0:
			break
	assert(n == 0)
	print(*answer)

1786B - Производство тортов

Problem author: KAN

Explanation

Code by KAN

#include <bits/stdc++.h>

using namespace std;

const int inf = 1000000000;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n, w, h;
    cin >> n >> w >> h;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
      cin >> b[i];
    }
    int minshift = -inf;
    int maxshift = inf;
    for (int i = 0; i < n; i++) {
      minshift = max(minshift, (b[i] + h) - (a[i] + w));
      maxshift = min(maxshift, (b[i] - h) - (a[i] - w));
    }
    if (minshift <= maxshift) {
      cout << "YES" << '\n';
    } else {
      cout << "NO" << '\n';
    }
  }
  return 0;
}

1785A - Монстры (простая версия)

Problem author: tourist

Explanation

Code by tourist

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    sort(a.begin(), a.end());
    vector<int> b(n);
    b[0] = 1;
    for (int i = 1; i < n; i++) {
      b[i] = min(b[i - 1] + 1, a[i]);
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
      ans += a[i] - b[i];
    }
    cout << ans << '\n';
  }
  return 0;
}

1785B - Обмен буквами

Problem author: tourist

Explanation

Code by PavelKunyavskiy

private fun IntArray.countOf(value: Int) = count { it == value }

private fun solve() {
    val s = "win"
    fun IntArray.bad() = (0 until 3).singleOrNull { c -> count { it == c } > 1 }
    val data = List(readInt()) { readLn().map { s.indexOf(it) }.toIntArray() }
    val ans = mutableListOf<String>()
    fun exchange(c1: Int, c2: Int, i1: Int, i2: Int) {
        ans.add("$$${i1+1} $$${s[c1]} $$${i2+1} $$${s[c2]}")
        val index1 = data[i1].indexOf(c1)
        val index2 = data[i2].indexOf(c2)
        data[i1][index1] = c2
        data[i2][index2] = c1
    }
    val todo = List(3) { List(3) { mutableListOf<Int> () } }
    for (i in data.indices) {
        val bad = data[i].bad() ?: continue
        for (j in 0 until 3) {
            if (data[i].countOf(j) == 0) {
                todo[bad][j].add(i)
            }
        }
    }

    for (i in 0 until 3) {
        for (j in 0 until 3) {
            if (i != j) {
                while (todo[i][j].isNotEmpty() && todo[j][i].isNotEmpty()) {
                    exchange(i, j, todo[i][j].removeLast(), todo[j][i].removeLast())
                }
            }
        }
    }
    while (todo[0][1].isNotEmpty() && todo[1][2].isNotEmpty() && todo[2][0].isNotEmpty()) {
        val a = todo[0][1].removeLast()
        val b = todo[1][2].removeLast()
        val c = todo[2][0].removeLast()
        exchange(0, 1, a, b)
        exchange(0, 2, b, c)
    }
    while (todo[1][0].isNotEmpty() && todo[2][1].isNotEmpty() && todo[0][2].isNotEmpty()) {
        val a = todo[1][0].removeLast()
        val b = todo[2][1].removeLast()
        val c = todo[0][2].removeLast()
        exchange(1, 0, a, c)
        exchange(2, 1, b, c)
    }
    println(ans.size)
    println(ans.joinToString("\n"))
}

fun main() {
    repeat(readInt()) {
        solve()
    }
}

private fun readLn() = readLine()!!
private fun readInt() = readLn().toInt()

1785C - Монстры (сложная версия)

Problem author: tourist

Explanation

Code by tourist

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    vector<int> mn(2 * n - 1);
    vector<int> add(2 * n - 1, 0);
    vector<int> pos(2 * n - 1);
    auto Pull = [&](int x, int z) {
      mn[x] = min(mn[x + 1], mn[z]) + add[x];
      pos[x] = (mn[x + 1] <= mn[z] ? pos[x + 1] : pos[z]);
    };
    function<void(int, int, int, int, int, int)> Modify = [&](int x, int l, int r, int ll, int rr, int v) {
      if (ll <= l && r <= rr) {
        mn[x] += v;
        add[x] += v;
        return;
      }
      int y = (l + r) >> 1;
      int z = x + 2 * (y - l + 1);
      if (ll <= y) {
        Modify(x + 1, l, y, ll, rr, v);
      }
      if (rr > y) {
        Modify(z, y + 1, r, ll, rr, v);
      }
      Pull(x, z);
    };
    function<void(int, int, int)> Build = [&](int x, int l, int r) {
      if (l == r) {
        mn[x] = l;
        pos[x] = l;
        return;
      }
      int y = (l + r) >> 1;
      int z = x + 2 * (y - l + 1);
      Build(x + 1, l, y);
      Build(z, y + 1, r);
      Pull(x, z);
    };
    Build(0, 1, n);
    long long s = 0;
    long long m = 0;
    for (int i = 0; i < n; i++) {
      s += a[i];
      m += 1;
      Modify(0, 1, n, a[i], n, -1);
      if (mn[0] < 0) {
        s -= pos[0];
        m -= 1;
        Modify(0, 1, n, pos[0], n, +1);
      }
      cout << s - m * (m + 1) / 2 << " \n"[i == n - 1];
    }
  }
  return 0;
}

1785D - Деревянная ложка

Problem author: tourist

Explanation

Code by tourist

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }

 private:
  Type value;
};

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);

Mint C(int n, int k) {
  if (k < 0 || k > n) {
    return 0;
  }
  while ((int) fact.size() < n + 1) {
    fact.push_back(fact.back() * (int) fact.size());
    inv_fact.push_back(1 / fact.back());
  }
  return fact[n] * inv_fact[k] * inv_fact[n - k];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  C(1 << n, 0);
  vector<Mint> dp(1 << n);
  dp[0] = (1 << n) * fact[1 << (n - 1)];
  for (int rd = n - 2; rd >= 0; rd--) {
    vector<Mint> new_dp(1 << n);
    Mint sum = 0;
    for (int i = 0; i < (1 << n); i++) {
      new_dp[i] = sum * C((1 << n) - 1 - i - (1 << rd), (1 << rd) - 1) * fact[1 << rd];
      sum += dp[i];
    }
    swap(dp, new_dp);
  }
  Mint sum = 0;
  for (int i = 0; i < (1 << n); i++) {
    cout << sum() << '\n';
    sum += dp[i];
  }
  return 0;
}

1785E - Бесконечная игра

Problem author: tourist

Explanation

Code by tourist

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }

  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

 private:
  Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int len = (int) s.size();
  vector<Mint> ans(3);
  for (int use = 1; use < (1 << 4); use++) {
    int pw = 1 << 8;
    int init = 0;
    for (int i = 0; i < 4; i++) {
      init += i << (2 * i);
    }
    vector<vector<int>> go_state(pw, vector<int>(2));
    vector<vector<int>> go_diff(pw, vector<int>(2));
    for (int state = 0; state < pw; state++) {
      for (int put = 0; put < 2; put++) {
        int new_diff = 0;
        int new_state = 0;
        for (int i = 0; i < 4; i++) {
          int to = (state >> (2 * i)) & 3;
          if (put == 0) {
            if (to & 1) {
              if (use & (1 << i)) {
                new_diff += 1;
              }
              to = 0;
            } else {
              to |= 1;
            }
          } else {
            if (to & 2) {
              if (use & (1 << i)) {
                new_diff -= 1;
              }
              to = 0;
            } else {
              to |= 2;
            }
          }
          new_state += to << (2 * i);
        }
        go_state[state][put] = new_state;
        go_diff[state][put] = new_diff;
      }
    }
    int limit = (len + 1) / 2 * 2 * __builtin_popcount(use);
    vector<vector<Mint>> dp(2 * limit + 1, vector<Mint>(pw));
    dp[limit][init] = 1;
    for (char c : s) {
      vector<vector<Mint>> new_dp(2 * limit + 1, vector<Mint>(pw));
      for (int sum = 0; sum < (int) dp.size(); sum++) {
        for (int state = 0; state < pw; state++) {
          if (dp[sum][state] == 0) {
            continue;
          }
          for (int put = 0; put < 2; put++) {
            if ((put == 0 && c == 'b') || (put == 1 && c == 'a')) {
              continue;
            }
            int new_sum = sum + go_diff[state][put];
            int new_state = go_state[state][put];
            new_dp[new_sum][new_state] += dp[sum][state];
          }
        }
      }
      swap(dp, new_dp);
    }
    for (int sum = 0; sum < (int) dp.size(); sum++) {
      for (int state = 0; state < pw; state++) {
        if (dp[sum][state] == 0) {
          continue;
        }
        vector<int> to(4);
        for (int i = 0; i < 4; i++) {
          to[i] = (state >> (2 * i)) & 3;
        }
        vector<int> seq(1, 0);
        while (true) {
          int nxt = to[seq.back()];
          bool done = false;
          for (int i = 0; i < (int) seq.size(); i++) {
            if (seq[i] == nxt) {
              done = true;
              seq.erase(seq.begin(), seq.begin() + i);
              break;
            }
          }
          if (done) {
            break;
          }
          seq.push_back(nxt);
        }
        int real_use = 0;
        for (int x : seq) {
          real_use |= (1 << x);
        }
        if (use == real_use) {
          ans[sum > limit ? 0 : (sum < limit ? 2 : 1)] += dp[sum][state];
        }
      }
    }
  }
  for (int i = 0; i < 3; i++) {
    cout << ans[i]() << '\n';
  }
  return 0;
}

1785F - Минимумы или медианы

Problem author: tourist

Explanation

Code by tourist, O(n^2)

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }

 private:
  Type value;
};

template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);

Mint C(int n, int k) {
  if (k < 0 || k > n) {
    return 0;
  }
  while ((int) fact.size() < n + 1) {
    fact.push_back(fact.back() * (int) fact.size());
    inv_fact.push_back(1 / fact.back());
  }
  return fact[n] * inv_fact[k] * inv_fact[n - k];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  Mint ans = 1;
  for (int p = 1; p <= k; p++) {
    for (int q = 0; q <= max(0, k - 1 - p); q++) {
      if (2 * (k - p - q) + 1 <= n - p) {
        ans += (q == 0 ? 1 : C((k - 1 - p) - (q - 1), q));
      }
    }
  }
  for (int q = 1; q <= k - 1; q++) {
    int pos = 2 * (k - q) + 2;
    int shifts = max(1, pos - n);
    int left = k - shifts;
    ans += C(left - (q - 1), q);
  }
  cout << ans() << '\n';
  return 0;
}

Code by tourist, O(n)

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }

 private:
  Type value;
};

template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);

Mint C(int n, int k) {
  if (k < 0 || k > n) {
    return 0;
  }
  while ((int) fact.size() < n + 1) {
    fact.push_back(fact.back() * (int) fact.size());
    inv_fact.push_back(1 / fact.back());
  }
  return fact[n] * inv_fact[k] * inv_fact[n - k];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  Mint ans = 1;
  for (int q = 0; q <= k - 1; q++) {
    int bound = k - q - max(1, 2 * (k - q) - n + 1);
    ans += C(bound + 1, q + 1);
  }
  for (int q = 1; q <= k - 1; q++) {
    int pos = 2 * (k - q) + 2;
    int shifts = max(1, pos - n);
    int left = k - shifts;
    ans += C(left - (q - 1), q);
  }
  cout << ans() << '\n';
  return 0;
}

Полный текст и комментарии »

Разбор задач VK Cup 2022 - Финальный раунд (Engine)

Разбор задач Codeforces Round 850 (Div. 1, основан на Финальном раунде VK Cup 2022)

Разбор задач Codeforces Round 850 (Div. 2, основан на Финальном раунде VK Cup 2022)

tourist
21 месяц назад
11

VK Cup '22/23 — Финал (Engine) и Codeforces Round #850

Автор tourist, 22 месяца назад, По-русски

Привет!

VK Cup 2022 - Финальный раунд (Engine) начнётся уже скоро: 05.02.2023 15:05 (Московское время). Это соревнование предназначено для 16 лучших участников отборочного раунда VK Cup 2022. Раунд будет рейтинговым.

Остальных приглашаем на открытые для всех Codeforces Round 850 (Div. 1, основан на Финальном раунде VK Cup 2022) и Codeforces Round 850 (Div. 2, основан на Финальном раунде VK Cup 2022), которые начнутся в то же время и тоже будут рейтинговыми.

Все задачи финального раунда придуманы и подготовлены мной, а KAN придумал и подготовил две задачи для второго дивизиона. Также этот раунд стал лучше благодаря errorgorn, irkstepanov, qwerty787788, Merkurev, IgorI, PavelKunyavskiy, izban, Alexdat2000, ashmelev, Akulyat, mike_live, Ekler, Kalashnikov.

Вам будет предложено 6 задач и 3 часа на их решение.

Участники финального раунда поборются за призы:

1-е место — 300 000 рублей;
2-е место — 250 000 рублей;
3-е место — 150 000 рублей;
4-е место — 100 000 рублей.

UPD: Присоединяйтесь к видеотрансляции финала VK Cup 2022!

UPD: Разбор

Поздравляем победителей финального раунда:

Также поздравляем победителей зеркала:

Полный текст и комментарии »

Анонс VK Cup 2022 - Финальный раунд (Engine)

Анонс Codeforces Round 850 (Div. 1, основан на Финальном раунде VK Cup 2022)

Анонс Codeforces Round 850 (Div. 2, основан на Финальном раунде VK Cup 2022)

+455

tourist
22 месяца назад
346

Codeforces Round #844 Editorial

Автор tourist, 22 месяца назад, перевод, По-русски

1782A - Ноутбук и проектор

Explanation

Source

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int w, d, h;
    cin >> w >> d >> h;
    int a, b;
    cin >> a >> b;
    int f, g;
    cin >> f >> g;
    int ans = b + abs(a - f) + g;
    ans = min(ans, a + abs(b - g) + f);
    ans = min(ans, (d - b) + abs(a - f) + (d - g));
    ans = min(ans, (w - a) + abs(b - g) + (w - f));
    cout << ans + h << '\n';
  }
  return 0;
}

1782B - Поход в кинотеатр

Explanation

Source 1

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> cnt(n + 1);
    for (int i = 0; i < n; i++) {
      int a;
      cin >> a;
      cnt[a] += 1;
    }
    int ans = 0;
    int sum = 0;
    for (int k = 0; k <= n; k++) {
      if (cnt[k] == 0 && sum == k) {
        ans += 1;
      }
      sum += cnt[k];
    }
    cout << ans << '\n';
  }
  return 0;
}

Source 2

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = 0;
    for (int k = 0; k <= n; k++) {
      if (k == 0 || a[k - 1] < k) {
        if (k == n || a[k] > k) {
          ans += 1;
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

1782C - Равные частоты

Explanation

Source

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<int>> at(26);
    for (int i = 0; i < n; i++) {
      at[(int) (s[i] - 'a')].push_back(i);
    }
    vector<int> order(26);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return at[i].size() > at[j].size();
    });
    string res = "";
    int best = -1;
    for (int cnt = 1; cnt <= 26; cnt++) {
      if (n % cnt == 0) {
        int cur = 0;
        for (int i = 0; i < cnt; i++) {
          cur += min(n / cnt, (int) at[order[i]].size());
        }
        if (cur > best) {
          best = cur;
          res = string(n, ' ');
          vector<char> extra;
          for (int it = 0; it < cnt; it++) {
            int i = order[it];
            for (int j = 0; j < n / cnt; j++) {
              if (j < (int) at[i].size()) {
                res[at[i][j]] = (char) ('a' + i);
              } else {
                extra.push_back((char) ('a' + i));
              }
            }
          }
          for (char& c : res) {
            if (c == ' ') {
              c = extra.back();
              extra.pop_back();
            }
          }
        }
      }
    }
    cout << n - best << '\n';
    cout << res << '\n';
  }
  return 0;
}

1782D - Много точных квадратов

Explanation

Source

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    int ans = 1;
    auto Test = [&](long long x) {
      int cnt = 0;
      for (int v : a) {
        long long u = llround(sqrtl(v + x));
        if (u * u == v + x) {
          cnt += 1;
        }
      }
      ans = max(ans, cnt);
    };
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        int diff = a[j] - a[i];
        for (int k = 1; k * k <= diff; k++) {
          if (diff % k == 0) {
            long long q = k + diff / k;
            if (q % 2 == 0) {
              q /= 2;
              if (q * q >= a[j]) {
                Test(q * q - a[j]);
              }
            }
          }
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

1782E - Сжатие прямоугольников

Explanation

Source

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> r1(n), c1(n), r2(n), c2(n);
    for (int i = 0; i < n; i++) {
      cin >> r1[i] >> c1[i] >> r2[i] >> c2[i];
      assert(1 <= r1[i] && r1[i] <= r2[i] && r2[i] <= 2 && c1[i] <= c2[i]);
      --c1[i];
    }
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return c1[i] < c1[j];
    });
    set<pair<int, int>> s;
    int ans = 0;
    int p1 = -1;
    int p2 = -1;
    for (int i : order) {
      if (r1[i] == 1 && r2[i] == 2) {
        if (p1 >= c2[i]) {
          r1[i] = 2;
        }
        if (p2 >= c2[i]) {
          r2[i] = 1;
        }
        if (r1[i] > r2[i]) {
          continue;
        }
      }
      if (r1[i] == 1 && r2[i] == 2) {
        while (!s.empty()) {
          auto it = prev(s.end());
          if (it->first >= c1[i]) {
            c2[it->second] = c1[i];
            s.erase(it);
          } else {
            break;
          }
        }
        ans += (c2[i] - max(c1[i], p1)) + (c2[i] - max(c1[i], p2));
        p1 = p2 = c2[i];
        s.emplace(c2[i], i);
        continue;
      }
      assert(r1[i] == r2[i]);
      if (r1[i] == 1) {
        c1[i] = max(c1[i], p1);
        p1 = max(p1, c2[i]);
      } else {
        c1[i] = max(c1[i], p2);
        p2 = max(p2, c2[i]);
      }
      if (c1[i] < c2[i]) {
        ans += c2[i] - c1[i];
        s.emplace(c2[i], i);
      }
    }
    cout << ans << '\n';
    for (int i = 0; i < n; i++) {
      ++c1[i];
      if (r1[i] <= r2[i] && c1[i] <= c2[i]) {
        cout << r1[i] << " " << c1[i] << " " << r2[i] << " " << c2[i] << '\n';
      } else {
        cout << "0 0 0 0" << '\n';
      }
    }
  }
  return 0;
}

1782F - Вставка скобок

Explanation

Source

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }

  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}

template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  Mint p;
  cin >> n >> p;
  p /= 10000;
  vector<vector<Mint>> C(n + 1, vector<Mint>(n + 1));
  for (int i = 0; i <= n; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
  }
  vector<vector<Mint>> dp(n + 1, vector<Mint>(n + 1));
  vector<vector<Mint>> aux(n + 1, vector<Mint>(n + 1));
  for (int b = 0; b <= n; b++) {
    dp[0][b] = aux[0][b] = 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int b = 0; b <= n - i; b++) {
      for (int y = 0; y <= i - 1; y++) {
        dp[i][b] += C[i - 1][y] * aux[i - 1 - y][b] * (dp[y][b + 1] * p + (b == 0 ? 0 : dp[y][b - 1] * (1 - p)));
      }
      for (int j = 0; j <= i; j++) {
        aux[i][b] += dp[j][b] * dp[i - j][b] * C[i][j];
      }
    }
  }
  auto ans = dp[n][0];
  for (int i = 1; i <= 2 * n; i += 2) {
    ans /= i;
  }
  cout << ans << '\n';
  return 0;
}

1782G - Разнообразная раскраска

Explanation

Source (2nd approach)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 1; i < n; i++) {
      cin >> p[i];
      --p[i];
    }
    for (int i = 2; i <= n; i++) {
      if (i == 4 && p[1] == 0 && p[2] == 1 && p[3] == 1) {
        cout << 2 << '\n';
      } else {
        cout << i % 2 << '\n';
      }
    }
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++) {
      g[p[i]].push_back(i);
    }
    string res = "";
    auto Solve = [&](int nn) {
      vector<vector<vector<bool>>> good(nn);
      vector<vector<vector<vector<int>>>> prevs(nn);
      vector<int> sz(nn);
      vector<int> L(nn);
      vector<int> R(nn);
      function<void(int)> Dfs = [&](int v) {
        sz[v] += 1;
        for (int u : g[v]) {
          Dfs(u);
          sz[v] += sz[u];
        }
        L[v] = sz[v] / 2;
        R[v] = L[v] + 1;
        good[v].assign(2, vector<bool>(R[v] - L[v] + 1, false));
        prevs[v].assign(2, vector<vector<int>>(R[v] - L[v] + 1));
        auto Set = [&](int c, int k, vector<int> pr) {
          if (k >= L[v] && k <= R[v]) {
            good[v][c][k - L[v]] = true;
            prevs[v][c][k - L[v]] = pr;
          }
        };
        if (g[v].size() == 0) {
          Set(0, 1, {});
        }
        if (g[v].size() == 1) {
          int u = g[v][0];
          for (int cu = 0; cu < 2; cu++) {
            for (int ku = L[u]; ku <= R[u]; ku++) {
              if (good[u][cu][ku - L[u]]) {
                Set(1, 1 + (sz[u] - ku), {cu, ku, 1});
                if (cu == 1) {
                  Set(0, 1 + ku, {cu, ku, 0});
                }
              }
            }
          }
        }
        if (g[v].size() == 2) {
          int u = g[v][0];
          int w = g[v][1];
          for (int cu = 0; cu < 2; cu++) {
            for (int ku = L[u]; ku <= R[u]; ku++) {
              if (good[u][cu][ku - L[u]]) {
                for (int cw = 0; cw < 2; cw++) {
                  for (int kw = L[w]; kw <= R[w]; kw++) {
                    if (good[w][cw][kw - L[w]]) {
                      Set(1, 1 + (sz[u] - ku) + (sz[w] - kw), {cu, ku, 1, cw, kw, 1});
                      if (cu == 1) {
                        Set(1, 1 + ku + (sz[w] - kw), {cu, ku, 0, cw, kw, 1});
                      }
                      if (cw == 1) {
                        Set(1, 1 + (sz[u] - ku) + kw, {cu, ku, 1, cw, kw, 0});
                      }
                      if (cu == 1 && cw == 1) {
                        Set(0, 1 + ku + kw, {cu, ku, 0, cw, kw, 0});
                      }
                    }
                  }
                }
              }
            }
          }
        }
      };
      Dfs(0);
      int best = nn + 1;
      int best_k = -1;
      for (int k = L[0]; k <= R[0]; k++) {
        if (good[0][1][k - L[0]]) {
          int val = abs(k - (nn - k));
          if (val < best) {
            best = val;
            best_k = k;
          }
        }
      }
      assert(best <= nn);
      res = string(nn, '.');
      function<void(int, int, int)> Restore = [&](int v, int c, int k) {
        int ptr = 0;
        for (int u : g[v]) {
          res[u] = (prevs[v][c][k - L[v]][ptr + 2] == 0 ? res[v] : (char) ('w' ^ 'b' ^ res[v]));
          Restore(u, prevs[v][c][k - L[v]][ptr], prevs[v][c][k - L[v]][ptr + 1]);
          ptr += 3;
        }
      };
      res[0] = 'w';
      Restore(0, 1, best_k);
      return best;
    };
    Solve(n);
    cout << res << '\n';
  }
  return 0;
}

1782H1 - Оконные сигналы (простая версия)

Explanation

Source for easy version

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }

  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}

template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}

template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int h, w, k;
    cin >> h >> w >> k;
    vector<Mint> fib(h * w + 1);
    fib[0] = 1;
    fib[1] = 2;
    for (int i = 2; i <= h * w; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
    }
    vector<pair<int, int>> p(k);
    for (int i = 0; i < k; i++) {
      cin >> p[i].first >> p[i].second;
      --p[i].first; --p[i].second;
    }
    long long Q = 0;
    Mint ans = 0;
    for (int ww = 1; ww <= w; ww++) {
      for (int hh = 1; hh <= h; hh++) {
        for (int top = 0; top < 2; top++) {
          for (int bottom = 0; bottom < 2; bottom++) {
            for (int left = 0; left < 2; left++) {
              for (int right = 0; right < 2; right++) {
                int sign = ((top + bottom + left + right) % 2 == 0 ? 1 : -1);
                int rh = max(0, hh - top - bottom);
                int rw = max(0, ww - left - right);
                Q += rh * rw + (h - hh) * (w - ww);
                ans += sign * power(Mint(2), rh * rw);
                vector<vector<int>> g(hh * ww);
                vector<bool> must(hh * ww, false);
                bool any = false;
                for (int i = 0; i <= h - hh; i++) {
                  for (int j = 0; j <= w - ww; j++) {
                    vector<pair<int, int>> here;
                    for (auto& c : p) {
                      if (c.first >= i + top && c.first < i + hh - bottom && c.second >= j + left && c.second < j + ww - right) {
                        here.emplace_back(c.first - i - top, c.second - j - left);
                      }
                    }
                    if (here.size() == 0) {
                      any = true;
                    }
                    if (here.size() == 1) {
                      int x = here[0].first * rw + here[0].second;
                      must[x] = true;
                    }
                    if (here.size() == 2) {
                      int x = here[0].first * rw + here[0].second;
                      int y = here[1].first * rw + here[1].second;
                      g[x].push_back(y);
                      g[y].push_back(x);
                    }
                  }
                }
                if (!any) {
                  Mint ways = 1;
                  vector<bool> was(rh * rw, false);
                  for (int i = 0; i < rh * rw; i++) {
                    if (!was[i] && g[i].empty()) {
                      was[i] = true;
                      if (!must[i]) {
                        ways *= 2;
                      }
                    }
                  }
                  for (int i = 0; i < rh * rw; i++) {
                    if (!was[i] && g[i].size() == 1) {
                      vector<bool> seq;
                      int x = i;
                      while (true) {
                        was[x] = true;
                        seq.push_back(must[x]);
                        int to = -1;
                        for (int y : g[x]) {
                          if (!was[y]) {
                            to = y;
                            break;
                          }
                        }
                        if (to == -1) {
                          break;
                        }
                        x = to;
                      }
                      int sz = (int) seq.size();
                      int beg = 0;
                      while (beg < sz) {
                        if (seq[beg]) {
                          beg += 1;
                          continue;
                        }
                        int end = beg;
                        while (end + 1 < sz && !seq[end + 1]) {
                          end += 1;
                        }
                        int len = end - beg + 1;
                        ways *= fib[len];
                        beg = end + 1;
                      }
                    }
                  }
                  assert(was == vector<bool>(rh * rw, true));
                  ans -= sign * ways;
                }
              }
            }
          }
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

Source for hard version

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }

  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}

template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}

template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

class dsu {
 public:
  vector<int> p;
  vector<int> sz;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    sz.assign(n, 1);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      sz[y] += sz[x];
      return true;
    }
    return false;
  }
};

int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    int h, w, k;
    cin >> h >> w >> k;
    vector<Mint> fib(h * w + 1);
    fib[0] = 1;
    fib[1] = 2;
    for (int i = 2; i <= h * w; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
    }
    vector<pair<int, int>> p(k);
    for (int i = 0; i < k; i++) {
      cin >> p[i].first >> p[i].second;
      --p[i].first; --p[i].second;
    }
    Mint ans = 0;
    for (int ww = 1; ww <= w; ww++) {
      for (int top = 0; top < 2; top++) {
        for (int left = 0; left < 2; left++) {
          for (int right = 0; right < 2; right++) {
            if (ww == 1 && left + right > 0) {
              continue;
            }
            int sign = ((top + left + right) % 2 == 0 ? 1 : -1);
            dsu d(h * ww);
            vector<vector<int>> g(h * ww);
            vector<bool> must(h * ww);
            bool done = false;
            Mint prod = power(Mint(2), (h - top) * (ww - left - right));
            for (int i = 0; i < h; i++) {
              for (int j = 0; j <= w - ww; j++) {
                vector<pair<int, int>> here;
                for (auto& c : p) {
                  if (c.first >= i + top && c.second >= j + left && c.second < j + ww - right) {
                    here.emplace_back(c.first - i, c.second - j);
                  }
                }
                if (here.size() == 0) {
                  ans += sign * prod;
                  done = true;
                  break;
                }
                if (here.size() == 1) {
                  int x = here[0].first * ww + here[0].second;
                  if (!must[x]) {
                    must[x] = true;
                    int px = d.get(x);
                    prod /= fib[d.sz[px]];
                    d.sz[px] -= 1;
                    int sub = 0;
                    for (int y : g[x]) {
                      if (!must[y]) {
                        sub += 1;
                      }
                    }
                    ans += sign * prod * fib[d.sz[px] - sub];
                    prod *= fib[d.sz[px]];
                  }
                }
                if (here.size() == 2) {
                  int x = here[0].first * ww + here[0].second;
                  int y = here[1].first * ww + here[1].second;
                  int px = d.get(x);
                  int py = d.get(y);
                  assert(px != py);
                  prod /= fib[d.sz[px]];
                  prod /= fib[d.sz[py]];
                  if (!must[x] && !must[y]) {
                    int subx = 1;
                    for (int t : g[x]) {
                      if (!must[t]) {
                        subx += 1;
                      }
                    }
                    int suby = 1;
                    for (int t : g[y]) {
                      if (!must[t]) {
                        suby += 1;
                      }
                    }
                    ans += sign * prod * fib[d.sz[px] - subx] * fib[d.sz[py] - suby];
                    g[x].push_back(y);
                    g[y].push_back(x);
                  }
                  d.unite(px, py);
                  prod *= fib[d.sz[py]];
                }
              }
              if (done) {
                break;
              }
              for (int j = left; j < ww - right; j++) {
                int x = (h - 1 - i) * ww + j;
                if (must[x]) {
                  done = true;
                  break;
                }
                int px = d.get(x);
                prod /= fib[d.sz[px]];
                d.sz[px] -= 1;
                prod *= fib[d.sz[px]];
                for (int y : g[x]) {
                  if (!must[y]) {
                    must[y] = true;
                    int py = d.get(y);
                    prod /= fib[d.sz[py]];
                    d.sz[py] -= 1;
                    prod *= fib[d.sz[py]];
                  }
                }
              }
              if (done) {
                break;
              }
            }
          }
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

Полный текст и комментарии »

Разбор задач VK Cup 2022 - Отборочный раунд (Engine)

Разбор задач Codeforces Round 844 (Div. 1 + Div. 2, основан на Отборочном раунде VK Cup 2022)

+253

tourist
22 месяца назад
21

VK Cup '22/23 — Отбор (Engine) и Codeforces Round #844 (Div. 1 + Div. 2)

Автор tourist, 22 месяца назад, По-русски

Привет!

VK Cup 2022 - Отборочный раунд (Engine) начнётся уже скоро: 15.01.2023 15:05 (Московское время). Это соревнование предназначено для тех, кто решил хотя бы 6 задач из 8 в квалификационном раунде VK Cup 2022. Раунд будет рейтинговым.

Остальных приглашаем на открытый для всех Codeforces Round 844 (Div. 1 + Div. 2, основан на Отборочном раунде VK Cup 2022), который начнётся в то же время и тоже будет рейтинговым.

Все задачи придуманы и подготовлены мной. Также этот раунд стал лучше благодаря KAN, errorgorn, lperovskaya, dario2994, Monogon, Arpa.

Участникам будет предложено 8 задач и 3 часа на их решение.

64 лучших участника закрытого отборочного раунда получат фирменные футболки VK Cup, а 16 лучших пройдут в финал и смогут побороться за призы 4-5 февраля очно в офисе VK или онлайн:

1-е место — 300 000 рублей;
2-е место — 250 000 рублей;
3-е место — 150 000 рублей;
4-е место — 100 000 рублей.

UPD: Разбор

Поздравляем победителей отборочного раунда:

и остальных участников, попавших в число сильнейших.

Также поздравляем победителей открытого для всех раунда:

и отдельно maroonrk как автора единственного принятого решения по задаче H2.

Полный текст и комментарии »

Анонс VK Cup 2022 - Отборочный раунд (Engine)

Анонс Codeforces Round 844 (Div. 1 + Div. 2, основан на Отборочном раунде VK Cup 2022)

+1287

tourist
22 месяца назад
501

SNWS 2022 streams

Автор tourist, 3 года назад, По-английски

Tune in at twitch.tv/the__tourist at around 22:30 MSK, 11 Jan 2022 to watch me solving SnarkNews Winter Series 2022 Round 1 live! First I will do the round competitively without much interaction, and I'll be up for discussing the problems on stream afterwards.

SnarkNews Winter/Summer Series (SNWS/SNSS) is organized by snarknews and consists of 5 rounds. Each round is a virtual 6-problem 80-minute contest open for 10 days. The series is open to all, but problem statements are in Russian only. On stream, I'll read the problem statements automatically translated to English.

To make the stream more fun and for easier understanding of what will be going on, you're welcome to do the round yourself beforehand! If you don't understand Russian, you can also compete using automatic translators. Alternatively, you may just read the problems without solving them. In any case, don't discuss the problems in Codeforces comments before the round window ends.

Tentative schedule of future streams:

Round 2 (contest link): 22:30 MSK, 16 Jan 2022
Round 3 (contest link): 22:30 MSK, 21 Jan 2022
Round 4 (contest link): 22:30 MSK, 26 Jan 2022
Round 5 (contest link): 22:30 MSK, 31 Jan 2022

I might be streaming at other times too, so be sure to follow me on Twitch to get instant notifications.

See you on stream!

Полный текст и комментарии »

+243

tourist
3 года назад
7

TCO 2021 Algo Semi 2

Автор tourist, 3 года назад, По-английски

Topcoder Open 2021 Algorithm Semifinal 2 is right around the corner, starting in less than 5 minutes!

The competitors are Benq aka bqi343, Petr, scott_wu, neal aka neal_wu, SpyCheese, maroonrk aka maroon_kuri, krijgertje, and Sugar_fan.

The top 4 advance to the Finals. The advancers from Semi 1 are ecnerwala, tourist, Um_nik, and ACRush.

Watch the live broadcast on YouTube and Twitch, featuring Pena, Egor, tourist, and ksun48!

Полный текст и комментарии »

tourist
3 года назад
2

TCO 2021 Algo Semi 1

Автор tourist, 3 года назад, По-английски

Topcoder Open 2021 Algorithm Semifinal 1 is right around the corner, starting in less than 5 minutes!

The competitors are tourist, ecnerwala aka ecnerwal, ACRush, hos.lyric aka lyrically, Um_nik, ko_osaga aka gs14004, PavelKunyavskiy aka kuniavski, and never_giveup aka grumpy_gordon.

Watch the live broadcast on YouTube and Twitch, featuring scott_wu, Petr, and krijgertje!

Полный текст и комментарии »

+133

tourist
3 года назад
7

Codeforces Round #740 Editorial

Автор tourist, 3 года назад, По-английски

Hope you enjoyed the round!

Tutorial is loading...

Полный текст и комментарии »

Разбор задач Codeforces Round 740 (Div. 1, основан на VK Cup 2021 - Финал (Engine))

Разбор задач Codeforces Round 740 (Div. 2, основан на VK Cup 2021 - Финал (Engine))

Разбор задач VK Cup 2021 - Финальный раунд (Engine)

+346

tourist
3 года назад
132

VK Cup 2021 — Финал (Engine) и Codeforces Round #740

Автор tourist, 3 года назад, По-русски

И снова привет!

VK Cup 2021 - Финальный раунд (Engine) начнётся совсем скоро: в 22.08.2021 15:05 (Московское время). В финале примут участие 32 лучших участника отборочного раунда, которые разыграют между собой солидные призы:

1-е место — 300 000 рублей;
2-е — 250 000;
3-е — 150 000;
4-е — 100 000;
5-е — 80 000;
6-е — 30 000;
и 7-е — 20 000.

Следить за ходом соревнования и болеть за любимых участников можно будет по этой ссылке. Также смотрите прямую трансляцию в сообществе Команды ВКонтакте (нет, спойлеров к задачам финала не будет).

Всех остальных, кроме финалистов VK Cup 2021, мы приглашаем на Codeforces Round 740 (Div. 1, основан на VK Cup 2021 - Финал (Engine)) и Codeforces Round 740 (Div. 2, основан на VK Cup 2021 - Финал (Engine)), которые начнутся на пару дней позже: во 24.08.2021 17:35 (Московское время). Раунды будут рейтинговыми для всех.

Все задачи были придуманы и подготовлены мной. Большое спасибо всем, без кого этот раунд не смог бы состояться: KAN, PavelKunyavskiy, scott_wu, xiaowuc1, Monogon, Aleks5d, lperovskaya, MikeMirzayanov. Отдельное спасибо s-quark (2-е место первого в истории VK Cup 2012!) за вдохновение для названий задач.

Участникам в обоих дивизионах будет предложено 6 задач и 2 часа 30 минут на их решение. Рекомендуем прочитать условия всех задач. Удачи!

UPD: Распределение баллов в финале VK Cup: 500 — 1250 — 1500 — 2000 — 3000 — 3500

UPD2: Поздравляем победителей финала VK Cup 2021!

UPD3: В первом дивизионе участникам будет предложен набор задач финала VK Cup 2021 без изменений.

Распределение баллов для первого дивизиона: 500 — 1250 — 1500 — 2000 — 3000 — 3500

Во втором дивизионе задачи BDEF будут совпадать с задачами ABCD первого дивизиона. Задачи A и C второго дивизиона будут похожи на задачи F и E первого дивизиона (но, конечно же, будут гораздо проще). Кроме того, для задачи D второго дивизиона добавлена подзадача с меньшими ограничениями, чем в оригинальной задаче.

Распределение баллов для второго дивизиона: 500 — 1250 — 1250 — (1500 + 1000) — 2500 — 3500

Напоминаю, что таблица результатов финала VK Cup доступна по этой ссылке — можете попробовать получить конкурентное преимущество, используя всю данную информацию до начала контеста :)

UPD4: Выложен разбор задач на английском языке.

Полный текст и комментарии »

Анонс Codeforces Round 740 (Div. 1, основан на VK Cup 2021 - Финал (Engine))

Анонс Codeforces Round 740 (Div. 2, основан на VK Cup 2021 - Финал (Engine))

Анонс VK Cup 2021 - Финальный раунд (Engine)

+798

tourist
3 года назад
210

Codeforces Round #733 Editorial (all problems)

Автор tourist, 3 года назад, По-английски

Hope you enjoyed the round! Editorials for all problems are out now. Also check out ecnerwala's stream where we went through individual problems and discussed the contest as a whole: https://www.youtube.com/watch?v=5Q4tGWT7p7I.

Tutorial is loading...

Полный текст и комментарии »

Разбор задач Codeforces Round 733 (Div. 1 + Div. 2, основан на VK Cup 2021 - Отбор (Engine))

Разбор задач VK Cup 2021 - Отборочный раунд (Engine)

+349

tourist
3 года назад
136

VK Cup 2021 — Отбор (Engine) и Codeforces Round #733 (Div. 1 + Div. 2)

Автор tourist, 3 года назад, По-русски

Привет, Codeforces!

VK Cup 2021 - Отборочный раунд (Engine) уже совсем скоро, не пропустите начало: 17.07.2021 17:35 (Московское время). Это соревнование предназначено для тех, кто решил хотя бы 7 задач из 8 в квалификационном раунде VK Cup 2021. Раунд будет рейтинговым для всех.

Но даже если вы не регистрировались на VK Cup 2021, добро пожаловать на объединенный Div. 1 + Div. 2 раунд Codeforces Round 733 (Div. 1 + Div. 2, основан на VK Cup 2021 - Отбор (Engine)), который начнётся в то же время. Он также будет рейтинговым и открытым для обоих дивизионов.

Все задачи были придуманы и подготовлены мной. Большое спасибо всем, без кого этот раунд не смог бы состояться: PavelKunyavskiy, KAN, lperovskaya, ksun48, Sert, Aleks5d, MikeMirzayanov.

Участникам будет предложено 8 задач и 3 часа на их решение. Рекомендуем прочитать условия всех задач. Удачи!

Среди участников закрытого отборочного раунда, 64 лучших участника получат фирменные футболки VK Cup, а топ 32 пройдут в финал и будут бороться за солидные призы:

1-е место — 300 000 рублей;
2-е — 200 000;
3-е — 100 000;
4-е — 50 000;
и 5-е — 30 000.

UPD: Распределение баллов: 500 — 750 — 1000 — 1500 — 2000 — 2750 — 3750 — 4750

UPD2: Поздравляем победителей!

VK Cup 2021 — Отборочный раунд (Engine):

Codeforces Round #733:

Выложен разбор задач A-E на английском языке.

UPD3: В разборе появились решения задач F-H на английском языке. Русскоязычная версия разбора появится позднее.

Полный текст и комментарии »

Анонс Codeforces Round 733 (Div. 1 + Div. 2, основан на VK Cup 2021 - Отбор (Engine))

Анонс VK Cup 2021 - Отборочный раунд (Engine)

+2795

tourist
3 года назад
429

Разбор квалификационного раунда VK Cup 2021

Автор tourist, 3 года назад, По-русски

Tutorial is loading...

Полный текст и комментарии »

Разбор задач VK Cup 2021 - Квалификация (Engine)

tourist
3 года назад
5

Квалификация VK Cup 2021

Автор tourist, 3 года назад, По-русски

Привет!

Квалификационный раунд VK Cup 2021 начнётся в May/24/2021 12:00 (Moscow time) и завершится 30 мая в 23:59 МСК. Задачи для раунда подготовлены мной. Он пройдёт по правилам ICPC без учёта штрафного времени и неудачных попыток — решения тестируются сразу на полном наборе тестов, а участники ранжируются по числу решённых задач. Для прохода в отборочный раунд нужно будет решить задач не меньше, чем участник на 256 месте.

Регистрация открыта до конца квалификации! Чтобы присоединиться к соревнованию, привяжите к вашему аккаунту на codeforces аккаунт ВКонтакте и заполните анкету прямо на Codeforces.

Начать соревнование Engine

Трек Engine приглашает спортивных программистов, участвовать могут все русскоязычные программисты с четырнадцати лет, без ограничений по рейтингу или количеству участий в прошлых VK Cup. Топ 64 отборочного раунда получат фирменные футболки соревнований, а 32 лучших приедут в Санкт-Петербург на финальный раунд, где поделят призовой фонд в 680 000 рублей:

1 место: 300 000 рублей
2 место: 200 000 рублей
3 место: 100 000 рублей
4 место: 50 000 рублей
5 место: 30 000 рублей

Если вам хочется попробовать свои силы в чём-то новом, то приглашаем в другие треки VK Cup: Design, Mobile и ML. Присоединяйтесь к официальному сообществу Команды ВКонтакте, чтобы быть в курсе последних новостей.

Полный текст и комментарии »

Анонс VK Cup 2021 - Квалификация (Engine)

tourist
3 года назад
19

touristream 012: Codeforces Round 672 (Div. 2)

Автор tourist, 4 года назад, По-английски

Tune in to my Twitch to watch me solve today's Codeforces Round 672 (Div. 2) virtually.

UPD: Video on YouTube.

Полный текст и комментарии »

+175

tourist
4 года назад
17

touristream 011: Codeforces Round 670 (Div. 2) + Educational 95

Автор tourist, 4 года назад, По-английски

Hey there!

During my last stream (link to YouTube), besides the expected SNSS Round 5, I did Codeforces Round 669 (Div. 2) virtually trying to explain most of my thoughts in the process. I'd say it went pretty well!

Tomorrow I'll hold another stream solving the most recent Codeforces Div. 2 rounds: Round 670 and Educational 95. I might also do today's AtCoder Beginner Contest 178.

I'm planning to go live right after Educational 95 finishes — that is, around 19:45 MSK.

A question is, given that I will do both Round 670 and Educational 95, which one should I do first? Vote here :)

As usual, the stream will be live on my Twitch, make sure to follow and get instant notifications. Stream recording will be posted to my YouTube afterwards.

See you!

Полный текст и комментарии »

+286

tourist
4 года назад
10

touristreams are back! 006: SNSS 2020 R1, and more

Автор tourist, 4 года назад, По-английски

It's this time of the year again!

Tune in at twitch.tv/the__tourist at around 21:45 MSK, 21 Aug 2020 to watch me solving SnarkNews Summer Series 2020 Round 1 live! First I will do the round competitively without much interaction, and I'll be up for discussing the problems on stream afterwards.

SnarkNews Winter/Summer Series (SNWS/SNSS) is organized by snarknews yearly and consists of 5 rounds. Each round is a virtual 6-problem 80-minute contest open for 10 days. The series is open to all, but problem statements are in Russian only. Unlike last series, I'll be reading problem statements automatically translated to English on stream.

Tentative schedule of future streams:

Round 2 (contest link): 21:45 MSK, 25 Aug 2020
Round 3 (contest link): 21:45 MSK, 5 Sep 2020
Round 4 (contest link): 21:45 MSK, 7 Sep 2020
Round 5 (contest link): 21:45 MSK, 9 Sep 2020

I might be streaming at other times too, so be sure to follow me on Twitch and get instant notifications.

See you on stream!

UPD: Round 1 stream is available on my channel: link. Round 2 stream is starting as planned, in 8 hours — be sure to join! Here is the contest link if you'd like to do the contest or read the problems beforehand.

UPD2: Round 2 stream: link. Unfortunately, Round 3 has not started yet — therefore, the next streams have to be postponed. Follow this blog and my Twitch for updates.

UPD3: New dates of Rounds 3-5 (and hence my streams) have been announced!

UPD4: Just a friendly reminder: Round 3 ends in less than 24 hours, and thus my next stream is coming tomorrow! Also note that Rounds 4 and 5 are about to end as well, there are just two days between consecutive rounds.

UPD5: Round 3 stream: link. Round 4 stream is coming in less than 4 hours from now!

UPD6: Round 4 stream: link. The last stream of the series, Round 5, is coming today in less than 3 hours!

UPD7: Round 5 stream: link (with virtual Codeforces Round 669 (Div. 2) as a practice before SNSS). This was the last stream of the series, thank you for tuning in! However, this was not the last stream of the season — check this blog post for more.

Полный текст и комментарии »

+747

tourist
4 года назад
39

XX Open Cup: GP of Gomel

Автор tourist, 5 лет назад, перевод, По-русски

XX Open Cup Grand Prix of Gomel takes place on Sunday, February 16, 2020, at 11:00 AM Petrozavodsk time.

The links to the contest:

You need an Open Cup login to participate.

I'm the writer of all the problems. Let's discuss them here after the contest!

UPD: Thanks for your participation! Editorial is available.

Полный текст и комментарии »

+135

tourist
5 лет назад
15

touristream 005: SNWS 2020 R5

Автор tourist, 5 лет назад, По-английски

(Previous episodes: Episode 001, Episode 002, Episode 003, Episode 004)

Hey there, it's time for the final stream of the series!

Tune in at twitch.tv/the__tourist at around 22:45 MSK, 06 Feb 2020 to watch me solving SnarkNews Winter Series 2020 Round 5 live! I'm going to do the round competitively without any interaction, and I'll try to explain the problems in English on stream afterwards.

As usual, I invite you to do the round yourself before I do! If you don't understand Russian, you may compete using automatic translators, or you may just read the problems beforehand without solving them. In any case, don't discuss the problems in Codeforces comments before the stream ends.

See you on stream!

UPD: Video at YouTube. This series is over now! Thanks for watching, and I hope you enjoyed the streams.

Полный текст и комментарии »

+123

tourist
5 лет назад
7

touristream 004: SNWS 2020 R4

Автор tourist, 5 лет назад, По-английски

(Previous episodes: Episode 001, Episode 002, Episode 003)

Hey there!

Tune in at twitch.tv/the__tourist at around 21:45 MSK, 28 Jan 2020 to watch me solving SnarkNews Winter Series 2020 Round 4 live! I'm going to do the round competitively without any interaction, and I'll try to explain the problems in English on stream afterwards.

See you on stream!

UPD: Video is available at YouTube.

Полный текст и комментарии »

+101

tourist
5 лет назад
1

touristream 003: SNWS 2020 R3

Автор tourist, 5 лет назад, По-английски

(Previous episodes: Episode 001, Episode 002)

Hey there!

Tune in at twitch.tv/the__tourist at around 21:45 MSK, 22 Jan 2020 to watch me solving SnarkNews Winter Series 2020 Round 3 live! I'm going to do the round competitively without any interaction, and I'll try to explain the problems in English on stream afterwards.

See you on stream!

UPD: Thanks for watching! Video is available at YouTube. My performance was remarkably bad, but hopefully that didn't make the stream less fun :)

Полный текст и комментарии »

+133

tourist
5 лет назад
4

touristream 002: SNWS 2020 R2

Автор tourist, 5 лет назад, По-английски

Episode 001

Hey there!

Tune in at twitch.tv/the__tourist at around 21:45 MSK, 17 Jan 2020 to watch me solving SnarkNews Winter Series 2020 Round 2 live! I'm going to do the round competitively without any interaction, and I'll try to explain the problems in English on stream afterwards.

Just like the last time, I invite you to do the round yourself before I do! If you don't understand Russian, you may compete using automatic translators, or you may just read the problems beforehand without solving them. In any case, don't discuss the problems in Codeforces comments before the stream ends.

See you on stream!

UPD: Video at YouTube. This time with more implementation-oriented problems and worse performance of mine, but clearer sound and more thorough explanations :) Do let me know what you think.

The next stream is planned at the end of SNWS 2020 Round 3: 21:45 MSK, 22 Jan 2020.

Полный текст и комментарии »

+226

tourist
5 лет назад
8

touristream 001: SNWS 2020 R1

Автор tourist, 5 лет назад, По-английски

Hey there!

Tune in at twitch.tv/the__tourist at around 21:45 MSK, 12 Jan 2020 to watch me solving SnarkNews Winter Series 2020 Round 1 live! First I will do the round competitively without any interaction, and I'll be up for discussing the problems on stream afterwards.

SnarkNews Winter/Summer Series (SNWS/SNSS) is organized by snarknews yearly and consists of 5 rounds. Each round is a virtual 6-problem 80-minute contest open for 10 days. The series is open to all, but problem statements are in Russian only. Nevertheless, I'm going to discuss the problems in English.

To make the stream more fun and for easier understanding of what will be going on, you're welcome to do the round yourself before I do! If you don't understand Russian, you may compete using automatic translators. Alternatively, you may just read the problems beforehand without solving them. In any case, don't discuss the problems in Codeforces comments before the stream ends.

See you on stream!

UPD: The stream is over. If everything goes well, the next stream will happen at the end of SNWS 2020 R2: 21:45 MSK, 17 Jan 2020. Do let me know whether you liked it and any other thoughts/suggestions in comments!

UPD2: The video of the stream is now available at YouTube.

Полный текст и комментарии »

+463

tourist
5 лет назад
35

AtCoder Grand Contest 041

Автор tourist, история, 5 лет назад, По-английски

We will hold AtCoder Grand Contest 041. This is the last contest of 2019 that counts for AtCoder Race Ranking.

Contest URL: https://atcoder.jp/contests/agc041
Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20191228T2100&p1=248
Duration: 150 minutes
Number of Tasks: 6
Writer: tourist
Rated range: All

The point values will be 300 — 700 — 900 — 1200 — 1600 (800 + 800) — 2000.

We are looking forward to your participation!

Полный текст и комментарии »

+391

tourist
5 лет назад
61

Codeforces Global Round 5 Editorial

Автор tourist, история, 5 лет назад, По-английски

Enjoy!

A. Balanced Rating Changes

B. Balanced Tunnel

C1. Balanced Removals (Easier)

C2. Balanced Removals (Harder)

D. Balanced Playlist

E. Balanced Binary Search Trees

F. Balanced Domino Placements

Tutorial is loading...

Solution by arsijo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 998244353;
const int MAX = 3610;
ll dp1[MAX][MAX], dp2[MAX][MAX];
int has1[MAX], has2[MAX];
ll fac[MAX], c[MAX][MAX];
int n, m, k;

void make(int n){
    dp1[0][0] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= m; j++){
            dp1[i][j] = dp1[i - 1][j];
            if (j && i >= 2 && has1[i] == 0 && has1[i - 1] == 0){
                dp1[i][j] += dp1[i - 2][j - 1];
            }
            dp1[i][j] %= MOD;
        }
    }
}

int main(){
    cin >> n >> m >> k;
    int t = max(n, m) + 1;
    vector<ll> f(t);
    for (int i = 1; i <= k; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (has1[a] || has1[c] || has2[b] || has2[d]){
            cout << 0 << endl;
            return 0;
        }
        has1[a] = has1[c] = has2[b] = has2[d] = 1;
    }
    int N = n, M = m;
    for (int i = 1; i <= n; i++){
        N -= has1[i];
    }
    for (int i = 1; i <= m; i++){
        M -= has2[i];
    }
    make(n);
    swap(dp1, dp2);
    swap(has1, has2);
    make(m);
    swap(dp1, dp2);
    swap(has1, has2);
    c[0][0] = 1;
    f[0] = 1;
    for (int i = 1; i < t; i++){
        f[i] = (f[i - 1] * i) % MOD;
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++){
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            if (c[i][j] >= MOD){
                c[i][j] -= MOD;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; (i << 1) <= N; i++){
        for (int j = 0; (j << 1) <= M; j++){
            int have1 = N - 2 * i;
            int have2 = M - 2 * j;
            ll res = dp1[n][i] * dp2[m][j];
            res %= MOD;
            res *= c[have1][j];
            res %= MOD;
            res *= c[have2][i];
            res %= MOD;
            res *= f[i];
            res %= MOD;
            res *= f[j];
            res %= MOD;
            ans += res;
        }
    }
    ans %= MOD;
    cout << ans << endl;
}

G. Balanced Distribution

Tutorial is loading...

Solution by KAN

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 200005;
const int maxk = 19;
const int inf = 1e9;

ll a[2 * maxn];
ll psum[2 * maxn];
pair2<int> go[maxk][2 * maxn];
map<ll, int> lst[maxn];
int id[2 * maxn];
int n, k;
ll need;
vector<pair<int, vector<ll>>> answer;

void perform(int l)
{
    int fn = min(l + k, n);
    assert(psum[fn] >= 0);
    ll wassum = psum[fn];
    vector<ll> exchange = vector<ll>(k, need);
    int start = min(n - k, l);
    for (int i = start; i < l; i++) exchange[i - start] = need + a[i];
    exchange[l - start] += -psum[l];
    exchange.back() += psum[fn];
    answer.pb({start, exchange});
    for (int i = l; i < fn; i++) a[i] = 0;
    a[l] += -psum[l];
    a[fn - 1] += psum[fn];
    for (int i = start; i < start + k; i++) psum[i + 1] = psum[i] + a[i];
    assert(wassum == psum[fn]);
}

void restore(int l)
{
    if (l >= n) return;
    if (a[l] == 0 && psum[l] == 0)
    {
        restore(l + 1);
        return;
    }
    int fn = min(l + k, n);
    if (psum[fn] >= 0)
    {
        perform(l);
        restore(l + k - (psum[fn] > 0));
        return;
    } else
    {
        restore(l + k - 1);
        assert(psum[fn] == 0);
        perform(l);
    }
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    need = accumulate(a, a + n, 0LL);
    assert(need % n == 0);
    need /= n;
    for (int i = 0; i < n; i++) a[i] -= need;
    for (int i = 0; i < n; i++) a[i + n] = a[i];
    partial_sum(a, a + 2 * n, psum + 1);
    pair2<int> ans = {inf, -1};
    for (int j = 0; j < maxk; j++) go[j][2 * n] = {2 * n, 0};
    for (int i = 2 * n - 1; i >= 0; i--)
    {
        int curid = id[i + 1];
        if (lst[curid].count(psum[i]))
        {
            int to = lst[curid][psum[i]];
            go[0][i] = {to, (to - i - 1) / (k - 1)};
        } else
        {
            int to = 2 * n;
            go[0][i] = {to, (to - i + k - 2) / (k - 1)};
        }
        for (int j = 1; j < maxk; j++) go[j][i] = {go[j - 1][go[j - 1][i].fi].fi, go[j - 1][i].se + go[j - 1][go[j - 1][i].fi].se};
        
        if (i < n)
        {
            int to = n + i;
            int cur = i;
            int curans = 0;
            for (int j = maxk - 1; j >= 0; j--) if (go[j][cur].fi <= to)
            {
                curans += go[j][cur].se;
                cur = go[j][cur].fi;
            }
            if (cur < to) curans += (to - cur - 1 + k - 2) / (k - 1);
            ans = min(ans, {curans, i});
        }
        
        id[i] = (2 * n - i) % (k - 1);
        lst[id[i]][psum[i]] = i;
    }
    
    rotate(a, a + ans.se, a + n);
    partial_sum(a, a + n, psum + 1);
    restore(0);
    
    assert((int)answer.size() == ans.fi);
    printf("%d\n", (int)answer.size());
    for (auto &t : answer)
    {
        printf("%d", (t.fi + ans.se) % n);
        for (auto tt : t.se) printf(" %lld", tt);
        printf("\n");
    }
    return 0;
}

H. Balanced Reversals

Tutorial is loading...

Solution by KAN

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 4005;

vector<int> ss, tt;
char s[maxn], t[maxn];
int n;
vector<int> answer;
int cnt[5];

vector<int> prepare(char *s)
{
    vector<int> ans;
    for (int i = 0; i < 2 * n; i += 2) ans.pb((s[i] - '0') * 2 + (s[i + 1] - '0'));
    return ans;
}

inline void addanswer(int x)
{
    if (x <= 0) return;
    answer.pb(x);
}

void doreverse(vector<int> &v, int l)
{
    reverse(v.begin(), v.begin() + l);
    for (int j = 0; j < l; j++) if (v[j] >= 1 && v[j] <= 2)
    {
        v[j] = 3 - v[j];
    }
}

int main()
{
    int NT;
    scanf("%d", &NT);
    for (int T = 0; T < NT; T++)
    {
        scanf("%s%s", s, t);
        n = strlen(s) / 2;
        ss = prepare(s);
        tt = prepare(t);
        for (auto &t : tt) if (t == 1 || t == 2) t = 3 - t;
        cnt[0] = cnt[1] = cnt[2] = cnt[3] = 0;
        for (auto t : ss) cnt[t]++;
        for (auto t : tt) cnt[t]--;
        if (cnt[0] != 0 || cnt[3] != 0)
        {
            printf("-1\n");
            continue;
        }
        bool found = cnt[1] == 0;
        int before = -1;
        int after = -1;
        for (int i = 1; i <= n && !found; i++)
        {
            cnt[ss[i - 1]]--;
            cnt[3 - ss[i - 1]]++;
            if (cnt[1] == 0)
            {
                before = 2 * i;
                doreverse(ss, i);
                found = true;
            }
        }
        if (!found)
        {
            for (int i = 1; i <= n; i++)
            {
                cnt[ss[i - 1]]++;
                cnt[3 - ss[i - 1]]--;
            }
        }
        for (int i = 1; i <= n && !found; i++)
        {
            cnt[tt[i - 1]]++;
            cnt[3 - tt[i - 1]]--;
            if (cnt[1] == 0)
            {
                after = 2 * i;
                doreverse(tt, i);
                found = true;
            }
        }
        assert(found);
        
        answer.clear();
        addanswer(before);
        for (int i = n - 1; i >= 0; i--)
        {
            int wh = -1;
            for (int j = n - 1 - i; j < n; j++) if (ss[j] == tt[i]) wh = j;
            addanswer(2 * wh);
            doreverse(ss, wh);
            addanswer(2 * wh + 2);
            doreverse(ss, wh + 1);
        }
        addanswer(after);
        
        for (auto t : answer) reverse(s, s + t);
        assert(strcmp(s, t) == 0);
        
        printf("%d ", (int)answer.size());
        for (auto t : answer) printf("%d ", t);
        printf("\n");
    }
    return 0;
}

Полный текст и комментарии »

Разбор задач Codeforces Global Round 5

+569

tourist
5 лет назад
172

←