The problems gonna be delayed...

Orz Holland_Pig.

you are already approximately blue...xD

I did it!

If a comment has rating between 0 and -5, it's shown that its rating is 0. Your previous comments had rating 0, but maybe they were like -1 or -2 so, after some time, your contribution became -1. I guess that's the reason.

No,in educational rounds,you can only hack after the round ends for 12 hours.This will not effect your score.

But if you hack others' solution successfully,and their ranks are higher than yours,your rank may become higher.

But the round hasn't even started yet!

hope to have a rated contest.

Epicenter major grand final PepeHands

Are you a C++ coder or a python coder or some language else's?

*late

And it gets delayed by 10 min '__'

Rated for Div2, that's what it says above. :)

It seems like new tradition of CF. I am observing it since last 4 contests.

traditions bro. Traditions.

Exactly I am yet to take my dinner today. And I delayed it for two hours for contest. If i knew it was 10 mins later then I could have managed taking my dinner as well before contest :(.

They are waiting for 10k registrations.

This 10 minutes is the most boring time of day :3

they want to wait until the number of participants increases over 10k

Good explanation!

First of all it's arsijo,, and this kind of aggression towards him !!!! , even aggressive cows didn't have this much aggression towards each other

D was definitely harder, it was hacked left and right.

I agree. In my opinion hard ad-hoc problems are always harder than problems that need a general algorithm or paradigm to be solved.

Probably something like
5 2
1 4 5
0 2 5

try this 10 3 1 3 6 1 6 7 0 2 8

C, D and E needed some trick? I didn't use a single data structure, well known algorithm or "trick" in them and in fact I think that C and D were quite interesting.

Edit: fuck my life.

E did not need a "trick" in my opinion, it was an interesting DP on Trees problem.

Similar to 1092F - Дерево максимальной стоимости. DP on Trees

How to solve D?

I solved that F problem without any help,but couldn't solve E now...

I did E using sliding through nodes only(Sliding Window??)

Oh,I solved it,They are REALLY similar problem... interesting,of course...

Maybe hack so strong even author's solution crashed

int n; cin >> n;

int a[n];
    int b[n];

    vsi dp;
    si tmp;
    dp.assign(n, tmp);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        dp[a[i]].insert(i);
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i]--;
    }

    SegTree st(a);
    bool fl = true;
    for (int i = 0; i < n && fl; i++) {
        if (dp[b[i]].size() != 0) {
            int ind = *(dp[b[i]].begin());
            dp[b[i]].erase(dp[b[i]].begin());
            if(ind == 0){
                a[ind]=(1<<30);// is not necessary
                st.update(ind , (1<<30));
                continue;
            }
            int min = st.rmq(0 , ind-1);
            if(a[min] < a[ind])
                fl = false;
            else{
                //update segment tree and with INF value instead of delete
                a[ind]=(1<<30); // is not necessary
                st.update(ind , (1<<30));
            }
        } else fl = false;

    }

    if(fl) cout << "YES\n";
    else cout << "NO\n";

You will get wrong for testcase:
5 2
1 2 5
0 1 5

Have you tried this case:

7 4
1 1 3
1 5 7
0 3 4
0 4 5

You forgot to return true in your chk() function.

Start from node 7 or 8.

Overlapping ranges... I think you need to check every single index, if index and index+1 must be sorted, or must be unsorted. Then you can build the array easyly.

Yes, it was DP on tree

Wow, didn't think of that :(

I got this right but still got hacked, any other case?

After you build the array using the "1" facts, loop through all of the "0" facts to see if any of them are sorted.

Build a pref matrix: matrix[letters][index], then use it to find the least indice that for each letter in the name, matrix[letter][index] >= frequency[letter] in the given string.

First pre-compute the given string by taking a vector of vector of size 26 and insert there indexes . Then for each query make a frequency array for all 26 letters and iterate frequency array and if frequency is not 0 check for the minimum index needed for given frequency in pre-computed array . Here is my solution

Your solution is probably $$$O(N\sum{t_i})$$$. You need to pre-process the string in order to quickly answer the farthest position needed for each name. You can do this by storing the $$$k$$$th occurrence of each letter. Then you just have to use this lookup table to find the answer for each name. Then the runtime is $$$O(N+\sum{t_i})$$$ (plus a constant factor for the size of the alphabet).

You should generate big tests with "generated input", in case you were just copying your test cases. I may be wrong

For testcases larger than 256KB you need to upload a generator i.e. a program which prints that testcase.

use generator for large test case

The key idea is the following: you need to sort subsegments of length 2, i.e. swap pair of consecutive elements if the first one is larger.

