Разбор Educational Codeforces Round 103

№	Пользователь	Рейтинг
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

Идея: vovuh

Разбор

Решение (adedalic)

#include<bits/stdc++.h>

using namespace std;

int main() {
  int t; cin >> t;
  while(t--) {
    long long n, k;
    cin >> n >> k;
    
    long long cf = (n + k - 1) / k;
    k *= cf;
    
    cout << (k + n - 1) / n << endl;
  }
  return 0;
}

1476B - Инфляция

Идея: adedalic

Разбор

Решение (adedalic)

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const int INF = int(1e9);

int main() {
  int t; cin >> t;
  while(t--) {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
      cin >> p[i];
    
    li x = 0;
    li pSum = p[0];
    for (int i = 1; i < n; i++) {
      x = max(x, (100ll * p[i] - k * pSum + k - 1) / k);
      pSum += p[i];
    }
    cout << x << endl;
  }
  return 0;
}

1476C - Наидлиннейший простой цикл

Идея: adedalic

Разбор

Решение (adedalic)

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

typedef long long li;

int main() {
  int t;
  cin >> t;

  while (t--) {
    int n;
    cin >> n;
    vector<int> c(n), a(n), b(n);
    for (int i = 0; i < n; i++)
      cin >> c[i];
    for (int i = 0; i < n; i++)
      cin >> a[i];
    for (int i = 0; i < n; i++)
      cin >> b[i];
    
    li ans = 0;
    li lstLen = 0;
    for (int i = 1; i < n; i++) {
      li curLen = c[i] + 1ll + abs(a[i] - b[i]);
      if (a[i] != b[i])
        curLen = max(curLen, c[i] + 1ll + lstLen - abs(a[i] - b[i]));
      ans = max(ans, curLen);
      lstLen = curLen;  
    }
    cout << ans << endl;
  }
  return 0;
};

1476D - Путешествие

Идея: BledDest

Разбор

Решение 1 (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);

char buf[300043];

int main()
{
    int t;
    scanf("%d", &t);
    for(int _ = 0; _ < t; _++)
    {
        int n;
        scanf("%d", &n);
        scanf("%s", buf);
        string s = buf;
        vector<vector<int>> g(2 * n + 2);
        for(int i = 0; i < n; i++)
            if(s[i] == 'L')
            {
                g[(i + 1) * 2].push_back(i * 2 + 1);
                g[i * 2 + 1].push_back((i + 1) * 2);
            }
            else
            {
                g[i * 2].push_back((i + 1) * 2 + 1);
                g[(i + 1) * 2 + 1].push_back(i * 2);   
            }
        vector<int> comp(2 * n + 2, -1);
        vector<int> cnt;
        for(int i = 0; i < 2 * n + 2; i++)
        {
            if(comp[i] != -1) continue;
            int c = 1;
            int cc = cnt.size();
            queue<int> q;
            comp[i] = cc;
            q.push(i);
            while(!q.empty())
            {
                int k = q.front();
                q.pop();
                for(auto y : g[k])
                {
                    if(comp[y] == -1)
                    {
                        c++;
                        comp[y] = cc;
                        q.push(y);
                    }
                }
            }
            cnt.push_back(c);
        }
        for(int i = 0; i <= n; i++)
            printf("%d%c", cnt[comp[i * 2]], " \n"[i == n]);
    }
}

Решение 2 (BledDest)

t = int(input())

for _ in range(t):
    n = int(input())
    s = input()
    dpl = [i for i in range(n + 1)]
    dpr = [i for i in range(n + 1)]
    for i in range(n + 1):
        if i == 0 or s[i - 1] == 'R':
            dpl[i] = i
        elif i == 1 or s[i - 2] == 'L':
            dpl[i] = i - 1
        else:
            dpl[i] = dpl[i - 2]
    for i in range(n, -1, -1):
        if i == n or s[i] == 'L':
            dpr[i] = i
        elif i == n - 1 or s[i + 1] == 'R':
            dpr[i] = i + 1
        else:
            dpr[i] = dpr[i + 2]
    ans = [(dpr[i] - dpl[i]) + 1 for i in range(n + 1)]
    print(*ans)

1476E - Сопоставление шаблонов

Идея: BledDest

Разбор

Решение 1 (awoo)

#include <bits/stdc++.h>

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

using namespace std;

struct pattern{
  string s;
  int i;
};

bool operator <(const pattern &a, const pattern &b){
  return a.s < b.s;
}

