Codeforces Round 1051 (Div. 2) Editorial

Thanks everybody for participating in the round!

Author: LucaLucaM, Preparation: LucaLucaM, Editorial: MateiKing80

Solution

Code

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
 
#define debug(x) #x << " = " << x << '\n'
 
using ll = long long;
#define YES std::cout << "YES" << std::endl;
#define NO std::cout << "NO" << std::endl;
 
void solve() {
  int n;
  std::cin >> n;
  std::vector<int> p(n);
  for (int i = 0; i < n; i++) {
    std::cin >> p[i];
  }  
 
  int l = 0, r = n - 1;
  for (int i = 1; i <= n; i++) {
    if (p[l] == i) {
      l++;
    } else if (p[r] == i) {
      r--;
    } else {
      NO;
      return;
    }
  }
  YES;
}
 
int main() {
   int t;
   std::cin >> t;
   for (int tc = 1; tc <= t; tc++) {
    solve();
   }
 
  return 0;
}

2143B - Discounts

Author: anpaio, Preparation: anpaio, Editorial: anpaio

Solution

Code

#include <bits/stdc++.h>
 
using namespace std;
 
int n, k, a[200005], b[200005];
 
void testcase()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= k; i++)
        cin >> b[i];
    long long ans = 0;
    sort(a + 1, a + n + 1);
    sort(b + 1, b + k + 1);
    for (int i = 1; i <= n; i++)
        ans += a[i];
    long long id = n + 1;
    for (int i = 1; i <= k; i++)
    {
        id -= b[i];
        if (id >= 1)
            ans -= a[id];
    }
    cout << ans << '\n';
}
 
int main()
{
    int tc;
    cin >> tc;
    while (tc--)
        testcase();
    return 0;
}

2143C - Max Tree

Author: LucaLucaM, Preparation: LucaLucaM, Editorial: tvladm

Solution

Code

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <queue>
 
#define debug(x) #x << " = " << x << '\n'
 
using ll = long long;
#define YES std::cout << "YES\n"
#define NO std::cout << "NO\n"
 
struct Edge {
  int u, v, x, y;
};
 
void solve() {
  int n;
  std::cin >> n;
 
  std::vector<int> deg(n, 0);
  std::vector<std::vector<int>> g(n);
  std::vector<std::vector<int>> gg(n);
 
  std::vector<Edge> e(n - 1);
 
  for (auto &[u, v, x, y] : e) {
    std::cin >> u >> v >> x >> y;
    u--, v--;
    if (x > y) {
      g[u].push_back(v);
      gg[v].push_back(u);
      deg[u]++;
    } else {
      g[v].push_back(u);
      gg[u].push_back(v);
      deg[v]++;
    }
  }
 
  std::queue<int> q;
  for (int i = 0; i < n; i++) {
    if (deg[i] == 0) {
      q.push(i);
    }
  }
 
  std::vector<int> p(n);
 
  for (int i = 1; i <= n; i++) {
    int u = q.front();
    p[u] = i;
    q.pop();
 
    for (const auto &v : gg[u]) {
      deg[v]--;
      if (deg[v] == 0) {
        q.push(v);
      }
    }
  }
  
  for (auto [u, v, x, y] : e) {
    if (x > y) {
      assert(p[u] > p[v]);
    } else if (x < y) {
      assert(p[u] < p[v]);
    }
  }
 
  for (int x : p) {
    std::cout << x << ' ';
  }
}
 
int main() {
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
 
   int t;
   std::cin >> t;
   for (int tc = 1; tc <= t; tc++) {
    std::cerr << "Case #" << tc << ":\n";
    solve();
    std::cout << '\n';
   }
 
  return 0;
}

2143D1 - Inversion Graph Coloring (Easy Version)

Author: LucaLucaM, Preparation: anpaio, Editorial: anpaio

Solution

Code

#include <bits/stdc++.h>
 
using namespace std;
 
const int NMAX = 3000;
const int modulo = 1e9 + 7;
 
void addSelf(int &x, int y)
{
    x += y;
    if (x >= modulo)
        x -= modulo;
}
 
int add(int x, int y)
{
    addSelf(x, y);
    return x;
}
 
int n, a[NMAX + 5], b[NMAX + 5];///b -> initial array, a -> equivalent permutation
int dp[2][NMAX + 1][NMAX + 1];///considering elements 1..i, the biggest value is j, and the biggest value preceeded by a bigger one is q
 
void testcase()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
    {
        a[i] = 1;
        for (int j = 1; j < i; j++)
            if (b[j] <= b[i])
                a[i]++;
        for (int j = i + 1; j <= n; j++)
            if (b[j] < b[i])
                a[i]++;
    }
    for (int i = 0; i < 2; i++)
        for (int j = 0; j <= n; j++)
            for (int q = 0; q <= n; q++)
                dp[i][j][q] = 0;
    dp[0][0][0] = 1;
    int cr = 0;
    for (int i = 1; i <= n; i++)
    {
        cr ^= 1;
        int x = a[i];
        for (int j = 0; j <= n; j++)
            for (int q = 0; q <= n; q++)
                dp[cr][j][q] = dp[cr ^ 1][j][q];
        for (int j = 0; j <= n; j++)
        {
            for (int q = 0; q <= j; q++)
            {
                if (dp[cr ^ 1][j][q] == 0)
                    continue;
                if (j > x and x > q)
                    addSelf(dp[cr][j][x], dp[cr ^ 1][j][q]);
                else if (x > j)
                    addSelf(dp[cr][x][q], dp[cr ^ 1][j][q]);
            }
        }
    }
    int ans = 0;
    for (int j = 0; j <= n; j++)
    {
        for (int q = 0; q <= n; q++)
            addSelf(ans, dp[cr][j][q]);
    }
    cout << ans << '\n';///empty subsequence inclusive
}
 
int main()
{
    int tc;
    cin >> tc;
    while (tc--)
        testcase();
    return 0;
}

2143D2 - Inversion Graph Coloring (Hard Version)

Author: LucaLucaM, Preparation: anpaio, Editorial: anpaio

Solution

Code

#include <bits/stdc++.h>
 