Let's suggest that the element $$$b[1]$$$ is in the position $$$a[pos]$$$. If $$$min(a[1..pos]) < a[pos]$$$ then there is no way to move $$$a[pos]$$$ to $$$a[1]$$$. Otherwise, we can move it and, moreover, relative order of $$$a[1..(pos - 1)]$$$ doesn't change. So we "delete" $$$a[pos]$$$ and $$$b[1]$$$ and solve recursively.

Of course, you need to write it in an efficient way.

Match indices of a to corresponding indices of b (this matching is unique if equal elements aren't reordered). Create an array pos where pos[i] = j means that a[i] is matched to b[j]. Then, if there is some pair (i, j) such that i < j, a[i] < a[j] and pos[i] > pos[j], then the answer is NO. So this gives a necessary condition that no such pairs exist. I didn't prove it's sufficient though :(

Keffa2's solution this might help...

First check that arrays are permutations, and get the map fuction $$$p$$$ such that if the $$$k$$$-th occurrence of value $$$v$$$ in $$$A$$$ is in position $$$i$$$, and the $$$k$$$-th occurrence of value $$$v$$$ in $$$B$$$ is in position $$$j$$$, then $$$p(i) = j$$$.

Then, instead of "sorting a range", think of your operation as "swapping consecutive elements $$$A_i$$$ and $$$A_{i+1}$$$ if $$$A_i > A_{i+1}$$$", if you can get to an array by sorting ranges, you can also get to it by swapping consecutive elements, like that.

You can notice that your operation allows you to "remove" already existing inversions, but you definitely can't create new ones. Then, finding a single "new" inversion present in $$$B$$$ is enough to answer NO, and, I haven't proved this yet, but I think that if you don't have any "new" inversion, then you can safely answer YES.

You can check that you are not creating new inversions by going through the array $$$A$$$, and maintaining a segment tree that answers the maximum in a range.

The idea is that $$$ST[v]$$$ is the maximum index (in $$$B$$$) in which an already seen value of $$$v$$$ (in $$$A$$$) ends up. When you are at position $$$i$$$, check if there was a previous smaller value $$$v$$$ ($$$v \leq A_i$$$) that ends up after $$$A_i$$$, if this happens, you can already say NO. Otherwise, just update the $$$ST$$$ accordingly.

The code snippet might be easier to understand:

for(int i = 0; i < n; ++i){
  int mx = ST.query(0, A[i]);
  if(mx > p[i]){
    ok = false;
    break;
  }
  ST.upd(A[i], p[i]);
}

You can also check my code: 56332559.

int n; cin >> n;

int a[n];
    int b[n];

    vsi dp;
    si tmp;
    dp.assign(n, tmp);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
        dp[a[i]].insert(i);
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i]--;
    }

    SegTree st(a);
    bool fl = true;
    for (int i = 0; i < n && fl; i++) {
        if (dp[b[i]].size() != 0) {
            int ind = *(dp[b[i]].begin());
            dp[b[i]].erase(dp[b[i]].begin());
            if(ind == 0){
                a[ind]=(1<<30);// is not necessary
                st.update(ind , (1<<30));
                continue;
            }
            int min = st.rmq(0 , ind-1);
            if(a[min] < a[ind])
                fl = false;
            else{
                //update segment tree and with INF value instead of delete
                a[ind]=(1<<30); // is not necessary
                st.update(ind , (1<<30));
            }
        } else fl = false;

    }

    if(fl) cout << "YES\n";
    else cout << "NO\n";

That's what happen when someone shares his solution with one friend, and don't share it with the other lol

https://mirror.codeforces.com/blog/entry/68060?#comment-523900

just store Kth occurance of every character like count[ch][k]=i (character ch appeared k times at index i)
then count the occurance of every character from query string. for example in query string 'a' appeared 2 times 'b' appeared 3 times. so the answer will be maximum of count['a'][2] and count['b'][3]

at the end, the editorial get hacked and the contest becomes unrated...

happy ending for every hacked person :-)

What should be the condition for printing NO in problem C?

Pretty much means some solutions might be filtered out during the system test so don't be too happy if your solution hasn't been hacked (notes to myself... ahem).

Lol, there are 152 test cases right now :)

Answer is $$$E[(1+\sum_{i = 1}^{i = n-1}(x_{i} != x_{i+1}))^2]$$$ = $$$E[(1 + \sum_{i=1}^{i=n-1}(x_{i} != x_{i+1})^{2} + 2\times \sum_{i=1}^{i=n-1}(x_{i} != x_{i+1}) + 2 \times \sum_{i!=j}(x_{i} != x_{i+1})(x_{j} != x_{j+1})]$$$.
Now use linearity of expectations to calculate it.

Count expected number of group pairs.

Yes and Yes :)