Разбор Educational Codeforces Round 163

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

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

1948A - Специальные символы

Разбор

Решение (Neon)

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    if (n % 2 == 1) {
      cout << "NO" << '\n';
      continue;
    }
    cout << "YES" << '\n';
    for (int i = 0; i < n / 2; ++i)
      for (int j = 0; j < 2; ++j)
        cout << "AB"[i & 1];
    cout << '\n';
  }
}

1948B - Исправление массива

Идея: BledDest

Разбор

Решение (Neon)

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    vector<int> b({a[n - 1]});
    for (int i = n - 2; i >= 0; --i) {
      if (a[i] > b.back()) {
        b.push_back(a[i] % 10);
        b.push_back(a[i] / 10);
      } else {
        b.push_back(a[i]);
      }
    }
    cout << (is_sorted(b.rbegin(), b.rend()) ? "YES" : "NO") << '\n';
  }
}

1948C - Стрелочный путь

Идея: BledDest

Разбор

Решение (Neon)

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<char> ok1(n / 2), ok2(n / 2);
    for (int i = 0; i < 2; ++i) {
      string s;
      cin >> s;
      for (int j = 0; j < n; ++j) if ((i + j) & 1) {
        ok1[(i + j) / 2] |= (s[j] == '>');
        ok2[(j - i + 1) / 2] |= (s[j] == '>');
      }
    }
    bool ans = true;
    for (int i = 0; i < n / 2; ++i) ans &= ok1[i] && ok2[i];
    cout << (ans ? "YES" : "NO") << '\n';
  }
}

1948D - Тандемные повторы?

Идея: BledDest

Разбор

Решение (awoo)

for _ in range(int(input())):
    s = input()
    n = len(s)
    ans = 0
    for d in range(1, n // 2 + 1):
        cnt = 0
        for i in range(n - d):
            cnt += s[i] == s[i + d] or s[i] == '?' or s[i + d] == '?'
            if i - d >= 0:
                cnt -= s[i - d] == s[i] or s[i - d] == '?' or s[i] == '?'
            if i - d >= -1 and cnt == d:
                ans = 2 * d
    print(ans)

1948E - Разделение на клики

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n), c(n);
    for(int i = 0; i < n; i++)
    {
        a[i] = i + 1;
        c[i] = i / k + 1;
    }
    int q = *max_element(c.begin(), c.end());
    for(int i = 1; i <= q; i++)
    {
        int l = find(c.begin(), c.end(), i) - c.begin();
        int r = c.rend() - find(c.rbegin(), c.rend(), i);
        int m = (l + r) / 2;
        reverse(a.begin() + l, a.begin() + m);
        reverse(a.begin() + m, a.begin() + r);
    }
    for(int i = 0; i < n; i++)
        cout << a[i] << " \n"[i == n - 1];
    cout << q << "\n";
    for(int i = 0; i < n; i++)
        cout << c[i] << " \n"[i == n - 1];
}
 
int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

1948F - Редкие монеты

Идея: BledDest

Разбор

Решение (Neon)

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

const int MOD = 998244353;

int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  return x;
}

int mul(int x, int y) {
  return x * 1LL * y % MOD;
}

int binpow(int x, int y) {
  int z = 1;
  while (y) {
    if (y & 1) z = mul(z, x);
    x = mul(x, x);
    y >>= 1;
  }
  return z;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n), b(n);
  for (auto& x : a) cin >> x;
  for (auto& x : b) cin >> x;
  vector<int> suma(n + 1), sumb(n + 1);
  for (int i = 0; i < n; ++i) {
    suma[i + 1] = suma[i] + a[i];
    sumb[i + 1] = sumb[i] + b[i];
  }
  int m = sumb[n];
  vector<int> f(m + 1), invf(m + 1);
  f[0] = 1;
  for (int i = 1; i <= m; ++i) f[i] = mul(f[i - 1], i);
  invf[m] = binpow(f[m], MOD - 2);
  for (int i = m; i > 0; --i) invf[i - 1] = mul(invf[i], i);
  vector<int> sumc(m + 2);
  for (int i = 0; i <= m; ++i)
    sumc[i + 1] = add(sumc[i], mul(f[m], mul(invf[i], invf[m - i])));
  int pw2 = binpow(binpow(2, MOD - 2), m);
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l;
    int k = 2 * (suma[r] - suma[l]) - suma[n];
    int cur = sumb[r] - sumb[l];
    int mx = max(0, min(k + cur, m + 1));
    int cnt = sumc[mx];
    cout << mul(cnt, pw2) << ' ';
  }
}