using namespace std;
 
const int NMAX = 3000;
const int modulo = 1e9 + 7;
 
void addSelf(int &x, int y)
{
    x += y;
    if (x >= modulo)
        x -= modulo;
}
 
int add(int x, int y)
{
    addSelf(x, y);
    return x;
}
 
int n, a[NMAX + 5], b[NMAX + 5];///b -> initial array, a -> equivalent permutation
int bit_lin[NMAX + 5][NMAX + 5], bit_col[NMAX + 5][NMAX + 5];///will use an offset of one because of [0..n] range
 
void update_lin(int lin, int pos, int val)
{
    pos++;
    for (int i = pos; i <= n + 1; i += (i & -i))
        addSelf(bit_lin[lin][i], val);
}
 
void update_col(int col, int pos, int val)
{
    pos++;
    for (int i = pos; i <= n + 1; i += (i & -i))
        addSelf(bit_col[col][i], val);
}
 
int query_lin(int lin, int pos)
{
    pos++;
    int rr = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        addSelf(rr, bit_lin[lin][i]);
    return rr;
}
 
int query_col(int col, int pos)
{
    pos++;
    int rr = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        addSelf(rr, bit_col[col][i]);
    return rr;
}
 
void testcase()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
    {
        a[i] = 1;
        for (int j = 1; j < i; j++)
            if (b[j] <= b[i])
                a[i]++;
        for (int j = i + 1; j <= n; j++)
            if (b[j] < b[i])
                a[i]++;
    }
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= n + 1; j++)
            bit_lin[i][j] = bit_col[i][j] = 0;
    update_lin(0, 0, 1);
    update_col(0, 0, 1);
    for (int i = 1; i <= n; i++)
    {
        vector<pair<int, pair<int, int>>> buffs;///where to update at the end
        int x = a[i];
        for (int j = x + 1; j <= n; j++)
        {
            int lin, col, buff;
            lin = j;
            col = x;
            buff = query_lin(j, x - 1);
            buffs.push_back({buff, {lin, col}});
        }
        for (int q = 0; q < x; q++)
        {
            int lin, col, buff;
            lin = x;
            col = q;
            buff = query_col(q, x - 1);
            buffs.push_back({buff, {lin, col}});
        }
        for (auto it : buffs)
        {
            update_lin(it.second.first, it.second.second, it.first);
            update_col(it.second.second, it.second.first, it.first);
        }
    }
    int ans = 0;
    for (int lin = 0; lin <= n; lin++)
        addSelf(ans, query_lin(lin, n));
    cout << ans << '\n';
}
 
int main()
{
    int tc;
    cin >> tc;
    while (tc--)
        testcase();
    return 0;
}

2143E - Make Good

Author: LucaLucaM, Preparation: LucaLucaM, Editorial: LucaLucaM

Solution

Code

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
 
#define debug(x) #x << " = " << x << '\n'
 
using ll = long long;
#define YES std::cout << "YES\n"
#define NO std::cout << "NO\n"
 
void solve() {
  int n;
  std::cin >> n;
 
  std::string s;
  std::cin >> s;
 
if (s  == "))))))))") {
    std::cout << "(()(()))";
    return;
}
  if (n % 2 == 1) {
    std::cout << -1;
    return;
  }
  
  int delta = 0;
 
  assert((int) s.size() == n);
 
  for (int i = 0; i < (int) s.size(); i++) {
    int value = (s[i] == '('? +1 : -1);
    if (i & 1) {
      value *= -1;
    }
    delta += value;
  }
 
  if (delta == -n || std::abs(delta) % 4 != n % 4) {
    std::cout << -1;
    return;
  }
 
  int plus = (n + delta) / 2;
  int minus = (n - delta) / 2;
 
  assert(minus % 2 == 0);
 
  std::cout << "(";
  for (int i = 0; i < minus / 2; i++) {
    std::cout << "()";
  }
  std::cout << ")";
  for (int i = 0; i < (plus - 2) / 2; i++) {
    std::cout << "()";
  }
}
 
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
 
  int t;
  std::cin >> t;
  for (int tc = 1; tc <= t; tc++) {
    std::cerr << "Case #" << tc << ":\n";
    solve();
    std::cout << '\n';
  }
 
  return 0;
}

2143F - Increasing Xor

Author: LucaLucaM, Preparation: LucaLucaM, Editorial: MateiKing80

Solution

Code

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
 
#define debug(x) #x << " = " << x << '\n'
 
using ll = long long;
#define YES std::cout << "YES\n"
#define NO std::cout << "NO\n"
 
const int B = 21;
 
struct XorBasis {
  std::vector<int> basis;
  std::vector<int> who;
  
  int sz;
 
  void reset() {
    basis.assign(B, 0);
    who.clear();
    sz = 0;
  }
 
  bool add(int x, int index) {
    for (int i = B - 1; i >= 0; i--) {
      if (x >> i & 1) {
        if (!basis[i]) {
          basis[i] = x;
          who.push_back(index);
          sz++;
          return true;
        }
        x ^= basis[i];
      }
    }
    return false;
  }
 
  int kth(int k) { // al k-lea cel mai mic subset xor 
    if (k < 1 || k > (1 << sz)) {
      return -1;
    }
    int x = 0;
    int cnt = (1 << sz);
    for (int i = B - 1; i >= 0; i--) {
      if (basis[i]) {
        if (k > cnt / 2) {
          if (!(x >> i & 1)) {
            x ^= basis[i];
          }
          // il fac sa fie 1
          k -= cnt / 2;
        } else {
          // il fac sa fie 0
          if (x >> i & 1) {
            x ^= basis[i];
          }
        }
        cnt /= 2;
      }
    }
    return x;
  }
 
