awoo's blog

Educational Codeforces Round 148 Editorial
By awoo, history, 3 weeks ago, translation, In English

1832A - New Palindrome

Idea: BledDest

Tutorial
Solution (Neon)

1832B - Maximum Sum

Idea: BledDest

Tutorial
Solution (awoo)

1832C - Contrast Value

Idea: BledDest

Tutorial
Solution (Neon)

1832D1 - Red-Blue Operations (Easy Version)

Idea: BledDest

Tutorial

1832D2 - Red-Blue Operations (Hard Version)

Idea: BledDest

Tutorial
Solution (awoo)

1832E - Combinatorics Problem

Idea: BledDest

Tutorial
Solution (BledDest)

1832F - Zombies

Idea: BledDest

Tutorial
Solution (awoo)
  • Vote: I like it
  • +83
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

imbalanceForces

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

F is so cool! Thanks for authors!

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

SorrowForces

→ Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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$$$

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 

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 ??

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    $$$k$$$ is given in the statement. upd: $$$k$$$ is the total number of operations, $$$m$$$ is the number of operations of the first type (when we delete two minimum elements)

    $$$(k-m)$$$ maximums is $$$(k-m)$$$ greatest elements of the array, i. e. $$$(k-m)$$$ last elements in sorted order.

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The basic idea is that since you need to maximise the sum of the final array, you have to minimise the sum of the removed elements. So, first of all, we sort the array. Then we have to go through all the different combinations of selecting min and max elements. So, we will use a loop in which i will denote the number of starting elements (minimum elements) we will take (multiplied by two, since we have to delete two min elements at once) and k — i will be the number of elements from back (maximum elements). i = 0 means 0*2 = 0 elements from start and k -0 = k elements from end. i = 1 means 1*2 = 2 elements from start and k — 1 elements from end. .... i = k means k*2 elements from start and 0 elements from end.

    In each iteration, we need to get the sums of taking i*2 elements from start and k — i elements from the end. To get this sum in O(1) time we will use prefix sum.

    You can check my C++ code here https://mirror.codeforces.com/contest/1832/submission/205586590

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh i got the approach. Thanks a lot I will now try to code it.

      → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like 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://mirror.codeforces.com/contest/1832/submission/206185565.

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
13 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like 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

→ Reply
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I dont think that greede solution is correct. But it also O(n*k) and even it be correct, it gets TLE.

    → Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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;

}

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
18 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

(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://mirror.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://mirror.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://mirror.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?

→ Reply