Разбор Educational Codeforces Round 131

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	157
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	Petr	145
9	pajenegod	145

Разбор

Решение (vovuh)

for _ in range(int(input())):
    a = [list(map(int, input().split())) for i in range(2)]
    cnt = sum([sum(a[i]) for i in range(2)])
    if cnt == 0:
        print(0)
    elif cnt == 4:
        print(2)
    else:
        print(1)

1701B - Перестановка

Идея: BledDest

Разбор

Решение (Neon)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    cout << 2 << '\n';
    for (int i = 1; i <= n; ++i) if (i % 2 != 0)
      for (int j = i; j <= n; j *= 2)
        cout << j << ' ';
    cout << '\n';
  }
}

1701C - Организация расписания

Идея: BledDest

Разбор

Решение (awoo)

#include <bits/stdc++.h>

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

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int n, m;
		scanf("%d%d", &n, &m);
		vector<int> a(m);
		forn(i, m){
			scanf("%d", &a[i]);
			--a[i];
		}
		vector<int> cnt(n);
		forn(i, m) ++cnt[a[i]];
		auto check = [&](int t){
			long long fr = 0, need = 0;
			forn(i, n){
				if (t >= cnt[i])
					fr += (t - cnt[i]) / 2;
				else
					need += cnt[i] - t;
			}
			return need <= fr;
		};
		int l = 0, r = 2 * m;
		int res = -1;
		while (l <= r){
			int m = (l + r) / 2;
			if (check(m)){
				res = m;
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		printf("%d\n", res);
	}
	return 0;
}

1701D - Восстановление перестановки

Идея: BledDest

Разбор

Решение (Neon)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int& x : b) cin >> x;
    vector<pair<int, int>> ev(n);
    for (int i = 0; i < n; ++i)
      ev[i] = {(i + 1) / (b[i] + 1) + 1, i};
    sort(ev.begin(), ev.end());
    set<pair<int, int>> s;
    int j = 0;
    for (int i = 1; i <= n; ++i) {
      while (j < n && ev[j].first == i) {
        int id = ev[j++].second;
        s.insert({b[id] ? (id + 1) / b[id] : n, id});
      }
      a[s.begin()->second] = i;
      s.erase(s.begin());
    }
    for (int& x : a) cout << x << ' ';
    cout << '\n';
  }
}

1701E - Текстовый редактор

Идея: vovuh

Разбор

Решение (vovuh)

#include <bits/stdc++.h>

using namespace std;

vector<int> zf(const string &s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            ++z[i];
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        string s, t;
        cin >> n >> m >> s >> t;
        
        int ans = 1e9;
        
        bool bad = false;
        vector<int> lpos(m), rpos(m);
        for (int i = 0; i < m; ++i) {
            if (i > 0) {
                lpos[i] = lpos[i - 1] + 1;
            } else {
                lpos[i] = 0;
            }
            while (lpos[i] < n && s[lpos[i]] != t[i]) {
                ++lpos[i];
            }
            if (lpos[i] >= n) {
                bad = true;
                break;
            }
        }
        for (int i = m - 1; i >= 0; --i) {
            if (i + 1 < m) {
                rpos[i] = rpos[i + 1] - 1;
            } else {
                rpos[i] = n - 1;
            }
            while (rpos[i] >= 0 && s[rpos[i]] != t[i]) {
                --rpos[i];
            }
            if (rpos[i] < 0) {
                bad = true;
                break;
            }
        }
        if (bad) {
            cout << -1 << endl;
            continue;
        }
        
        for (int pos = 0; pos <= n; ++pos) {
            string tmp = s.substr(0, pos);
            reverse(tmp.begin(), tmp.end());
            tmp += "#" + t;
            reverse(tmp.begin() + pos + 1, tmp.end());
            vector<int> z = zf(tmp);
            for (int suf = 0; suf <= m; ++suf) {
                if (pos - suf < 0) {
                    continue;
                }
                if (suf < m && rpos[suf] < pos) {
                    continue;
                }
                if (suf - 1 >= 0 && lpos[suf - 1] > pos) {
                    continue;
                }
                int rg = 0;
                if (suf != 0) {
                    int sum = (pos - z[pos + 1 + m - suf]) + (pos - suf);
                    rg = (sum != 0) + sum;
                } else {
                    rg = pos;
                }
                ans = min(ans, (n - pos) + rg);
            }
        }
        cout << ans << endl;
    }
    
    return 0;
}

