awoo's blog

By awoo, history, 7 weeks ago, translation, In English

1473A - Replacing Elements

Idea: BledDest, adedalic

Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>

using namespace std;

int main() {
  int tc;
  cin >> tc;
  while (tc--) {
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    cout << (a.back() <= d || a[0] + a[1] <= d ? "YES" : "NO") << endl;
  }
}

1473B - String LCM

Idea: BledDest

Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>

using namespace std;

int main() {
  auto mul = [](string s, int k) -> string {
    string res = "";
    while (k--) res += s;
    return res;
  };
  
  int tc;
  cin >> tc;
  while (tc--) {
    string s, t;
    cin >> s >> t;
    int n = s.length(), m = t.length();
    int g = __gcd(n, m);
    if (mul(s, m / g) == mul(t, n / g))
      cout << mul(s, m / g) << endl;
    else
      cout << "-1" << endl;
  }
}

1473C - No More Inversions

Idea: adedalic

Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(' ').map { it.toInt() }

        for (i in 1 until (k - (n - k)))
            print("$i ")
        for (i in k downTo (k - (n - k)))
            print("$i ")
        println("")
    }
}

1473D - Program

Idea: BledDest

Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int t;
	cin >> t;
	forn(_, t){
		int n, m;
		string s;
		cin >> n >> m;
		cin >> s;
		vector<int> sul(1, 0), sur(1, 0);
		for (int i = n - 1; i >= 0; --i){
			int d = s[i] == '+' ? 1 : -1;
			sul.push_back(min(0, sul.back() + d));
			sur.push_back(max(0, sur.back() + d));
		}
		reverse(sul.begin(), sul.end());
		reverse(sur.begin(), sur.end());
		vector<int> prl(1, 0), prr(1, 0), pr(1, 0);
		forn(i, n){
			int d = s[i] == '+' ? 1 : -1;
			pr.push_back(pr.back() + d);
			prl.push_back(min(prl.back(), pr.back()));
			prr.push_back(max(prr.back(), pr.back()));
		}
		forn(i, m){
			int l, r;
			cin >> l >> r;
			--l;
			int l1 = prl[l], r1 = prr[l];
			int l2 = sul[r] + pr[l], r2 = sur[r] + pr[l];
			printf("%d\n", max(r1, r2) - min(l1, l2) + 1);
		}
	}
	return 0;
}

1473E - Minimum Path

Idea: Neon

Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 13;

int n, m;
vector<pair<int, int>> g[N];
long long d[N][2][2];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int v, u, w;
    scanf("%d%d%d", &v, &u, &w);
    --v; --u;
    g[v].emplace_back(u, w);
    g[u].emplace_back(v, w);
  }
  
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        d[i][j][k] = (long long)1e18;

  d[0][0][0] = 0;
  set<pair<long long, array<int, 3>>> q;
  q.insert({0, {0, 0, 0}});

  while (!q.empty()) {
    auto [v, mx, mn] = q.begin()->second;
    q.erase(q.begin());
    for (auto [u, w] : g[v]) {
      for (int i = 0; i <= 1 - mx; i++) {
        for (int j = 0; j <= 1 - mn; j++) {
          if (d[u][mx | i][mn | j] > d[v][mx][mn] + (1 - i + j) * w) {
            auto it = q.find({d[u][mx | i][mn | j], {u, mx | i, mn | j}});
            if (it != q.end())
              q.erase(it);
            d[u][mx | i][mn | j] = d[v][mx][mn] + (1 - i + j) * w;
            q.insert({d[u][mx | i][mn | j], {u, mx | i, mn | j}});
          }
        }
      }
    }
  }

  for (int i = 1; i < n; i++) {
    printf("%lld ", d[i][1][1]);
  }
  puts("");
}

1473F - Strange Set

Idea: BledDest

Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>

using namespace std;

template<typename T>
struct dinic {
    struct edge {
        int u, rev;
        T cap, flow;
    };
    
    int n, s, t;
    T flow;
    vector<int> lst;
    vector<int> d;
    vector<vector<edge>> g;
    