1948G - MST с паросочетанием

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>

using namespace std;

int n, c;
int g[21][21];

const int INF = int(1e9);

int primMST(int vertex_cover_mask)
{
    vector<int> d(n, INF);
    vector<bool> used(n, false);
    d[0] = 0;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int idx = -1;
        for(int j = 0; j < n; j++)
        {
            if(!used[j] && d[j] < INF && (idx == -1 || d[j] < d[idx]))
                idx = j;
        }
        if(idx == -1) return INF;
        used[idx] = true;
        ans += d[idx];
        for(int k = 0; k < n; k++)
        {
            if(used[k]) 
                continue;
            if((vertex_cover_mask & (1 << idx)) == 0 && (vertex_cover_mask & (1 << k)) == 0)
                continue;
            d[k] = min(d[k], g[idx][k]);
        }
    }
    return ans;
}

int main()
{
    cin >> n >> c;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> g[i][j];
            if(g[i][j] == 0) g[i][j] = INF;
        }
    }
    int ans = INF;
    for(int mask = 0; mask < (1 << n); mask++)
    {
        int cur = primMST(mask);
        if(cur != INF) ans = min(ans, cur + c * __builtin_popcount(mask));
    }
    cout << ans << endl;
}

1948C - Arrow Path The key observation for this problem that works for all these approaches is that, since we never skip a move and never try to move outside the grid, we can split the cells into two groups: if the sum of coordinates of the cell is even (we will call it "even cell"), we can end up in such a cell only after moving along the arrow (only after the second action during each second); otherwise, if the sum of coordinates of the cell is odd (we will call it "odd cell"), we can end up in such a cell only after making a move on our own (only after the first action during each second).

Комментарии (54)

Написать комментарий?

ttmasoi

8 месяцев назад, # |

Did you place a same tutorial for G as F?

→ Ответить

realizeee

In problem B why do we need to iterate through array from right to left and not from left to right?

denk

8 месяцев назад, # ^ |

← Rev. 4 →

Counterexample:

12 46 20

If we will iterate from left to right we will get:

1) 12 < 46. Don't change the array

2) 46 > 20. Split 46 by 4 and 6

And we got:

12 4 6 20. Which is not a non-growth sorted array.

If we will iterate from right to left we will get:

1) 46 > 20. Split 46 by 4 and 6

2) 12 > 4. Split 12 by 1 and 2

1 2 4 6 20. Which is a non-growth sorted array.

Summary, iterating from left to right will give us the wrong answer. This is because the right element can split and become smaller than the left element, but we have already checked that the left element is larger than the right element and will not go back to check it again.

thx

guntarakesh971

Nice Explanation , Thanks

BledDest

Suppose initially $$$a_{i-1} \le a_i$$$; but after considering $$$a_i$$$ with $$$a_{i+1}$$$, we find out that we have to split $$$a_i$$$. This might break the condition $$$a_{i-1} \le a_i$$$, so if we iterate from left to right, we sometimes have to backtrack to fix the conditions we've broken

darishkhan

You can go from left to right also. My logic while going from left to right: https://codeforces.me/contest/1948/submission/251609551

^read lastDigit as lastNumber

Vanjanja

I solved the problem by iterating from left to right with following logic: you want current element (CUR which can also be last digit if we divided the number in previous step) to be as small as possible because that can only help for next numbers, so you have two cases: 1) if you CAN divide current element i into it's digits with equality holding: CUR <= dig1 <= dig2 you do so, because then CUR = dig2 which is smallest possible. If you can't, if CUR <= a[i] then CUR = a[i]. If both do not hold, return NO. This works because at any moment, last element you have in your new array will be smallest possible which can only help for both of previously mentioned checks.

gaurav03kr

← Rev. 2 →

I write a simple brute force for Problem :B. But it is failing of hidden case.I am not able guess what it lacks. Can you please help. https://ideone.com/g5da0S

