Educational Codeforces Round 181 Editorial

Tutorial

Solution (awoo)

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int tc;
    cin >> tc;
    while (tc--){
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        reverse(s.begin(), s.end());
        cout << s << '\n';
    }
}

2125B - Left and Down

Idea: BledDest

Tutorial

Solution (ifive)

from math import gcd
for _ in range(int(input())):
    a, b, k = map(int, input().split())
    g = gcd(a, b)
    print(1 if a // g <= k and b // g <= k else 2)

2125C - Count Good Numbers

Idea: BledDest

Tutorial

Solution 1 (BledDest)

def good(x):
    return x % 2 > 0 and x % 3 > 0 and x % 5 > 0 and x % 7 > 0
 
def get_naive(x):
    ans = 0
    for i in range(x):
        if good(i):
            ans += 1
    return ans
 
def get(r):
    return (r // 210) * get_naive(210) + get_naive(r % 210)
 
t = int(input())
for i in range(t):
    l, r = map(int, input().split())
    print(get(r+1) - get(l))

Solution 2 (awoo)

for _ in range(int(input())):
    l, r = map(int, input().split())
 
    def f(x):
        res = 0
        ps = [2, 3, 5, 7]
        for mask in range(16):
            m = 1
            sg = 1
            for i in range(4):
                if (mask >> i) & 1:
                    m *= ps[i]
                    sg = -sg
            res += sg * (x // m)
        return res
    
    print(f(r) - f(l - 1))

2125D - Segments Covering

Idea: BledDest

Tutorial

Solution 1 (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
using pt = pair<int, int>;
 
const int MOD = 998244353;
 
int add(int x, int y) {
   x += y;
   if (x >= MOD) x -= MOD;
   if (x < 0) 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 divide(int x, int y) {
  return mul(x, binpow(y, MOD - 2));
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<pt>> a(m + 1);
  for (int i = 0; i < n; ++i) {
    int l, r, p, q;
    cin >> l >> r >> p >> q;
    a[r].emplace_back(l - 1, divide(p, q));
  }
  vector<int> pr(m + 1);
  pr[0] = 1;
  for (int i = 1; i <= m; ++i) {
    int cur = 1;
    for (auto [_, p] : a[i]) cur = mul(cur, add(1, -p));
    pr[i] = mul(pr[i - 1], cur);
  }
  vector<int> dp(m + 1);
  dp[0] = 1;
  for (int i = 1; i <= m; ++i) {
    for (auto [l, p] : a[i]) { 
      int cur = divide(pr[i], pr[l]);
      cur = divide(cur, add(1, -p));
      cur = mul(cur, p);
      dp[i] = add(dp[i], mul(dp[l], cur));
    }
  }
  cout << dp[m] << endl;  
}

Solution 2 (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
using pt = pair<int, int>;
 
const int MOD = 998244353;
 
int add(int x, int y) {
     x += y;
     if (x >= MOD) x -= MOD;
     if (x < 0) 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 divide(int x, int y) {
    return mul(x, binpow(y, MOD - 2));
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<pt>> a(m + 1);
    vector<int> dp(m + 1);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        int l, r, p, q;
        cin >> l >> r >> p >> q;
        int val = divide(p, q);
        a[r].emplace_back(l - 1, val);
        dp[0] = mul(dp[0], add(1, -val));
    }
    for (int i = 1; i <= m; ++i) {
        for (auto [l, p] : a[i]) { 
            int cur = dp[l];
            cur = divide(cur, add(1, -p));
            cur = mul(cur, p);
            dp[i] = add(dp[i], cur);
        }
    }
    cout << dp[m] << endl;  
}

2125E - Sets of Complementary Sums

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int MOD = 998'244'353;
 
void solve(){
    int n, x;
    cin >> n >> x;
    // need sum(mx + 1 - ai) <= mx + 1
    // start with 1, 2, 3, ... n
    // min sum + 1 is n + 1
 
    if (n == 1){
        cout << x << '\n';
        return;
    }
 
    int s_cur = n * (n + 1) / 2;
    int need = s_cur - (n + 1);
 
    // leads to n is O(sqrt(s))
    if (n + need > x){
        cout << 0 << '\n';
        return;
    }
 
    // so we can do dp[sum] knapsack
 
    vector<int> dp(x + 1);
    dp[0] = 1;
 
    // for -1 and 0
    for (int j = 0; j < 2; j++){
        for (int i = 0; i < x; i++){
            dp[i + 1] = (dp[i + 1] + dp[i]) % MOD;
        }
    }
 
    for (int i = 1; i <= n - 2; i++){
        for (int j = 0; j < x; j++){
            // increase sum by i -> mx increase by 1 + i
            if (j + i + 1 <= x){
                dp[j + i + 1] = (dp[j + i + 1] + dp[j]) % MOD;
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i <= x; i++){
        int cur = n + need + i;
        if (cur > x){
            break;
        }
        ans = (ans + dp[i]) % MOD;
    }
 
    cout << ans << '\n';
}
 
signed main()
{
#ifdef FELIX
    auto _clock_start = chrono::high_resolution_clock::now();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
 
#ifdef FELIX
    cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
        chrono::high_resolution_clock::now()
            - _clock_start).count() << "ms." << endl;
#endif
    return 0;
}

2125F - Timofey and Docker

Idea: FelixArg

Tutorial

Solution (awoo)

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 
 
const int INF = 1e8;
const string al = "docker";
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int tc;
    cin >> tc;
    while (tc--){
        string s;
        cin >> s;
        int n = s.size();
        int mx = n / 6;
        int m;
        cin >> m;
        vector<int> dx(mx + 2);
        forn(i, m){
            int l, r;
            cin >> l >> r;
            r = min(r, mx);
            if (l > r) continue;
            ++dx[l];
            --dx[r + 1];
        }
        forn(i, mx + 1) dx[i + 1] += dx[i];
 
        int cur = 0;
        vector<int> dif(max(0, n - 5));
        forn(i, n - 5){
            forn(j, 6)
                dif[i] += s[i + j] != al[j];
            cur += dif[i] == 0;
        }
 
        int mxcnt = *max_element(dx.begin(), dx.end());
        int k = -1;
        int ans = INF;
        forn(i, mx + 1){
            if (dx[i] != mxcnt) continue;
            if (i <= cur){
                ans = min(ans, cur - i);
                continue;
            }
            k = i;
            break;
        }
 
        if (k == -1){
            cout << ans << '\n';
            continue;
        }
 
        auto calc = [&](int d){
            vector<pair<long long, int>> dp(n + 1, {(long long)1e18, -1});
            dp[0] = {0, 0};
            forn(i, n){
                dp[i + 1] = min(dp[i + 1], dp[i]);
                if (i + 6 <= n)
                    dp[i + 6] = min(dp[i + 6], {dp[i].first + dif[i] + d, dp[i].second - 1});
            }
            return dp[n];
        };
 
        int l = -INF, r = 0, sv = INF;
        while (l <= r){
            int m = (l + r) / 2;
            auto [val, cnt] = calc(m);
            if (-cnt >= k){
                sv = val - k * 1ll * m;
                l = m + 1;
            }
            else{
                r = m - 1;
            }
        }
        ans = min(ans, sv);
 
        cout << ans << '\n';
    } 
}

long long solve2(long long x) { return (x/2) + (x/3) + (x/5) + (x/7) - (x/6) - (x/10) - (x/14) - (x/15) - (x/21) - (x/35) + (x/30) + (x/42) + (x/105) - (x/210); } void solve() { long long l, r; cin >> l >> r; l--; long long a = solve2(r); long long b = solve2(l); long long ans = (r - a) - (l - b); cout << ans << endl; } int main() { int t; cin >> t; while(t--) { solve(); } }

~~~~~ #include<bits/stdc++.h> #define lli long long int #define MOD 998244353 using namespace std; lli gcd(lli a, lli b); lli binary_exp(lli a, lli b, lli mod); priority_queue<lli, vector<lli>> MAX_HEAP; priority_queue<lli, vector<lli>, greater<lli>> MIN_HEAP; void solve(){ lli n, m; cin >> n >> m; vector<tuple<lli, lli, lli, lli>> segment; for(int i=0;i<n;i++){ lli l, r, p, q; cin >> l >> r >> p >> q; segment.push_back({r, l, p, q}); // note i put {r, l} rather than {l, r} } sort(segment.begin(), segment.end()); // sorting the segments based on r vector<lli> dp(m+1, 0); // dp[i] = probablity of filling 1 -> i exactly once with currently seen segments vector<lli> not_take(n, 0); // not_take[i] = prod of probablity of not taking segments 0 -> i dp[0] = 1; for(int i=0;i<n;i++){ auto seg = segment[i]; lli l = get<1>(seg), r = get<0>(seg), p = get<2>(seg), q = get<3>(seg); lli not_p = ((q-p) * binary_exp(q, MOD-2, MOD))%MOD; // just getting the probablity of the segment not existing lli take_p = (p * binary_exp(q, MOD-2, MOD))%MOD;// probablity of segment existing if(i == 0){ // special case, first segment not_take[i] = not_p; dp[r] = take_p; continue; } // probablity of filling 1-> r if current segment doens't exist dp[r] = (dp[r]*not_p)%MOD; not_take[i] = (not_p * not_take[i-1])%MOD; // updating not_take // exlude represents the probablity of not taking segments which overlap with the current segment. lli exclude = not_take[i-1]; auto it = lower_bound(segment.begin(), segment.begin() + i, make_tuple(l, 0, 0, 0)); if(it != segment.begin()){ // 0 -> idx should index all the segment which do not overlap with the current segment int idx = distance(segment.begin(), it);idx--; // removing the probablity of non overlapping segment not existing exclude = (exclude * binary_exp(not_take[idx], MOD-2, MOD))%MOD; } // updating dp[r] dp[r] = (dp[r] + (((take_p * exclude)%MOD)*dp[l-1])%MOD)%MOD; } cout << (dp[m]%MOD) << endl; } bool multitestcase = false; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int testCase = 1; if(multitestcase) cin >> testCase; while(testCase--){ solve(); } return 0; } lli gcd(lli a,lli b) { if(b == 0) return a; return gcd(b, a%b); } lli binary_exp(lli a, lli b, lli mod){ lli res = 1; while(b > 0){ if(b&1){ res = (res*a)%mod; } a = (a*a)%mod; b = b/2; } return res; }

Comments (35)

Show archived | Write comment?

Ryuu7

15 months ago, hide # |

+24

Return of the MathForces

→ Reply

MEDAAA

+100

It is not just a gap between D and E. It is a GAAAAAAAAAP.

xcx2010

15 months ago, hide # ^ |

-14

No. E is very easy. All you need to do is to write a brute-force for small n and x, and find some rules on the answers to small n and x (the rule is really easy to find), finally apply the rule to every n and x.

lupengheyyds

Could you explain the brute-force approach?

I managed to solve it myself.Thanks anyway.

_paranoid_android_

Can anyone help me with why I'm getting it wrong for C?

EChen6

You forgot +(x/70)

sarvagya2545

You missed x / (2 * 5 * 7);

You're better off using a for loop instead of enumerating all the conditions manually, as it makes your code clearer and less likely to miss some elements.

PIYUSHERE

3 months ago, hide # ^ |

thanks Dear, i learn something new approach from your solution

HhunterR

I had a question. How many question should I try to upsolve. As I failed in C. I went through the theory and still it is little tough for me. Will it be any good if I upsolved problems > D?

pilliamw

Personally, I think D is a good problem for practicing modular arithmetic & DP. At your rating, I wouldn't worry too much about upsolving EFs since those are at a CM/M level.

Negationist

Slightly different derivation of the sufficient and necessary condition for question E. Consider any (sorted) output set x = {x(1),x(2),...,x(n)} that we want to make a input set for for. Consider the difference array {d(2),d(3),..d(n)} where d(i) = x(i)-x(i-1) we know there must be some term z after which the following terms come, z+d(n), z+d(n)+d(n-1), z+d(n)+d(n-1)+d(n-2).., in the input set. Thus let us only have those terms for now. Note that it is optimal to make z=1, since any higher z would only make the input sum higher raising all our output terms by a constant, which we can just do instead by adding more 1 terms should we need to. Now we have the input array {1,1+d(n),1+d(n)+d(n-1),...,1+(sum of all d(i)}. Lets find the sum of this array, note that 1 adds to n terms, (x(n)-x(n-1)) adds to n-1 terms, (x(n-1)-x(n-2)) adds to n-3 terms, etc. It is not hard to see that each x term will be subtracted once except for x(n), thus the final sum is just n+x(n)*(n-1)-(sum of all x(i) s.t i<n). Now, from the construction, we know that this corresponds to an output array that is off by the original set x by some constant, i.e it has the same difference array when sorted. The only question now is, is the highest term, and thus all the terms, small enough? Remember that too small is ok since we can raise the sum, but too big is not ok. We know that the largest term will be equal to the sum-1, since the lowest term is 1, so we know it is just n+x(n)*(n-1)-(sum of all x(i) s.t i<n)-1 and this must be less than or equal to x(n). Thus we have n+x(n)*(n-1)-(sum of all x(i) s.t i<n) — 1 <= x(n). Rearranging this we get x(n)*(n-1)+(n-1) — (sum of all x(i) s.t i<n) <= x(n) and then we get (x(n)+1)*(n-1) — (sum of all x(i)) <= 0, exactly the condition found in the editorial.

chenhongrui

+14

This contest felt like there was a huge gap between ABCD and EF. I solved ABCD in the first 20 minutes, spent 1 hour on F, and ultimately couldn't pass E.

However, I think E is still a good problem. I really didn't notice that with $$$s=\max(Q)+1$$$, you can construct a solution (if one exists).

But does anyone know why I got penalty time for WA on test 2 in problem F? Isn't the second test case the sample?

kyuukyuusha

← Rev. 2 →

Only error on test 1 (or compile error) doesn't give penalty. Error on test 2 and onwards always gives penalty (assuming you solve), regardless if it is sample or not.

Looks like this has been around for a while.

thank you very much!

cowwycow

+13

i solved E simply by looking for patterns.

outputing the first 5x30 values then removing the zeroes before gives me this dp:

dp[i][j] = dp[i - 1][j] + dp[i][j - i + 1]

which can be precomputed in o(nsqrt) time and instant o(1) per testcase, making the sum of n and x over all testcases irrelevant.

heres the code: link

edit: this is actually just an offline version of the official edit im sorry guys

rnishu12

Could you tell me what the bruteforce code was?

here it is:

brute force code on ideone

Thanks so much that is a crazyyy solution. Also you have very good function naming practices.

SLEEPY_INTROVERT

what does sus array calculates?

sus[i] denotes the number of zeros at the beginning of dp[i], which explains why there is an if statement in solve():

if(x <= sus[n]){
    cout << 0 << endl;
    return;
}

then i proceed to subtract sus[n] from x in order to get the correct dp explained above.

GromovIAL

Can anyone explain C? I don't understand.

esh_war2

https://cses.fi/problemset/task/2185 Similar but tight constraints.

defnotmee

← Rev. 3 →

Why the $$$1 \leq l_i, r_i \leq 10^9$$$ constraints on F? It follows directly from the statement that values that are bigger than $$$n$$$ don't matter. This just gaslights you into thinking you read the problem wrong :/

Badri41

Why TLE on Systest 31

I think this is efficient enough

Code

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<pair<int, Mint>>> adj(m);
    Mint deno = 1;
    vector<Mint> dp(m + 1);
    dp[m] = 1;
    Mint one = 1;
    rep(i, 0, n) {
        int l, r, p, q; cin >> l >> r >> p >> q;
        l--;
        adj[l].pb({r, Mint(p) / Mint(q)});
        deno *= one - Mint(p) / Mint(q);
    } 
    function<void(int)> dfs = [&] (int u) {
        for (auto [v, p] : adj[u]) {
            if (dp[v] == 0) dfs(v);
            dp[u] += p / (one - p) * dp[v];
        }
    };
    dfs(0);
    cout << (dp[0] * deno).x << nline;
}

qq11123334

You’re using dp[v] == 0 to mean “not computed yet”. But 0 is also a valid value for dp[v]. So every time you touch a vertex whose true answer is 0, you call dfs(v) again, recomputing it over and over. I guess it's why got TLE.

I seriously can't thank you enough. Fixing this solved the problem. I couldn't think of this and was stuck.

alyosha

Can someone please help me with this, I have been trying to solve this question for hours. I don't understand why is it failing testcase 8 always. I don't know what i missed. My solution seems similar to the idea discussed in the edutorial. I have added comments to make it more clear. Any discussion would be helpful, Thanks.

~~~~~

Coder_Fang

It is better to introduce the "alien tricks" in the solution of F.

sarcia3

In the editorial for E, is $$$\mathrm{dp}[st]$$$ really equal to 1? From what I understand we should have $$$\mathrm{dp}[st+n] = 1$$$ instead (with $$$\mathrm{dp}[st]=0$$$).

$$$\mathrm{dp}[i]$$$ is defined as "the number of different sets of complementary sums such that the maximum in these sets equals $$$i$$$ and equality in condition (1) holds". As $$$st$$$ is defined as the number of additions of ones to all of the elements of the set {$$$1, 2, \dots, n$$$} needed to make it satisfy the condition (1), it can be zero (with $$$n=2$$$). With $$$n=2$$$, $$$\mathrm{dp}[0] \neq 1$$$, because every set of complementary sums with more than one element* has only positive values inside, so the maximum of those values can't be zero. On the other hand, $$$\mathrm{dp}[st+n] = 1$$$ makes sense -- the set {$$$1, 2, \dots, n$$$} after the additions will have its maximum equal to $$$n+st$$$, thus $$$\mathrm{dp}[n+st] = 1$$$.

*in the editorial it is not specified that in the $$$\mathrm{dp}$$$ we only care about sets of size $$$n$$$, but I don't see how that wouldn't be true.

FelixArg

You're right, thanks. Now fixed.

SidneySun

14 months ago, hide # |

The Problem E is good, but the tutorial is difficult to understand for me.

We can represent the operations of adding to the suffix of length j as an item

Since j is smaller than n, why enumerate from 0 to x?

What is the connection between prefix sum and +1 operation?

We start from {1, ..., n}, why dp[0] = 1;

It's too difficult.

icpc_loser

13 months ago, hide # |

Thanks for the editorial. Can someone explain in the editorial for E, how is f(1) = n-2. As per my calculation I am getting f(1) as n. I am referring to:

we define f(i) as the change in the sum on the left side of condition (1) if we added 1 to the suffix of length i. We can easily calculate all f(i).

13 months ago, hide # ^ |

I got it. I swapped the sign of 1 in the summation from negative to positive, and hence the delta of 2.

#	User	Rating
1	Benq	3676
2	jiangly	3670
3	Kevin114514	3657
4	maroonrk	3355
5	Um_nik	3353
6	squareOf105	3346
7	tourist	3343
8	strapple	3324
9	heuristica	3322
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	158
2	nik_exists	150
2	maspy	150
4	AmShZ	143
5	Um_nik	141
6	Errichto	139
7	adamant	137
8	BledDest	133
8	maroonrk	133
10	qwexd	130

awoo's blog