    T scaling_lim;
    bool scaling;
    
    dinic() {}
    
    dinic(int n, int s, int t, bool scaling = false) : n(n), s(s), t(t), scaling(scaling) {
        g.resize(n);
        d.resize(n);
        lst.resize(n);
        flow = 0;
    }

    void add_edge(int v, int u, T cap, bool directed = true) {
        g[v].push_back({u, g[u].size(), cap, 0});
        g[u].push_back({v, int(g[v].size()) - 1, directed ? 0 : cap, 0});
    }

    T dfs(int v, T flow) {
        if (v == t)
            return flow;
        if (flow == 0)
            return 0;
        T result = 0;
        for (; lst[v] < g[v].size(); ++lst[v]) {
            edge& e = g[v][lst[v]];
            if (d[e.u] != d[v] + 1)
                continue;
            T add = dfs(e.u, min(flow, e.cap - e.flow));
            if (add > 0) {
                result += add;
                flow -= add;
                e.flow += add;
                g[e.u][e.rev].flow -= add;
            }
            if (flow == 0)
                break;
        }
        return result;
    }

    bool bfs() {
        fill(d.begin(), d.end(), -1);
        queue<int> q({s});
        d[s] = 0;
        while (!q.empty() && d[t] == -1) {
            int v = q.front(); q.pop();
            for (auto& e : g[v]) {
                if (d[e.u] == -1 && e.cap - e.flow >= scaling_lim) {
                    q.push(e.u);
                    d[e.u] = d[v] + 1;
                }
            }
        }
        return d[t] != -1;
    }

    T calc() {
        T max_lim = numeric_limits<T>::max() / 2 + 1;
        for (scaling_lim = scaling ? max_lim : 1; scaling_lim > 0; scaling_lim >>= 1) {
            while (bfs()) {
                fill(lst.begin(), lst.end(), 0);
                T add;
                while((add = dfs(s, numeric_limits<T>::max())) > 0)
                flow += add;
            }
        }   
        return flow;
    }
    
    vector<bool> min_cut() {
        vector<bool> res(n);
        for(int i = 0; i < n; i++) 
            res[i] = (d[i] != -1);
        return res;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n; i++)
        cin >> b[i];
    int s = n;
    int t = n + 1;
    dinic<int> d(n + 2, s, t, true);
    vector<int> last(101, -1);
    for(int i = 0; i < n; i++){
        if(b[i] > 0)
            d.add_edge(s, i, b[i]);
        if(b[i] < 0)
            d.add_edge(i, t, -b[i]);
        for(int k = 1; k <= 100; k++)
            if(last[k] != -1 && a[i] % k == 0)
                d.add_edge(i, last[k], int(1e9));
        last[a[i]] = i;    
    }   
    int sum = 0;
    for(int i = 0; i < n; i++)
        sum += max(0, b[i]);
    cout << sum - d.calc() << endl;
}

1473G - Tiles

Idea: Neon, adedalic

Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
#define sz(a) int((a).size())

template<const int &MOD>
struct _m_int {
  int val;
 
  _m_int(int64_t v = 0) {
    if (v < 0) v = v % MOD + MOD;
    if (v >= MOD) v %= MOD;
    val = int(v);
  }
 
  _m_int(uint64_t v) {
    if (v >= MOD) v %= MOD;
    val = int(v);
  }
 
  _m_int(int v) : _m_int(int64_t(v)) {}
  _m_int(unsigned v) : _m_int(uint64_t(v)) {}
 
  static int inv_mod(int a, int m = MOD) {
    int g = m, r = a, x = 0, y = 1;
 
    while (r != 0) {
      int q = g / r;
      g %= r; swap(g, r);
      x -= q * y; swap(x, y);
    }
 
    return x < 0 ? x + m : x;
  }
 
  explicit operator int() const { return val; }
  explicit operator unsigned() const { return val; }
  explicit operator int64_t() const { return val; }
  explicit operator uint64_t() const { return val; }
  explicit operator double() const { return val; }
  explicit operator long double() const { return val; }
 