1701F - Точки

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;
const int M = 200001;

typedef array<long long, 3> vec;
typedef array<vec, 3> mat;

vec operator+(const vec& a, const vec& b)
{
    vec c;
    for(int i = 0; i < 3; i++) c[i] = a[i] + b[i];
    return c;
}

vec operator-(const vec& a, const vec& b)
{
    vec c;
    for(int i = 0; i < 3; i++) c[i] = a[i] - b[i];
    return c;
}

vec operator*(const mat& a, const vec& b)
{
    vec c;
    for(int i = 0; i < 3; i++) c[i] = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            c[i] += a[i][j] * b[j];
    return c;
}

mat operator*(const mat& a, const mat& b)
{
    mat c;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            c[i][j] = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                c[i][k] += a[i][j] * b[j][k];
    return c;
}

mat F = {vec({1, 0, 0}), vec({1, 1, 0}), vec({1, 2, 1})};
mat B = {vec({1, 0, 0}), vec({-1, 1, 0}), vec({1, -2, 1})};
mat E = {vec({1, 0, 0}), vec({0, 1, 0}), vec({0, 0, 1})};

vec S = {1, 0, 0};
vec Z = {0, 0, 0};

vec t[4 * N];
mat f[4 * N];
bool active[4 * N];
bool has[N];
int d, q;

vec getVal(int v)
{
    if(!active[v]) return Z;
    return f[v] * t[v];
}

void recalc(int v)
{
    t[v] = getVal(v * 2 + 1) + getVal(v * 2 + 2);    
}

void build(int v, int l, int r)
{
    if(l == r - 1)
    {
        f[v] = E;
        t[v] = S;
        active[v] = false;                 
    }
    else
    {
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
        f[v] = E;
        recalc(v);
        active[v] = true;               
    }
}

void push(int v)
{
    if(f[v] == E) return;
    t[v] = f[v] * t[v];
    f[v * 2 + 1] = f[v] * f[v * 2 + 1];
    f[v * 2 + 2] = f[v] * f[v * 2 + 2];
    f[v] = E;
}

void updSegment(int v, int l, int r, int L, int R, bool adv)
{
    if(L >= R) return;
    if(l == L && r == R)
    {
        if(adv) f[v] = F * f[v];
        else f[v] = B * f[v];
        return;
    }
    push(v);
    int m = (l + r) / 2;
    updSegment(v * 2 + 1, l, m, L, min(m, R), adv);
    updSegment(v * 2 + 2, m, r, max(m, L), R, adv);
    recalc(v);
}

void setState(int v, int l, int r, int pos, bool val)
{
    if(l == r - 1)
    {   
        active[v] = val;
        return;
    }
    push(v);
    int m = (l + r) / 2;
    if(pos < m)
        setState(v * 2 + 1, l, m, pos, val);
    else
        setState(v * 2 + 2, m, r, pos, val);
    recalc(v);
}

void addPoint(int x)
{
    int lf = max(0, x - d);
    int rg = x;
    if(lf < rg)
        updSegment(0, 0, M, lf, rg, true);
    setState(0, 0, M, x, true);        
}

void delPoint(int x)
{
    int lf = max(0, x - d);
    int rg = x;
    if(lf < rg)
        updSegment(0, 0, M, lf, rg, false);
    setState(0, 0, M, x, false);        
}

void query(int x)
{
    if(has[x])
    {
        has[x] = false;
        delPoint(x);
    }
    else
    {
        has[x] = true;
        addPoint(x);
    }
    vec res = getVal(0);
    printf("%lld\n", (res[2] - res[1]) / 2);
}

int main()
{
    scanf("%d %d", &q, &d);
    build(0, 0, M);
    for(int i = 0; i < q; i++)
    {
        int x;
        scanf("%d", &x);
        query(x);
    }
}

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

Показать архивные | Написать комментарий?

haiender288

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

← Rev. 2 →

+13

Please make more rounds like this one, they make me feel a bit better about myself

→ Ответить

beethoven97

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

+42

Me too

lis05

orz

death_bringer

-43

