Educational Codeforces Round 184 Editorial

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	146
3	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Idea: Roms

Tutorial

Solution (Roms)

#include <bits/stdc++.h>
 
using namespace std;
 
int t;
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        int n, a;
        cin >> n >> a;
        vector <int> v(n);
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            cin >> v[i];
            if (a > v[i]) ++l;
            if (a < v[i]) ++r;
        }
        
        cout << (l > r ? a - 1 : a + 1) << endl;
    }
    return 0;
}

2169B - Drifting Away

Idea: BledDest

Tutorial

Solution (awoo)

for _ in range(int(input())):
    s = input()
    for i in range(len(s) - 1):
        if s[i] != '<' and s[i + 1] != '>':
            print(-1)
            break
    else:
        print(len(s) - min(s.count('<'), s.count('>')))

2169C - Range Operation

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
using li = long long;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    li s = 0, mn = 0, bst = 0;
    for (int i = 0; i < n; ++i) {
      int x;
      cin >> x;
      s += x;
      li cur = (i + 1) * li(i + 2) - s;
      mn = min(mn, cur);
      bst = max(bst, cur - mn);
    }
    cout << s + bst << '\n';
  }
}

2169D1 - Removal of a Sequence (Easy Version)

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include <bits/stdc++.h>
 
using namespace std;
 
const long long INF = 1000000000000LL + 1;

