E. Correct Bracket Sequence Editor

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently Polycarp started to develop a text editor that works only with correct bracket sequences (abbreviated as CBS).

Note that a bracket sequence is correct if it is possible to get a correct mathematical expression by adding "+"-s and "1"-s to it. For example, sequences "(())()", "()" and "(()(()))" are correct, while ")(", "(()" and "(()))(" are not. Each bracket in CBS has a pair. For example, in "(()(()))":

• 1st bracket is paired with 8th,
• 2d bracket is paired with 3d,
• 3d bracket is paired with 2d,
• 4th bracket is paired with 7th,
• 5th bracket is paired with 6th,
• 6th bracket is paired with 5th,
• 7th bracket is paired with 4th,
• 8th bracket is paired with 1st.

Polycarp's editor currently supports only three operations during the use of CBS. The cursor in the editor takes the whole position of one of the brackets (not the position between the brackets!). There are three operations being supported:

• «L» — move the cursor one position to the left,
• «R» — move the cursor one position to the right,
• «D» — delete the bracket in which the cursor is located, delete the bracket it's paired to and all brackets between them (that is, delete a substring between the bracket in which the cursor is located and the one it's paired to).

After the operation "D" the cursor moves to the nearest bracket to the right (of course, among the non-deleted). If there is no such bracket (that is, the suffix of the CBS was deleted), then the cursor moves to the nearest bracket to the left (of course, among the non-deleted).

There are pictures illustrated several usages of operation "D" below.

All incorrect operations (shift cursor over the end of CBS, delete the whole CBS, etc.) are not supported by Polycarp's editor.

Polycarp is very proud of his development, can you implement the functionality of his editor?

Input

The first line contains three positive integers n, m and p (2 ≤ n ≤ 500 000, 1 ≤ m ≤ 500 000, 1 ≤ p ≤ n) — the number of brackets in the correct bracket sequence, the number of operations and the initial position of cursor. Positions in the sequence are numbered from left to right, starting from one. It is guaranteed that n is even.

It is followed by the string of n characters "(" and ")" forming the correct bracket sequence.

Then follow a string of m characters "L", "R" and "D" — a sequence of the operations. Operations are carried out one by one from the first to the last. It is guaranteed that the given operations never move the cursor outside the bracket sequence, as well as the fact that after all operations a bracket sequence will be non-empty.

Output

Print the correct bracket sequence, obtained as a result of applying all operations to the initial sequence.

INPUT

8 4 5

(())()()

RDLD

OUTPUT

()

The way I used to solved this question is very similar to the way Bohdan solved the question for vessels. DIV2(D) and it was a very nice technique. We use doubly linklist here to represent the prev and next of every bracket. Whenever we have operation "go to left" or "go to right" we simply shift to previous of present position or next of present postion. But when we have a DELETE operation we change the resepective previous and next nodes.

For printing we traverse from 0 while we dont reach l+1 and print all in between 

**********************************HERE IS MY CODE**************************************************

#include<bits/stdc++.h>

using namespace std;

int pre[500010];

int ne[500010];

char str[500010];

int mo[500010];

int mc[500010];

int main()

{

      int l;

      int op;

      int inpos;

      cin>>l>>op>>inpos;

  string s;

      cin>>s;

      string q;

      cin>>q;

      for(int i=1;i<=l;i++)

      {

         str[i]=s[i-1];

  }

  stack<int> st;

  for(int i=1;i<=l;i++)

  {

       if(str[i]=='(')

       st.push(i);

       else

       {

              

    mo[st.top()]=i;

mc[i]=st.top();

st.pop();

 }

  }

  ne[0]=1;

  pre[l+1]=l;

  for(int i=1;i<=l;i++)

  {

     pre[i]=i-1;

     

     ne[i]=i+1;

  }

  /*for(int i=1;i<=l;i++)

  cout<<mo[i]<<" ";

  cout<<endl;

  for(int i=1;i<=l;i++)

  cout<<mc[i]<<" ";

  cout<<endl;*/

  for(int i=0;i<op;i++)

  {

 // cout<<"beforr inpos "<<inpos<<endl;

     if(q[i]=='R')

     {

      inpos=ne[inpos];

}

else if(q[i]=='L')

{

 inpos=pre[inpos];

}

else

{

   if(str[inpos]=='(')

   {

        int en=mo[inpos];

        ne[pre[inpos]]=ne[mo[inpos]];

        pre[ne[mo[inpos]]]=pre[inpos];

//        cout<<"set next of "<<pre[inpos]<<" as "<<ne[mo[inpos]]<<endl;

//        cout<<"set pre of "<<ne[mo[inpos]]<<" as "<<pre[inpos]<<endl;

if(ne[pre[inpos]]==l+1)

        {

           inpos=pre[inpos];

}

else

{

  inpos=ne[pre[inpos]];

}

}

else

{

         

       pre[ne[inpos]]=pre[mc[inpos]];

//        cout<<"set pre of "<<ne[inpos]<<" as  "<<pre[mc[inpos]]<<endl;

ne[pre[mc[inpos]]]=ne[inpos];

//        cout<<"next of "<<pre[mc[inpos]]<<" as "<<ne[inpos]<<endl;

       if(ne[pre[mc[inpos]]]!=l+1)

{

  inpos=ne[pre[mc[inpos]]];

}

else

inpos=pre[mc[inpos]]; 

}

}

//     cout<<"agter "<<inpos<<endl;

  }

  

//  cout<<"done "<<endl;

  int pos=0;

  

  while(pos!=l+1)

  {

   pos=ne[pos];

   if(pos!=l+1)

cout<<str[pos];

   

  }

  cout<<endl;

  return 0;

}