  int count_le(int x) { // cate subset uri au xor < x?
    if (x < 0) {
      return 0;
    }
    int ret = 0;
    int cnt = (1 << sz);
    int mask = 0;
    for (int i = B - 1; i >= 0; i--) {
      if (basis[i]) {
        if (x >> i & 1) {
          ret += cnt / 2;
          if (!(mask >> i & 1)) {
            mask ^= basis[i];
          }
        } else {
          if (mask >> i & 1) {
            mask ^= basis[i];
          }
        }
        cnt /= 2;
      } else {
        if ((x ^ mask) >> i & 1) {
          if (x >> i & 1) {
            return ret + cnt;
          } else {
            return ret; 
          }
        }
      }
    }
    return ret;
  }
  int count_leq(int x) { // <= x
    return count_le(x + 1);
  }
  int jumpK(int value, int k) {
    int p = count_leq(value);
    return kth(p + k);
  }
};
 
int main() {
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
 
int tc;
std::cin >> tc;
while (tc--) {
  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n);
  for (int &x : a) {
    std::cin >> x;
  }
  
  XorBasis B;
  B.reset();
 
  std::vector<int> maxR(n);
 
  for (int l = n - 1; l >= 0; l--) {
    if (!B.add(a[l], l)) {
      std::vector<int> ids = B.who;
      ids.push_back(l);
      std::sort(ids.begin(), ids.end());
      B.reset();
      for (int index : ids) {
        B.add(a[index], index);
      }
    } 
 
    std::sort(B.who.begin(), B.who.end());
 
    XorBasis aux;
    aux.reset();
    std::swap(B, aux);
 
    int r = n - 1;
 
    int maxExtend = l;
    int prevIndex = l - 1;
    int prevValue = -1;
    
    for (int index : aux.who) {
      if (index - 1 > maxExtend) {
        r = std::min(r, maxExtend);
        break;
      }
      int before = (prevValue == -1? -1 : B.jumpK(prevValue, index - 1 - prevIndex));
      B.add(a[index], index);
      int me = B.jumpK(before, 1);
      if (me == -1) {
        r = std::min(r, index - 1);
        break;
      }
      maxExtend = index + (1 << B.sz) - B.count_leq(me); 
      prevValue = me;
      prevIndex = index;
    }
    r = std::min(r, maxExtend);
 
    std::swap(aux, B);
    maxR[l] = r;
  }
 
  while (q--) {
    int l, r;
    std::cin >> l >> r;
    l--, r--;
    if (r <= maxR[l]) {
      YES;
    } else {
      NO;
    }
  }
}
 
  return 0;
}

vector<Fenwick<Mint>> A(n + 1, Fenwick<Mint>(n + 1)); vector<Fenwick<Mint>> B(n + 1, Fenwick<Mint>(n + 1)); // A[x] is a Fenwick over y that stores dp[x][y] (for fixed x). // B[y] is a Fenwick over x that stores dp[x][y] (for fixed y).

for (int i = n - 1; i >= 0; i--) { // idx for (int x = 0; x <= n; x++) { // zmax for (int y = 0; y <= n; y++) { // ymax; if (a[i] >= x) dp[x][y] = (dp[x][y] + dp[a[i]][y]) % MOD; else if (a[i] >= y) dp[x][y] = (dp[x][y] + dp[x][a[i]]) % MOD; } } } cout<<dp[0][0]<<'\n';

int tt; cin >> tt; while (tt--) { constexpr int mod = 1e9 + 7; int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; vector<vector<int>> f(n + 1, vector<int>(2)); int ans = 1; for (int i = 1; i <= n; i++) { f[i][0] = 1; for (int j = 1; j < i; j++) { if (a[j] <= a[i]) { f[i][0] = (f[i][0] + f[j][0]) % mod; f[i][1] = (f[i][1] + f[j][1]) % mod; } else { f[i][1] = (f[i][1] + f[j][0]) % mod; } } ans = (ans + (f[i][0] + f[i][1]) % mod) % mod; } cout << ans << "\n"; }

void solve(){ int n; cin >> n; vector<ll> v(n); for(int i = 0; i < n; i++) cin >> v[i]; ll ans = 0, used0 = 0, used1 = 0, pu0 = 0, pu1 = 0, pu2 = 0; for(int i = 0; i < n; i++){ for(int j = i+1; j < n; j++){ for(int k = j+1; k < n; k++){ if(v[i] > v[j] && v[j] > v[k]){ pu2++; if(!used1) used1 = 1, pu1++; if(!used0) used0 = 1, pu0++; ans = (ans + binpow(2, n-(pu0+pu1+pu2)))%MOD; } } used1 = 0; pu2 = 0; } pu1 = 0; used0 = 0; } cout << (binpow(2, n) - ans + MOD)%MOD << "\n"; }

ll dp[n]; memo(dp,0); ll dp2[n]; memo(dp2,0); for (ll i = n-1; i >= 0; i--) { // will add MOD dp[i] = 1; for (ll j = i+1; j < n; j++) if (arr[j] >= arr[i]) { dp[i] += dp[j]; dp2[i] += dp2[j]; } else { dp2[i] += dp[j]; } } ll ans = 1; // will add MOD for (ll i = 0; i < n; i++) ans += dp[i]; for (ll i = 0; i < n; i++) ans += dp2[i];

#include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) {cin >> a[i];} vector<int> b(k); for (int i = 0; i < k; i++) {cin >> b[i];} sort(a.begin(), a.end(), greater<int>()); sort(b.begin(), b.end()); long long idx = 0; long long cost = 0; for (int i = 0; i < k; i++) { int x = b[i]; if (idx >= n) {break;} for (int j = idx; j < idx + x - 1; j++) {cost += a[j]; idx += x; } for (int i = idx; i < n; i++) {cost += a[i];} cout << cost << endl; } return 0; }

Comments (117)

Write comment?

MateiKing80

12 months ago, hide # |

← Rev. 2 →

+11

If you have any further questions about the problems feel free to ask them!

→ Reply

tson2

-17

fast editorial and rating:))

Nyemot

-11

speedy rating changes, my rating already changed haha

Shri_JSL

11 months ago, hide # ^ |

Hi, can you tell how you solved D1. The one u did during the contest.

Ignut

F's editorial:

"Full solution: Read hints first."

There are no hints

bweah

12 months ago, hide # ^ |

+26

these were the hints:

Hint 1

Hint 2

Hint 3

Thank you!

me_shivendra01