  _m_int& operator+=(const _m_int &other) {
    val -= MOD - other.val;
    if (val < 0) val += MOD;
    return *this;
  }
 
  _m_int& operator-=(const _m_int &other) {
    val -= other.val;
    if (val < 0) val += MOD;
    return *this;
  }
 
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
    return unsigned(x % m);
#endif
    // Optimized mod for Codeforces 32-bit machines.
    // x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
    unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
    unsigned quot, rem;
    asm("divl %4\n"
      : "=a" (quot), "=d" (rem)
      : "d" (x_high), "a" (x_low), "r" (m));
    return rem;
  }
 
  _m_int& operator*=(const _m_int &other) {
    val = fast_mod(uint64_t(val) * other.val);
    return *this;
  }
 
  _m_int& operator/=(const _m_int &other) {
    return *this *= other.inv();
  }
 
  friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
  friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
  friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
  friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }
 
  _m_int& operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
 
  _m_int& operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
 
  _m_int operator++(int) { _m_int before = *this; ++*this; return before; }
  _m_int operator--(int) { _m_int before = *this; --*this; return before; }
 
  _m_int operator-() const {
    return val == 0 ? 0 : MOD - val;
  }
 
  friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; }
  friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; }
  friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; }
  friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; }
  friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; }
  friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; }
 
  _m_int inv() const {
    return inv_mod(val);
  }
 
  _m_int pow(int64_t p) const {
    if (p < 0)
      return inv().pow(-p);
 
    _m_int a = *this, result = 1;
 
    while (p > 0) {
      if (p & 1)
        result *= a;
      a *= a;
      p >>= 1;
    }
 
    return result;
  }
  
  friend string to_string(_m_int<MOD> x) {
    return to_string(x.val);
  }
 
  friend ostream& operator<<(ostream &os, const _m_int &m) {
    return os << m.val;
  }
};

extern const int MOD = 998244353;
using Mint = _m_int<MOD>;

const int g = 3;
const int LOGN = 15;

vector<Mint> w[LOGN];
vector<int> rv[LOGN];

void prepare() {
  Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));
  forn(st, LOGN - 1) {
    w[st].assign(1 << st, 1);
    Mint bw = wb.pow(1 << (LOGN - st - 1));
    Mint cw = 1;
    forn(k, 1 << st) {
      w[st][k] = cw;
      cw *= bw;
    }
  }
  forn(st, LOGN) {
    rv[st].assign(1 << st, 0);
    if (st == 0) {
      rv[st][0] = 0;
      continue;
    }
    int h = (1 << (st - 1));
    forn(k, 1 << st)
      rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
  }
}

void ntt(vector<Mint> &a, bool inv) {
  int n = sz(a);
  int ln = __builtin_ctz(n);
  forn(i, n) {
    int ni = rv[ln][i];
    if (i < ni) swap(a[i], a[ni]);
  }
  forn(st, ln) {
    int len = 1 << st;
    for (int k = 0; k < n; k += (len << 1)) {
      fore(pos, k, k + len){
        Mint l = a[pos];
        Mint r = a[pos + len] * w[st][pos - k];
        a[pos] = l + r;
        a[pos + len] = l - r;
      }
    }
  }
  if (inv) {
    Mint rn = Mint(n).inv();
    forn(i, n) a[i] *= rn;
    reverse(a.begin() + 1, a.end());
  }
}

vector<Mint> mul(vector<Mint> a, vector<Mint> b) {
  int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));
  a.resize(cnt);
  b.resize(cnt);
  ntt(a, false);
  ntt(b, false);
  vector<Mint> c(cnt);
  forn(i, cnt) c[i] = a[i] * b[i];
  ntt(c, true);
  return c;
}