E. Intellectual Inquiry

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

After getting kicked out of her reporting job for not knowing the alphabet, Bessie has decided to attend school at the Fillet and Eggs Eater Academy. She has been making good progress with her studies and now knows the first k English letters.

Each morning, Bessie travels to school along a sidewalk consisting of m + n tiles. In order to help Bessie review, Mr. Moozing has labeled each of the first m sidewalk tiles with one of the first k lowercase English letters, spelling out a string t. Mr. Moozing, impressed by Bessie's extensive knowledge of farm animals, plans to let her finish labeling the last n tiles of the sidewalk by herself.

Consider the resulting string s (|s| = m + n) consisting of letters labeled on tiles in order from home to school. For any sequence of indices p1 < p2 < ... < pq we can define subsequence of the string s as string sp1sp2... spq. Two subsequences are considered to be distinct if they differ as strings. Bessie wants to label the remaining part of the sidewalk such that the number of distinct subsequencesof tiles is maximum possible. However, since Bessie hasn't even finished learning the alphabet, she needs your help!

Note that empty subsequence also counts.

Input

The first line of the input contains two integers n and k (0 ≤ n ≤ 1 000 000, 1 ≤ k ≤ 26).

The second line contains a string t (|t| = m, 1 ≤ m ≤ 1 000 000) consisting of only first k lowercase English letters.

Output

Determine the maximum number of distinct subsequences Bessie can form after labeling the last n sidewalk tiles each with one of the first k lowercase English letters. Since this number can be rather large, you should print it modulo 109 + 7.

Please note, that you are not asked to maximize the remainder modulo 109 + 7! The goal is to maximize the initial value and then print the remainder.

INPUT

1 3
ac

output

8

input
0 2
aaba
output
10




Editorial of the match


For simplicity, let’s represent the letters by 1, 2, ..., k instead of actual characters. Let a[i] denote the number of distinct subsequences of the string that end in the letter i. Appending the letter j to a string only changes the value of a[j]. Note that the new a[j] becomes —we can have the single letter j, or append j to any of our old subsequences.

The key observation is that no matter what character j we choose to append, a[j] will always end up the same. This suggests a greedy algorithm—always appending the character j with the smallest a[j]. But how do we know which a[j] is minimal while maintaining their values modulo 109 + 7?

The final observation is that if the last occurrence of j is after the last occurrence of j' in our string, then a[j] > a[j']. This is true because appending j to the string makes a[j] larger than all other a[i]. So instead of choosing the minimum a[i], we can always choose the letter that appeared least recently. Since the sequence of letters we append becomes periodic, our solution runs in . Of course, we can also find the least recently used letter with less efficient approaches, obtaining solutions with complexity O((L + n)k).

                 ***************************HERE RUNS THE CODE***********************************



#include<bits/stdc++.h>

using namespace std;

int dp[2000010];

int occ[30];

int h[30];

#define mod 1000000007

int p2[2000010];

int n;

int k;

void pre()

{

    p2[0]=1;

    for(int i=1;i<=1000001;i++)

    p2[i]=(2*p2[i-1])%mod;

}

int findnext()

{

 /*  int mi=100000000;

   for(int i=0;i<k;i++)

   {

       if(h[i]<mi)

       mi=h[i];

   }

   //cout<<"mi "<<mi<<endl;

   int freq=0;

   for(int i=0;i<k;i++)

   {

        if(h[i]==mi)

        freq++;

   }*/

   int minpos=10000000;

   int ch;

   for(int i=0;i<k;i++)

   {

      //if(h[i]==mi)

     // {

          if(occ[i]<minpos)

    {

         minpos=occ[i];

      ch=i; 

    } 

 //   }

   }

   return ch;

}

