Educational Codeforces Round 103 Editorial

#	User	Rating
1	tourist	3682
2	ecnerwala	3603
3	Benq	3549
4	Radewoosh	3494
5	Petr	3452
6	ksun48	3413
7	maroonrk	3406
8	Miracle03	3314
9	scott_wu	3313
10	Um_nik	3299

#	User	Contrib.
1	1-gon	214
2	Errichto	189
3	awoo	188
4	rng_58	187
5	SecondThread	186
6	Um_nik	178
7	Ashishgup	177
8	maroonrk	173
9	antontrygubO_o	172
10	-is-this-fft-	169

Tutorial

Solution (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 - Inflation

Idea: adedalic

Tutorial

Solution (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 - Longest Simple Cycle

Idea: adedalic

Tutorial

Solution (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 - Journey

Idea: BledDest

Tutorial

Solution 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]);
    }
}

Solution 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 - Pattern Matching

Idea: BledDest

Tutorial

Solution 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;
}

Solution 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 - Lanterns

Idea: BledDest

Tutorial

Solution (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 - Minimum Difference

Idea: Neon

Tutorial

Solution (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);
}

Comments (47)

Write comment?

saquib2508

3 months ago, # |

+42

Problem E was beautiful! Thanks :D

→ Reply

runt1m3_3rr0r

-9

Finally a contest with less ad-hoc!

Pursuit_of_Accepted

past 2 contests have realised me that i'm more noob at maths than programming :(

alokmaurya_81

3 months ago, # ^ |

me too

sy201901y

Me Tooooooooooooo

jad-debugs

Great Contest! Thanks

Too many Hacks for problem A . My solution was also hacked .

lifeisloop

great contest. life is loop.

last_ninja

+89

contest is good but statement of E was awful

Eurus7

Isnt problem D much easier than problem C?

saranshsingh

-13

that's what she said : | : |

atish1999

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

+44

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

thanks !!

__SON-GOKU__

4 weeks ago, # ^ |

Can u please have a look why my solution for C is giving wrong answer for first test case , subtest 3 :( https://ideone.com/VlyDdV

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://codeforces.com/contest/1476/submission/106090614

puru98

2 months ago, # ^ |

I did the exact same thing.. but my solution didn't work. Any edge cases I might be missing? My code

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:

-10

Lol I took the idea from here

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

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;

Abdallah0011

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.

vinu_93

why we need to take the ceil.

Thank you for clarifying that. However, when I use ceil(100ll * p[i] - k * pSum), it says Wrong Answer. What is the reason for this? Also no one has used the in-built ceil function in their code. Please clarify if possible.

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?

-53

First of all, I have to wait for 10 minutes to comment, and second, you are cute (are you interested in unrated guys ??)

_antisimp_

Can ya bitches stop being creepy to random ladies over the internet?

-38

you created an account just to comment on this. I respect that.

in the numerator why x = max(x, (100ll * p[i] — k * pSum + k — 1) / k); k-1

fengxunling

2 months ago, # |

For E, why can't I topsort it?

Bad_Algorithm

← Rev. 3 →

BledDest problem E : can there be a pattern which matches non of given string?i meant redundant pattern.

Edit : yup!! that was silly,

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.

Nobody4931

couldn't you also have used two pointers in problem D (journey)?

using two other pointers to find the longest distance you can travel to the left/right, and calculating if you are able to travel in the direction or not.

the answer would be one plus the distance you can travel to the right and the distance you can travel to the left, as you would be able to travel back in any point in time

my solution

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! :)

awoo's blog