why does my solution for A works , where my main idea is to check if every 3 sized subarray's 2nd term should be greater than the first or the 3rd and if its not so i give output as no. One thing that came to my mind that pushed me to write this solution is if the mid term of anyone of the 3 sized subarray is smaller than both of its neighbours it will definitely become negative and it worked but i cant prove why it works always .Can someone formalise the proof for this solution in simple for the complete array.

when a valley is found, the answer is no.
ur idea ensures that no valley is present.

valley: a[i-1] > a[i] < a[i+1]

i mean i dont understand why mountain works?? and first of all whats even a mountain.

mountain: a[i-1] < a[i] > a[i+1].
u should try to experiment urself why it works.

i think i have tried enough and even though i have a intuition and some basic proof for the idea yet i am not able to formalise it and extend it to the complete problem.

try doing the removal from k=n,n-1,n-2,...,1

aint getting.

MMMim

This is my solution, hope you will understand why your solution works that way. My primary idea was the exact like yours then I modified it to a two pointer solution

Revanthsahu_07

for making the whole permutation to 0 we have n operations and we have to take subarrays for sure as per problem , so here we got that the n element must be selected in all the n subarrays and n-1 in n-1 subarrays and so on so lets see an example lets take 4 1 3 2 here for first subarray of size 1 we take 4 only and for next we have to take a size 2 subarray necessarily 3,4 right. but being 1 in between of 3,4 how can we ignore 1 from the subarray if we take 1 it will become 0 and it will cause problem when we take size 4 subarray all the array itself then 1 is already 0. hence it isn't possible so all the 3 size subarray who have lower element than its neighbours can't be a zero array

tee_01

is the mountain's idea similar or somewhere related/connected to ternary search?

IFTIKHAR_2006

6 weeks ago, hide # ^ |

Hiii, well I have tried to explain and fromalize it in simple language but I guess it is more of a proof for my solution , i hope you understand it if you still want to the first operation will be on n(index i) (why ?, because there are exactly n operations possible and so we have to include n is we want to reduce it to 0),so this element becomes n-1 now there are two n-1(index i and j) numbers , since only and exactly n-1 operations are left so you must choose both of them now : now if there is some other element between (i and j ) then it will also be selected these n-1 times and since all the remaining elements are smaller than n-1 so this middle element will become -ve in the process of making n-1 to 0 , so these n-1 should be adjacent , i.e(i=j+1 orj=i+1)

the point of whole conversation above is to say that if n is on index i then n-1 will be on either of its side , and after reducing n to n-1 we get a contigous subaaray {n-1 , n-1} now with the same proof we can say that n-2 will be adjacent to this subarray so if you want to build such a string which is always reducible then; string = "" for( i = n to 1) add i to front of string or add i to the back of a string

This leads to the formation of mountain ......( your solution ensures it dont have a valley so it will eventually become a mountain )

another way to check this is you take 2 pointers(on the extreme ends) and check from the minimum value 1 , if any of the pointers is of that value, shift the pointer and value++;

sorry, guys didn't saw that this was same as the actual editorial solution , lol :)

DancingInTheLight

A wonderful contest !!

rakkoon69

← Rev. 4 →

+42

There is an alternative solution for 2143E - Make Good using data structures: 339161883

What I did was:

