Blog entries - Codeforces

#	User	Rating
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

#	User	Contrib.
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's blog

Code Weekend #1

By tourist, 6 months ago, translation, In English

Hello everyone!

We, the RGBTeam (qwerty787788, Romka and tourist), are huge fans of heuristic programming competitions and are quite saddened by the fact that they are becoming less and less frequent each year. One day, we decided to organize our own competition :) Despite the fact that such ideas often remain just ideas, this time we have a serious mindset, and now we want to invite you all to participate in the first — and hopefully not last — Code Weekend #1!

The competition will be held in a format quite similar to ICFPC/Google Hashcode — there will be one problem and several dozen tests for it. You will need to submit just an output according to the rules of the problem for each test, which can be obtained using any algorithms, written in any language, and running for any duration of time. Midway through the competition, the problem statement will be expanded, and new tests will be added.

The competition starts on June 7th at 21:00 UTC and will last 48 hours. A day after it begins, on June 8th at 21:00 UTC, a second, expanded version of the problem along with a set of tests for it will be released. The competition ends another day after the release of the second version, on June 9th at 21:00 UTC.

The expanded version of the problem will be a superset of the basic version. For instance, if the problem is "given a chess position, find the best move," the basic version may only include pawns, bishops, and knights, while the expanded version will use rooks and queens.

The competition is team-based, and there is no limit on team size, but we've tried to balance the problem in a way that larger teams don't have a significant advantage over smaller ones. Therefore, the recommended team size is 1-4 people.

Unlike ICFPC, the focus of the competition will be on heuristic algorithms rather than functional programming (although in recent years ICFPC hasn't been focused on FP either).

Attention! The contest will be held on the website https://codeweekend.dev, you need to register there (once per team). All the announcements during the competition will be in the Discord chat, so join it via the link https://discord.gg/M6pG5zp3DF. Be sure to invite your friends, relatives, pets, and anyone else who might find it interesting :)

UPD. Our competition will be generously sponsored by the TON Foundation, for which we are immensely grateful!

As a result, the following prizes will be awarded in the competition:

1st place — 400 TON
2nd place — 300 TON
3rd place — 200 TON
4th place — 100 TON

Additional prizes:

1st place after the first day of the competition — 111 TON.
At the end of each minute of the competition, the current leader (provided there is at least one team with a positive score) receives 0.1 TON.
300 TON will be distributed equally for the best solution of each test at the end of the competition. For example, if there are 10 tests, and Team A has the best result in the first three tests while Team B has the best result in the remaining seven, Team A will receive 300/10*3 = 90 TON, and Team B will receive 300/10*7 = 210 TON.

All ties are resolved by time — the team that achieves its result earlier ranks higher.

Thus, the total prize fund for the competition is over $10,000 at the current exchange rate.

Full text and comments »

contest, heuristics

+1034

tourist
6 months ago
28

Codeforces Round #850 Editorial

By tourist, 21 month(s) ago, translation, In English

1786A2 - Alternating Deck (hard version)

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 - Cake Assembly Line

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 - Monsters (easy version)

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 - Letter Exchange

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 - Monsters (hard version)

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 - Wooden Spoon

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 - Infinite Game

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 - Minimums or Medians

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;
}

Full text and comments »

Tutorial of VK Cup 2022 - Финальный раунд (Engine)

Tutorial of Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round)

Tutorial of Codeforces Round 850 (Div. 2, based on VK Cup 2022 - Final Round)

tourist
21 month(s) ago
8

Codeforces Round #850

By tourist, 22 months ago, translation, In English

Hello!

Welcome to Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round) and Codeforces Round 850 (Div. 2, based on VK Cup 2022 - Final Round) that will start on Feb/05/2023 15:05 (Moscow time). Both rounds will be rated.

This round is a mirror of VK Cup 2022 Final — annual programming championship for Russian-speaking competitors organized by VK. VK Cup started in 2012 and has grown to be a five-track competition in competitive programming, Mobile, ML, Go, and JavaScript.

All the problems of Div. 1 round are authored and prepared by me, while KAN authored and prepared two problems for Div. 2. Thanks to errorgorn, irkstepanov, qwerty787788, Merkurev, IgorI, PavelKunyavskiy, izban, Alexdat2000, ashmelev, Akulyat, mike_live, Ekler, Kalashnikov for making this round better.

You will be given 6 problems and 3 hours to solve them.

UPD: Editorial

Congratulations to the winners:

Full text and comments »

Announcement of VK Cup 2022 - Финальный раунд (Engine)

Announcement of Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round)

Announcement of Codeforces Round 850 (Div. 2, based on VK Cup 2022 - Final Round)

+455

tourist
22 months ago
325

Codeforces Round #844 Editorial

By tourist, 22 months ago, In English

1782A - Parallel Projection

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 - Going to the Cinema

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 - Equal Frequencies

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 - Many Perfect Squares

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 - Rectangle Shrinking

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 - Bracket Insertion

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 - Diverse Coloring

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 - Window Signals (easy version)

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;
}

Full text and comments »

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

Tutorial of Codeforces Round 844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round)

+253

tourist
22 months ago
21

Codeforces Round #844 (Div. 1 + Div. 2)

By tourist, 22 months ago, translation, In English

Hello!

Welcome to the Codeforces Round 844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) that will start on Jan/15/2023 15:05 (Moscow time). It will be a combined rated round for both divisions and open to everyone.

This round is a mirror of VK Cup 2022 Elimination — annual programming championship for Russian-speaking competitors organized by VK. VK Cup started in 2012 and has grown to be a five-track competition in competitive programming, Mobile, ML, Go, and JavaScript.

All the problems are authored and prepared by me. Thanks to KAN, errorgorn, lperovskaya, dario2994, Monogon, Arpa for making this round better.

You will be given 8 problems and 3 hours to solve them.

UPD: Editorial

Congratulations to the winners:

and to maroonrk for getting the only accepted solution to problem H2.

Full text and comments »

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

Announcement of Codeforces Round 844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round)

+1287

tourist
22 months ago
462

SNWS 2022 streams

By tourist, 3 years ago, In English

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!

Full text and comments »

+243

tourist
3 years ago
7

TCO 2021 Algo Semi 2

By tourist, 3 years ago, In English

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!

Full text and comments »

tourist
3 years ago
2

TCO 2021 Algo Semi 1

By tourist, 3 years ago, In English

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!

Full text and comments »

+133

tourist
3 years ago
7

Codeforces Round #740 Editorial

By tourist, 3 years ago, In English

Hope you enjoyed the round!

Tutorial is loading...

Full text and comments »

Tutorial of Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine))

Tutorial of Codeforces Round 740 (Div. 2, based on VK Cup 2021 - Final (Engine))

Tutorial of VK Cup 2021 - Final (Engine)

+346

tourist
3 years ago
132

VK Cup 2021 — Final (Engine) and Codeforces Round #740

By tourist, 3 years ago, translation, In English

Hello again!

VK Cup 2021 - Final (Engine) starts very soon: on Aug/22/2021 15:05 (Moscow time). Today, 32 best contestants of the elimination round will be fighting for cash prizes and eternal glory.

You can follow the course of the contest and root for your favorite contestants via this link.

Everyone except for VK Cup 2021 finalists is invited to Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine)) and Codeforces Round 740 (Div. 2, based on VK Cup 2021 - Final (Engine)) that start a couple of days later: on Aug/24/2021 17:35 (Moscow time). The rounds will be rated for everyone.

All the problems were authored and prepared by me. Big thanks to everyone without whom this round would not be possible: KAN, PavelKunyavskiy, scott_wu, xiaowuc1, Monogon, Aleks5d, lperovskaya, MikeMirzayanov. Special thanks to s-quark (2nd place of the first ever VK Cup 2012!) for inspiring problem titles.

You will be given 6 problems and 2 hours 30 minutes to solve them in both divisions. It is recommended to read all the problems. Good luck!

UPD: Scoring distribution in the VK Cup finals: 500 — 1250 — 1500 — 2000 — 3000 — 3500

UPD2: Congratulations to the winners of the VK Cup 2021 Final Round!

UPD3: Division 1 round will be held on the VK Cup 2021 Finals problem set without any changes.