vector<vector<int>> g;
vector<int> used, ord;
bool cyc;

void ts(int v){
  used[v] = 1;
  for (int u : g[v]){
    if (used[u] == 0)
      ts(u);
    else if (used[u] == 1)
      cyc = true;
    if (cyc)
      return;
  }
  used[v] = 2;
  ord.push_back(v);
}

int main() {
    cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n, m, k;
  cin >> n >> m >> k;
  vector<pattern> p(n);
  g.assign(n, vector<int>());
  forn(i, n){
    cin >> p[i].s;
    p[i].i = i;
  }
  sort(p.begin(), p.end());
  pattern nw;
  nw.s = string(k, '_');
  forn(i, m){
    string cur;
    int mt;
    cin >> cur >> mt;
    --mt;
    bool ok = false;
    forn(mask, 1 << k){
      forn(j, k)
        nw.s[j] = ((mask >> j) & 1 ? cur[j] : '_');
      auto it = lower_bound(p.begin(), p.end(), nw);
      if (it != p.end() && it->s == nw.s){
        if (it->i != mt)
          g[mt].push_back(it->i);
        else
          ok = true;
      }
    }
    if (!ok){
      puts("NO");
      return 0;
    }
  }
  used.assign(n, 0);
  cyc = false;
  ord.clear();
  forn(i, n) if (!used[i]){
    ts(i);
    if (cyc){
      cout << "NO\n";
      return 0;
    }
  }
  reverse(ord.begin(), ord.end());
  cout << "YES\n";
  forn(i, n)
    cout << ord[i] + 1 << " ";
  cout << "\n";
  return 0;
}

Решение 2 (awoo)

#include <bits/stdc++.h>

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

using namespace std;

struct pattern{
  string s;
  int i;
};

bool operator <(const pattern &a, const pattern &b){
  return a.s < b.s;
}

vector<vector<int>> g;
vector<int> used, ord;
bool cyc;

void ts(int v){
  used[v] = 1;
  for (int u : g[v]){
    if (used[u] == 0)
      ts(u);
    else if (used[u] == 1)
      cyc = true;
    if (cyc)
      return;
  }
  used[v] = 2;
  ord.push_back(v);
}

struct node{
  int nxt[28];
  int term;
  node(){
    memset(nxt, -1, sizeof(nxt));
    term = -1;
  }
};

vector<node> trie;

void add(const string &s, int i){
  int cur = 0;
  for (char c : s){
    int x = c - '_';
    if (trie[cur].nxt[x] == -1){
      trie[cur].nxt[x] = trie.size();
      trie.push_back(node());
    }
    cur = trie[cur].nxt[x];
  }
  trie[cur].term = i;
}

bool check(int i, int v, const string &s, int mt){
  if (i == int(s.size())){
    assert(trie[v].term != -1);
    if (trie[v].term != mt)
      g[mt].push_back(trie[v].term);
    else
      return true;
    return false;
  }
  bool res = false;
  if (trie[v].nxt[s[i] - '_'] != -1 && check(i + 1, trie[v].nxt[s[i] - '_'], s, mt))
    res = true;
  if (trie[v].nxt[0] != -1 && check(i + 1, trie[v].nxt[0], s, mt))
    res = true;
  return res;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  trie = vector<node>(1);
  int n, m, k;
  cin >> n >> m >> k;
  g.assign(n, vector<int>());
  forn(i, n){
    string cur;
    cin >> cur;
    add(cur, i);
  }
  pattern nw;
  nw.s = string(k, '_');
  forn(i, m){
    string cur;
    int mt;
    cin >> cur >> mt;
    if (!check(0, 0, cur, mt - 1)){
      cout << "NO\n";
      return 0;
    }
  }
  used.assign(n, 0);
  cyc = false;
  ord.clear();
  forn(i, n) if (!used[i]){
    ts(i);
    if (cyc){
      cout << "NO\n";
      return 0;
    }
  }
  reverse(ord.begin(), ord.end());
  cout << "YES\n";
  forn(i, n)
    cout << ord[i] + 1 << " ";
  cout << "\n";
  return 0;
}

1476F - Фонари

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);

struct segTree
{
    int n;
    bool mx;
    vector<int> t;

    void fix(int v)
    {
        t[v] = (mx ? max(t[v * 2 + 1], t[v * 2 + 2]) : min(t[v * 2 + 1], t[v * 2 + 2]));
    }