you are iterating from left to right , as explanied in above comment ( https://codeforces.me/blog/entry/127182#comment-1128987 ) iterate from right to left then it might results in correct answer.

Coder_Nayak

In the place of tutorial of G ,it is showing tutorial of F.Update it please.

awoo

Fixed it, sorry.

Mr.Whitebird

is it possible to solve Div2-D in less than O(n^2)?

elseecay

Верующие на месте?

manaskesh

Can someone please explain in solution of problem C. What are ok1 and ok2 actually signifying? How are we taking the indices of ok1 and ok2.

I have been trying to understand for an hour, please help.

$$$ok1[i]$$$ and $$$ok2[i]$$$ refer to the second solution from the editorial. If $$$ok[i]$$$ is true, then the $$$i$$$-th diagonal pair of odd cells has at least one arrow to the right ($$$ok1$$$ and $$$ok2$$$ denote different diagonal directions).

You can instead check every diagonal pair by bruteforcing all pairs of adjacent odd cells.

Xiyy

7 месяцев назад, # ^ |

but if n=4 and i,j=0,3.then (j-i+1)/2=2.ok2.size() is 2,so will cross the border?

9inai

I thought D was hashes, wasnt able to implement it well tho... The author's solution is kinda weird

_Kee

Let me explain my solution of D -- I hope this might be easier to understand.

First, let's fix the length of a tandem, and call it $$$2d$$$ ($$$d$$$ is the length of each half of the tandem). For each $$$d$$$, we try to find a tandem repeat of length $$$2d$$$, and the answer to the problem is the length of the longest one we could find. Also let's define the length of $$$s$$$ as $$$n = |s|$$$.

A substring $$$s_l s_{l+1} \cdots s_{l + 2d - 1}$$$ is a tandem repeat if, for all indices $$$i \in \{ l, l+1, \ldots, l+d-1 \}$$$, $$$s_i = s_{i+d}$$$ is held. So, what matters here is the relationship between characters with distance $$$d$$$. With that in mind, let's define an array $$$\{ a_i \} \; (1 \le i \le n - d)$$$ as follows: $$$a_i = 1$$$ if $$$s_i = \text{'?'}$$$ or $$$s_{i+d} = \text{'?'}$$$ or $$$s_i = s_{i+d}$$$; $$$a_i = 0$$$ otherwise. Intuitively, $$$a_i$$$ is $$$1$$$ if $$$s_i$$$ and $$$s_{i+d}$$$ are equal or can be made equal. With this array $$$\{ a_i \}$$$, we can rephrase the condition that $$$s_l s_{l+1} \cdots s_{l + 2d - 1}$$$ can be a tandem repeat to: $$$a_l = a_{l+1} = \cdots = a_{l+d-1} = 1$$$ (selection of $$$\text{'?'}$$$s do not matter because each pair of letters in a tandem do not interfere with any other pairs). Thus, if there is a contiguous sequence of $$$1$$$s of length $$$d$$$ in $$$\{ a_i \}$$$, we have a tandem repeat of length $$$2d$$$; otherwise, there's no such tandem.

Building $$$\{ a_i \}$$$ and finding contiguous $$$1$$$s can be done in $$$O(n)$$$-time, so $$$O(n^2)$$$-time overall.

KietAPCS

Thank for explaining

snehasish01

nice explanation

Misuki

"Kruskal's algorithm with DSU might be a bit slower, but can also get accepted"

I don't thinks so :(

+22

I think it's possible to optimize this, for example, by sorting all edges only once, not for every Kruskal run.

Didn't think of that, thanks you!

bruce_x001

Problem D (Tandem Repeat) Video Editorial : (Audio : Hindi)

Link : ---Click Here (YOUTUBE)

Problem A, B Video Editorial : --Click Here

pramana

+28

Here's a formulation of F as a probability problem (mostly because I am in a probability class right now :3).

Suppose we have $$$s$$$ silver coins in the bag, $$$g$$$ gold coins in the bag, $$$t_s$$$ total silver coins and $$$t_g$$$ total gold coins. The value of the silver coins in the bag is represented by the random variable $$$S\sim \mathrm{Binom}(s,\frac{1}{2})$$$. The value of the rest of the silver coins is represented by the random variable $$$S'\sim \mathrm{Binom}(t_s-s,\frac{1}{2})$$$.

We wish to compute

$$$ \mathbb{P}\left(S + g> S' + t_g-g\right) = \mathbb{P}\left(S - S'> t_g-2g\right). $$$

The difference between random variables isn't nice to compute, so we want to turn it into a sum. Notice that the random variable $$$S' ':= t_s-s-S'$$$ has the same $$$\mathrm{Binom}(t_s-s,\frac{1}{2})$$$ distribution as $$$S'$$$ (this only holds because our probabilities are $$$\frac{1}{2}$$$). Therefore,

$$$ \mathbb{P}\left(S - S'> t_g-2g\right) = \mathbb{P}\left(S + S' ' > t_s - s +t_g-2g\right). $$$

But the sum of binomial random variables is itself a binomial random variable: $$$S+S' '\sim \mathrm{Binom}(t_s-s+s,\frac{1}{2}) = \mathrm{Binom}(t_s,\frac{1}{2})$$$, which gives us the formula

$$$ \mathbb{P}\left(S + S' ' > t_s - s +t_g-2g\right) = \left(\frac{1}{2}\right)^{t_s}\sum_{k=t_s - s +t_g-2g + 1}^{t_s}\binom{t_s}{k}. $$$

Here is my submission implementing this: 251836049.

Alliy666

This n^3 method passed systest. Can anyone hack it?

code

manitianajay45

Video Editorial For Problems A,B,C,D,E,F.

False.cx

Problem G is awesome. I cannot put forward Konig's theory because I didn't realize that a tree is a bipartite graph during the contest. Sad.

_Candy_Man

Can someone please a solution for problem B using DP , we need to use bit masking if i am not wrong as the value of dp[i] ( that is whether operating on the i'th elemet gives a sorted array or not ) is dependent on the set the indexes on which the operation is alredy performed i.e we need to have a mask which specify on which perticular indexs we have performed the operation , Thanks for help .

Can anyone please provide the solution of B using DP , I think we can use bit masking to solve this as the value of Dp[i] (whether performing operation on the i'th index will result in a sorted array or not ) depends on the pervious values too , so we can have a mask that denotes on which of the previous indexes we have performed the operation ,Thanks for the help .

yadavDipesh

jgsr031200

Can you take a look into this code

I did BF using recursion to find all possibilities, but a test case is failing ?

mohit2003praja

Solution of Problem C is failing for testcase: 1 4

<<

Remilia1023

Very fun problems, I like this contest!

Hiedeki

In problem B i dont understand why when i Used a variable to iterate through the inputs of the array it and manipulate using the same algorithm it didnt work , however when i accepted all inputs in a vector , and started iterating and using my algorithm it worked out ? (check my accepted solution and the rejected one Using the Second Testing table) 252372121 252375040 Would be nice if someone can explain :/

zlibigot

253317512 can someone please explain the problem of this code in the B problem because most of the cases works and I cant see the problem case

second_saturday

problem D have weak test cases

My O(N^3) solution passes : O(N^3) submission

sasanking

I have found an alternative solution to problem C only using if condition and do while loops -(https://codeforces.me/blog/entry/127853)

lucaminiati

Hi, for Problem D, when I run my code locally with the provided testcases I get the correct answer. However, when I submit, I get a different output. Any ideas what's going on? link to submission

stonk

7 месяцев назад, # |

← Rev. 3 →

Hi, can anyone explain for me why the example answer of F — rare coins is that long line of integer?

Loganwick

I am not able to understand how the parity of coordinates sum will decide the category of a cell?

TDangTK

In problem F, why we use pw2 = binpow(binpow(2, MOD - 2), m) but not pw2 = binpow(binpow(2, m), MOD - 2)? I really don't understand it, can anyone explain this for me?

im_dumb

they calculate the same thing.

remember that binpow(x, MOD — 2) is finding the inverse of $$$x$$$, which is effectively $$$1/x$$$. So binpow(binpow(2, MOD — 2), m) means $$$(1/2)^m$$$. And binpow(binpow(2, m), MOD — 2) means $$$1/(2^m)$$$

hashman

6 месяцев назад, # ^ |

$$$(2^x)^y = (2^y)^x = 2^{xy}$$$

Saucemaster102

Did anyone else solve problem d (tandem repeats) with DP?

My O(N**2) DP solution passed

Noluck_167

4 месяца назад, # |

Gotta say Tandem repeat taught me here.Good EDU problem

maddy30445r

3 месяца назад, # |

I have written dp solution for C problem....i am new in dp and only trying to solve any dp tagged prob with dp only so i tried not going towards other approach and finally was able to dpify the solution

LINK : https://codeforces.me/problemset/submission/1948/279865881