Scoring distribution for Div. 1: 500 — 1250 — 1500 — 2000 — 3000 — 3500

In Division 2 problems BDEF will match problems ABCD of Div. 1. Problems A and C of Div. 2 will be similar to problems F and E of Div. 1 (albeit being much easier). Besides that, problem D of Div. 2 will have a subtask with lower constraints than the original problem.

Scoring distribution for Div. 2: 500 — 1250 — 1250 — (1500 + 1000) — 2500 — 3500

As a reminder, the standings of the VK Cup Finals are available via this link — feel free to try gaining an advantage using all the information available before the round :)

UPD4: Editorial is available.

Full text and comments »

Announcement of Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine))

Announcement of Codeforces Round 740 (Div. 2, based on VK Cup 2021 - Final (Engine))

Announcement of VK Cup 2021 - Final (Engine)

+798

tourist
3 years ago
196

Codeforces Round #733 Editorial (all problems)

By tourist, 3 years ago, In English

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...

Full text and comments »

Tutorial of Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine))

Tutorial of VK Cup 2021 - Elimination (Engine)

+349

tourist
3 years ago
136

Codeforces Round #733 (Div. 1 + Div. 2)

By tourist, 3 years ago, translation, In English

Hello, Codeforces!

Welcome to the Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine)) that will start on Jul/17/2021 17:35 (Moscow time). It will be a combined rated round for both divisions.

This round is a mirror of VK Cup 2021 Elimination. VK Cup is an annual championship for Russian-speaking competitors organized by VK — a social networking service based in Saint Petersburg and the most popular website in Russia. VK Cup started in 2012 and has grown to be a four-track competition in competitive programming, ML, design, and mobile development.

All the problems were authored and prepared by me. Big thanks to everyone without whom this round would not be possible: PavelKunyavskiy, KAN, lperovskaya, ksun48, Sert, Aleks5d, MikeMirzayanov.

You will be given 8 problems and 3 hours to solve them. It is recommended to read all the problems. Good luck!

UPD: Scoring distribution: 500 — 750 — 1000 — 1500 — 2000 — 2750 — 3750 — 4750

UPD2: Congratulations to the winners!

VK Cup 2021 — Elimination (Engine):

Codeforces Round #733:

Editorial of problems A-E is out, problems F-H will appear later.

UPD3: Editorial now contains problems F-H as well.

Full text and comments »

Announcement of Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine))

Announcement of VK Cup 2021 - Elimination (Engine)

+2795

tourist
3 years ago
412

touristream 012: Codeforces Round 672 (Div. 2)

By tourist, 4 years ago, In English

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

UPD: Video on YouTube.

Full text and comments »

+175

tourist
4 years ago
17

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

By tourist, 4 years ago, In English

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!

Full text and comments »

+286

tourist
4 years ago
10

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

By tourist, 4 years ago, In English

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.

Full text and comments »

+747

tourist
4 years ago
39

XX Open Cup: GP of Gomel

By tourist, 5 years ago, In English

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.

Full text and comments »

+135

tourist
5 years ago
15

touristream 005: SNWS 2020 R5

By tourist, 5 years ago, In English

(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.

Full text and comments »

+123

tourist
5 years ago
7

touristream 004: SNWS 2020 R4

By tourist, 5 years ago, In English

(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.

Full text and comments »

+101

tourist
5 years ago
1

touristream 003: SNWS 2020 R3

By tourist, 5 years ago, In English

(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 :)

Full text and comments »

+133

tourist
5 years ago
4

touristream 002: SNWS 2020 R2

By tourist, 5 years ago, In English

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.

Full text and comments »

+226

tourist
5 years ago
8

touristream 001: SNWS 2020 R1

By tourist, 5 years ago, In English

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.

Full text and comments »

+463

tourist
5 years ago
34

AtCoder Grand Contest 041

By tourist, history, 5 years ago, In English

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!

Full text and comments »

+391

tourist
5 years ago
61

Codeforces Global Round 5 Editorial

By tourist, history, 5 years ago, In English

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;
}

Full text and comments »

Tutorial of Codeforces Global Round 5

+569

tourist
5 years ago
171

←