    void build(int v, int l, int r)
    {
        if(l == r - 1)
            t[v] = (mx ? -INF : INF);
        else
        {
            int m = (l + r) / 2;
            build(v * 2 + 1, l, m);
            build(v * 2 + 2, m, r);
            fix(v);
        }
    }

    void upd(int v, int l, int r, int pos, int val)
    {
        if(l == r - 1)
            t[v] = (mx ? max(t[v], val) : min(t[v], val));
        else
        {
            int m = (l + r) / 2;
            if(pos < m)
                upd(v * 2 + 1, l, m, pos, val);
            else
                upd(v * 2 + 2, m, r, pos, val);
            fix(v);
        }
    }

    int get(int v, int l, int r, int L, int R)
    {
        if(L >= R)
            return (mx ? -INF : INF);
        if(l == L && r == R)
            return t[v];
        int m = (l + r) / 2;
        int lf = get(v * 2 + 1, l, m, L, min(R, m));
        int rg = get(v * 2 + 2, m, r, max(m, L), R);
        return (mx ? max(lf, rg) : min(lf, rg));
    }

    void upd(int pos, int val)
    {
        upd(0, 0, n, pos, val);
    }

    int get(int L, int R)
    {
        return get(0, 0, n, L, R);
    }

    void build()
    {
        return build(0, 0, n);
    }

    segTree() {};
    segTree(int n, bool mx) : n(n), mx(mx)
    {
        t.resize(4 * n);
    }
};

int main()
{
    int t;
    scanf("%d", &t);
    for(int _ = 0; _ < t; _++)
    {
        int n;
        scanf("%d", &n);
        vector<int> p(n);
        for(int i = 0; i < n; i++)
            scanf("%d", &p[i]);
        vector<int> dp(n + 1, -INF);
        vector<int> par(n + 1, -2);
        dp[0] = 0;
        par[0] = -1;
        vector<int> lf(n), rg(n);
        for(int i = 0; i < n; i++)
        {
            lf[i] = max(1, i - p[i] + 1);
            rg[i] = min(n, i + p[i] + 1);
        }
        segTree sn(n + 1, false);        
        segTree sx(n, true);
        sn.build();
        sx.build();
        for(int i = 0; i < n; i++)
            sx.upd(i, rg[i]);
        sn.upd(0, 0);
        for(int i = 1; i <= n; i++)
        {
            int j = i - 1;
            int k = lf[j] - 1;
            
            int m = sn.get(k, n + 1);                 
            if(m != INF)
            {
                int nval = max(sx.get(m, i - 1), i - 1);
                if(nval > dp[i])
                {
                    dp[i] = nval;
                    par[i] = m;
                }
            }
            if(dp[j] >= i && max(dp[j], rg[j]) > dp[i])
            {
                dp[i] = max(dp[j], rg[j]);
                par[i] = -1;
            }
            if(dp[j] > dp[i])
            {
                dp[i] = dp[j];
                par[i] = -1;
            }
            sn.upd(dp[i], i);                
        }
        if(dp[n] != n)
            puts("NO");
        else
        {
            puts("YES");
            string ans;
            int cur = n;
            while(cur != 0)
            {
                if(par[cur] == -1)
                {
                    cur--;
                    ans += "R";
                }
                else
                {
                    int pcur = par[cur];
                    int diff = cur - pcur;
                    ans += "L";
                    for(int j = 0; j < diff - 1; j++)
                        ans += "R";
                    cur = pcur;    
                }
            }
            reverse(ans.begin(), ans.end());
            puts(ans.c_str());
        }
    }
}

1476G - Минимальная разница

Идея: Neon

Разбор

Решение (Neon)

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)

typedef pair<int, int> pt;

const int N = 100 * 1000 + 13;
const int P = 2000;