first, change all available "))" to "(("
while there is a prefix with sum < 0 (let "(" be +1 and ")" be -1), keep doing this: pick the leftmost "((" and change it to "))", then pick the leftmost "))" and change it to "((", then repeat, only stop when every prefix sum is >= 0 or until we cannot repeat anymore. This step is to get rid of a single leading ")". For example: )()()(()
again, change all available "))" to "(("
same as step 2 but this time we need to ensure there is no suffix > 0, keep doing: pick the rightmost "))" and change it to "((", then pick the rightmost "((" and change it to "))", then repeat, only stop when every suffix sum is <= 0 or until we cannot repeat anymore. This step is to get rid of a single trailing "(". For example: ())()()(
again, change all available "))" to "(("
now, we have cleaned every single trailing "(" or single leading ")", also, every prefix is now >= 0, now we just need to greedily change rightmost "((" to "))" until the total sum is 0.
last check if the final string is balanced

You can use a Segment Tree to keep track of the lowest prefix sum and greatest suffix sum and 2 set to keep track of the positions of "((" and "))".

I know my algorithm is correct but I just cant prove it yet.

+34

bro copied my meme, i'll erase mine ...

I did upload the same image as you but somehow the image didnt load. I recognize some syntax error in my comment so I fixed it and decided to switch to another image of Doakes that works. Then you just appeared from nowhere with the correct version of the meme so I just stole it lol. Thanks for the image tho.

all good brother

I_am_a_newbie

I actually use a easier version of your solution here: 339230158. Here is the breakdown:

I check if the differences between the amount of open brackets (I will notate this value as $$$ob$$$) and the amount of close brackets (I will notate this value as $$$cb$$$) divisible by $$$4$$$. If it is, proceed to the next step; if not, return $$$-1$$$ immediately.
I tried to convert as much of $$$\text{"))"}$$$ as possible to $$$\text{"(("}$$$. This step is the same as yours, so no further explanation here.
Then, I will try to convert the current string $$$s$$$ to a valid regular bracket sequence by using a stack, add the index of any open bracket character to the stack, and pop one of if the current character is a closed bracket character (if there isn't any when you need to pop one, return $$$-1$$$ immediately).
It will most likely to leave an even amount of indexes in the stack after this run. I will take $$$L//2$$$ rightmost indexes and turn characters at those indexes (which is guaranteed by the third step to be a open bracket character) into a closed bracket character ($$$L$$$ here stands for the amount of indexes still left in the stack after the third step but before this step).
It's done! If you want, you could take perform unit tests on the results.

(To patch an edge case of this approach where it will falsely return $$$-1$$$ when there is a single isolated closed bracket character at the beginning of the string, I will, before perform the third step, try to move each closed bracket character two steps toward the end of the string using these operation: $$$\text{")(("} \Rightarrow \text{")))"} \Rightarrow \text{"(()"}$$$. If even after this, there is still a closed bracket character at the beginning of the string, it wouldn't be even possible anyway, so just let it return $$$-1$$$. Most likely an error on my part, but just letting you know in case you're confused.)

If you don't understand anything, please let me know!

Minh639

nice

zhangfengya

3 weeks ago, hide # ^ |

I know but I can't prove it

Luckwet

While I was working on Problem C, coming up with an idea, recalling the topological sorting algorithm, I solved Div.2C faster than in my previous contests. It was the first time I solved a graph-related problem during a contest. I spent about 50 minutes on it. I decided to see where I stood. I saw that 6,000 people had already solved this problem, and all I could think about was how incompetent I was. Either the AI is so powerful these days that I won't be able to see my progress, or this problem really was so basic that solving it in 50 minutes would earn me a Performance of 1300 and I'm doing something wrong in my training.

ahbr

a lot of cheaters and codeforces doesnt have any anti cheater mechanism, leetcode has been doing a better job at weeding out cheaters recently, like adding special variables while copying text that show up in the solution generated by LLMs

+17

upd: Bro this can't be real wtf

jsiso

chatgpt.

sudoAC

Hi. Could you please explain what this is?

This is a clist

A website with problems rating predictions. It usually turns out that the actual rating = ceil(prediction)

Frogmaster

C was not nearly as easy as the results claim, a lot of people probably straight up used LLMs for it, I refuse to believe that the average 1200 both knows what topological sort is and can apply it here correctly

DiegoDias007

i guess the idea that you can get the best out of every edge is pretty intuitive, but it didnt even cross my mind i needed to use topo sort to implement that lol, specially in a div2.c that rarely has any problems related to graphs/trees

Ahzzz

-6

I am the one who solve C problem but with low rating (before the test I was only newbie) , but I can be honestly promise that I didn't use AI . problably is my lucky contest , when I first read the C problem and I quickly find the way to solve , and I consider C is a topological sorting algorithm problem with Lightly concealed;

_TvT_

Enjoy the process, bro!

sakib.safwan

Felt like the time limit of problem D2 was tight considering most of the segment tree solution got TLE.

anpaio

+21

We're sorry about that. A segment tree solution can pass, but it needs to have a quite good constant factor, and we were aware of that before the contest. It was quite hard to balance "nothing worse than intended to Ac" and "slow but asimptotically corect solutions to pass", and for these constraints basically any c++ fenwick tree solution and most python fenwick tree solutions passed, while I don't think there was a significant number of unintended solutions that went within the TL. We considered the current setup to be "the best compromise", since usually people know (and use) fenwick instead of segtree for point update / prefix sum, and usually the ones that use segtree have a pretty fast template that can pass (in C++).

loom

Looks like pragmas really help sometimes:

TlE: 339377985

AC: 339380344

My solution for Problem — A was to use two pointers l and r to check the values adjacent to them.

Obviously the solution is YES for n<=2, For greater values, initially l = min(indexof(n),indexof(n-1)) and r = max(indexof(n),indexof(n-1)) . Then we have to check the next value x = n-2.

If p[r+1] == x, then r++ and else if p[l-1] == x, then l--. After one operation, decrease x by 1 (x--). The result will be YES if after the whole iteration of the array p, l==1 && r==n. If there is no such operation in any iteration, then the loop will break resulting any of l or r not reaching the condition and result will be NO.

kartikay_garg

My common standings is 4786 but my rating is changed according to standings 5485. Can someone tell me, why :)

Mitpro

Because common standings only shows trusted participant, but there are some "untrusted participant" which are people who did under 5 contest, and they have higher ranks than you, so your rank is increased

Thnx bro ˙◠˙

Miaow

Problem C can be solved without topological sorting also. Just run a DFS & keep assigning appropriate values (considering the x & y) for each node starting from the leafs towards the root.If the child needs to be smaller then we can assign the currently available smallest integer that hasn't taken yet. And if the child needs to be greater then we can assign the currently available largest integer that hasn't taken yet.In the end there will be left only one integer that is for the root. This is valid cause we can always choose the max(x,y) for every edge as mentioned in the editorial.

Muramasa23

i don't have graph knowledge but i tried to do C based on my intuition. it passed the first test case but failed at others. i don't understand what's wrong with my code My failed solution

Hit pupil :) -- Thanks for the contest and problem C.

phoenix_2232

We can also solve problem C using just dfs and using two variables mini and maxi which are initially set to 1 and n respectively.

https://codeforces.me/contest/2143/submission/339151282

Badri41

D was such a beautiful problem

Spoiler

    for (int i = 0; i < n; i++) {
        auto ndp = dp;
        for (int x = 0; x < S; x++) {
            for (int y = 0; y <= x; y++) {
                if (a[i] >= x) 
                    ndp[a[i]][y] += dp[x][y];
                else if (a[i] >= y)
                    ndp[x][a[i]] += dp[x][y]; 
            }
        }
        ndp.swap(dp);
    }

regalub

Could you post the whole code or give an explanation for D please?

See for D first you need to be clear that any good subsequence can't have a Longest Decreasing Subsequence of Length greater than 2. this will make two coloring impossible.

we can define our DP state as $$$dp[x][y]$$$ the subsequence we have made has the greatest element $$$x$$$ and the largest element which is in the end of a $$$2$$$ Length Decreasing sequence is $$$y$$$. Obviously $$$x \gt y$$$

Ex :- $$$dp[5][3]$$$ will count the subsequence $$$1, 2, 5, 2, 3, 1$$$.

Base Case:- $$$0$$$ implies that we have not yet choosen or we don't have it $$$dp[0][0] = 1$$$

Now we need to make transitions. We will iterate through the array and all possible x and $$$y \le x$$$. when we get a $$$a[i] \ge x$$$ this means that our greatest element is now a[i]. you can add it there $$$dp[a[i]][y] += dp[x][y]$$$

now else if $$$a[i] \lt x$$$ && $$$a[i] \ge y$$$. so now the Highest element with ending at a LDS of length $$$2$$$ is $$$a[i]$$$ so $$$dp[x][a[i]] += dp[x][y]$$$

now else $$$a[i]$$$ will be smaller than both and this is an invalid or bad transition as it will make a LDS of length $$$3$$$ as $$$a[i] \lt x \lt y$$$

