But why not as Second Condition states there should be at least one X and and one Y and here cnt(X) = 1 & cnt(Y) = 5 .

What are the $$$7!$$$ states here? Are they a relative ordering of the visit times of the last $$$7$$$ states? If so when we have these values for the previous $$$7$$$ positions before the position $$$i$$$, how do we figure out how many are smaller / larger than the visit time of $$$i$$$ ? Do you mind elaborating a bit?

DELETED

Oops, I overkilled it then.

I just noticed the problem was equivalent to the number of ways of partitioning the set of nodes $$$S = (1, 2, \ldots n)$$$ into two sets $$$X$$$, $$$Y$$$ such that the adjacency list of all nodes in $$$X$$$ is exactly $$$Y$$$ and counted that using hashing + maps.

But clearly for this to occur, in the inverse graph, $$$X$$$ must be a disconnected complete graph so I don't know how I missed that.

I have done exactly the same. To check if a component (of x nodes) is a complete graph or not, I checked if the sum of count of all edges from every node in the component is equal to x*(x-1) [since every edge will be counted twice in the sum]. I also handled the case that x cannot be 1, and that the input graph isn't complete itself. I got WA though (my submission). Can someone let me know what about my code is incorrect? Is the way I determine if a component is fully connected correct?

Consider the initial problem of choosing non-overlapping subsequences. Lets call the two phone numbers $$$a$$$ and $$$b$$$ for convenience.

We can calculate this using a dp on the minimum position $$$i$$$ in the magic string such that we can fit the first $$$x$$$ characters of $$$a$$$ and the first $$$y$$$ characters of $$$b$$$ in the range $$$[1, i]$$$. Lets define this as $$$dp[x][y] = i$$$.

Now clearly, if we're placing the these first $$$x$$$ characters of $$$a$$$ and first $$$y$$$ characters of $$$b$$$, the last character placed will be the $$$x$$$-th character of $$$a$$$ or the $$$y$$$-th character of $$$b$$$. So $$$dp[x][y] = min(next[dp[x - 1][y]][a_{x}], next[dp[x][y - 1]][b_{y}])$$$, where $$$next[p][q]$$$ is the first occurrence of character $$$q$$$ strictly after position $$$p$$$ in the magic string. We can pre-calculate all values of $$$next$$$ in $$$O(n)$$$ time by processing the magic string $$$m$$$ in back to front order, so we can perform these transitions in $$$O(1)$$$ time.

But this takes $$$O(|a| \cdot |b|)$$$ time to calculate, which is too slow to calculate for each query.

But do we need to recalculate everything? What does appending / removing a value from a string constitute?

The $$$i$$$-th row of the dp grid corresponds to the $$$i$$$-th position of $$$a$$$ and the $$$j$$$-th column corresponds to the $$$j$$$-th position of $$$b$$$. So adding / erasing a new digit to / from the end of the mobile number is equivalent to just adding / removing a new row or column to / from the dp.

So we only have to evaluvate $$$|a|$$$ or $$$|b|$$$ new states, allowing each query to be performed in $$$max(|a|, |b|))$$$ time . So we can solve the entire problem in $$$O(n + d \cdot max(|a|, |b|))$$$ which is fast enough.

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;

const int maxlen = 1005, maxn = 5e5 + 5;

int n, d, dp[maxlen][maxlen], ne[maxn][10];
string m;
vector<int> nums[2];

int get_next(int frompos, int val)
{
    if(frompos >= n)
        return 2e9;
    return ne[frompos][val];
}

int solve(int x, int y)
{
    assert(x <= nums[0].size() && y <= nums[1].size());
    if(dp[x][y] < -1e9)
    {
        int takepos = 2e9;
        if(x > 0)
            takepos = min(takepos, get_next(solve(x - 1, y) + 1, nums[0][x - 1]));
        if(y > 0)
            takepos = min(takepos, get_next(solve(x, y - 1) + 1, nums[1][y - 1]));
        dp[x][y] = takepos;
    }
    return dp[x][y];
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for(int i = 0; i < maxlen; i++)
        for(int j = 0; j < maxlen; j++)
            dp[i][j] = -2e9;
    dp[0][0] = -1;
    cin >> n >> d >> m;
    int curne[10] = {0};
    for(int j = 0; j < 10; j++)
        ne[n][j] = curne[j] = 2e9;
    for(int i = n - 1; i >= 0; i--)
    {
        curne[m[i] - '0'] = i;
        for(int j = 0; j < 10; j++)
            ne[i][j] = curne[j];
    }
    for(int i = 0; i < d; i++)
    {
        string type, name;
        int val;
        cin >> type >> name;
        if(type == "append")
        {
            cin >> val;
            if(name == "Aryan")
                nums[0].push_back(val);
            else if(name == "Ali")
                nums[1].push_back(val);
            else
                assert(false);
            solve(nums[0].size(), nums[1].size());
        }
        else if(type == "erase")
        {
            if(name == "Aryan")
            {
                assert(!nums[0].empty());
                for(int i = 0; i < maxlen; i++)
                    dp[nums[0].size()][i] = -2e9;
                nums[0].pop_back();
            }
            else if(name == "Ali")
            {
                assert(!nums[1].empty());
                for(int i = 0; i < maxlen; i++)
                    dp[i][nums[1].size()] = -2e9;
                nums[1].pop_back();
            }
            else
                assert(false);
        }
        else
            assert(false);
        if(dp[nums[0].size()][nums[1].size()] < n)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

F

Suppose there be set of vertices (say k vertices) . Let's say we make these k vertices Y color. Now all the other one should be S colored and they must be disconnected among each of them as separation bw X should be there . So in order to be disconnected all the remaining (n — k) vertices should form a COMPLETE Graph from the erased edges(This constitutes a single Arrangement . If they do not form complete graph , then there must be two vertices which are connected and this violates 2 X adjacent to each other . Sorry for bad English

Are you reffering to the "almost-complete" graph or to the new one I construct with erased edges? EDIT: Nevermind, I just got it, what a stupid mistake. Why wasn't this case included in the samples?

If you erase an edge from the graph, its endpoints can't have different states because of the condition that all Y's should be adjacent to an X. This implies that for a connected component, all of its nodes should have the same state, but it's not always possible to have a connected component with all X's. Consider in the sample, the connected component of 2, 3, 4 and 5, the edge 3-4 isn't present in this component so it still exists in the "almost-complete" graph from the statement, so because of the condition that 2 adjacent nodes can't have state X, this component can't have state X. Now it's easy to realize that for a connected component to have state X for all nodes it should be a clique(complete graph, so it doesn't have adjacent nodes in the complement graph and we are allowed to fill it with X). When a component's state is considered to be X, others components will not have state X because they are all connected with our component in the "almost-complete graph" from the statement, so all the others component will have state Y. Now it's clear that to count all the different solutions it's enough to count the number of connected components in the "erased-graph" which ale cliques.

The fact that KINGATCK had that very stupid case not included in the samples is let-alone very disappointing, at least the cheaters should be removed, because a lot of people have already lost enough in ranking.