what do you mean by ad-hoc? ( one of prerequisites)
Can someone provide a solution for the same above problem if the word prefix was removed. I am getting considerable difficulties in doing this version. Eg. for <<<<<<<<> output:2 , for <><><<<<<<<<<> output:4.
My problem is that how do we track whether the new contiguous sub sequence extends the previous one or not. As in <<>><<>> output:8 but for <<>><<<>> output:4.
Please help!
you can solve the problem using divide and conquer approach with a segment tree. At each node of the segment tree, store the following 5 variables:
l -> the maximum positive sum from right end
li -> the index at which the maximum sum is achieved
r -> the minimum negative sum from left end
ri -> the index at which this minimum sum is achieved
b -> longest perfect bracket sequence in the interval
So, for a node N, the best can be calculated as the maximum of b values of the children, or taking the joint of the r value of the right child and l value of the left child. if mod of l of left child is less than mod of r of right child, then just find the index in the right child where the prefix sum is equal to -l. similar procedure if mod of r is smaller than mod of l. this is work in NlogN.
CodeChef: Practical coding for everyone .WA checked with all cases discused above .Thanks in advance
For which test case am i getting WA ?. Please someone answer . my subbmission CodeChef: Practical coding for everyone Thanks in advance
What must be the output of ><<>> …Should it be 0 or 4 ??
Why do we need to calculate “ans=max(ans,i+1)”? We can just write “ans=i+1” which will also work.
https://www.codechef.com/viewsolution/15906400
i dn know why i am getting WA please anyone suggest some edge cases .
Can anyone tell me what’s wrong with my code ?
Thanks !
Are these test cases correct ?
$ ./test < test.txt
6
4
0
0
2
6
4
$ cat test.txt
7
<><><><<<<>>>>
<<>>
><
><>
<><
<<>><<<<>>>>
><<>><<<>>>
def check(s):
t=0,ans=0
for i=0 to N-1:
if s[i]==’<’: t++;
else:
t–;
//Now, if t=0, means, the string s[0,i] is valid.
if t==0: ans=max(ans,i+1) ------> I can see there is no use of max function here as i always more than max every time t==0, so simple ans=i+1 is sufficient.
else if t<0: break //string s whole is invalid.
print ans
#include
#include<bits/stdc++.h>
#include
using namespace std;
typedef unsigned long long int ull;
#define F first
#define S second
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define f(i,a,b) for(int i=a;i<b;i++)
#define MOD 1000000007
#define fastscan ios_base::sync_with_stdio(0); cin.tie(NULL);
int main(int argc, char const *argv[])
{
long int t;
cin>>t;
while(t--){
string s;
cin>>s;
ull len=s.length();
stack<char> st;
ull run=0;
for (ull i = 0; i < len; ++i)
{
if(s[i]=='<'){
st.push('<');
run++;
}
else if(s[i]=='>' && !st.empty()){
st.pop();
run++;
}
else{
break;
}
}
cout<<run<<endl;
}
return 0;
}
//Anybody tell me whats wrong in this code…
I have implemented this algorithm in Go and tried to run it but getting a time limit exceed error. But the same algorithm I’ve implimented in Python3 and run it and it accepted. Is Go compiler not well implemented?
Could anyone please tell me what I am missing in my code? Getting WA. Have attached my own test cases.
Can anyone tell me what is wrong with this solution? O4w7qo - Online C++0x Compiler & Debugging Tool - Ideone.com
Can anyone help me with this
[1]. Any suggestion is warmly welcomed,thankyou
[1]: https://www.codechef.com/viewsolution/18731588
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
ll t;
cin>>t;
while(t–)
{
//ll cnt=0;
stack s;
string s1;
cin>>s1;
ll n=s1.size();
if(n==1||s1[0]==’>’)
{
cout<<0<<endl;
continue;
}
int i=0;
ll cnt=0,res=0;
while(s1[i]!=’\0’)
{
if(s1[i]==’<’)
{
s.push(s1[i]);
cnt++;
}
else if(s1[i]==’>’)
{
s.pop();
}
if(s.empty())
{
res+=cnt;
cnt=0;
}
i++;
}
cout<<res*2<<endl;
}
return 0;
}
what is the prob with my code ??
i have checked most of the testacases all are passing still am getting wa.
please help me with testcases
- Solved it using stack
- Take a counter c=0 and a summing variable like sum=0
- when ‘<’ comes push into stack
- When ‘>’ comes, check when a pair closes(means top of stack should be ‘<’) increment the counter and after that pop one’<’ from stack and check if stack is empty add 2*c to the sum
- also check if the stack is already empty and ‘>’ comes break your loop of string and print sum
Rest is your implementation of code you can check my code
link text
both author and setter has wrong ans.
Check for “>><>” this.
answer should be 2.
but your solution shows, 0.