Please No more binary search :(. I'm bad at identifying binary search in the wild. If someone suggests me to use binary search then I'm able to solve the problem easily but when I encounter them in the wild they ravish me. Any suggestion on how to handle them?

adityagamer

+27

Just think that someone has suggested you to use binary search

quater_nion

correct xd

Rukashi

ye, me too. i just love the concept behind each problem :3

lmqzzz

+19

can someone explain the idea of problem E with DP pls, I've seen many solutions with an array like f[N][3] or f[N][N][3], can anyone explain the approach pls.

BucketPotato

+95

(sorry if this is a bit long/confusing, I'm not the most experienced at explaining)

First off, imagine choosing some subset of the letters in $$$s$$$ that form $$$t$$$: for example if $$$s$$$ is zzzabczzz and $$$t$$$ is abc, then the abc is useful but all the zs are useless fluff.

Then you want to delete all the fluff. Here's one approach: first, you delete fluff from the end of the string until you come to useful letters. Then, you iterate past the useful letters, until you come to more fluff to delete. Repeat until all the fluff is gone.

This may not always be optimal, for example if $$$s$$$ is zaaaa and $$$t$$$ is aaaa: then you want to go to the start, go forward, and delete the singular z.

When you're deleting fluff from the back, it takes $$$1$$$ operation to iterate past useful letters and $$$1$$$ operation to delete the fluff. When you delete fluff from the beginning, it takes $$$1$$$ operation to iterate past useful letters, but $$$2$$$ operations to delete fluff (you need to iterate forward then delete).

Then, the optimal solution will look something like this: there is some prefix (possibly empty) of the string where you've deleted from the beginning, then some contiguous segment of useful letters you haven't iterated over, and finally, some suffix of the string where you've deleted from the end.

If the prefix isn't empty, then it needs $$$2x+y+1$$$ operations, where $$$x$$$ is the number of fluff characters in the prefix, and $$$y$$$ is the number of useful characters. Otherwise it takes $$$0$$$ operations.

Next, the contiguous segment of useful letters, this takes $$$0$$$ operations since you don't iterate over it at all.

Finally, for the suffix, it takes $$$x+y$$$ operations.

At least in my solution, the dp[3][N] was something like this: 0 for the prefix, 1 for the contiguous segment, and 2 for the suffix. The transitions were somewhat tedious to implement but fairly straightforward.

+12

Thanks! P/S : It's a very nice explanation.

isirazeev

I really liked problem E, the solution is very interesting for me(also like a problem)

aditm

In the problem E's editorial while calculating the answer for prefix, the substring notations used were t[0;m-suf] and s[0;n-pos], then acc to editorial we have to build the z-function on $$$s[0;pos)^{-1}$$$ + # + $$$t^{-1}$$$, shouldn't it be n-pos instead of pos?

vovuh

Yeah, this is a typo. It should be $$$s[0; pos)$$$ and $$$t[0; m - suf)$$$. Thanks.

In the second para there is a typo I guess then, the suffixes rather being $$$s[n-pos,n)$$$ and $$$t[m-suf,suf)$$$, shouldn't it be $$$s[pos,n)$$$ instead ? I am confused about pos, is it assumed as a forward iterator or a backward iterator?

Yeah, it is $$$s[pos; n)$$$. Forgot to fix that along with previous typos.

epsilon_573

Video Solutions of Problem C and Problem D.

Btw F can be solved using SQRT decomposition on queries in $$$O(NsqrtN)$$$

submission

TheLostCookie

+33

One way of doing F without storing $$$f(i)^2$$$ would be to observe that $$$\frac{(f(i)+1)f(i)}{2} - \frac{f(i)(f(i)-1)}{2} = f(i)$$$. In other words, if a point is added in its range, the change in its contribution to the answer is simply $$$f(i)$$$. Thus, for each point $$$i$$$, we can store only two values: whether it is currently in the set, and what its value of $$$f(i)$$$ is.

To change the answer when a point $$$j$$$ is added, it suffices to query the sum of $$$f(i)$$$ over the interval $$$[j-d,j)$$$ and to calculate the value of $$$f(j)$$$ itself by querying how many points in $$$(j,j+d]$$$ are in the set. Removing a point works similarly.

Xhnxhn

I have a solution to problem C in linear time.163331694

CharlesWuQiushi

← Rev. 3 →

+40

There's an $$$\mathrm{O}(q\log q)$$$ solution for Problem F with balanced search trees (Splay, Treap, etc).

We may consider new/deleted beautiful triples when point $$$x$$$ is added/deleted from the set as three parts, in which:

$$$x$$$ is treated as the right endpoint;
$$$x$$$ is treated as the left endpoint;
$$$x$$$ is caught in the middle.

It's quite simple to calculate the first two types, since we may find the number of $$$y$$$'s that satisfy $$$y \in (x-d, x)$$$ or $$$y \in(x, x+d)$$$, then add two arithmetic progressions of common difference $$$1$$$. But we find it not very easy to add the number of type 3 triples instantly. So it's necessary to maintain 'if we add/delete point $$$x$$$ from the set, the number of $$$x$$$-as-the-middle triples being added/deleted' in some way.

Let's discuss how many triples will turn invalid when we remove a point from the set. One may notice that if we're adding $$$x$$$ to the set $$$S$$$, then for each $$$y \in S, y \in (x-d, x)$$$, for every point $$$z$$$ satisfying $$$z \in [x-d, y), z \in S$$$, $$$(z, y, x)$$$ will be a new beautiful triple in which $$$y$$$ sandwiching in between $$$x, z$$$. Let $$$c_y$$$ be the number of such $$$z$$$'s for each $$$y$$$. Obviously if we consider all valid $$$y$$$'s in increasing order (denoting $$$x-d<y_1<y_2<\cdots<y_k<x$$$), then $$$c_{y_i}=i-1$$$. It's similar for $$$y \in (x, x+d)$$$. Thus we may maintain set $$$S$$$ with a binary search tree, and add arithmetic progressions on a specific segment — which is a classic trick — when adding an element to $$$S$$$. Once we want to remove a point $$$x$$$ from the set, substract the number of first 2 types along with the count of type 3 triples from the answer, which we've stored on the BST. Also, its deletion will lead to a negative contribution of $$$c_{y_i}$$$ for all valid $$$y$$$'s mentioned above, so don't forget to add the opposite number of a progression on the BST maintaining $$$S$$$.

The next part is considering 'if $$$x$$$ is not in the set, how many $$$x$$$-in-the-middle triples will turn valid after adding it'. Suppose we're adding $$$x$$$ to the set $$$S$$$. We still consider $$$x-d<y_1<y_2<\cdots<x$$$; then for each $$$i \in \lbrace{1,2,\cdots,k-1}\rbrace$$$, for all $$$z \in (y_i,y_{i+1})$$$, $$$(y_j,z,x), j \in \lbrace{1,2,\cdots,i}\rbrace$$$ will be new beautiful $$$z$$$-in-the-middle triples if $$$z$$$ is added after $$$x$$$. It's obvious that for all $$$z$$$ in the same segment whose endpoints are adjacent $$$y$$$'s, the numbers of potential new valid triples are the same. Similarly, for each segment, the sequence of new potential valid triples is an arithmetic progression of common difference $$$1$$$. Thus we may use another BST to maintain all segments $$$(l,r), l\in S, r\in S, \nexists p \in S, p \in (l,r)$$$ and proceed the sum of progressions. If we want to add $$$x$$$ to set $$$S$$$, then add the sum of contributions of type 1 & 2 triples and the segment's to the answer, split the segment it belongs to to two (empty segments should be preserved), and do operations above.

When removing $$$x$$$ from $$$S$$$, we may first add the opposite number of contributions of $$$x$$$ on two BST. What about merging two segments on the second BST? Do they have the same potential new triples after $$$x$$$ is deleted? The answer is YES. Apparently, for $$$x,y$$$ in segment $$$(l, r)$$$, if $$$(p, x, q), p\leq l, q \geq r$$$ is a valid potential triple, so does $$$(p, y, q)$$$ and vice versa. So it's ok to set the contribution of new $$$(l, r)$$$ (in which $$$x$$$ has just been removed) as $$$(l, x)$$$'s.

A careful and efficient implementation is required for this solution. Submission #163416351

Sorry for any grammar/vocabulary mistakes above.

tushar_kumar

← Rev. 5 →

anyone please tell me why i am getting TLE on test case 4 in problem C . 163421348

edit — the problem accepted when i used priorty_queue instead of multiset 163422803

nicolasalba

The problem is in the method 'findMax' and 'findMin' you are copying the entire data structure each time the method is calling.

int findMin(multiset my_set) this means that the first argument will be copied, so in the worst scenario it will copy a huge data structure each time.

The solution is this add '&' before the identifier of the argument: int findMin(multiset &my_set), now the multiset won't be copied.

There are two ways to pass an argument, by reference or by coping the entire argument.

This is your solution only adding '&' in those two methods: https://codeforces.com/contest/1701/submission/163423017

I hope this could help, greeting bro

thank u

people_plus_plus

Let's calculate value of $$$\sum f(i)$$$ in every node (it's simple). If we know this sum, we can restore value of $$$\sum f^2(i) - f(i)$$$. Let's say, we already somehow calculate it after some query: $$$F(i) = \sum f^2(i) - f(i)$$$.

If we add $$$k$$$ to all $$$f(i)$$$ we need to update our $$$F(i)$$$ value. Now the right value must be equal to $$$\sum (f(i) + k)^2 - (f(i) + k)=\sum f^2(i) + k^2 + 2 \cdot kf(i) - (f(i) + k)=\sum f^2(i) - f(i) + \sum k^2 + 2 \cdot kf(i) -k$$$.

$$$\sum f^2(i) - f(i)$$$ we already know, it is $$$F(i)$$$. Let's find $$$\sum k^2 + 2 \cdot kf(i) - k$$$. Value of $$$\sum 2 \cdot k f(i)$$$ we know too, because we store value of $$$\sum f(i)$$$ in every node. Value of $$$\sum k^2 - k$$$ we can calculate if we know how many points are now "active" in our node.

So now we get $$$F(i) = F(i) + 2 \cdot k \cdot \sum f(i) + cnt \cdot (k^2 - k)$$$; $$$f(i) = f(i) + cnt \cdot k$$$, where $$$cnt$$$ equals to number of active points.

H-1

good round

Sushil07

In Problem 2, whats the difference between these two codes ?? Wrong Code- void solve() { int n;cin>>n: cout<<2<<endl;//d will be always 2

for(int i=1;i<(n+1);i++){
    if(i%2==1){
       cout<<i<<" ";
       while(i*2<=n){
         cout<<i*2<<" ";
       }
    }
    else continue;
}
cout<<endl;

}

Right Code- void solve() { int n;cin>>n; cout<<2<<endl;//d will be always 2

for(int i=1;i<(n+1);i++){
    if(i%2==1){
       int j=i;
       while(j<=n){
         cout<<j<<" ";
         j*=2;
       }
    }
}
cout<<endl;

You are not updating value of i

while(i*2<=n){
  cout<<i*2<<" ";
}

In problem D, sweep line is not needed. Simply sorting the range in increasing order of ending point is enough. AC code: https://codeforces.com/contest/1701/submission/163624301

BeruboIV

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

Why increasing order of end point and not increasing order of starting point?

You should sort in increasing order of end point because let's say if at a point there are multiple points to choose from then choosing the one which ends later may make it possible to make an answer. For example, consider the ranges [1,2],[2,2],[1,3]

Thanks understood.

It would be nice if you added some comments to the solution code for F.

berkay.ozkan

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

Problem C is quite similar to 781C — Tree Infection, and can similarly be solved by simply simulating the entire process.

drugkeeper

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

Alternative solution for C:

We just simulate the whole process, second by second. We always try to allocate the current task to the most efficient worker. If there are any free workers (they do not have any more good tasks for them), then we have to take a task from the worker with the most tasks. This suggests that we need to use a treeset for fast insert / delete in log(n) time.

The code goes like this: while we have tasks remaining, we let all the busy workers do their task first, then for the free workers, we transfer the task from the worker with the most tasks to it.

We notice that to make the free worker do a task for 2 seconds, we just skip their turn and transfer the task from the busy worker to the free worker. So the next moment that same worker will be busy and will do the task.

Submission: https://codeforces.com/contest/1701/submission/207853000

jkajhvckjab290e127hlkc

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

thanks, i have the same approach and been debugging my code since like 5 hours now, finally found what's wrong in my code by looking at yours ^_^

SXZZ5

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

And how does one prove that it is optimal to assign the workers(that do not have any good tasks for them) to go help the worker with the maximum number of remaining tasks ?

Suppose not, then it means that a worker helps someone with less than max number of remaining tasks x. Then, we did not change the worst case timing of x when we could have done so by making worker i help worker x. Thus there is a contradiction for optimality.

Okay. I think I get it. It's amazing you could recall your solution/reasoning from a 6month old problem. Thanks a lot.

Блог пользователя awoo