int main()

{

 pre();

    cin>>n>>k;

 string s;

 cin>>s;

 memset(occ,-1,sizeof(occ));

 int m=s.length();

 dp[0]=1;

 for(int i=1;i<=m;i++)

 {

            dp[i]=2*dp[i-1];

        //    dp[i]++;

            dp[i]%=mod;

     if(occ[s[i-1]-'a']!=-1)

     {

         dp[i]-=dp[occ[s[i-1]-'a']-1];

      dp[i]+=mod;

      dp[i]%=mod; 

     }

     occ[s[i-1]-'a']=i; 

 }

// for(int i=1;i<=m;i++)

// cout<<dp[i]<<" ";

// cout<<endl;

 for(int i=0;i<m;i++)

 h[s[i]-'a']++;

 for(int i=m+1;i<=n+m;i++)

 {

 // cout<<"haire "<<endl;

            int ch=findnext();

   //     cout<<"hc "<<ch<<endl;

      dp[i]=dp[i-1]*2;

      dp[i]%=mod;

      if(occ[ch]!=-1)

      {

              dp[i]-=dp[occ[ch]-1];

        dp[i]+=mod;

        dp[i]%=mod; 

      }

      h[ch]++;

      occ[ch]=i; 

 }

// for(int i=1;i<=n+m;i++)

// cout<<dp[i]<<" ";

// cout<<endl;

 int ans=0;

    ans=dp[n+m];

 ans%=mod;

 cout<<ans<<endl;

 return 0;          

}

Problem Statement for BracketSequenceDiv2