int main() {
  prepare();
  
  vector<Mint> fact(1, 1), ifact(1, 1);
  auto C = [&](int n, int k) -> Mint {
    if (k < 0 || k > n) return 0;
    while (sz(fact) <= n) {
      fact.push_back(fact.back() * sz(fact));
      ifact.push_back(fact.back().inv());
    }
    return fact[n] * ifact[k] * ifact[n - k];
  };
  
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  forn(i, n) cin >> a[i] >> b[i];
  
  vector<Mint> ans(1, 1);
  forn(i, n) {
    vector<Mint> Cs;
    for (int j = b[i] - sz(ans) + 1; j < sz(ans) + a[i]; ++j)
      Cs.push_back(C(a[i] + b[i], j));
    auto res = mul(ans, Cs);
    int cnt = sz(ans);
    ans.resize(cnt + a[i] - b[i]);
    forn(j, sz(ans)) ans[j] = res[cnt + j - 1];
  }
  
  cout << accumulate(ans.begin(), ans.end(), Mint(0)) << endl;
}
 
 
 
 
  • Vote: I like it
  • +133
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +67 Vote: I do not like it

The terminology of using "path" for problem E was a bit misleading, since path is normally defined as a walk in which all vertices are distinct, which may not be necessary in this case. Would have given greater clarity if "path" was defined within the problem.

Otherwise, great problem with an even better solution.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Completely agreed. I spent 30 minutes wondering how to eliminate repetitive edges during the contest (that would be a much harder problem, I believe). Since the term "path" is redefined, it deserves a more detailed distinction.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please tell about time complexity for $$$E$$$. My doubt is regarding when graph will be like simple line then for $$$i^{th}$$$ vertex we will have $$$i_{C_2}$$$ many possible value of triplets for $$$i^{th}$$$ node so wouldn't it will go $$$O(n^2)$$$?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Let's count the number of vertices in the new graph. Since each vertex is defined by 3 independent values, the number of vertices will equal to the product of numbers of possible values. So, the first value is the number of vertex, so there are $$$n$$$ possible values. Every flag has 2 values, so there are only $$$4\cdot n$$$ vertices in the new graph. Without thinking much you can find an upper bound $$$16 \cdot m$$$ for number of edges. So, time complexity of Dijkstra algorithm on the new graph is still $$$O(m \log n)$$$

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ohh my bad. Thanks. We are not maintaining the edge removed/added instead we are using flag. Thank you!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Interesting... In portuguese a "walk" is a "path" and a "path where no vertices are repeated" is a "simple path".

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    There exist cases that passing one edge more than once would decrease the total weight?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      4 3
      1 2 10
      2 3 1
      2 4 10
      

      Solution is 3 2 13

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh! So the solution never pass the 4*n vertices more than once but may pass original vertices more than once. Thanks.

»
7 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

fixed

»
7 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it
»
7 weeks ago, # |
Rev. 2   Vote: I like it +32 Vote: I do not like it

I know this will sounds biased, but is n = 1000 necessary for G? I've read the official solution, and assuming that the constant factor of NTT is 1, then that solution would require somewhere around 9e7 operations in worst case (which is something around multiplying 2 polynomials of size 5e6). Of course, the official solution runs in a mere 654ms on the hardest test, but it kills pretty much any recursive NTT solution. (I swapped the solution's NTT with an recursive NTT, and it TLEd on custom invocation on the hardest test, and Codeforces gives 15000ms on custom invocation.) While using recursive NTT itself is folly, I've yet to seen a NTT problem on Educational rounds that forces the participant to use iterative NTT. Which leads to the original question: is this problem intended to introduce iterative NTT to more experienced participants, or was it just an overtly pushed limit to fight brute force?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I wouldn't call it overly pushed.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Wait, so brute force actually pass lower limits? o_O

»
7 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

During the contest , what was your lane of thought while solving C ? How you approached it before reaching to the solution?

I saw that even SecondThread (in his screencast) and Skybytskyi.Nikita (in comments) misread the problem C twice and same happened with me . Finally i wrote brute force and observed the pattern and passed somehow.