struct query {
  int t, l, r, k, i;
};

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> a(n);
  forn(i, n) scanf("%d", &a[i]);
  
  vector<query> q;
  vector<array<int, 3>> upd;
  
  forn(i, m) {
    int tp;
    scanf("%d", &tp);
    if (tp == 1) {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      q.push_back({sz(upd), l - 1, r - 1, k, sz(q)});
    } else {
      int p, x;
      scanf("%d%d", &p, &x); --p;
      upd.push_back({p, a[p], x});
      a[p] = x;
    }
  }
  
  sort(q.begin(), q.end(), [](const query &a, const query &b) {
    if (a.t / P != b.t / P)
      return a.t < b.t;
    if (a.l / P != b.l / P)
      return a.l < b.l;
    if ((a.l / P) & 1)
      return a.r < b.r;
    return a.r > b.r; 
  });
  
  for (int i = sz(upd) - 1; i >= 0; --i)
    a[upd[i][0]] = upd[i][1];
  
  vector<int> cnt(N), ord(N);
  vector<pt> bounds(N, {N, 0});
  bounds[0] = {0, N - 1};
  int L = 0, R = -1, T = 0;
  
  auto add = [&](int x) {
    int c = cnt[x];
    ++ord[bounds[c].x];
    bounds[c + 1].y = bounds[c].x;
    if (bounds[c + 1].x == N)
      bounds[c + 1].x = bounds[c].x;
    if (bounds[c].x == bounds[c].y)
      bounds[c].x = N - 1;
    ++bounds[c].x;
    ++cnt[x];
  };
  
  auto rem = [&](int x) {
    int c = cnt[x];
    --ord[bounds[c].y];
    if (bounds[c - 1].x == N)
      bounds[c - 1].y = bounds[c].y;
    bounds[c - 1].x = bounds[c].y;
    if (bounds[c].x == bounds[c].y)
      bounds[c].x = N;
    --bounds[c].y;
    --cnt[x];
  };
  
  auto apply = [&](int i, int fl) {
    int p = upd[i][0];
    int x = upd[i][fl + 1];
    if (L <= p && p <= R) {
      rem(a[p]);
      add(x);
    }
    a[p] = x;
  };
  
  vector<int> ans(sz(q));
  
  for (auto qr : q) {
    int t = qr.t, l = qr.l, r = qr.r, k = qr.k;
    while (T < t) apply(T++, 1);
    while (T > t) apply(--T, 0);
    while (R < r) add(a[++R]);
    while (L > l) add(a[--L]);
    while (R > r) rem(a[R--]);
    while (L < l) rem(a[L++]);
    
    int res = N;
    for (int i = 0, j = 0, sum = 0; i < N && ord[i] > 0; i = bounds[ord[i]].y + 1) {
      while (j < N && ord[j] > 0 && sum < k) {
        sum += bounds[ord[j]].y - bounds[ord[j]].x + 1;
        j = bounds[ord[j]].y + 1;
      }
      if (sum >= k) res = min(res, ord[i] - ord[j - 1]);
      sum -= bounds[ord[i]].y - bounds[ord[i]].x + 1;
    }
    if (res == N) res = -1;
    ans[qr.i] = res;
  }
  
  for (int x : ans) printf("%d\n", x);
}

double a[] = new double[n]; for(int i=0;i<n;i++) a[i]=sc.nextDouble(); double denominator = 0, dummy=0; for(int i=1;i<n;i++) { double numerator = a[i]; denominator = denominator+a[i-1]; dummy = dummy+a[i-1]; if((numerator/denominator)*100<=k); else { double required = (numerator/k)*100 - denominator; denominator = denominator + Math.ceil(required); } } System.out.println((long)denominator-(long)dummy);

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

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

saquib2508

4 года назад, # |

+42

Problem E was beautiful! Thanks :D

→ Ответить

-senshi-

Finally a contest with less ad-hoc problems!

-9

Finally a contest with less ad-hoc!

ammaka

+89

contest is good but statement of E was awful

regex

In problem C , How the value of the following test case will be 6? please explain..

input
3
2 4 2 
-1 2 4 
-1 2 1 
output
6

ScarletS

4 года назад, # ^ |

+44

Excuse the use of Paint lol, but it looks something like this (the blue edges are the ones forming the cycle):

black_trees

I think Problem D is simpler to use the Disjoint-set. Am I right?

utsavparakhiya

It can be done simply by moving from current city to Right to find the largest pattern of RL...RL or RL...RLR and similarly on left from current city to left as LR...LR or LR...LRL and length of both the patterns + 1 will be the max cities visited from current city

You can see my solution : https://mirror.codeforces.com/contest/1476/submission/106090614

not-an-alt

← Rev. 2 →

This was a very nice contest after a while. Kudos to the authors, each and every problem in the contest that I solved / up-solved taught me something new. Hope for more such rounds :)

kcravuritg

definitely an alt :rofl:

Yzm007

Can someone help me figure out the error of code for submission below? My Code Here is my code for problem F. It gets wrong answer on test 5, case 1259. However, I can't get that sample.

somyamehta_24

Can Anyone tell me how to solve question D recursively and doing memoization?

Not by recursive dp, but Errichto explained the iterative dp approach in his yesterday's stream

No like I am asking like can we solve it that way(recursive dp) like I am stuck and unable to move forward in my approach.

