Codeforces Round #850 Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

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

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

Comments (7)

Show archived | Write comment?

no_oneplb

21 month(s) ago, # |

+11

Thanks for the editorial,waiting from a long time.

→ Reply

Satrpx

Finally an editorial! After a long week and a half.

AshutoshChoudhary

11 months ago, # |

Another approach for B

If we are shifting to left it means we are moving in negative direction If we are shifting to right it means we are moving in positive direction

We can try all possible values of shifting by binary search, and compare if we want to shift in positive and negative direction and reduce the search space on each try

https://codeforces.me/contest/1786/submission/238301378

priyamrai

5 months ago, # ^ |

← Rev. 2 →

Why is it obvious that the ith cake should be below the ith dispenser ??It maybe that a cake's last part is below start of some dispenser and another cake is below the same dispenser ?@AshutoshChoudhary

kir_tan22

6 months ago, # |

help with B please? what goes wrong here?

appreciated. 262313860

xie_lzh

7 weeks ago, # |

Did anyone notice that the binomal in the the solution of F is wrong ?

7 weeks ago, # ^ |

Sorry I'm wrong

tourist's blog