Though after seeing the solution it doesn't seems to be difficult , we just needed to observed that in palindrome number of inversions would remain same.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I just figured out the number of inversions for the original array, messed around a bit and noticed the pattern, and tried my luck lol.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    I read the problem then guessed the solution based on "this is C so it should be easy". In fact it was the hardest problem to think about for me.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hi! in problem C, no more inversion for the test case n= 6, k= 4, the expected output is -> 1 4 3 2 . but the answer 4 1 2 3 may also be correct. since the number of inversions are '3' ans also 4 1 2 3 is lexiographically greater than 1 4 3 2.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        1 2 3 4 3 2

        1 4 3 2 3 4

        4 1 2 3 2 1

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    rananjay23 Can you please provide any blog where this observation : "In Palindrome, number of inversions would remain same" is proven formally or at least an inituition is given. Thanks in advance :)

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi, I want to ask you a thing, since you have watched screencast so, his code for C problem he created a "toReverse" variable whose value is n-k+1 whereas I declared it as 2k-n. Although I set different answers for k=2 and n=2, but not able to understand the logic behind that and so please explain this. It would be very helpful. I also included the same code here as well.

    int torev = n-k+ 1; 
                int si = k - torev, ei = k -1;
                for (int i = 0; i < torev / 2; i++) {
                    int l = si + i, r = ei - i;
                    int temp = a[l];
                    a[l] = a[r];
                    a[r] = temp;
                }

    Thanks in Advance

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sorry , I watched his stream long back . I don't remember now . If you have any doubt in editorial , i can help you in that.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Video Tutorial for problem A,B and D link of problem D : https://www.youtube.com/watch?v=botAQ-AZNOQ

link of problem B : https://www.youtube.com/watch?v=H3qBEDYwwX4

link of problem A : https://www.youtube.com/watch?v=YjC6CcxYxo8&t=263s

Hope you guys will enjoy and understand the intution behind the solutions !!!

»
7 weeks ago, # |
Rev. 3   Vote: I like it +24 Vote: I do not like it

Here is an attempt to make an unofficial video editorial of Educational Round 102 by COPS IIT BHU (English) (Problem A-E).

Blog link : https://codeforces.com/blog/entry/86815

Do check it out. https://www.youtube.com/playlist?list=PLLt4yMoVgczWm1VzN3O4y29VElipDNJ1H

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can we solve the D problem using segment trees also ? If yes can someone explain their approach along with code link ?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    To solve using segtree, you just need to know how to join two segments. Each segment will store the smallest x, the largest x and the current x. Node and junction code are these:

    struct Node{
      int l, r, curr;
      Node(){
        l = r = curr = 0;
      }
      Node(char c){
        if(c == '+')
          l = 0, r = 1, curr = 1;
        else
          l = -1, r = 0, curr = -1;
      }
      Node(int a, int b, int c){
        l = a, r = b, curr = c;
      }
    };
    
    inline Node join(Node a, Node b){
      return Node(min(a.l, b.l + a.curr), max(a.r, b.r + a.curr), a.curr + b.curr);
    }
    

    Full code: https://codeforces.com/contest/1473/submission/104307027

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for sharing your approach. I had watched this explanation in stevenkplus's stream but wasn't able to implement.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    code
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I did with segment tree , I used range sum segment tree to find sum for [l,r] , rest of the approach is same as editorial you can check here : https://codeforces.com/contest/1473/submission/104444800

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep, 104324446 was what I did in-contest

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the solution for problem E .

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    sorry for my poor English
    Firstly,add "extra information" when you running dijkstra.Original dijkstra only cares about which point is visted,but now we add two new information on every point.Like copy every point 4 times.When dijkstra is over,we get the shortest path from 1 to others,and the conversions in editorial works based on the answer we get is the "shortest",and "shortest" means we must delete the maximum edge's cost,and multiple the minimum edge's cost twice.This exactly fits the problem.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in what world G is a div 2 problem? (or under 2100)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Educational Contests are typically a bit harder than the regular Div. 2 Rounds (c) neal

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    In the world where a div2 has problem G.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Usually, F&G in Educational Contests focus on more complex algorithms(flow,fft...),but use it as a template.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there any problems similar to E ?

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem C, maybe I'm misreading forever and I can't figure out where it is, can someone help me?