FatihSolak

You can solve it by recursion just reverse the starting position

VVD4

3 года назад, # ^ |

check my solution using memoization https://mirror.codeforces.com/problemset/submission/1476/128826229

amitvikram.pujar

For B, can anyone explain why there's a k-1 added to 100ll * p[i] - k * pSum?

IaMaNanBord

It is basically done to take ceil of the value.

Let me make it more clear — Ceil(a/b) == (a+(b-1))/b

You can check this by taking two cases -

a = k*b. Both functions return k
a = k*b + x (0<x<b). Both functions return k+1;

abdallah21

but in editorial he didn't mention the ceil thing i understand it from the code but i dont understand the purpose of it, if u can explain please

It is mentioned in the editorial that -

$$$x \ge \left\lceil \frac{100 \cdot p_j - k \cdot (p_0 + \dots + p_{j - 1})}{k} \right\rceil$$$

Notice the bracket, that is for denoting ceil function.

Now the next question is why do we even need that — because x is a non negative integer and right hand side acc. to maths will return a floating value (which may not be integer).

Let's take an example — You know x is an integer and after solving RHS you get -

$$$x \geq 1.2 $$$

So definitely you know you should pick next integer (ceil value) as answer i.e. x = 2.

ftiasch

A constant optimization for 1476G - Minimum Difference -- observing that the upper bound of value $$$c$$$ always equals to the lower bound of $$$(c + 1)$$$, we can store only the lower bounds (but not both as in the model solution),

You can see my submission 106048247 for the detail.

+13

There is no need of segment trees for 1476F - Lanterns. We need only two operations:

The one is to query $$$\max\{(j + p_j), \dots, (i + p_i)\}$$$ for increasing $$$i$$$.
The other one is to find the minimum $$$j$$$ where $$$\mathrm{dp}[j] \geq i - p_i - 1$$$.

The two operations can be supported by two standard (monotonic) stack and std::lower_bound.

My submission 106219219.

HELLO_MF

-39

forget about this stupid problem is your profile photo-real ??

Sure. What's your point?

munditva

Hello, can you take a look at my submission for problem F Lanterns.

I have not used a segment tree but a sparse table and for each lantern(let us say i) that points to the left, I have kept a pointer to the last lantern(let us say j) such that the lanterns 1 to j cover some continuous segment of lanterns not covered by the lantern i.

I am failing at some 1200+ subtest of test case 5 and will be much thankful if you can help me point out where my algorithm fails. Or if you can provide some test case where it fails?

Any help will be much appreciated. Thanks!

fengxunling

For E, why can't I topsort it?

snacache

In E you can also find a match converting the string to integer. The number of possible strings is $$$27^k$$$, so every pattern can be indexed.

Dzhao

Question for problem E

Input

4 4 4
aaaa
aaaa
aaaa
aaaa
aaaa 2
aaaa 2
aaaa 2
aaaa 2

The solution's output is "NO", but I think 2 1 3 4 is right, do I understand the problem wrong?

alhasan

Your input is not correct. All patterns should be pairwise distinct.

Oh, many thanks! :)

its_frost

in solution of problem b x = max(x, (100ll * p[i] — k * pSum + k — 1) / k); why we need to add k and minus 1 here k * pSum + k — 1

MUSAFIR

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

it is the process of getting ceil value. if you want ceil(5/2) than it will be (5 + 2 — 1)/2; hope you will understand.

SkyWalkerPS

In the first problem, I did the same thing with ceil function but it threw wrong answer...How is it possible to get the correct answer by just using ceil in a different mathematical way as shown in tutorial??

amireripmav786

3 года назад, # |

Problem B : Inflation.

int n =sc.nextInt(); double k =sc.nextDouble();

This fails on test 4. Can someone tell me why ?

My code to F Lanterns fail at some 1200+ test of test case 5. Can someone take a look at my submission and guide me to where my code's failing? Or provide a test case where it fails?

Help will be much appreciated. Thanks!

NeverCompromise

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

For problem F, there also exists another dp.

For any $$$i$$$, we will assume that we use only the first $$$i$$$ lanters, and define $$$dp(i, j)$$$ to be the maximum possible value of $$$(i + p[i])$$$ among all right-facing lanterns in the first $$$i$$$ lanterns, if the $$$j$$$'th ($$$j < i$$$) lantern is the leftmost uncovered lantern.

Transitions are somewhat similar to the editorial, but we require only one segment tree instead of two.

Implementation: link

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