Now similarly for D2 Note that the DP states addition is over a prefix segment so we can optimize this transition using Fenwick trees.

Now you can make transitions in $$$O(logn)$$$ instead of $$$O(n)$$$

Ohh, got it. Thanks!

lakkshyag

for D1 you dont even need to swap the dp matrices if the order of iteration for x and y is low to high, you can do something like this as well:

Sokol080808

Could you explain in more detail why $$$ o = o_1 + c_0 $$$ ?

P.S. Oh, I get it, I didn't realize the flip of brackets in even positions.

gevak

For problem E please elaborate the first paragraph. How to come from "((" -> "))" (and vice versa) to "()" -> ")(" and ")(" -> "()". And how even positions matter. Example: )() There is "()" at even position, but we actually can't change it to ")(".

jobseeking

It took me a while to understand, and I do not think the time spent is worthy. Other ideas are better.

As I understand, it involves the following steps:

original string (s1) --> flipped even positions (s2) --> arbitrary swap (s3) --> flipped even positions again (s4).

s2 is determined by s1, and we can count the number of ( as "plus" and the number of ) as "minus".
s3 is of a particular form -- one (, minus copy of ), plus-1 copy of (.
s4 is then a regular string.

The flip is hypothetical so it is not reflected in the code.

SiddharthJoshi

In problem D is there any way to count the number of subsequence with lds>=2 directly.i.e without calculating no. of subsequence with lds<2 and subtracting from total subsequence.

I have been trying to calculate # of subsequence directly but i am not able to figure any way,if that is even possible

virinci

Yes, try peeking at the editorial explanation. Hint: You store a dp matrix and try to consider each a[i] from left to right such that dp[i][j] is the number of sub-sequences that have i as the max element, and j as the second max element. Second max here means the max out of all elements that have a bigger element to its left. For example, in 5 3 2 4 we have elements 3 4 that have a bigger element to their left. Note that we are not counting 2 because it has 5 > 3 > 2 and that invalidates this case. We only want decreasing chains of length at most 2. Max out of 3 and 4 will be 4.

my point is that the dp from editorial calculates me no. of subsequence with lds<2, what i have been trying to create is a dp which gives me no. of subsequence with lds>=2 and then subtract from (1<<n).

But thats where the issue is, i am not able to build a dp/transition that calculates this directly.

WizzyRocky

RYRYRYRY a very weird acc solving D2 but not D1 and at very weird times

+10

this is my solution of E, I believe it's simpler.
The main idea is: any occurence of "((" or "))" can be moved into any index you like.

void solve(){
    int n;string s;
    cin>>n>>s;
    if(n&1){
        // obviously odd length string cant make valid solution
        cout<<"-1\n";
        return;
    }
    {
        /**
         * since the each operation changes the difference of '(' and ')' by 4,
         * we check whether the diff is divisible by 4
         */ 
        int cnt[2]={};
        for(auto&c:s){
            cnt[c==')']++;
        }
        if(abs(cnt[0]-cnt[1])%4==2){
            cout<<"-1\n";
            return;
        }
    }
    string ans;// buffer to process 's' into ans
    int cnt = 0;
    for(auto&c:s){
        ans+=c;
        if(ans.size()>1&&ans[ans.size()-1]==ans[ans.size()-2]){
            // store '((' and '))' as cnt instead
            ans.pop_back();
            ans.pop_back();
            cnt++;
        }
    }
    // at this point ans will be either '()()()' or ')()()(' format
    // odd-length is impossible
    if(!ans.empty() && ans.front()==')' && cnt==0){
        // can't remove front ')' and back '('
        cout<<"-1\n";
        return;
    }
    if(cnt){// cnt is always multiple of 2
        /** 
         * wrap ans to make it valid,
         * previously valid t will still be valid
         */
        ans = "((" + ans + "))";
        cnt-=2;
    }
    // prints ans and the rest of the unused bracket (stored in cnt).
    cout << ans << string(cnt,'(') << string(cnt,')') << '\n';
}

_I_hate_Summer_

Can you explain why any occurence of "((" or "))" can be moved into any index we like?

seeforty4040

it suffices to show for moving just one step right for ((, if the next one is open bracket then: '(('(---->('((' otherwise next one is closed bracket: '((')---->'))')---->)'))'---->)'(('

Arnav_Singhal1

In problem E,I tried this solution we can always swap i and i+2 character as if they are same no need of swap else middle character is same as one of them and we can swap. So if we somehow manage to make counts of open brackets and closed brackets same, we can sort the string on odd positions and even positions separately and then check if the resulting string is valid. But I don't have a proof of why it works.339182646

bladewaltz

After sorting odd and even positions, your sequence will look like (((( )()( )))) or (((( ()() )))) where the first part consists of an even number of '('s and the last part consists of an even number of ')'s, and in the middle '('s and ')'s appear alternately.
Since counts of '('s and ')'s are the same, the first part and the last part have the same number of brackets. And the only situation that the answer's a NO is when the sequence is )()...()( , which can be checked by your program.

Engulf

Can anyone explain why this dp method for D cannot pass the last testcase of sample?

11
7 2 1 9 7 3 4 1 3 5 3

f[i][0] denotes the number of subsequences that ends with i, with no descending elements f[i][1] denotes the number of subsequences that ends with i, with only 1 descending elements

TeletubiGaim33

← Rev. 3 →

You might not be counting a subsequence like 7 2 9 7.

I wrote the same dp and then realised this

Thank you

EndpoInt

thank you sir for fast editorial

jarvis22

How to write problem E's special judge?

zztqwq

Same question, is there any principle/algorithm to judge if the original string can be transformed to the answer string?

If it does have, there might be some simpler answer to this problem.

i think if u see my answer, it's very simple to create the judge code.
but I don't have formal proof.
my solution

your solution is the same as mine, but I can't prove it is the only way (by moving "((" and "))") to construct the answer either :(

with intuition, I claim that
1. "((" "))" moving
2. "((" tranform "))" and vice versa
encompasses all possible operation.
other interpretation of this problem is a derivative of these 2 operations.
therefore all answer/possible solution can be constructed.

my idea would be to count how many () occurs + if there is a obligation to make
THE ONE (()()) [or the longer version with () inserted between ).(]
all other valid permutation of (( )) is accepted.

LucaLucaM

Use the invariant described in the editorial: Flip brackets on even positions then check if the number of open brackets is the same in s and t

fugazi_zeitgeist

(IMO) easier solution for E : observe that any bracket can be made to "jump" over adjacent opposite brackets in increments of 2, for instance, "(()" can be transformed to ")((", "()((" can be transformed to "((()", etc. It's easy to convince yourself that this can't happen in odd increments.

That gives us the following construction : transform as many "))" into "((" as possible (we will flip some of these back at the end if needed), leaving us with some closing brackets. If we can move all these closing brackets as close to the right end of the sequence as possible while only using even jumps (which is optimal since any other reachable sequence with these closing brackets earlier can be transformed into our construction, also with even jumps), we can check if the sequence can then be made balanced by flipping some of the earlier opening brackets in sets of 2. There can be many ways to do this and there are some annoying edge cases, but I found simulating this process in O(n) to be simpler than the editorial.

Hot take

that is what my solution and zztqwq said

Yup exactly this, though your implementation's much better (I just simulated the process like a caveman, much more code)

your comment doesn't prove that it is the only way to construct the answer however

I think for the string after the initial transformation of flipping "((" to "))" wherever possible, this construction is clearly optimal right? Since we take the last possible position for each of the closing brackets that is possible, if an answer does not exist here for any reason other than parity, we can't do any better

your comment does create an answer, but our problem is that how to write the special judge, you cannot prove the way to move (( and )) is the only construction

Ok, makes sense, I didn't realize the discussion was about the checker, but I think this can work as a judge too.

After moving all unpaired closing brackets to the front and cancelling any pairing, we'll be left with some closing brackets which only exist in one parity of indices, which will be the smallest number of closing brackets we simply must have which can't be adjacent. If you then move these as far back as possible and then flip the latest possible pairs of opening brackets, that should give you a unique answer since none of these closing brackets can appear any later.

The judge can simply be to apply this transformation to both the test case and the participant's solution and check for equality of the strings.

ariloc

It seems to be that $$$O(n^2 \log^2 n)$$$ solutions are also Accepted for Problem D2. I just upsolved the problem with a 2D Fenwick Tree instead of keeping separate Fenwick Trees for each dimension (339196787).

I also noticed that there's no need to store all updates and do them at the end, as the updates from one kind (row or line) don't overlap with the queries of the other kind in the matrix. Only positions $$$[a_i,0:a_i]$$$ and $$$[a_{i+1} : n, a_i]$$$ are updated for each kind respectively, therefore updates of one kind can be done in order without changing the result of the queries when processing the other kind.

hxano

Can someone hack my solution for E? 339199726

I tried to bruteforce to see if any patterns would come up, but then noticing it was running a bit too fast, I submitted and got AC. The time complexity seems to be $$$O(n)$$$ either $$$O(n^2)$$$.

dinklydoo

I didn't participate live but I'm going through problemset now,

for C I think topo-sort is not necessary, my solution includes creating a DLL with node pointers at each indices and greedily manipulating the prev/next pointers based on max(x,y). I keep my DLL sorted L->R where L is minimal index and R is maximal index. As we have a tree there will never be a cyclic dependency chain where d[a] < d[b], d[b] < d[c] and we encounter d[c] < d[a] so we can always insert based on max(x,y).

After construction of DLL I just create a deque and iterate setting each index incrementing from 1.

Take a look at my solution in profile if your interested.

esh_war2

Tried something similar .

liuyan1217

wow,so quick!wonderful

ashish1729

wow I find dp state for D1 a bit complicated, is there any other state ideas ?

Although I am quite curious that so many people solved it , is it some standard DP form which is used for subsequences ?

Dawg how are you back to specialist after 10 years of coding

aaarrrhhhh!!! please help.

only god can help you twin, thoughts and prayers with you

Take a look at my solution: https://codeforces.me/contest/2143/submission/339174828

Basically, we can identify each sub-sequence by two parameters. Its max element (mx1), and max element that has a bigger element to its left (mx2) (and that bigger element does not have an even bigger element to its left, as that will make the sub-sequence invalid). In 5 6 4 8 7, we have 8 as the max element, 7 as the max element with a bigger element (8) on its left.

We need these two params because we want to count all sub-sequences with LDS at most 2. If we were to count for LDS at most 3 then we will need 3 params, max, max with a bigger one to its left, max with a bigger one to its left that has an even bigger one to its left.

Now, suppose we have processed till index i-1 and we have count of all the sub-sequences of a[0..i-1], each stored at dp[mx1][mx2]. Also, note that mx1 > mx2 holds true for any sub-sequence. We want to process a[i]. The dp in its current state holds all sub-sequences of a[0..i] that exclude a[i] and we want to change the states so it accounts for a[i] too.

For all the sub-sequences that have mx1 <= a[i], we will have newer sub-sequences that have mx1 = a[i]. Note that a[i] is the global max element of this newer sub-sequence, so it cannot affect mx2 in any way, it cannot be the new mx2. We do dp[a_i][mx2] += a[mx1][mx2].

For all sub-sequences that have mx2 <= a[i] < mx1, we will have never sub-sequences that have the same mx1, but mx2 will change to a[i]. This is because we know that mx1 is bigger than a[i] and occurs to its left. And, a[i] >= mx2 so it will now be the max element that has a bigger element to its left.

After doing this update for each pair of (mx1, mx2), dp will now contain count of all sub-sequences of a[0..i] for each pair. After processing all the a[i], we can simply count the no. of sub-sequences for each pair of configuration (mx1, mx2).

I initialize dp[1][0] = 1 because we want the invariant mx1 > mx2 to hold true. And, for any sub-sequences, having mx1 = 1 will not affect the solution negatively. We can initialize with dp[0][0] = 1 but then we will need to change the inner for loop to iterate till mx2 <= mx1, instead of mx2 < mx1.

Also, dp[mx1][0] stores count of sub-sequences that have mx1 as its max element, but there is no mx2. This means the sub-sequence is non-decreasing.

thanks for sharing this I will try to read it and understand.

fucio

Explained much better than the editorials, thanks a lot, and clean code too

Can you accept my connection?

alpha_6124

Any recursive dp solution for D2

I believe someone would have problems on D1.We need to clarify one fact:m is the real biggest element,but mp is not.for example, a sequence like 2 3 1, dp[3][3][1] = 2, it contains 3 1 and 2 3 1.I think we need to think about it.

zubaerislam703

Really Helpful. Thanks for gives us such a great contest . I really enjoyed this contest to solve the problem.

lakshyasinghal006

Could anyone please explain why can't we just subtract the number of subsequences having LDS of at least 3 from 2^n in D1?? Or is my way of counting incorrect ??

I am getting WA on 4th test of sample tests

Code:

I think you're counting them incorrectly. Here's a shorter counterexample I found testing my solution against yours:

5
5 3 1 4 3

Yours returns 26, but it should return 25. These are $$$7$$$ invalid subsequences:

$$$[5,3,1]$$$
$$$[5,3,1,4]$$$
$$$[5,3,1,4,3]$$$
$$$[5,3,1,3]$$$
$$$[5,4,3]$$$
$$$[5,3,4,3]$$$
$$$[5,1,4,3]$$$

If I'm not mistaken, yours is failing when counting all subsequences containing $$$[5,4,3]$$$. There, you have to count $$$[5,3,4,3]$$$ and $$$[5,1,4,3]$$$, but not $$$[5,3,1,4,3]$$$. This happens because pu1 = 2 instead of 1 at that moment, since you've already counted subsequences containing $$$[5,3,1]$$$.

oh i see.. Thank you for the shorter counter example :') I'll try to correct my code

blazy

For problem D1, why does the author transform input array b into equivalent permutation a? And if there are duplicates in the original array, how to decide which occurrence is "greater" or "lesser" than the other?

MIRAJ12

11 months ago, hide # |

D1 and D2 are bothering me a lot. I had a solution during the contest, but it gave WA on test case 3. (So obviously I either misunderstood the problem or my logic is not correct)

I thought I could just add at most 2 disconnected components. Also an increasing sequence a < b < c as a component. Also a single component is always good.

Example : (4 5 6 7 | 3 3 4 5) (r r r r | b b b b)

so I wrote:

So can anyone please tell me why I’m getting WA?

AntaraAn

// #include // #include // #include // using namespace std;

// int minimalCost(vector &a, vector &b, int n, int k) // { // sort(a.begin(), a.end(), greater()); // sort(b.begin(), b.end()); // int i = 0; // int j = 0; // int minCost = 0; // while (i < n && j < k) // { // for (int p = 0; p < b[j] — 1; p++) // { // if (i + p < n) // minCost += a[i + p]; // } // i += b[j]; // j++; // }

// while (i < n) // { // minCost += a[i]; // i++; // }

// return minCost; // }

// int main() // { // int t; // cin >> t; // while (t--) // { // int n, k; // cin >> n >> k; // vector a(n); // vector b(k); // for (int i = 0; i < n; i++) // cin >> a[i]; // for (int i = 0; i < k; i++) // cin >> b[i]; // cout << minimalCost(a, b, n, k) << endl; // } // return 0; // }

Can someone tell me why I get wrong answer for this(Discount problem)!?

notakshattahskaton

In D1, I am trying a state like dp[i][j] which stores number of good subsequences till ith index with max number as j. I dont know, how is it overcounting, unable to think why, could somebody please help?

My code: https://pastebin.com/4C7BMxKX

ice_king

2d fenwick tree passes d2

https://codeforces.me/contest/2143/submission/339318285

bro_wtf

got absolutely cooked in D1. I can only imagine how hard is D2

rogger004

← Rev. 5 →

.....

manika12

-15

Dear Coordinators, I received an email regarding significant coincidence between my solution ( 339142917) and others for problem 2143C.That one person i don't even know. I want to assert that my solution was developed independently. The core of my approach involved observing that the pairwise comparisons ($$$u$$$ vs. $$$v$$$ based on $$$x$$$ and $$$y$$$) establish a relative order between the nodes. This is a classic relationship that immediately suggests modeling the problem as a Directed Acyclic Graph (DAG) and using Topological Sort (Kahn's Algorithm) to find a valid assignment of ranks.

