imbalanceForces

In the editorial of $$$E$$$, it is mentioned that $$$c_{i,0}=\sum_{j=1}^{i}{a_j}$$$. Actually, it should be $$$c_{i,0}=\sum_{j=1}^{i+1}{a_j}$$$ (with $$$c_{0,0}=a_1$$$ and $$$c_{n,0}$$$ is not needed).

Reason:

When we say $$$b_i$$$ (at $$$k$$$) $$$=$$$ $$$b_{i-1}$$$ (at $$$k$$$) $$$+$$$ $$$b_{i-1}$$$ (at $$$k-1$$$), this is true only when $$$k>1$$$, because this will cause the last term in both $$$\sum_{j=1}^{j=i}{{i-j \choose k} \cdot a_j}$$$ and $$$\sum_{j=1}^{j=i}{{i-j \choose k-1} \cdot a_j}$$$ to be $$$0$$$ (as $$$0 \choose x$$$ is $$$0$$$ for positive $$$x$$$). However, this is not the case for the $$$2^{nd}$$$ summation when $$$k=1$$$. The last term will not be eliminated as $$${0 \choose 0}=1$$$.

Submission.

SorrowForces

I liked c

My 3D Dp solution is giving wrong output ?? It would be huge help if someone explain . Thanks in advance !
https://codeforces.com/contest/1832/submission/205945700

D1

I see applying Operation 2 $$$n$$$ or $$$n-1$$$ times from begin.

then, $$$k-(n-(n+k) ~\text{mod}~ 2)-1$$$ should be $$$k-(n-(n+k) ~\text{mod}~ 2)+1$$$ ?

Or, $$$k-n+1 + (n+k) \text{mod}~2$$$

Problem B:

I don't understand what is 'k — m' maximums, and I don't know what is k when m is the number of operations. Can anyone explain from me pls ??

I can't understand how he solved maximum sum. Can someone help me understand it?

For problem F, quadrangle inequality properties also apply to array partition DP. So we can use Knuth's optimization for a second time on $$$dp$$$, which leads an $$$O(n^2)$$$ algorithm.

This is my submission: https://codeforces.com/contest/1832/submission/206185565.

Can problem A be solved in a different way other than unique function. Can't really understand it :(

Hi. can someone please tell me the error in this code which I used without prefix array

#include <bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;


int maxRemoval(vector<int> &v){
    int n = v.size(), sum = 0;
    for(int i=0;i<n-1;++i){
        sum += v[i];
    }
    return sum;
}

int minRemoval(vector<int> &v){
    int n = v.size(), sum = 0;
    for(int i=2;i<n;++i){
        sum += v[i];
    }
    return sum;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
    
        int n, k;
        cin >> n >> k;
        vector<int> v(n);
        for(int i=0;i<n;++i){
            cin >> v[i];
        }
        sort(begin(v), end(v));
       
        int ans = 0;
        for(int i=0;i<k;++i){
            int s1 = maxRemoval(v);
            int s2 = minRemoval(v);
        
            ans = max(s1, s2);
            if(s1 < s2){
                v.erase(v.end()-1);
            }
            else{
                v.erase(v.begin());
                v.erase(v.begin());
            }

        }
  
        cout << ans << endl;
  
    }
}

It runs correctly for 1st test case but tells that there is wrong answer on test 2 wrong answer 2459th numbers differ - expected: '8', found: '7' I mean does it really check 2459th number. did the testers even count upto that thing. I doubt it. Link to My Submission

Why is this code getting wrong ans in TC 3 ?

void solve() { int n;cin>>n; int k;cin>>k; vl a(n); fr(i,0,n) cin>>a[i]; sort(all(a));

int l=0,r=n-k;
ll sum=0ll;
fr(i,0,r)
    sum+=a[i];

// cout<<sum<<endl;

while(r<n && l<r)
{
    ll temp=sum-a[l]-a[l+1]+a[r];
    r++;
    l+=2;
    sum=max(sum,temp);

}
cout<<sum<<endl;

}

For the C, there is a counter example of 5 2 5 3 7 9 10, which should give the output as 4 (7 9 3 10) but from the code it will give 5

(first time commenting, apologize for bad formatting)

Problem B:

1 I try greedy by comparing oper1 and oper2, and it cant even pass example 5 cuz it gives me 12+13+15 = 40 instead of 10+11+12+13 = 46.

2 I then try to do it in reversed order ie i assume that I do oper2 for k times first. ie remove maximum for kth time.

https://codeforces.com/problemset/submission/1832/208181362

then i compare the most recently deleted maximum and the sum of 2 minimums. restore the maximums and delete the 2 minimums by moving the ptrs, if the maximum is greater.

It works most of the time.

it fails when:

9 3

50 51 60 61 62 63 102 103 900

my code: 60+61+62+63+102 = 348

answer: 102+103+900 = 1105

3 i change the code to do oper1 k times first. https://codeforces.com/problemset/submission/1832/208186847

similar comparison of 2.

it fails when:

9 3

25 26 27 28 29 30 31 32 60

my code: 31+32+60 = 123

answer: 25+26+27+28+29+30 = 165

4 i combine 2 and 3 by finding maximum of the results from two algorithms. https://codeforces.com/problemset/submission/1832/208192875

then it works.

Is there a reason that combining 2 and 3 give correct result for all of the cases?

https://codeforces.com/contest/1832/submission/209504476

I was trying to solve the Maximum Sum challenge, I tested it on my computer and it was fine, the test outputs were right as well but after submission it returned " Probably, the solution is executed with error 'out of bounds' on the line 24 " I couldn't find the error so if anyone could tell me were I'm wrong it would be very useful, thanks!

int k = unique(s.begin(), s.end()) — s.begin();

можете объяснить почему (s.begin(), s.end()) — s.begin() почему мы отнимаем begin

Hello guys, I am getting TLE in 1832E - Combinatorics Problem. I don't think I have made any logical errors, but I can't seem to understand why it's giving TLE. Please help :( -> 209759092

In B, can any one tell me what is the mistake I made in my code https://codeforces.com/contest/1832/submission/209911724. It will be very helpful for me . TIA

Will I learn Pascal Triangle in my lifetime ? Will I learn combinatorics in mylifeime ?

In Problem C,

Why should we use this?

n = unique(a.begin(), a.end())-a.begin(); int ans = n;

Why doesn't this pass some test cases?

int ans = unique(a.begin(), a.end())-a.begin();

I like the awoo solutions.. He make the solutions like my friend explaining to me.. Thx man++.

can someone please explain how this test case in problem B maximum sum is giving o/p 46

6 2

15 22 12 10 13 11

please help my code

include <bits/stdc++.h>

using namespace std;

define ll long long

define all(x) x.begin(), x.end()

define pb push_back

define F first

define S second

const int M = 1e9 + 7;

define ll long long

define yes cout << "YES" << endl

define no cout << "NO" << endl

define n1 cout << -1 << endl

int main() { int t; cin >> t; while (t--) { ll int n; cin >> n; int k; cin >> k; vector< ll int> v; for (ll int i = 0; i < n; i++) { ll int x; cin >> x; v.push_back(x); }

    sort(v.begin(), v.end());
    while (k--)
    {

       if (v[0] + v[1] <= v[v.size() - 1])
       {
         //cout << "hi" << endl;

         v.erase(v.begin(), v.begin() + 2);
       }
       else
       {
         //cout << "hello" << endl;

         v.pop_back();
       }
       if(v.size()<=2)
       {
         break;
       }
    }

    ll int ans = 0;
    for (ll int i = 0; i < v.size(); i++)
    {
       ans = ans + v[i];
    }
    cout << ans << endl;
}

}