For example n = 5, k = 3, sequence a will be "12321", and inversions of "12321" equals to 3.

The answer p is "321" then sequence b will be "32123", and inversions of "32123" equals to 4 ??

It exceeds the total number of inversions in a??

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    12321 has 4 inversions. (2, 1)(First appearance of 2), (3, 2), (3, 1), (2, 1) // second 2

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Oh!!! I understand that I couldn't find second (2, 1) for many hours...

      Very thanks!

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hi! in problem C, no more inversion for the test case n= 6, k= 4, the expected output is -> 1 4 3 2 . but the answer 4 1 2 3 may also be correct. since the number of inversions are '3' ans also 4 1 2 3 is lexiographically greater than 1 4 3 2.

»
7 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

finally...... rating:1599 :(

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What kind of solutions does the ML in F intend to block?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    O(N^2) edges I guess.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I was thinking that the ML was to block something other than flow because that edge-decreasing observation seemed rather obvious.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem E was too brilliant for my small mind

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain D , went thorugh the editorial multiple times but still ain't clear ? Thanks !

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the video tutorial mentioned in the comments might help you

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    You can plot a graph from the given string. As the graph is continuous , the answer will be $$$max + abs(min) + 1$$$. Now notice what happens when you remove a segment. Graph on the right side of the segment gets shifted up or down by $$$abs(\text{sum of segment l,r})$$$ , i.e. if you know the max and min on right side of the segment, you can calculate the new max and min. Solve this in O(1) using prefix, suffix arrays.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i have tried to explain it here

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

~~~~~ auto mul = [](string s, int k) -> string { string res = ""; while (k--) res += s; return res; };~~~~~

can someone explain this? new to c++

»
7 weeks ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

May I ask why $$$ans_{i, j} = \sum\limits_{k=1}^{m} \binom{a_i+b_i}{b_i-k+j} ans_{i-1,k}$$$ is established in problem G?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Consider an infinity grid.

    Let $$$ans_{i-1,k}$$$ be at $$$(x_1, y_1) = (k-1+OFFSET_{i-1}, 1-k+OFFSET_{i-1})$$$.

    Let $$$ans_{i,j}$$$ be at $$$(x_2, y_2) = (j-1+b_i+OFFSET_{i-1}, 1-j+a_i+OFFSET_{i-1})$$$.

    Where $$$OFFSET_{i-1}$$$ is some accumulated offset from $$$1$$$ to $$$i-1$$$.

    The number of ways walking from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$ using only right and down is $$$\binom{x2-x1+y2-y1}{x2-x1} = \binom{a_i+b_i}{b_i-k+j}$$$.

    Sum from $$$k=1$$$ to $$$k=m$$$ we get the formula.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks!

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      sorry...I can't understand the meaning of the coordinate. Could you help me? Thanks a lot

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        A diagonal line here(say x+y=CONSTANT) corresponds to a column in the original problem.

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

For G:

1e3 * 1e5 * 17 with constant factor C = 1.7e9 * C.

For NTT, obviously that C > 1.

And it's quite easy to reach the worst case.

How dare you set a 1e3 there.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    It's not even close to 1e5, it was something that slowly increases from 1 to 5001 in the worst case. Still, I think this is a pretty tight limit for G though.

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      I see. My mistook. Thanks for pointing it out.

      it's $$$\sum_{i=1}^{1000}{(10i-3)log_2{(10i-3)}}$$$.

      Too tight +1.

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Hi @BledDest,

For the problem F and the input:

2
1 2
100 -200

I guess the network should look like

Where is min-cut here? And where is the flow?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The min cut is 0 (take the set {s, 1}) and the answer is 100-0.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I just don't understand why in problem C, when n = 4, k = 3, p is (1, 3, 2). Shouldn't 'p' be (2, 3, 1) ??

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey can someone provide me a case where my submission for E fails? Almost all tests other than samples are too big to simulate by hand and I'm not able to think of a case :(

»
7 weeks ago, # |
Rev. 5   Vote: I like it -27 Vote: I do not like it

I tried solving D using segment tree but i was not able to solve the problem in contest but later i solved it._ Basic idea was to consider making node that will have sum,minval,maxval and two merge left and right child in specific manner. HERE IS MY SOLUTION

#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define loop(i,k,n) for(ll i=k;i<n;++i)
#define loopr(i,k,n) for (ll i=k;i>n;--i)
#define loopeq(i,k,n) for(ll i=k;i<=n;++i)
#define loopeqr(i,k,n) for(ll i=k;i>=n;--i)
struct node
{
    ll sum,maxval,minval;
};
node NEUTRAL={0ll,0ll,0ll};
node merge(node a,node b)
{
    return 
    {
        a.sum+b.sum,
        max(a.maxval,a.sum+b.maxval),
        min(a.minval,a.sum+b.minval),
    };
}
node single(ll x)
{
    return {x,max(x,0ll),min(x,0ll)};
}
struct segtree
{
    int size;
    vector<node> val;
    void init(int n)
    {
        size=1;
        while(size<n)
            size*=2;
        val.assign(2*size,NEUTRAL);
    }
    void build(vector<int>&a,int x,int lx,int rx)
    {
        if(rx-lx==1)
        {
            if(lx<a.size())
                val[x]=single(a[lx]);
            return;
        }
        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        val[x]=merge(val[2*x+1],val[2*x+2]);
    }
    void build(vector<int>&a)
    {
        build(a,0,0,size);
    }
    node calc(int l,int r,int x,int lx,int rx)
    {
        if(r<=lx||rx<=l)
            return NEUTRAL;
        if(l<=lx&&r>=rx)
            return val[x];
        int m=(lx+rx)/2;
        node sumleft=calc(l,r,2*x+1,lx,m);
        node sumright=calc(l,r,2*x+2,m,rx);
        return merge(sumleft,sumright);
    }
    node calc(int l,int r)
    {
        return calc(l,r,0,0,size);
    }
};
int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,m;
        cin>>n>>m;
        segtree st;
        st.init(n);
        vector<int> arr(n);
        char ch;
        loop(i,0,n)
        {
            cin>>ch;
            if(ch=='+')
                arr[i]=1;
            else
                arr[i]=-1;
        }
        st.build(arr);
        ll l,r;
        while(m--)
        {
            cin>>l>>r;
            node left=NEUTRAL;
            node right=NEUTRAL;
            if(l!=1)
                left=st.calc(0,l-1);
            if(r!=n)
                right=st.calc(r,n);
            node final=merge(left,right);
            cout<<final.maxval-final.minval+1<<"\n";
        }
    }
}
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me a visualization of new graph in problem E? Maybe using the first sample test please. I could not imagine how that graph may look like.

Thanks in advance.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    There is no new graph . Here dp[u][0][0],dp[u][0][1],dp[u][1][0],dp[u][1][1] are not effected by each other and thus can be seen as independent nodes with all edges attached to them similar to u.

    Few definitions (similar to editorial) :

    dp[u][0][0] :Minimum Path length from vertex 1 to u such that each edge in path is counted once .

    dp[u][0][1] :Minimum Path length from vertex 1 to u such that one edge in path is counted one more time.

    dp[u][1][0] :Minimum Path length from vertex 1 to u such that one edge in path is subtracted.

    dp[u][1][1] :Minimum Path length from vertex 1 to u such that one edge in path is counted one more time and one edge in path is subtracted (Note that both type of edges can be same and in that case it will be equivalent to dp[u][0][0]).

    Answer for node u will be dp[u][1][1] because it fits definition in the problem and the edge subtracted will be always maximum and edge added one more time will be of minimum length (see proof in editorial).

    Let's consider graph with n=3,m=2 .Edge 1----2 with weight 3 , 2----3 with weight 6 . Initially dp[u][x][y] = Infinity for all nodes and all values of x and y .

    clearly dp[1][0][0] = 0 . Now transitions :

    dp[2][0][0] = 3 + dp[1][0][0] = 3 . dp[2][0][1] = 3 + 3 + dp[1][0][0] = 6 . dp[2][1][0] = dp[1][0][0] = 0 . dp[2][1][1] = 3 + 3 — 3 + dp[0][0] = 3 . As expected answer for node 2 is 3.

    dp[3][0][0] = 6 + dp[2][0][0] = 9 . dp[3][0][1] = min(dp[2][0][0]+6+6,dp[2][0][1]+6) = min(15,12) = 12 . dp[3][1][0] = min(dp[2][1][0]+6,dp[2][0][0]) = 3 . dp[3][1][1] = min(dp[2][1][1]+6,dp[2][0][1]) = min(9,6) = 6 . As expected answer for node 3 is 6.

    It can coded exactly as Dijkstra where we start from dp[1][0][0]. See the code in editorial it's very short and easy to understand.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks for your detailed example. Such a creative use of Dijkstra.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        True. It can be best described by HealthyUG his comment in his stream

        Dijkstra is like a mixture of DP and Greedy. DP type technique with Greedy order of evaluation. That's why a lot of DP things can be used in Dijkstra, as long as the greediness is maintained.