Topological Sort is a standard algorithmic technique, and its application to this problem is, in my view, the most intuitive and straightforward path to a correct answer. It is highly probable that other strong contestants would arrive at the same natural approach independently. I can confirm I did not share my code, nor did I use any public sources or external materials other than standard C++ libraries.

luffy_sama_106

9 months ago, hide # |

my logic is correct and giving correct for test case but failing on test case 2. Plz help

mariza_CY

9 months ago, hide # ^ |

(These are based on your latest submission)

Hint: Check your submission: It says you get out of bounds error in the line highlighted with red (cost += a[j];). Why?

Answer

Fix

Thanks alot man I didnt knew we could see test case 2 in submission

Thanks for that tooo

Shoeib

8 months ago, hide # |

F is a cool XOR Basis problem

6 weeks ago, hide # |

for problem E ; I have checked the initial constraints related to parity since parity , n as even : if fails then "NO" o.w. possible after the checks ,since we can just reverse in pairs so I reversed wherever necessary to make the count of odd and even equal: now the problem reduces to shifting lets say it is an alternating sequence then it is already valid if it is not then it will have either "))" or "((" , it can be proved that either of them can be shifted to left or right , so from the given string I take all "((" in string open , all "))" in string close since all the pairs are taken the remaining sequence is alternating (call it mid) so the final answer return op+mid+cl with a final check if there is no op and the mid starts from close braket

383822507

#	User	Rating
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

#	User	Contrib.
1	Qingyu	158
2	maspy	150
3	Um_nik	146
4	Errichto	139
5	adamant	136
6	maroonrk	134
7	DNR	133
8	Dominater069	131
9	Proof_by_QED	130
9	AmShZ	130

LucaLucaM's blog