Codeforces Round 1049 (Div. 2) Editorial

№	Пользователь	Рейтинг
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

№	Пользователь	Вклад
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	141
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	BledDest	132
9	maroonrk	131
10	qwexd	129

Idea: shorya1835 Preparation: wakanda-forever

Solution

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
 
        int n;
        string s;
        cin >> n >> s;
 
        int ans = 0;
 
        string p = s;
        sort(p.begin(), p.end());
 
        for(int i = 0; i < n; i++) if(s[i] != p[i]) ans++;
 
        cout << ans / 2 << '\n';
 
    }
    return 0;
}

2140B - Another Divisibility Problem

Idea: wakanda-forever Preparation: wakanda-forever

Solution

Code

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int t;
    cin >> t;
    while(t--){
        int x;
        cin >> x;
        cout << 2*x<< '\n';
    }
    return 0;
}

2140C - Ultimate Value

Idea: shorya1835 Preparation: wakanda-forever

Solution

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
 
        int n;
        cin >> n;
 
        vector<long long> a(n);
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
 
        ll ans = 0;
        for(int i = 0; i < n; i++){
            if(i % 2) ans -= a[i];
            else ans += a[i];
        }
 
        ll init = ans;
 
        for(int i = 0; i < n; i++) ans = max(ans, init + i - (i % 2));
 
        ll min_even = LLONG_MAX / 2, min_odd = LLONG_MAX / 2;
        for(int i = 0; i < n; i++){
            if(i % 2){
                ans = max(init + i + a[i] + a[i] - min_even, ans);
                min_odd = min(min_odd, i - a[i] - a[i]);
            }
            else{
                ans = max(init + i - a[i] - a[i] - min_odd, ans);
                min_even = min(min_even, i + a[i] + a[i]);
            }
        }
 
        cout << ans << '\n';
 
    }
 
    return 0;
}

2140D - A Cruel Segment's Thesis

Idea: shorya1835 Preparation: shorya1835

Solution

Code

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

#define fo(i, a, b) for (ll i = a; i < b; i++)
#define F first
#define S second
#define pb push_back
#define mp make_pair
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    ll T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        vector<pl> a(n);
        fo(i, 0, n)cin >> a[i].first >> a[i].second;
        ll ans = 0;
        fo(i, 0, n)ans += a[i].second - a[i].first + 1;
        ans += n / 2;
        vector<pair<ll, pl>> b(n);
        fo(i, 0, n) {
            b[i].second = a[i];
            b[i].first = a[i].first + a[i].second;
        }
        sort(b.begin(), b.end());
        if (n % 2 == 0) {
            fo(i, 0, n) {
                ans += a[i].second;
            }
            fo(i, 0, n / 2) {
                ans -= b[i].first;
            }
            cout << ans - n - n / 2 << "\n";
        }
        else {
            ll k = 0, w = 0;
            fo(i, 0, n) {
                w += a[i].second;
            }
            fo(i, 0, n / 2+1) {
                w-= b[i].first;
            }
            fo(i, 0, n / 2 + 1) {
                k = max(k, w + b[i].S.F);
            }
            w += b[n / 2].first;
            fo(i, n / 2 + 1, n) {
                k = max(k, w - b[i].S.S);
            }
            cout << ans + k  - n - n / 2 << "\n";
        }
    }
}

2140E1 - Prime Gaming (Easy Version)

Idea: Divine_Spark Preparation: shorya1835

Solution

Code

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
int removebit(int n, int bit)
{
    int msk = (1 << 22);
    int filtermask = msk - (1 << bit);
    return ((n >> 1) & filtermask) | (n & ((1 << bit) - 1));
}
const ll MOD = 1e9+7;
class mint
{
public:
    ll val;
    static ll mod_exp(ll a, ll b)
    {
        ll res = 1;
        a = a % MOD;
        while (b > 0)
        {
            if (b % 2 == 1)
                res = (res * a) % MOD;
            b /= 2;
            a = (a * a) % MOD;
        }
        return res;
    }
    static ll gcdExtended(ll a, ll b, ll *x, ll *y)
    {
        if (a == 0)
        {
            *x = 0, *y = 1;
            return b;
        }
        ll x1, y1;
        ll gcd = gcdExtended(b % a, a, &x1, &y1);
        *x = y1 - (b / a) * x1;
        *y = x1;
        return gcd;
    }
    static ll modInverse(ll a)
    {
        ll x, y;
        ll g = gcdExtended(a, MOD, &x, &y);
        g++;
        ll res = (x % MOD);
        if (res < 0)
            res += MOD;
        return res;
    }
    mint() { val = 0; }
    mint(ll x)
    {
        val = x % MOD;
        if (val < 0)
            val += MOD;
    }
    mint &operator+=(const mint &other)
    {
        val += other.val;
        if (val >= MOD)
            val -= MOD;
        return (*this);
    }
    mint &operator-=(const mint &other)
    {
        val -= other.val;
        if (val < 0)
            val += MOD;
        return (*this);
    }
    mint &operator*=(const mint &other)
    {
        val = (val * other.val) % MOD;
        return (*this);
    }
    mint &operator/=(const mint &other)
    {
        val = (val * modInverse(other.val)) % MOD;
        return (*this);
    }
    mint &operator=(const mint &other)
    {
        val = other.val;
        return (*this);
    }
    mint operator+(const mint &other) const { return mint(*this) += other; }
    mint operator-(const mint &other) const { return mint(*this) -= other; }
    mint operator*(const mint &other) const { return mint(*this) *= other; }
    mint operator/(const mint &other) const { return mint(*this) /= other; }
    bool operator==(const mint &other) const { return val == other.val; }
 
    mint operator++()
    {
        ++val;
        if (val == MOD)
            val = 0;
        return (*this);
    }
    mint operator++(int)
    {
        val++;
        if (val == MOD)
            val = 0;
        return mint(val - 1);
    }
    mint operator--()
    {
        --val;
        if (val == -1)
            val = MOD - 1;
        return (*this);
    }
    mint operator--(int)
    {
        val--;
        if (val == -1)
            val = MOD - 1;
        return mint(val + 1);
    }
 
    // ^ has very low precedence, careful!!
 
    template <typename T>
    mint &operator^=(const T &other)
    {
        val = mod_exp(val, other);
        return (*this);
    }
    template <typename T>
    mint operator^(const T &other) const { return mint(*this) ^= other; }
 
    mint &operator^=(const mint &other)
    {
        val = mod_exp(val, other.val);
        return (*this);
    }
    mint operator^(const mint &other) const { return mint(*this) ^= other; }
 
    template <typename T>
    explicit operator T() { return (T)val; }
    template <typename T>
    friend mint operator+(T other, const mint &M) { return mint(other) + M; }
    template <typename T>
    friend mint operator-(T other, const mint &M) { return mint(other) - M; }
    template <typename T>
    friend mint operator*(T other, const mint &M) { return mint(other) * M; }
    template <typename T>
    friend mint operator/(T other, const mint &M) { return mint(other) / M; }
    template <typename T>
    friend mint operator^(T other, const mint &M) { return mint(other) ^ M; }
 
    friend std::ostream &operator<<(std::ostream &output, const mint &M) { return output << M.val; }
    friend std::istream &operator>>(std::istream &input, mint &M)
    {
        input >> M.val;
        M.val %= MOD;
        return input;
    }
};
 
const int maxn = 20;
const int maxm = 30;
 
ll modpow(ll a , ll b ) {
    ll res = 1 ;
    a %= MOD;
    while( b > 0 ) {
        if( b&1 ) res = ( res*a ) % MOD;
        a = ( a*a ) % MOD;
        b >>= 1 ;
    }
    return res ;
}
 
int main()
{   int t;
    cin >> t;
    while(t--){
        bool pl = 1;
        int n, m;
        cin >> n >> m;
        int k,x;
        cin >> k;
        vector<int> good;
        for(int i=0;i<k;i++){
            cin >> x;
            good.push_back(x);
        }
        if(m==1){
            cout << 1<< "\n";
            continue;
        }
        vector<vector<vector<bool>>> dp(2, vector<vector<bool>>(n + 1));
        int cntt = 0;
        for (int i = 1; i <= n; i++)
        {
    
            dp[0][i].resize(1 << i);
            dp[1][i].resize(1 << i);
            if (i == 1)
            {
                for (int j = 0; j <= 1; j++)
                {
                    for (int k = 0; k <= 1; k++)
                    {
                        dp[j][i][k] = k;
                    }
                }
            }
            else
            {
                for (int msk = 0; msk < (1 << i); msk++)
                {
                    bool ans0 = 1;
                    bool ans1 = 0;
                    for (auto x :good)
                    {
                        if (x <= i)
                        {
                            cntt++;
                            int finmsk = removebit(msk, x - 1);
                            ans0 &= dp[1][i - 1][finmsk];
                            ans1 |= dp[0][i - 1][finmsk];
                        }
                        else
                        {
                            break;
                        }
                    }
                    dp[0][i][msk] = ans0;
                    dp[1][i][msk] = ans1;
                }
            }
        }
        mint finans = 0;
        for (int r = 0; r < (1<<n); r++)
        {   
            finans += 1+dp[pl][n][r];
            
        }
        cout << finans << endl;
    }
}

2140E2 - Prime Gaming (Hard Version)

Idea: Divine_Spark Preparation:wakanda-forever, shorya1835

Solution

Code


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int removebit(int n, int bit)
{
    int msk = (1 << 22);
    int filtermask = msk - (1 << bit);
    return ((n >> 1) & filtermask) | (n & ((1 << bit) - 1));
}

const int maxn = 20;
const int maxm = 30;
 
ll binpow(ll a,ll b,ll m = MOD){
    ll res = 1;
    while (b){
        if (b&1) res = (res*a)%m;
        a = (a*a)%m;
        b>>=1;
    }
    return res;
}
int main()
{   int t;
    cin >> t;
    while(t--){
        bool pl = 1;
        int n, m;
        cin >> n >> m;
        int k,x;
        cin >> k;
        vector<int> good;
        for(int i=0;i<k;i++){
            cin >> x;
            good.push_back(x);
        }
        vector<vector<vector<bool>>> dp(2, vector<vector<bool>>(n + 1));
        vector<vector<vector<int>>> cnt(2, (n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1))));
        int cntt = 0;
        for (int i = 1; i <= n; i++)
        {
    
            dp[0][i].resize(1 << i);
            dp[1][i].resize(1 << i);
            if (i == 1)
            {
                for (int j = 0; j <= 1; j++)
                {
                    for (int k = 0; k <= 1; k++)
                    {
                        dp[j][i][k] = k;
                    }
                    cnt[j][1][1]++;
                }
            }
            else
            {
                for (int msk = 0; msk < (1 << i); msk++)
                {
                    bool ans0 = 1;
                    bool ans1 = 0;
                    for (auto x :good)
                    {
                        if (x <= i)
                        {
                            cntt++;
                            int finmsk = removebit(msk, x - 1);
                            ans0 &= dp[1][i - 1][finmsk];
                            ans1 |= dp[0][i - 1][finmsk];
                        }
                        else
                        {
                            break;
                        }
                    }
                    dp[0][i][msk] = ans0;
                    dp[1][i][msk] = ans1;
                    cnt[0][i][__popcount(msk)] += ans0;
                    cnt[1][i][__popcount(msk)] += ans1;
                }
            }
        }
        ll finans = 0;
        for (int r = 1; r <= n; r++)
        {   
            for(int k=1;k<=m;k++){
                finans += (((binpow(k-1,n-r)*binpow(m-k+1,r))%MOD) * (cnt[pl][n][r]))%MOD;
            }
        }
        cout << finans%MOD << endl;
    }
}

Bonus

2140F - Sum Minimisation

Idea: shorya1835 Preparation: wakanda-forever, shorya1835

Solution

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<ll, ll> pl;
#define fo(i, a, b) for (ll i = a; i < b; i++)
#define pb push_back

ll gcd(ll a,ll b){
    if(a==0)return b;
    else return gcd(b%a,a);
}
vl a;
ll lc, s, n;
bool good(){
    bool v=1;
    if(n>23){
        fo(i,0,n){
            if(a[i]!=a[0]){
                v=0;
                break;
            }
        }
    }
    else{
        fo(i,2,n){
            fo(j,0,n){
                if((a[j]%i)!=(a[0]%i)){
                    v=0;
                    break;
                }
            }
        }
    }
    v&=(s%n==0);
    return v;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    ll T;
    cin >> T;
    while (T--) {
        cin >> n;
        a.clear();
        a.resize(n);
        s=0;
        fo(i,0,n){
            cin >> a[i];
            s+=a[i];
        }
        sort(a.begin(),a.end());
        lc=1;
        if(n>23){
            lc=1e10;
        }
        else{
            fo(i,2,n+1){
                lc=(lc*i)/gcd(lc,i);
            }
        }
        if(good()){
            cout << s<< "\n";
            continue;
        }
        a[0]--;
        s--;
        if(good()){
            cout << s<< "\n";
            continue;
        }
        cout << -1 << "\n";


    }
}

Thanks to satyam343 for his help throughout the round.

[-]>[-]+[[-]>[-],[+[-----------[>[-]++++++[<------>-]<--<<[->>++++++++++<<]>>[-<<+>>]<+>]]]<]< // Inputs the number of testcases [> [-]>[-]+[[-]>[-],[+[-----------[>[-]++++++[<------>-]<--<<[->>++++++++++<<]>>[-<<+>>]<+>]]]<]< // Inputs n [->++<]> // Calculate 2*n >[-]>[-]+>[-]+<[>[-<-<<[->+>+<<]>[-<+>]>>]++++++++++>[-]+>[-]>[-]>[-]<<<<< [->-[>+>>]>[[-<+>]+>+>>]<<<<<]>>-[-<<+>>]<[-]++++++++[-<++++++>]>>[-<<+>>]<<] <[.[-]<]< // Output 2*n [-]++++++++++.[-] // Output newline character <<- // Decrement testcase number ]

import sys input = sys.stdin.readline MOD = 1_000_000_007 def ans(): n = int(input()) l = list(map(int, input().split())) s = x = y = 0 m = 1_000_000_007 ma = -1_000_000_007 for j in range(n): if j % 2 == 0: s += l[j] if (2*l[j] + j) < m: m, y = (2*l[j] + j), j else: s -= l[j] if (2*l[j] + j) > ma: ma, x = (2*l[j] + j), j xa = ya = 0 mr = 1_000_000_007 maa = -1_000_000_007 for j in range(1, n+1): if (n - j) % 2 == 0: if (2*l[-j] + j - 1) < mr: mr, ya = (2*l[-j] + j - 1), n - j else: if (2*l[-j] + j - 1) > maa: maa, xa = (2*l[-j] + j - 1), n - j u1 = ma - m u2 = maa - mr u = max(u1, u2) return s + max(u, (n - 1 - (n + 1) % 2)) for _ in range(int(input())): print(ans())

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

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

Ashar-Usmani

12 месяцев назад, скрыть # |

+37

noooo I want yesterday's rating please this one killed me:(

→ Ответить

ashish1729

A was very tricky for me to prove that such strategy gives minimum moves.

mrinmoy66sadhukhan

12 месяцев назад, скрыть # ^ |

← Rev. 2 →

yes..in low rating questions proving always more tricky than solving.

Nirupam

For the case 110100, we can take i = 1, j = 3, k = 4 and the string will become 111000 which is sorted but the answer given in test case is 2 steps

iblamemohit

000111 is considered sorted not 111000

tfg

+10

E2 bonus

shorya1835

That's for non distinct piles, bonus asks for distinct.

I'm pretty sure that

It's not that complicated, you can derive something closed form combined with the dp

+47

My principle if that if I don't need to think I don't think.

bruh

+19

That's correct

puniTT

Got clapped but round was nice, thanks !

lol

Prof_PsYcHo

Hey can anyone tell me what is wrong in my approach. And please while pointing out my mistake, tell me how to think in the way to get to the approach mentioned in the editorial. It would be of great help to me. 337853452

_KS_

Check it for this tc

1
4
5 5 5 5

Answer should be 3 (swap first and last element), but your code is giving 2 on this tc

Ivan_len

What's case 1 in editorial for F? Doesn't [3, 0, 1] fall into case 1, but allow only 1 single operation?

Array $$$a$$$ is assumed to be sorted in the blog, updating the blog

Nasr_

337862621

any clue why my code keeps wrong? give me hint plz

virinci

If you look at the failing 26th test case, it says:

3 2 2 1

You can see where your logic has fault. Hint: If you do mx-mn then you are also doing index(mx) — index(mn). This will be correct when mx lies to the right of mn, but that's not the case here.

uttej_777

I solved B by observing the pattern and got y = 10^9 - 1 - x always works, can anyone prove this

Someone did: https://codeforces.me/blog/entry/146147?#comment-1307743

Wax

Yes! let we have chosen y ...d=(length of y****)+1,,and mod=x+y. Then (x#y) = x*(10^d)+y.Then x#y is divisable by x+y;it will hold iff (x*(10^d)+y)%mod=0 i.e (x*(10^d)%mod+y%mod=0 as mod>x then y%mod=y so (x*(10^d))%mod must be x to hold the criteria of (x#y)%mod=0; we already know mod>x and mod>y; so if we can make 10^d %mod==1 we can fillup the criteria....so it will become 1 when mid=10^d-1 i.e x+y=10^d-1;.....thus it is ovbious for every d<i<=9; max value of d=9,,,,we can choose choose y=999999999-x everytime and it will pass every testcase!**____**

saquib2508

-6

2140B - Another Divisibility Problem can be solved with other values of $$$y$$$ as well, for example $$$y = 999... - x$$$ depending on $$$x$$$. Because,

$$$x \text{#} y = x \cdot 10^d + y = x \cdot (10^d − 1) + (x + y)$$$

So, to make the $$$10^d - 1$$$, which is basically $$$9999...$$$ for $$$d$$$ times, to be divisible by $$$x + y$$$, we can make $$$x + y$$$ itself be of this shape. For $$$x$$$ to be any $$$k$$$-digit number, $$$x + y$$$ can be of shape with any $$$k$$$ or more digits of $$$9$$$ s. Since the constraints state that $$$x \lt 10^8$$$ and $$$y \lt 10^9$$$, we can set $$$x + y$$$ to be $$$999,999,999$$$ i.e. $$$y = 10^9 - 1 - x$$$.

Also, obviously, $$$y = 8 \cdot x$$$ works for the same reason as tutorial.

Upd: can anybody explain why the downvotes? Cause I'm pretty sure there's nothing wrong in terms of logic cause I literally got AC with this approach. 337798106

Ashwanth.K

+11

E2 Bonus Solution:

Spoiler

satyam343

As $$$n$$$ is small, we can avoid interpolation using this idea.

bhajji

another way to look at D

SlInevitable2003

+17

My solution to Problem D works as follows: the original problem is equivalent to finding a matching among the intervals $$$1, \cdots, n$$$ that maximizes the value

$$$ \displaystyle\sum_{(j,k) \text{ are matched}} \max(r_j - l_k, r_k - l_j). $$$

Using the identity $$$\max(A, B) = \frac{A + B}{2} + \frac{|A - B|}{2}$$$, this expression can be rewritten as

$$$ \displaystyle\sum_{(j,k)} \max(r_j - l_k, r_k - l_j) = \sum_{(j,k)} \frac{(r_j - l_j) + (r_k - l_k)}{2} + \sum_{(j,k)} \frac{|(r_j + l_j) - (r_k + l_k)|}{2} \quad (\star). $$$

For even $$$n$$$, the first term is constant (equal to half the total sum of the lengths of the intervals), and the second term is maximized by partitioning the array $$$a[j] = r_j + l_j$$$ into two halves and subtracting the sum of the smaller half from the sum of the larger half. This can be computed efficiently using prefix sums in $$$\mathcal{O}(1)$$$ time per query after preprocessing.

For odd $$$n$$$, one interval (say $$$i$$$) remains unmatched. We enumerate each $$$i = 1, \cdots, n$$$ as the unmatched interval, and the value in equation $$$(\star)$$$ can be easily evaluated in $$$\mathcal{O}(1)$$$ time using a similar prefix sum approach with minor modifications, resulting to an $$$\mathcal{O}(n)$$$ solution.

This method is basically identical to the one in the editorial, but more clear to me.

slyezil

the second problem was a humbling experience for me

_CHAT_GPT_PREMIUM_

can someone explain this part This can be solved by maintain prefix minimum over odd and even indexes.

dj4zo6u.6

https://codeforces.me/contest/2140/submission/337817036

for problem E, dp[i][mask][1] is actually the same as dp[i][~mask][0]; you can just maintain one

Osama-Ashraf

For problem C, I used a DP approach. Surprisingly, when I implemented it with a regular array (initialized using memset), it resulted in TLE. However, switching to a map for memoization led to an AC. Could someone explain why this happens?

_Kee

You initialize the whole DP table with $$$8 \cdot 10^5$$$ elements for every test case. Since there are $$$10^4$$$ test cases at most, you're overwriting $$$8 \cdot 10^9$$$ elements in sum, which is too slow.

Oh, I see now. This means my array-based solution ends up doing about $$$2 \cdot 10^5$$$ operations for each test case, which ignores the fact that "the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$". In contrast, the map-based solution only stores and processes the states that are actually needed, so its complexity is closer to $$$O(n)$$$ overall. Is that correct?

You're correct. You don't need the whole DP array for a test case with smaller $$$n$$$. If you are given $$$n$$$ for a test case, make sure you only touch $$$O(n)$$$ elements; then your solution won't time out.

I see, thanks!

I have faced so many WAs over the years for this reason that I always take extra care when clearing/initializing arrays. Always clear only n+5 (or 2n + 5) elements, don't touch higher indices since you don't need them.

You'll get used to it haha. Good luck!

Kuroudo

Hello Osama, i want to show you a trick you can use when you come across dp problems that involve test cases, as someone previously replied clearing your dp each case is too slow, but also the map memo isn't the best practice when it comes to this sort of problems.

There are two main ways to to this better, first is to give each test case an id, and to distinguish if you have been in this state before in the same test case you check if vis[state] equals the current id. 338980284

Another way is to clear exactly the size you need for this test case, after taking input n, loop and set it to the value you want.

338981249

Hope this helps.

Thanks a lot, Adham — that was really helpful. I like how these approaches let us stick with arrays instead of maps and still avoid TLE. There’s just one thing I’m not fully clear on: in the first solution, the vis array isn’t initialized. Is it safe to compare its values like that? If not, then initializing it once like int vis[(int)(2e5 + 5)][2][2]{}; should be enough, right?

Welcome , glad to help.

When an array is declared globally it’s initialized with zeros, same for integers.

where balanced paranthesis come from in d editorial??? (*cry emoji)

How can u directly find out left out segment in O(1) in D editorial ??

DarkDevilVaqif

Oh WOW, that's a fast editorial.

Loved the problems, and I FINALLY became a specialist.

I got the idea of C, but for those who didn't, I think the change in the statement of C gave it away. B was a little hard tho

PokemonMaster

2140B extended The editorial was prepared together with my coach, after he tried during the contest to brute-force all divisors of $$$10^k-1$$$ and $$$x$$$ and ran into TLE. Submission.

moorally

What is wrong in this solution for D:

First we initially compute the sum of all segments , Initial_sum = $$$S = \sum_{i=1}^{n} y_i - x_i$$$ then we want to compute the additional segments length formed by marking these segments, if we sort the $$$l_i$$$'s and $$$r_i$$$'s and then take the sum of (highest $$$r_i$$$ — least $$$l_i$$$) + (2nd highest $$$r_i$$$ — 2nd least $$$l_i$$$) + ..... and add this sum to the Initial_sum

i_squared

You probably mean the highest r_i — least l_j for distinct i and j. The problem arises in the case when a segment with the largest r_i contains all other segments. In that case we have a choice between r_i of largest segment — second highest l_i and second highest r_i — l_i of largest segment.

Consider these segments: [1, 100], [5, 90], [98, 99]. You select the first two, but the optimal way is to take the first and the third segments.

Harshvardhan_Acharya

Can someone please explain the solution of E2 after calculating the dp values. How is it calculating the original answer from binary(0, 1)?

Divine_Spark

For a configuration where alice wins in easy version with the bits that are 1 here are values that are >= k (for some k we are looping through) and other(0) values are < k then Alice can Force Bob into making the final Answer >=k as it forced Bob into making the final value 1 for the corresponding 0-1 mask. so we just need to count for every k the sum of masks * no of ways to generate this mask (1 filled by >=k value and 0 filled by <k values)

jobin491

(k−1)^n−r⋅(m−k+1)^r⋅cnt[r]

isn't this line just the number of ways to create a mask with (n-r) places with < k and r places with >=k, cnt[r] times. So then how how are we accounting for the sum of the actual values left at last? What am i missing here?

For problem D, a very "neat" way of reaching the greedy conclusion is by expanding the formula of the chosen segments' sum. Let's name the of chosen segments $$$C$$$ and the rest be $$$R$$$.

Our formula is :

$$$ \sum_{i \in C} r_i - \sum_{j \in R} l_j $$$

If we manage to eliminate contribution of group $$$R$$$ from this equation it will be easy to select group $$$C$$$ to maximize this expression. To do so we can expand the second term, based on this substitution :

$$$\sum_{j \in R} l_j = \sum_{i=1}^n l_i - \sum_{k \in C} l_k $$$

Where $$$n$$$ is the input size, by substitution our formula becomes :

$$$ \sum_{i \in C} r_i - (\sum_{i=1}^n l_i - \sum_{i \in C} l_i )$$$ $$$ \sum_{i \in C} r_i + \sum_{i \in C} l_i - \sum_{i=1}^n l_i $$$ $$$ \sum_{i \in C} (r_i + l_i ) - \sum_{i=1}^n l_i $$$

Now it's clear to see that maximizing this expression is equivalent to maximizing sum of right and left of a segment, since summation of all lefts is constant.

Rudraksh

thanks for the straight forward explanation

Glad to help.

Anubhav_Sultania

"In Problem D editorial it says you can directly find the left out segment in O(1) — can someone explain how to actually do that part?"

MatttNguyen

Here's a brainf*ck solution of 2140B - Another Divisibility Problem for no reason

(Assuming all cells are 32-bit instead of 8-bit as normal, if someone can implement an 8-bit solution I'm more than excited to see it)

woonder

I don't understand the complexity in E1, isn't is supposed to be $$$O(n^2 \cdot 2^n)$$$, because of the for loop over "good" vector?

Thank you!!!

Similar problem for B from Project Euler. Editorial

bkdn25.yellowdude

In the editorial for problem D, I dont understand:

this part of editorial

My question being

the question

Thanks a lot in advance!

I am not sure, what your question is, can you elaborate?

I understand that part of the editorial

as follows.

Sorry if I misunderstood the editorial. And please excuse my English as well.

← Rev. 3 →

aaryamannx

For problem F, is y taken to be the absolute value of x — floor(x/k)*k? I'm not sure if it's ever possible to get infinitely decreasing sum otherwise.

Geothermal

I think there's a slight logical error in Case 2 in the editorial for F. The editorial asserts that if any operation can be performed on the last n-1 elements of the array, then performing that operation will take us to Case 1. This is not true when the operation only modifies one element and that element is equal to the minimum of the array. For example, consider the array [1, 1, 3, 3]. We can perform an operation on the three larger elements, which makes the array [0, 1, 3, 3], which does not fall under Case 1.

The reason the model solution still works is that if this happens, then we can perform the same operation again, replacing the element that was decreased with the original minimum element of the array. At this point, we have two occurrences of the original minimum — 1, so we have an element other than $$$a_1$$$ with the opposite parity of the elements of the original array, putting us into Case 1.

Yes, i am aware of that case, in my rough editorial i had written sometime ago, operation wasn't singular but plural. I had mistakenly changed it, when formalizing it. Thanks for pointing it out.

_Leon

When receiving the following input, the given code for problem F outputs -1, but I cannot figure out a way to achieve a sum of less than $$$12$$$. Maybe there's still some special cases when $$$n=3$$$?

1
3
2 2 10

Do operation on whole array to get a=[1,1,10], after that you can repeat the operation 1st, 3rd element and 1st,2nd elements infinitely.

Sorry, it seems that I misunderstood the problem. I thought it was "decrease the y-th element", haha. Thank you for helping out!

Blundermove

11 месяцев назад, скрыть # |

I don't understand this :

for (int r = 1; r <= n; r++)
{   
    for(int k=1;k<=m;k++){
        finans += (((binpow(k-1,n-r)*binpow(m-k+1,r))%MOD) * (cnt[pl][n][r]))%MOD;
    }
}
cout << finans%MOD << endl;

Why is the result calculated this way?

SHIVANG12

what is wrong with this approach for C-

Sean222299

2 месяца назад, скрыть # |

C is a nice problem. I almost solved it, but didn't complete the code.

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

E2 Bonus Solution: