awoo's blog

Educational Codeforces Round 154 Editorial
By awoo, history, 16 months ago, In English

1861A - Prime Deletion

Idea: BledDest

Tutorial
Solution (BledDest)

1861B - Two Binary Strings

Idea: Roms

Tutorial
Solution (Roms)

1861C - Queries for the Array

Idea: BledDest

Tutorial
Solution 1 (Roms)
Solution 2 (BledDest)

1861D - Sorting By Multiplication

Idea: Roms

Tutorial
Solution (Roms)

1861E - Non-Intersecting Subpermutations

Idea: BledDest

Tutorial
Solution (BledDest)

1861F - Four Suits

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +119
  • Vote: I do not like it

Comments Comments (46)
| Write comment?
»
16 months ago, # |
← Rev. 3   Vote: I like it +27 Vote: I do not like it

These solutions explain very clearly.

I'm sad I didn't AC problem D, but it is interesting!

→ Reply
»
16 months ago, # |
  Vote: I like it +15 Vote: I do not like it

thanks for the tutorial

→ Reply
»
16 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Good problems, thanks for the round!

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

"BledDest is a graph theory lunatic" had me cracked up.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    The point is that the sentence's coming from himself.

    → Reply
»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Test 3,682nd test case->great work in testing!

→ Reply
»
16 months ago, # |
  Vote: I like it +13 Vote: I do not like it

D was looking hard but it is easy

→ Reply
»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Another easy way to implement E is to just combine the last two states into one. So $$$dp_{i,j}$$$ counts how many of arrays of length $$$i$$$ exist such that the number of elements on the suffix we use is $$$x \equiv j \pmod k$$$ and the current cost of the array is $$$c = j\ /\ k$$$. Then the transitions are the same, but you just reset the partial sum whenever $$$j \equiv 0 \pmod k$$$ since you can never transition to a lower cost.

Submission: 221342327

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

In problem C, if you have : ++++1-0 when we verify the number elements in the array we have 3 elements but the array has to be sorted.

Edit : I misunderstood the second condition

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

during contest i had some trouble implementing C (i had same idea as described in approach 1) and using segment trees seemed easier to me. Idea is identical as described in approach 1 but it was easier for me to implement this way, so i thought of sharing it: code.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi all, it would really help if you can post some insights/hints for the problems of this contest on https://starlightps.org ! Here's a link to the problems: https://starlightps.org/problems/collection/cf-edu-154/. This will help us get more data so users can have a platform to:

  • share/discover hints/insights on various problems
  • find similar problems given insights they struggled with.

Check it out if you're interested. Thanks!

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

awoo,BledDest I think in tutorial of problem E, in the paragraph before the last, you should have written: "difference is: $$$dp_{i,j,c}$$$", instead of $$$dp_{i,j+1,c}$$$

because we have according to the second type of transitions

$$$dp_{i+1,j} <== d_{i,j} + d_{i,j+1} + ... + dp_{i,k-1}$$$

$$$dp_{i+1,j+1} <== d_{i,j+1} + d_{i,j+2} + ... + dp_{i,k-1}$$$

difference: $$$dp_{i+1,j}-dp_{i+1,j+1} = dp_{i,j}$$$ and not $$$dp_{i,j+1}$$$

I hope I'm not mistaking, but correct me if I'm wrong...

thx

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Thank you, this is an error. Will be fixed in a couple of minutes

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

woww clear editorial , tnx awoo , BledDest

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

at problem B wouldnt the example a = 00010000 b = 00011111 give a no?

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

    ignore the question I didnt read that it ends with 1 and starts with 0

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you for the editorial It was really helpful, I have a question How on earth did you come up with that idea of the last x elements on problem E, You assumed some number and built the dp table on the assumed number, it is my first time to see such a thing I Don't think this sort of things come from practice, and the amazing thing is that most of accepted solutions are the same idea, Is that I'm too dump or you are too smart? Thank You :D

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

The title for D in the tutuorial text is Russian, not English. awoo fix it pls, thx

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey Author,

I am in trouble to get the Problem B

according to me for the test case 

1
1000101
1000100

I am not able to find the way to make this same : (

but according to the Author code

it is printed YES

Can anyone know how to make this equal ??

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    According to the question .. both the strings should start with 0 and end with 1's.

    So your test case is wrong.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with this solution for C?

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    In your code dealing with '-' :

    if (!unsorted.empty() && elements < unsorted.back())
            unsorted.pop_back();

    IF shoule be replaced by WHLIE , for the cases like this : ++++000-1 , you need to pop back more than once.

    Then your code will get accepted. :)

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any one could help me I don't know what is the wrong in this solution

https://codeforces.net/contest/1861/submission/221355113

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain, what is the partial sum technique mentioned in E and why is it true?

→ Reply
»
16 months ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

For problem D can someone explain how can this be sorted in 4 operations? n = 9, a = [10 5 10 9 6 9 8 9 5]

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    l=1,r=2,x=3   30  15  10  9  6  9  8  9  5 
l=1,r=4,x=-1 -30 -15 -10 -9  6  9  8  9  5
l=7,r=8,x=2  -30 -15 -10 -9  6  9 16 18  5
l=9,r=9,x=4  -30 -15 -10 -9  6  9 16 18 20
    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C Approach 1(Roms) Can anyone explain why we need to check it after each query? After each query, we can just check that the longest sorted prefix is shorter than the shortest non-sorted prefix

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

    If the current query is '1', then make longest sorted prefix equal current length, which is consistent with the current query. And the shortest non-sorted prefix is consistent with the previous queries. If longest sorted prefix is shorter than the shortest non-sorted prefix, it means the current query is valid based on the previous queries.

    If the current query is '0', then make shortest non-sorted prefix=min(shortest non-sorted prefix, cur_length), which is consistent with the current query. Then check the inequality.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems like this editorial doesn't explain why there is no better solution in problem D, which makes prefix with length x negative by several multiplications on negative number

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    HELP, Can anyone prove the solution to Problem D. Why does this approach give an optimal solution? Thanks.

    → Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why Was My Submission Skipped Despite Submitting First https://codeforces.net/blog/entry/120756

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me in which test case is this solution going wrong it shows WA on 303 (test case 3)

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have an easier solution for E.

We can use dp in one dimension. Dp[i] means how many arrays with length i has the subarray from i-k+1 to i, which contains integers 1~k. Fac[i] means the factorial from 1 to i. Pw[i] means the i-th power of k.Every time, dpi has initial value fac[k] * pw[i-k]， because we chose number from 1~k optionally to fill the position 1 ~ i-k+1, and from 1-k+1 to i, the ways is equal to an arrangement of 1~k.

But this may cause duplication, for example. n = 4, k = 3 and for the array 1 2 3 1, we will calculate the contribution in both dp[3] and dp[4], but the cost of this array is 1. To solve this, when we calculate dp[i], we need to minus dp[j] which j is from i — k + 1 to i — 1. Actually we need to minus dp[j] * fac[i-j] because dp[j] only caluculate array of length j. From the position j+1 to i, the ways we fill it is equal to an arrangement of 1~i-j.

Submission: Code

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your solution is brilliant, although I don't know why the answer is sum of all dp[i] * Pow(k, n — i). It looks like taking any possible from the rest n — i elements, but it will be confused, as I don't know whether there is any duplication or not. Could you explain this part?

    → Reply
»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

In the BledDest approach for problem C, specifically in this line:
"In terms of our tree, it means that a vertex marked with 0 has an ancestor (possibly itself) marked with 1."
Shouldn't it be the other way? find a vertex marked with 1 that has an ancestor marked with 0?

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For C, what about the condition where something that is unsorted, is a prefix of something that's unsorted? Isn't that an automatic 'NO' as well?

For example, we have a 1, then we delete some characters without adding any, then we have a 0. That couldn't happen.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

someone know why this submission keep wrong on test 3 problem C pls

my submission

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <string.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <= b; i++)
int KadaneAlgorithm(const vector<int>& array) {
    int best = 0, sum = 0;
    for (int k = 0; k < array.size(); k++) {
        sum = max(array[k], sum + array[k]);
        best = max(best, sum);
    }
    return best;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t;
    cin >> t;
    while(t--)
    {
        ll n;
        cin >> n;
        vi a(n);
        for(int i = 0 ;i < n ;i++)
        {
            cin >> a[i];
        } 
        vi pref(n,0);
        pref[0] = 1;
        ll res = 0;
        //cout << 1 << " ";
        for(int i = 1 ;i < n ;i++)
        {
            pref[i] = pref[i-1] + (a[i] >= a[i-1]);
          //  cout << pref[i]<<" ";
        }
        //cout << endl;
        ll sum = 0;
        for(int i = 1 ; i < n ;i++)
        {
            if(a[i] <= a[i-1]) res++;
        }
        for(int i =  n - 2 ; i >= 0;i--)
        {
            if(a[i] >= a[i+1])
            {
                sum++;
             //   cout << sum << endl;
                
            }
            pref[i] += sum;
        }
        for(int i = 0 ;i < n ;i++)
        {
           // cout << pref[i] << " ";
        }
        //cout << endl;
        for(int i = 0 ;i < n ;i++)
        {
            res = min(res,pref[i]);
            //cout <<pref[i] + ((n- (i+1)) - (pref[n-1] - pref[i]) )<<endl;
        }
        cout << res << endl;
    }
    return 0;
}

Can anyone tell me where am i doing wrong this is d question.

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

For problem E, after some experimentation, the following relationship seems to be true for $$$m > k$$$:

$$$dp_{m,j} = k!\text{ }dp_{m-k,j} + \sum_{i=1}^{k-1}{(k-i)(i-1)!dp_{m-i,j}}, j=0,1,2,\dots,k-1$$$

where $$$dp_{i,j}$$$ is defined as in the editorial.

This can be proven with induction, but can someone offer a mathematical interpretation for the formula?

(Using this equation alongside $$$ans_n = k\text{ }ans_{n-1} + dp_{n,0} $$$ gives an $$$\mathcal{O}(k\text{ }log\text{ }k\text{ }log\text{ }n)$$$ solution to E via the standard problem of finding the $$$n$$$ th term of a linear recurrence relation.)

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice explanation

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

Can anybody tell me why this code might not be working for Problem C ? 293347966
Edit : my condition for checking if any unsorted prefix is present before the current length was a bit wrong. AC : 293354543
For the ones who were unable to understand the editorial for C : you just need to store the lengths which must be unsorted, and store the maximum length, which must be sorted. For this, maintain a set for storing the lengths which must be unsorted (lengths at the time when s[i] = '0'). And whenever you encounter s[i] = '1', make sure to take the maximum of the sorted length, because if i + 1 length is sorted, then i length must also be sorted. Now, just check if the array needs to be sorted for a length k, then there should not be an unsorted length present which is <= k. Similarly, if the array needs to be unsorted for a length k, then check that this length must be > longest sorted length. Also, when the current length becomes less than any length stored in unsorted set, remove them, and set the longest sorted length value to the current length.

→ Reply