void solve(){
    int x;
    long long y, k;
 
    cin >> x >> y >> k;
 
    long long l = 1, r = INF;
    long long m;
 
    while(l <= r){
        m = l + (r - l) / 2;
        long long ost = (m - 1);
        for (int i = 0; i < x; i++){
            ost -= ost / y;
        }
        if (ost + 1 > k){
            r = m - 1;
        }
        else{
            l = m + 1;
        }
    }
 
    if (r == INF){
        cout << -1 << '\n';
    }
    else{
        cout << r << '\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;
}

2169D2 - Removal of a Sequence (Hard Version)

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int INF = 1'000'000'000'000LL;
 
void solve(){
  int x, y, k;
  cin >> x >> y >> k;
 
  if (y == 1){
    cout << -1 << '\n';
    return;
  }
 
  for (int i = 0; i < x; ){
    int cur = (k - 1) / (y - 1);
    if (cur == 0){
      break;
    }
    int fk = (cur + 1) * (y - 1) + 1;
    int cnt = (fk - k + cur - 1) / cur;
    cnt = min(x - i, cnt);
    k += cnt * cur;
    if (k > INF){
      cout << -1 << '\n';
      return;
    } 
    i += cnt;
  }
 
  cout << k << '\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;
}

2169E - Points Selection

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
typedef long long li;
 
const int INF = int(1e9);
const li INF64 = li(1e18);
 
int n;
vector<li> x[3];
 
bool read() {
    if(!(cin >> n))
        return false;
    fore (k, 0, 3) {
        x[k].resize(n);
        fore (i, 0, n)
            cin >> x[k][i];
    }
    return true;
}
 
void solve() {
    vector< vector<li> > w(n, vector<li>(1 << 4, 0));
    fore (i, 0, n) {
        fore (mask, 0, 1 << 4) {
            fore (k, 0, 4) if ((mask >> k) & 1)
                w[i][mask] += x[k & 1][i] * (k < 2 ? -1 : 1);
        }
    }
 
    vector< vector<li> > d(n + 1, vector<li>(1 << 4, -INF64));
    d[0][0] = 0;
    fore (i, 0, n) fore (mask, 0, 1 << 4) {
        if (d[i][mask] < -INF64 / 2)
            continue;
        
        d[i + 1][mask] = max(d[i + 1][mask], d[i][mask] + x[2][i]);
 
        int filter = ((1 << 4) - 1) ^ mask;
        for (int cmask = filter; cmask > 0; cmask = (cmask - 1) & filter)
            d[i + 1][mask | cmask] = max(d[i + 1][mask | cmask], d[i][mask] + 2ll * w[i][cmask]);
    }
    cout << d[n][(1 << 4) - 1] << endl;
}
 
int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
 
    int t; cin >> t;
    while (t--) {
        read();
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

2169F - Subsequence Problem

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
const int LOGN = 19;
const int MOD = 998244353;
int g = 3;
 
int mul(int a, int b) {
    return int(a * 1ll * b % MOD);
}
int norm(int a) {
    while(a >= MOD) a -= MOD;
    while(a < 0) a += MOD;
    return a;
}
int binPow (int a, int k) {
    int ans = 1;
    for (; k > 0; k >>= 1) {
        if (k & 1)
            ans = mul(ans, a);
        a = mul(a, a);
    }
    return ans;
}
int inv(int a) {
    return binPow(a, MOD - 2);
}
 
vector<int> w[LOGN], rv;
bool precalced = false;
 
void precalc() {
    if(precalced)
        return;
    precalced = true;
    
    int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    fore(st, 0, LOGN) {
        w[st].assign(1 << st, 1);
 
        int bw = binPow(wb, 1 << (LOGN - st - 1));
        int cw = 1;
 
        fore(k, 0, (1 << st)) {
            w[st][k] = cw;
            cw = mul(cw, bw);
        }
    }
    
    rv.assign(1 << LOGN, 0);
    fore(i, 1, sz(rv))
        rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
}
 
const int MX = (1 << LOGN) + 3;
 
inline void fft(int a[MX], int n, bool inverse) {
    precalc();
    
    int ln = __builtin_ctz(n);
    assert((1 << ln) < MX);
    assert((1 << ln) == n);
 
    fore(i, 0, n) {
        int ni = rv[i] >> (LOGN - ln);
        if(i < ni) swap(a[i], a[ni]);
    }
 
    for(int st = 0; (1 << st) < n; st++) {
        int len = (1 << st);
        for(int k = 0; k < n; k += (len << 1)) {
            fore(pos, k, k + len) {
                int l = a[pos];
                int r = mul(a[pos + len], w[st][pos - k]);
 
                a[pos] = norm(l + r);
                a[pos + len] = norm(l - r);
            }
        }
    }
    
    if(inverse) {
        int in = inv(n);
        fore(i, 0, n)
            a[i] = mul(a[i], in);
        reverse(a + 1, a + n);
    }
}
 
int aa[MX], bb[MX], cc[MX];
 
vector<int> multiply(const vector<int> &a, const vector<int> &b, int cutoff) {
    int ln = 1;
    while(ln < (sz(a) + sz(b)))
        ln <<= 1;
    
    fore(i, 0, ln)
        aa[i] = (i < sz(a) ? a[i] : 0);
    fore(i, 0, ln)
        bb[i] = (i < sz(b) ? b[i] : 0);
        
    fft(aa, ln, false);
    fft(bb, ln, false);
    
    fore(i, 0, ln)
        cc[i] = mul(aa[i], bb[i]);
    fft(cc, ln, true);
    
    vector<int> ans(cc, cc + ln);
    while((ans.size() > 0 && ans.back() == 0) || ans.size() > cutoff)
        ans.pop_back();
    return ans;
}
 
vector<int> fact, ifact;
 
void precalc_factorials(int s) {
    fact.resize(s);
    fact[0] = 1;
    for(int i = 1; i < s; i++)
        fact[i] = mul(fact[i - 1], i);
    ifact.resize(s);
    for(int i = 0; i < s; i++)
        ifact[i] = inv(fact[i]);
}
 
int choose(int n, int k) {
    if(n < 0 || n < k || k < 0) return 0;
    return mul(fact[n], mul(ifact[n - k], ifact[k]));
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> lens(k);
    for(int i = 0; i < k; i++) cin >> lens[i];
 
    int cutoff = n + 1;
    precalc_factorials(1 << LOGN);
    vector<int> segments(6);
    segments[0] = 1;
    for(auto len : lens)
        for(int i = 1; i <= len; i++)
            segments[i]++;
    vector<vector<int>> poly(6);
    for(int i = 0; i < 6; i++) {
        if(segments[i] == 0)
            poly[i] = { 1 };
        else {
            int choices = norm(m - i);
            int p = 1;
            poly[i].resize(cutoff);
            for(int k = 0; k < cutoff; k++) {
                int cur = mul(p, choose(k + segments[i] - 1, k));
                poly[i][k] = cur;
                p = mul(p, choices);
            }
        }
    }
    vector<int> ans = { 1 };
    for(int i = 0; i < 6; i++)
        ans = multiply(ans, poly[i], cutoff);
 
    int used = 0;
    int coef = 1;
    for(auto len : lens) {
        coef = mul(coef, fact[len]);
        used += len;
    }
    int res = mul(coef, ans[n - used]);
    cout << res << endl;
}

ll x, y, k; cin>>x>>y>>k; ll nx = x; ll num = pow(10,12); ll dk = k; if(x>=1 && y==1){ cout<<-1<<endl; return; } while(nx--){ k += ( k + (k + ( k + ( k + ( k + (k + (k + ( k + (k + (k + (k + (k + k/y) / y) / y ) /y ) / y ) /y ) / y) / y ) /y ) / y ) /y ) / y) / y; if(k>num){ cout<<-1<<endl; return; } } k = dk; if(k<y){ cout<<k<<endl; return; } while(x--){ // cout<<k<<endl; k += ( k + (k + ( k + ( k + ( k + (k + (k + ( k + (k + (k + (k + (k + k/y) / y) / y ) /y ) / y ) /y ) / y) / y ) /y ) / y ) /y ) / y) / y; } cout<<k<<endl;

Comments (68)

Write comment?

thaibaotran555

5 months ago, hide # |

+19

Why is the system testing stuck in 95%? It has been like that for a whole day bro :/

→ Reply

syed_omega

What rating was the C problem? 1200?

Ronakcp24

5 months ago, hide # ^ |

clist states it is around 1298 so it is 1300 i guess.

milk_ka_cake

For D1, can someone explain why the answer will be max p?

Individual

As I see it we should find the minimum P for which after applying X operations we are left with K or more elements and that P will serve as the answer. In the case of several consecutive sequence lengths that are designated to end with K values, we want the minimal one since this is the only one that will have its max value (which is the sequence's length) preserved along all operations. Larger sequence lengths which result in the same K mean that they add elements to the sequence which get deleted during one of the operations.

Can you please elaborate on why the max value (for minimum p) will remain preserved across operations?

← Rev. 2 →

Each P represents the series of integers from 1 to P. Define f(P) to be the number of items remaining after applying X operations on a sequence of length P.

If f(P) == f(P - 1) + 1, that means that by increasing the sequence by one we were able to preserve one more element. Since whether an element gets deleted or not is determined solely by how many elements come before it and not after it, we can deduce that each element that will be deleted in the sequence of length P-1 will be deleted in the sequence of length P, thus the newly preserved element has to be the newly added one — P.

vshah45

← Rev. 3 →

This case will hold true for consecutive numbers only right? (i.e there are at max 2 numbers such that they go to a position k' after one operation and should be consecutive).Using f(P) defined by you: If p-f(p)==k' and p-m-f(p-m)==k', this can be true only if m==1 since f(p)==m+f(p-m) i.e floor(p/y) == m+floor((p-m)/y) which only holds for m==1 when x>=2. My question is why does min(p) never become 2nd consecutive number in one of the x operations?

-fft-

3 months ago, hide # ^ |

hey i just submitted this soln and it got accepted but i couldn't figure out like fundamentally why it got accepted , u know like i just thaught it might work , but how do i approach , how do i relate it with the editorial though?

Anyakwi

I dont understand this,too.

siddhantsachan

3 weeks ago, hide # ^ |

answer is min p, Let the final sequence after all operations is S = [a₁,a₂,a₃,...,a_k,...] where a_k = k-th surviving number Let f(p) be the number of elements that remain after doing all x removals on the prefix 1, 2,.., p so f(a_k) = k and f(a_k — 1) = k — 1 and f(a_k+1)=k+1 so for any number (r) between a_k and a_k+1, f(r)=k, but that number r is not in the final remaining sequence so that means that number would have already been removed in the process, so sequence till r results in exactly k numbers but r is not that kth number.

DarkDevilVaqif

add DP tag to C, as proven here: https://mirror.codeforces.com/contest/2169/submission/348989596

My idea is to calculate everything up to I. I use a simple prefix sum for this.

So one array represents when we have ALREADY used the operation before at some point, and the best we can get from this.

The other represents us using the operation on this index. Here our subarray will either start from the current index OR some the start of the subarray of i — 1.

I'd be happy to explain if there's something complicated

Mirou127

Yeah i solved it using dp also , this is my submission 350826621

I recall this pattern came in edu round problem D 1373D - Maximum Sum on Even Positions

They did add the DP tag just now :D

Also I'm quite sure your solution is recursion, not DP

i think DP can be implemented using two techniques : memoization (recursive like i did) and tabulation (like you did)

Yea

arin_chandurkar

damn, that's a really great idea,

I was thinking of dp too, but couldn't handle the fact about how I would maintain the start of the segment, but your solution is really elegant, loved it!

Thanks a lot, it truly does mean a lot.

I try my best to keep my code as tidy, and clean as possible

If it's bad, I might even improve it(if possible) and resubmit

Datcty

bro has the coolest code template i've ever seen

bhagwandai

"If we find such a maximum p that after all of Polycarp's actions exactly k elements remain, then this p will be the answer."

Isn't it minimum? awoo

mrinmoy66sadhukhan

Yes exactly.. it's a mistake i think

I don't understand how the time complexity for computing in groups is sqrt(A) for D2. Could someone maybe give me a hint?

LXL4510

1+2+3+4......+p-1+p=n, so p is about sqrt(n)

christopherbitti9

Thanks for explaining it! The editorial writer could learn from you.

Is this a known trick on Codeforces that I'll likely utilize again now that I've seen it? I don't see many people being able to justify the time complexity of this approach on the fly. It came to my mind for some reason, but I just couldn't see why it would be fast enough.

Not_So_Great

Read the fourth point from this blog. It provides a proof for the time complexity.

thanks man

MD_SAIDUZZAMAN

wow ,great explanation

EZDUBS

I disagree with sample 2 of problem A:

6 500

200 200 300 500 600 600

b>=501 gives score of 600+600=1200, whereas b=333 gives 200+200+300=700. Clearly the former is optimal.

gudubhaiya

we are not adding the difference but we are calculating total points only, if Alice is more close to a given number then he gets points otherwise bob

I made the same mistake during the contest, actually the score is defined as the number of balls won rather than the sum of the numbers written on them. So for this case it's 3>2 (1 for each ball).

Could you explain why this is the intended interpretation of the problem statement?

As per the explanation given for the first testcase — if Bob chooses 35, he gets 5 points for marbles 30,40,50,60,70. Although I agree that problem statement could have been clearer.

za_zoulati

Can anyone , give me the intuition behind the problem D2 ?

carvalj

Let

$$$p$$$

be the smallest number such that

$$$[1,2,\dots,p]$$$

reduces to a list of length

$$$k$$$

after $x$ operations. The first key observation is $$$p$$$ itself is in the final list of length k we obtain (if it wasnt, it wouldnt be the minimal such $$$p$$$!)

Now, let $$$L_{i}$$$ denote the length of the list after $$$i$$$ operations were applied. Trivially,

$$$L_{0} = p$$$, $$$L_{x} = k$$$.

The key observation now is that we can quite trivially obtain $$$L_{n-1}$$$ given $$$L_{n}$$$.

Almost Any group of $$$y-1$$$ elements in $$$L_{n}$$$ was obtained from deleting a single element from a group of size $$$y$$$ in $$$L_{n-1}$$$. The ONLY exception is a grouping of size $$$y-1$$$ that contains the last element $$$p$$$. Clearly, such a group was not obtained by removing an element, as this element would appear after $$$p$$$ in the original list, but $$$p$$$ is the maximal element in the original list.

Thus, only groups of size $$$y-1$$$ not including the last element contribute to the size. This gives

$$$L_{n-1} = L_{n} + \left\lfloor\frac{L_{n}-1}{y-1}\right\rfloor$$$

Once this formula is obtained it is simply a matter of computing ti efficiently. (Naive approach is O(n), too slow. But the "grouping" trick from editorial will allow for O(sqrt(n)))

WhatsDerivative

FelixArg for D2, do you have a link to more resources regarding the floor function and re-arranging to solve for $$$p$$$? I understand why we're dividing by $$$y - 1$$$ but couldn't follow why the numerator is $$$p' - 1$$$ instead of $$$p'$$$.

marcus06

hope he did, i have been stuck on this for hours...

xiangixuan

$$$x=1,y=3$$$, the seq is:

$$$1,2,X,3,4,X,5,6$$$ ($$$X$$$ means has been deleted)

there is only one $$$X$$$ before 4, which is $$$\frac{4-1}{3-1}=1$$$, not $$$\frac{4}{3-1}=2$$$

that's why $$$p'-1$$$ instead of $$$p'$$$

Ah I was mixing up indices with the values. Your example cleared it up for me, thank you very much!

cube_escape

Try to understand like this,we have one element removed for consecutive $$$k$$$ elements,in the function,we use the $$$k - 1$$$ as the divisor,which means $$$k - 1$$$ consecutive elements for one removed elements,but if we use $$$p'$$$ but not $$$p'- 1$$$ as the numerator,when $$$p \mod k \equiv k - 1$$$ ,we have a remainder $$$k-1$$$,but actually this $$$k-1$$$ elements can't contribute to the answer,as it only has $$$k-1$$$ elements,not enough for $$$k$$$ consecutive elements.

123gjweq2

$$$A$$$ is like the situation where you and your friend are driving somewhere and you both estimate how long it will take you to get there and whoever gets closer wins, and you say something like $$$30$$$ minutes then your friend always says either $$$29$$$ or $$$31$$$ minutes. Very cool problem.

kreukpg

Agree

coderrg21

FelixArg Is the formula in D2 correct? Since, If we take $$$p=y$$$, then $$$p'=y-1$$$. Thus

$$$p'+\left\lfloor\frac{p'-1}{y-1}\right\rfloor=y-1\ne p$$$

Can really $$$p \mod y \equiv 0$$$? If so,the p-th elemnt will be removed at once

NWm

I don't get your point. can you please shed some light at how to solve such a equation with floor function? It worked for me as long as I turn the p = p' + floor((p' — 1) / (y — 1)) and got accepted but I am still confusing how we get the equation from p — floor(p / y) = p' to the previous equation.

Refer to the comment I wrote above this comment.

nguyengiabach1201

Problem C can be solved using Dynamic Programming:

When we perform an operation on the range $$$[l,r]$$$, the total sum changes by $$$\Delta=(l+r)(r-l+1)-\sum_{i=l}^{r}a_i$$$. So for each value of $$$l$$$, we only need to find $$$r$$$, such that $$$\Delta$$$ is maximised. Now, the problem becomes a simple Dynamic Programming problem.

Let us define $$$pref_x$$$ as the sum of the first $$$x$$$ elements in the array $$$a$$$. We can rewrite $$$\Delta=(-l^2-l+r^2+r)+(-pref_r+pref_{l-1})$$$. As $$$l$$$ is fixed, now we want to maximise $$$r^2+r-pref_r$$$.

Let us define $$$suf_x$$$ as $$$max_{i=x}^{n}i^2+i-pref_i$$$. Then the answer is just simple $$$max_{i=1}^{n}-i^2-i+pref_{i-1}+suf_i$$$.

$$$\newline$$$

My Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define el '\n'
#define FNAME ""
#define ll long long
#define int long long
#define MOD (int)(1e9 + 7)
#define INF (ll)(1e18 + 1)

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if (fopen(FNAME ".inp", "r"))
    {
        freopen(FNAME ".inp", "r", stdin);
        freopen(FNAME ".out", "w", stdout);
    }

    return;
}

void solve()
{
    int n, ans = -INF;
    cin >> n;

    vector<int> a(n + 5);

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<int> prefSum(n + 5), sufMax(n + 5);
    sufMax[n + 1] = -INF;

    for (int i = 1; i <= n; ++i)
        prefSum[i] = prefSum[i - 1] + a[i];

    for (int i = n; i >= 1; --i)
        sufMax[i] = max({sufMax[i + 1], i * i + i - prefSum[i]});

    for (int i = 1; i <= n; ++i)
        ans = max({ans, -i * i + i + prefSum[i - 1] + sufMax[i]});

    cout << ans + prefSum[n] << el;
    return;
}

signed main()
{
    setup();

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

akashgunalan

Thank you for your solution it was the simplest solution I understood I recently started cf.

HuTa

2 months ago, hide # ^ |

Very intuitive solution, I was able to understand it, thanks a lot! Just a small finding (may be wrong typo), delta should be

$$$ \Delta = (-l^2 + l + r^2 + r) + (- pref_r + pref_{l-1}) $$$

wery0

D2 is actually solvable in $$$O(\sqrt{A} \cdot \log{A})$$$: 349377750

adamant

Genfunc approach to F:

Think of lexicographic smallest "valid" sub-sequence. Split final sequence into $$$k+1$$$ parts:

Part $$$i$$$ for $$$i \leq k$$$ corresponds to the block containing numbers from $$$l_i$$$
The last part is the free block that may contain any numbers

We can enumerate each block independently, and then multiply their EGFs to get the EGF for the full sequence, as it will correspond to concatenating them.

For the last part, the EGF is simply $$$\frac{1}{1-mx}$$$ as we can append zero or more integers from $$$[1, m]$$$.

For the $$$l_i$$$ block, we can pick the order in which the elements appear in any of $$$l_i!$$$ ways. Then,

Until first element pops up, we can only use $$$m-l_i$$$ "free" numbers
Until second element pops up, we can use $$$m-l_i$$$ "free" numbers or the first element
...
Until last element pops up, we can use any of $$$m-1$$$ other numbers

This can also be perceived independently as concatenation of $$$l_i$$$ blocks, the $$$j$$$-th ending in the first occurrence of $$$a_{ij}$$$. Therefore, we get the EGF for the $$$i$$$-th block:

$$$ l_i! \prod\limits_{j=m-l_i}^{m-1} \frac{x}{1-jx} $$$

In other words, the answer to the whole problem is

$$$ [x^n] \frac{1}{1-mx} \prod\limits_{i=1}^k l_i! \prod\limits_{j=m-l_i}^{m-1} \frac{x}{1-jx} $$$

This can be evaluated in $$$O(n \log^2 n)$$$ with divide and conquer, or in $$$O(n \log n)$$$ with log and exp.

baldy

4 months ago, hide # ^ |

How in D1 the function is monotonic?

C's solution is beautiful

anyone knows how to arrive at the equations for C ? and also is there any proof or smtng for the alternate approach of forming array b.like we can get 2i — a[i] only if l==r , but then if we do that for the entire array a , and find the max sum subarray , how is it guaranteed to the right answer , like how is it related to (r — l + 1 ) * (l + r) ?

4 months ago, hide # |

how in D1 the function is monotonic, can someone provide a proof for that..

Tadas

This is a speculative guess, but I think that's because $$$p-\lfloor{\frac{p}{x}}\rfloor\leq p+1-\lfloor{\frac{p+1}{x}}\rfloor$$$ (on RHS we have +1, while $$$\lfloor{\frac{p+1}{x}}\rfloor$$$ can grow by at most 1 comparing with $$$\lfloor{\frac{p}{x}}\rfloor$$$)

PrimeCoder_

There is a non-dp solution to E where we collect the best candidates for the perimeter by integrating the cost within the coordinates and then brute force them to choose the best combination ,as the sample set of candidates we made is small the brute force does not give TLE , got the idea myself but as i am not good enough in implementation yet had to use AI. https://mirror.codeforces.com/contest/2169/submission/354519911 Can the idea be optimised?

rex333

My C++ solution for problem B

Code

ketoinPhoenix

Have a different solution to D1 :

As x is small, thought of iterating over x and finding the kth element after each iteration

For x = 0, res = k

For x = 1, and onward I iteratively check

how many elements smaller that k have to be removed which will be -> (res / y) and add it to res += res / y;

Now the new res might have been increased to a new range where more elements might have been deleted,

so now I keep calculating (res / y) — (prevRes / y), and updating res by adding this term and prevRes is just the older res without this term, I keep doing this till res / y == prevRes / y.

This guarantees that we have added the count of elements that have been deleted before res in the current iteration, and have recursively added count of all the elements that have been introduced newly after adding the deleted no. count

And k + (all these deletions for each iteration) will be the kth no. after x iterations.

Example : x = 2, y = 3, k = 5

Initialize res = 5 for x = 0

x = 1 => res += (res / y); res = 5 + 1 = 6

res / y = 2 and prevRes / y = 1, so res += 1 -> 7

res / y = 2 and prevRes / y = 2, done with x = 1

x = 2 => res += (res / y); res = 7 + 2 = 9

res / y = 3 and prevRes / y = 2, res += 1 -> 10

res / y = 3 and prevRes / y = 3. End Result = 10

Submission : https://mirror.codeforces.com/contest/2169/submission/355288758

I need help with figuring out the exact time complexity for this solution, to me it makes sense that it is x * number of times I'm adding those differences (res / y — prevRes / y) in each iteration until it's 0.

I could see that they reach 0 fast but not sure of the exact tc, is it logarithmic? How can I calculate

ByteWizard_22

Thanks a lot! Thought of similar approach, but was not able to develop properly.

tristansun

I think that although the formula given in the editorial for D2 is correct, the explanation slightly wrong or inadequate. The equation

$$$ p' = p - \left \lfloor \frac{p}{y} \right \rfloor $$$

does not have a unique solution for $$$p$$$ in terms of $$$p'$$$. For example, if $$$y = 3$$$ and $$$p' = 10$$$, then $$$p=14$$$ and $$$p=15$$$ both satisfy the equation. Instead of saying that we go from $$$p'$$$ to any $$$p$$$ which satisfies the equation, we should instead say that the algorithm goes from $$$p'$$$ to the unique value of $$$p$$$ such that if the operation was applied on $$$1, \dots, 10^{12}$$$ then $$$p$$$ would end up on position $$$p'$$$. This is equivalent to adding the stipulation that $$$p$$$ is not a multiple of $$$y$$$.

This value of $$$p$$$ is indeed equal to

$$$ p' + \left \lfloor \frac{p' - 1}{y - 1} \right \rfloor $$$

because the numbers $$$1, \dots, p$$$ must have had exactly

$$$ \left \lfloor \frac{p}{y} \right \rfloor = \left \lfloor \frac{p' - 1}{y - 1} \right \rfloor $$$

groups of size $$$y$$$ (remember that we stipulated that $$$p$$$ is not the last element of a group). You can also show this algebraically.

dejunchen

3 months ago, hide # |

First solution of the 2169C is wrong. How about the case 1 3 7 9 10?

1 3 9 7 10. Not 1 3 7 9 10.

With the case 1 3 9 7 10. f(0)=0, f(1)=1, f(2)=2, f(3)=-1, f(4)=0, f(5)=0. When l=3 ,f(l) gets the minimum value.The r is bigger than 3. r=4 or r=5,but the answer is wrong. The correct answer is l=1(l-1=0),r=2.

The second solution is correct! For 2169C!

Sorry, the first solution of 2169C is correct!

singhtejas1313

in problem B what is s[i]=='>' && s[i+1]=='*' answer should ne -1 but not accroding to code they have given

memoryallocator

2 weeks ago, hide # |

we subtract the number $$$\lfloor p/y \rfloor$$$ each time, and since $$$y$$$ is fixed, it follows that there are at most $$$\sqrt p$$$ different values of the subtracted numbers

I am a bit confused by this. Let $$$p = p_1 = 20, y = 3$$$. Then

$$$ p_2 = p_1 - \lfloor p_1 / y \rfloor = 20 - \lfloor 20 / 3 \rfloor = 20 - 6 = 14 \newline p_3 = p_2 - \lfloor p_2 / y \rfloor = 14 - \lfloor 14 / 3 \rfloor = 14 - 4 = 10 \newline p_4 = p_3 - \lfloor p_3 / y \rfloor = 10 - \lfloor 10 / 3 \rfloor = 10 - 3 = 7 \newline p_5 = p_4 - \lfloor p_4 / y \rfloor = 7 - \lfloor 7 / 3 \rfloor = 7 - 2 = 5 \newline p_6 = p_5 - \lfloor p_5 / y \rfloor = 5 - \lfloor 5 / 3 \rfloor = 5 - 1 = 4 \newline p_7 = p_6 - \lfloor p_6 / y \rfloor = 4 - \lfloor 4 / 3 \rfloor = 4 - 1 = 3 \newline p_8 = p_7 - \lfloor p_7 / y \rfloor = 3 - \lfloor 3 / 3 \rfloor = 3 - 1 = 2 \newline p_9 = p_8 - \lfloor p_8 / y \rfloor = 2 - \lfloor 2 / 3 \rfloor = 2 - 0 = 2 $$$

The unique values of $$$ \lfloor p_k / y \rfloor $$$ are $$$ 6, 4, 3, 2, 1, 0 $$$. There are 6 unique values in total. But $$$ \lceil \sqrt p \rceil = \lceil \sqrt 20 \rceil = 5 \lt 6 $$$.

awoo's blog

Problem C can be solved using Dynamic Programming: