What’s wrong with my solution?
I am getting WA in subtask#1 test case#2 only 
https://www.codechef.com/viewsolution/7959488
The solution given here is quite complicated , my code complexity is O(n*k) , just sort the different segments in ascending order based on differnce (or their length) ,and balance them in the same order . Those who are left unalloted , allot them any value u want to bcoz that dosen’t change ur answer . here is my solution
CodeChef: Practical coding for everyone
1 Like
@s1d_3 Exactly a similar problem. Couldn’t find a test case where greedy should fail.
Alloted ( to the left place and ) to the right indices for all k. Then filled the remaining places wity alternate ( and).
Just 1 test case passed though.
https://www.codechef.com/viewsolution/7956764
#include <bits/stdc++.h>
using namespace std;
char a[2001];
void complete(long st,long end,long size)
{
long b[size],j=0;
for(long i=st+1;i<end;i++)
{
if(a[i]!='(' && a[i]!=')')
{
b[j]=i;
j++;
}
}
for(long i=0,k=j-1;i<k;i++,k--)
{
a[b[i]]='(';
a[b[k]]=')';
}
}
void completefinish(long st,long end,long size)
{
long b[size],j=0;
for(long i=st;i<end;i++)
{
if(a[i]!='(' && a[i]!=')')
{
b[j]=i;
j++;
}
}
for(long i=0,k=j-1;i<k;i++,k--)
{
a[b[i]]='(';
a[b[k]]=')';
}
}
int main() {
int t;
cin>>t;
while(t–)
{
long long n,q,size,m=LLONG_MIN;
cin>>n>>q;
size=2q;
long l[size];
for(long i=0;i<2q;i=i+2)
{
cin>>l[i]>>l[i+1];
a[l[i]]=’(’;
a[l[i+1]]=’)’;
}
long j=0,k;
for(long i=0;i<q;i=i+2)
{
complete(l[i],l[i+1],(l[i+1]-l[i]));
}
completefinish(0,n,n);
for(long i=0;i<n;i++)
cout<<a[i];
cout<<endl;
}
return 0;
}
not geting why getting wrong anstion can anyone tell
The question asks to print any of the output. How does an online compiler checks every output?
Please tell us what is First and fifth test case or what is wrong with my approach its basically O(N) solution i guesslink text
Since there could be multiple possible answers for this problem…the tester’s algorithm only checks if the segment between ‘x’ and ‘y’ (exclusive) is balanced or not.Hence lot of incorrect solutions got accepted.
I don’t claim this to be correct but I suppose this may be.
Weak Test cases… My wrong solution got passed.
SORT THE RANGES in terms of their of difference.
and they apply the ranges on the decreasing order.
For sorting the range with key “difference of the range”, you may use a vector pair pair in c++.
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