»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In C, is the number of inversions in the original sequence, a, always $$$(n-k)^2$$$?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice proof for problem C.

For problem D, let's note $$$a_i = 1_{s_i='+'} - 1_{s_i='-'}$$$. For the suffix max, the quantity that we want to compute is:

$$$ s_i = \max(0, a_i, a_i + a_{i+1}, a_i + a_{i+1} + a_{i+2}, ..., a_i + a_{i+1} + ... + a_n) \\ = \max(0, a_i + \max(0, a_{i+1}, a_{i+1} + a_{i+2}, ..., a_{i+1} + ... + a_n)) \\ = \max(0, a_i + s_{i+1}) $$$
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is there any video editorial for F ??

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain where i am wrong in Probem E

i am getting WA on test 5

although i did similar as mentioned in editorial.

SUBMISSION

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Does the fact: "a palindromic sequence of distinct numbers has a fixed number of inversions regardless of the elements" should be known by contestants before the contest? Is it a widely known fact?

»
6 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

can someone check why my code doesnt work for B.

include <bits/stdc++.h>

using namespace std;

lcm(int a, int b) { int s=a; while(s%b!=0) s=s+a; return s; } int issubstring(char c1[],char c2[],int l1, int l2) { int l=lcm(l1,l2); for(int i=0;i<l;i++) { if(c1[i%l1]!=c2[i%l2]) return 0; } return l; }

stringlcm() { char c1[20], c2[20]; scanf("%s",c1); scanf("%s",c2);

int l1=strlen(c1);
int l2=strlen(c2);

if(int l=issubstring(c1,c2,l1,l2))
{
    for(int i=0;i<l;i++)
    cout<<c1[i%l1];
    cout<<"\n";
}
else
cout<<"-1\n";

} main() { int n; cin>>n; while(n--) stringlcm(); }

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Tutorial for problem A,B and D link of problem D : https://www.youtube.com/watch?v=botAQ-AZNOQ

link of problem B : https://www.youtube.com/watch?v=H3qBEDYwwX4

link of problem A : https://www.youtube.com/watch?v=YjC6CcxYxo8&t=263s

Hope you guys will enjoy and understand the intution behind the solutions !!!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F is Closure problem.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hi! in problem C, no more inversion for the test case n= 6, k= 4, the expected output is -> 1 4 3 2 . but the answer 4 1 2 3 may also be correct. since the number of inversions are '3' ans also 4 1 2 3 is lexiographically greater than 1 4 3 2.

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

adedalic for the editorial of problem f how do you prove this part "It can be proven that any maximum flow algorithm that relies on augmenting paths will finish after O(v) iterations in this network"