I have solbed it using semaphore like logic in O(n) time
Please Check here
https://www.codechef.com/viewsolution/7963748
Please let me know whats wrong or can u please share test cases
1 Like
Can I know the solution of this test case,
8 3
1 6
0 3
4 7
I ran on few accepted solutions and found the solution is ()()()(). Now how can the sub-string with x = 1 and y = 6 is balanced for such a solution? Resulting sub-string is )()()( which is not balanced.
#include<stdio.h>
int main()
{
int t;
scanf("%d", &t);
while(t–)
{
int n, k;
scanf("%d %d", &n, &k);
int i, x[k], y[k], j;
char s[n];
for(i=0;i<k;i++)
scanf("%d %d", &x[i], &y[i]);
for(i=0;i<n;i++)
s[i]=’)’;
int c1, c2;
for(i=0;i<k;i++)
{
s[x[i]]=’(’ ;
s[y[i]]=’)’ ;
c1=1;
for(j=x[i]+1; j<y[i]; j++ )
{
if( s[j]==’(’ )
c1++;
else
c1–;
if(c1<0)
{
s[j]=’(’;
c1+=2;
}
}
}
for(i=0;i<n;i++)
printf("%c", s[i]);
printf("\n");
}
return 0;
}
The logic is very simple, solution in O(n*k) for the worst case.
someone has done it in o(k) complaxity by just sorting all given k values according to starting range value.
CodeChef: Practical coding for everyone.
can anyone explain that how this solution in correct mathematically?
Interesting! I just sorted the queries by start index (breaking ties by end index) and for each constraint I just alternated “(” and “)” from segm.begin to segm.end, overwriting any previous changes. Complexity is O(N * K), although I’m sure it can become O(N + K*log(N)) with some sort of segment trees.
Funny story. It got AC. Not sure why.
Here is my solution: link
Hi guys, I agree test cases for this problem were week. 
and I apologize for the same. I missed one case which lead to pass incorrect solutions, but it would not be fair to re-judge the problem. So, I will add that test case in the practice section, where you can check you solution.
while(t--)
{
char a[2001];
int n,k,x,y;
cin>>n>>k;
a[n] = '\0';
for(int i=0;i<k;i++)
{
cin>>x>>y;
a[x] = '(';
a[y] = ')';
bool isSet = 0;
for(int j = x+1;j<y;j++,isSet = !isSet)
{
if(!isSet)
a[j] = '(';
else
a[j] = ')';
}
}
cout<<a<<endl;
}
Why my solution fails can anyone give testcase on where it fails ??
Input
1
10 4
3 6
2 9
4 5
8 9
Output should be ((((()))()
but those codes like CodeChef: Practical coding for everyone and many others
giving output as ((()()()() are also accepted, which is wrong. So please rejudge
What is the problem with this code? Only the first substask is passing.
Please can u provide the test cases.
#include
#include
using namespace std;
int main()
{
long long int t,n,k,i,x,y;
cin>>t;
while(t–)
{
cin>>n>>k;
char arr[n];
for(i=0;i<n-1;i+=2)
{
arr[i]=‘(’;
arr[i+1]=‘)’;
}
// cout<<endl;
// cin>>x>>y;
// arr[x]=‘(’;
// arr[y]=‘)’;
// low=x;
// high=y;
//k=k-1;
while(k–)
{
cin>>x>>y;
for(i=x;i<y;i+=2)
{
//if(arr[i]==‘(’)
// break;
//else
{
arr[i]=‘(’;
arr[i+1]=‘)’;
}
}
//arr[x]='(';
//arr[y]=')';
//if(x<low)
// low=x;
// if(y>high)
//high=y;
}
/* c=0;
//cout<<high<<" "<<low<<endl;
mid=((high-low)+1)/2;
//cout<<mid<<endl;
for(i=0;i<low;i++)
arr[i]='(';
for(i=low;i<=high;i++)
{
if(arr[i]=='0' && c < mid)
{
arr[i]='(';
c++;
}
else if(arr[i]=='(')
c++;
else if(arr[i]==')')
c--;
else
{ arr[i]=')';
c--;
}
}
for(i=high+1;i<n;i++)
arr[i]=')';
//cout<<arr<<endl;*/
for(i=0;i<n;i++)
cout<<arr[i];
cout<<endl;
}
return 0;
}
I have never got so may wrong answers for a question as in this one.Still unable to find a test case where this fails.Please someone find a test case for me…I have matched with all the test cases of this page and all those cases works fine in my code…Link to my code:
https://www.codechef.com/viewsolution/7951755
In the column “Breaking down the partially intersecting constraints into simpler form:”
what if length of the segment [c,b] is odd?
I have to re-post it, but still the question in practice is still accepting the incorrect solutions and it gave wrong answer to my correct solution, that’s totally disappointing from the codechef…
Codechef should also not include this contest for calculating the rating coz it has an erroneous problem which gave many users including me WA during the contest and the actual in-correct solution were passed giving them AC… one way for codechef to improve and make up for their error…
give a test case where this logic fails-
make a string of length n as ()()…() -total n chars
then if query is x,y it assigns String[x]=’(’ String[y]=’)’
Why you are putting a ‘)’ at the end and ‘(’ at the beginning. It is given that only the queries are always balanced but no description about the string(original string) it can be balanced/unbalanced.
They need not check every output. Compiler can run the input queries on this number, and check if they are all balanced.
1 Like
That’s true, but then it doesn’t matter what I am giving at the end anyway. In case there was a query involving the ends, they would have been ‘(’ for the start and ‘)’ for the end anyway. And if there wasn’t, then it doesn’t matter what I am giving here.
Can you/anybody help me with a test case for which this could fail?
thanks. I always used the method
./a.out < input > output
and used diff command to check. I assumed online compilers also did that
@s1d_3: Your solution gives wrong answer for the following test case:
1
8 3
0 5
1 2
4 7
Your solution gives : (()(()() which is wrong. One correct answer could be :
(())()()