Problem Statement      Correct bracket sequences can be defined recursively as follows: The empty string "" is a correct sequence. If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence. If "X" is a correct sequence, then "(X)" is a correct sequence. Each correct bracket sequence can be derived using the above rules. Examples of correct bracket sequences include "", "()", "()()()", "(()())", and "(((())))". A string T is called a subsequence of a string S if we can erase some (possibly none or all) characters of S to obtain T. For example, "bdf" is a subsequence of "abcdefg". You are given a String s that consists of the characters '(' and ')' only. Let X be the number of different non-empty subsequences of s that are correct bracket sequences. Note that each distinct subsequence should only be counted once, even if it can be obtained from s in multiple ways. (See the examples for clarification.) Compute and return the value (X modulo 1,000,000,007).   Definition      Class: BracketSequenceDiv2 Method: count Parameters: String Returns: int Method signature: int count(String s) (be sure your method is public)        Constraints - s will contain between 1 and 100 characters, inclusive. - Each character in s will be '(' or ')'.   Examples 0)      "(())(" Returns: 2 Correct non-empty bracket subsequences are "()" and "(())". 1)      "())" Returns: 1 Only "()" is suitable. 2)      ")(((" Returns: 0 There are no non-empty correct bracket subsequences. 3)      "()()()()()()()()(())))(()()()()))())" Returns: 364675 4)      "()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()" Returns: 122826009 Do not forget to take answer modulo 1,000,000,007. This DP opened up a new dimension for me. The way we look at solving the DP, heres the cool blog by Vexorian That we need to count the unique subsequences makes things more complicated because we don't want to count duplicates. To work around this, imagine if we were generating the subsequence and then checking if it is possible to find the subsequence in the string. Imagine we had a subsequence like "(())()" to check if it is a possible subsequence of s${\displaystyle s}$ we can begin with its first character "(" and find the left-most position j${\displaystyle j}$ of "(" in s${\displaystyle s}$. Then we continue with the second character which is another "(" and find the left-most position after j${\displaystyle j}$ that is equal to "(" and so and so until we find all the characters in the subsequence in s${\displaystyle s}$ or until we run out of positions of s${\displaystyle s}$ Dynamic programming In order to use that logic we would have to generate the subsequence step by step. We begin with an empty string and add "(" or ")" in each step, making sure the subsequence is a correct bracket sequence. We also start with a pointer i${\displaystyle i}$ to a position in s${\displaystyle s}$. When we decide to add a "(" to the subsequence, find the smallest position j${\displaystyle j}$ greater than or equal to i${\displaystyle i}$ such that s[j]${\displaystyle s\left[j\right]}$ is "(" then move i${\displaystyle i}$ to j+1${\displaystyle j+1}$. The same with ")". This would look like a backtracking problem. We can find a dynamic programming approach by noticing that, in order to make sure the subsequence is a valid bracket sequence, we don't need to remember all the contents of the subsequence, just the number of open brackets. So if the characters currently in the subsequence are: "(()((()", then we only need to know there are 3 open bracket. With this in mind we can create a function f(o,i)${\displaystyle f(o,i)}$ that will give us the number of ways to complete a subsequence with o${\displaystyle o}$ open brackets if we can only use characters in s${\displaystyle s}$ after index i${\displaystyle i}$: When o=0${\displaystyle o=0}$, we already found a valid subsequence, because all the brackets are closed. We can also decide to add a "(" to the subsequence. Find the left-most position j${\displaystyle j}$ such that: s[j]${\displaystyle s\left[j\right]}$ is "(" and j≥i${\displaystyle j\ge i}$. Then we can continue adding characters to the subsequence but this time the number of open brackets increased and i${\displaystyle i}$ changed to j+1${\displaystyle j+1}$: There are f(⊕1,j+1)${\displaystyle f(\oplus 1,j+1)}$ ways to complete the subsequence after this step. If o≠0${\displaystyle o\ne 0}$ we can decide to close a bracket by adding a ")" character. Find the smallest j${\displaystyle j}$ such that s[j]${\displaystyle s\left[j\right]}$ is ")" and j≥i${\displaystyle j\ge i}$. This adds f(o−1,j+1)${\displaystyle f(o-1,j+1)}$ new ways to complete the subsequence. The sum of those 3 cases is the result. In some cases, the "(" or ")" characters cannot be found in the string so we ignore them. The function f(o,i)${\displaystyle f(o,i)}$ has O(n2)${\displaystyle O\left(n^2\right)}$ possible states. In each state, we might need an O(n)${\displaystyle O\left(n\right)}$ loop to find the smallest position of the "(" and ")" characters. The total time complexity is O(n3)${\displaystyle O\left(n^3\right)}$, very appropriate for n≤100${\displaystyle n\le 100}$. #include<bits/stdc++.h> using namespace std; #define mod 1000000007 #define ll long long int  int  dp[110][110]; int getnext(string s,int idx,int ch,int l) {     int i;   for(i=idx;i<l;i++)   {        if(s[i]==ch)                {             return i;  }   }   return i; } int solve(int op,int idx,string s,int l) { //cout<<"op  idx "<<op<<" "<<idx<<endl;    if(idx==l)    {      if(op==0)      return 1;      return 0; } if(dp[op][idx]!=-1) return dp[op][idx]; int ret=0; if(op==0) ret++; int poso=getnext(s,idx,'(',l); // cout<<"for idx "<<idx<<" "<<poso<<endl; if(poso<l) { // cout<<"caleed "<<endl; ret+=solve(op+1,poso+1,s,l);     ret%=mod; }   int pose=getnext(s,idx,')',l); // cout<<" of idx "<<idx<<" "<<pose<<endl; if(op>=1 && pose<l) { // cout<<"clled close "<<endl;   ret+=solve(op-1,pose+1,s,l);   ret%=mod; } dp[op][idx]=ret; return ret; } int count(string s) {   int l=s.length();   memset(dp,-1,sizeof(dp));   int idx=0;   while(s[idx]!='(')   idx++;   if(idx==l)   return 0;   return solve(1,idx+1,s,l);  }#include<bits/stdc++.h> using namespace std; #define mod 1000000007 #define ll long long int  int  dp[110][110]; int getnext(string s,int idx,int ch,int l) {     int i;   for(i=idx;i<l;i++)   {        if(s[i]==ch)                {             return i;  }   }   return i; } int solve(int op,int idx,string s,int l) { //cout<<"op  idx "<<op<<" "<<idx<<endl;    if(idx==l)    {      if(op==0)      return 1;      return 0; } if(dp[op][idx]!=-1) return dp[op][idx]; int ret=0; if(op==0) ret++; int poso=getnext(s,idx,'(',l); // cout<<"for idx "<<idx<<" "<<poso<<endl; if(poso<l) { // cout<<"caleed "<<endl; ret+=solve(op+1,poso+1,s,l);     ret%=mod; }   int pose=getnext(s,idx,')',l); // cout<<" of idx "<<idx<<" "<<pose<<endl; if(op>=1 && pose<l) { // cout<<"clled close "<<endl;   ret+=solve(op-1,pose+1,s,l);   ret%=mod; } dp[op][idx]=ret; return ret; } int count(string s) {   int l=s.length();   memset(dp,-1,sizeof(dp));   int idx=0;   while(s[idx]!='(')   idx++;   if(idx==l)   return 0;   return solve(1,idx+1,s,l);  }