I maintain a difference array so that when overlapping of activities goes above 3 then i can print “IMPOSSIBLE” because at that time i thought that more then 2 activities at a time might be single case where no solution exist. so when there is not more then 2 activities overlapping and still there exist no solution, in that case it should print “something is wrong".
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,ii;
cin>>t;
for(ii=0; ii<t; ii++){
int n,i,x,y;
cin>>n;
std::vector<pair<pair<int, int>, int>> v;
vector<pair<int, char>>v3;
for(i=0; i<n; i++){
cin>>x>>y;
v.push_back(make_pair(make_pair(x,y), i));
}
sort(v.begin(), v.end());
v3.push_back(make_pair(v[0].second, 'C'));
v3.push_back(make_pair(v[1].second, 'J'));
int cfree = v[0].first.second;
int jfree = v[1].first.second;
int flag=0;
for(i=2; i<n; i++){
if(v[i].first.first>=cfree){
v3.push_back(make_pair(v[i].second, 'C'));
cfree = v[i].first.second;
}else if(v[i].first.first>=jfree){
v3.push_back(make_pair(v[i].second, 'J'));
jfree = v[i].first.second;
}else{
flag=1;
break;
}
}
cout<<"Case #"<<ii+1<<": ";
if(flag==1){
cout<<"IMPOSSIBLE"<<endl;
}else{
sort(v3.begin(), v3.end());
for(i=0; i<n; i++){
cout<<v3[i].second;
}
cout<<endl;
}
}
}
get hints from this code… try to figure out where you are doing wrong…
The issue with your brute force is that you assign the intervals to C prematurely even before processing other intervals (without any sorting of intervals). Consider this testcase:
Input:
1
4
1 3
6 8
2 5
4 7
Your code gives output IMPOSSIBLE since it assigns [1,3] and [6,8] to C and no such solution follows. However, CJJC is a valid solution.
4 Likes
There is a similar bias towards choosing C (even though you sort) in your other solution (“first solution”) which fails for the following testcase:
1
4
1 3
2 5
6 7
4 8
Here, your code returns an error even though CJJC is a valid solution.
1 Like
// YATIN KWATRA
//#pragma GCC optimize “trapv”
//#include <boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl “\n”
#define fin for(int i = 0; i<n ; i++)
#define fim for(int i = 0; i<m ; i++)
#define fjn for(int j = 0; j<n ; j++)
#define fjm for(int j = 0; j<m ; j++)
using namespace std;
bool cmp(pair<int,int>a,pair<int,int>b)
{
// if(a.first != b.first)
return a.first<b.first;
//return a.second < b.second;
}
int main() {
FIO
int t;
cin >> t;
int m = 1;
while(m<=t)
{
int n;
cin >> n;
pair<ll,ll>a[n+1],c[n+1];
for(int i = 0; i<n ; i++)
{
cin >> a[i].first >> a[i].second;
c[i].first = a[i].first;
c[i].second = a[i].second;
}
sort(a,a+n,cmp);
/* fin
{
cout << c[i].first << ' ' << c[i].second << endl;
}
*/
map<pair<ll,ll>,char>h;
ll sC = 0, sJ = 0;
ll flag = 0;
for(int i = 0 ; i<n ; i++)
{
if(a[i].first >= sC)
{
h[make_pair(a[i].first,a[i].second)] = 'C';
sC = a[i].second;
}
else if(a[i].first >= sJ)
{
h[make_pair(a[i].first,a[i].second)] = 'J';
sJ = a[i].second;
}
else
{
flag = 1;
break;
}
}
if(flag) cout << "Case #" << m <<": " << "IMPOSSIBLE" << endl;
else
{
string ans = "";
for(int i = 0; i<n ; i++)
{
int val1 = c[i].first;
int val2 = c[i].second;
ans += h[make_pair(val1,val2)];
}
cout << "Case #" << m <<": " << ans << endl;
}
m++;
}
return 0;
}
i tried a lot of testcases but still couldn’t figure out where i am going wrong.
please help me finding the issue in this one
I used vector tuple to store all three values instead of pair. It’s an approach which you could adopt.
Here is my solution . . .
#include<bits/stdc++.h>
using namespace std;
struct triple{
int first, second, third;
};
bool cmp(triple &t1, triple &t2){
return t1.first < t2.first;
}
int main()
{
// #ifndef ONLINE_JUDGE
// freopen("ip.txt", "r", stdin);
// freopen("op.txt", "w", stdout);
// #endif
int t; cin >> t;
for(int test = 1; test <= t; ++test){
string ans = "IMPOSSIBLE", s;
int n, flag = 0;
cin >> n;
vector<triple> acts(n);
for(int i = 0; i < n; i++){
s += '0';
cin >> acts[i].first >> acts[i].second;
acts[i].third = i;
}
sort(acts.begin(), acts.end(), cmp);
bool c = 0, f = 0;
int fends = -1, cends = -1;
for(int i = 0; i < n; ++i){
if(acts[i].first >= fends){
f = 0;
}
if(acts[i].first >= cends){
c = 0;
}
if(!f){
f = 1;
s[acts[i].third] = 'J';
fends = acts[i].second;
}else if(!c){
c = 1;
s[acts[i].third] = 'C';
cends = acts[i].second;
}else{
flag = 1;
break;
}
}
cout << "Case #" << test << ": " << (flag ? ans : s) << endl;
}
}
Hey @rathi_22 can you provide any resource where I can find out the proof why sorting by start or end time works for a specific solution !
my solution is giving WA can someone help me
#include <bits/stdc++.h>
using namespace std;
long long int M= 1000000007;
int fun(vector& v,int start,int end)
{
for (int i = start; i < end; i++)
{ if (v[i]!=1)
{return -1;}
}
for (int i = start; i < end; i++)
{ v[i]=0; }
return 1;
}
int main()
{ int t,z;
cin >> t;
z=t;
while (t–)
{
int n,x,k, ans,ctr=0,flag=0,ele1,ele2;
cin>>n;
string str;
vector cv(200000,1),jv(200000,1),s,e;
for (int i = 0; i < n; i++)
{ cin>>ele1>>ele2;
s.push_back(ele1);
e.push_back(ele2);
}
for ( int i = 0; i < n; i++)
{int temp=0;
temp=fun(cv,s[i],e[i]);
if(temp==1)
{str=str+‘C’;}
else if(temp==-1)
{int temp2=0;
temp2=fun(jv,s[i],e[i]);
if(temp2==1)
{str=str+‘J’;}
else if(temp2==-1)
{flag=-1;break;}
}
}
if(flag==-1)
{cout<<“Case #”<<z-t<<": IMPOSSIBLE"<<endl;}
else
{cout<<“Case #”<<z-t<<": "<<str<<endl;}
}
return 0;
}
can u please provide more detail about this approach
Can you anyone proof this why sorting by start time works here and why fails if sort by end time ?
1 Like
actually i think sorting by end time doesn’t fail here ,
1 4
0 200
50 100
150 300
250 270
Its giving correct answer for this case (Case #1: CJJC)
please help me. I do not know why it is failing the second test set
LINK to CODE: https://rextester.com/WFWPN36747
Can anyone explain what is the entution behind the sorting with start time and not the end.(or when to sort on the basis of start time and end time)
Hey @cap_coder, you could start with some observations. I’ll give the sketch and you can work out the finer details. So firstly, note that if 3 intervals overlap at a given point, then assigning tasks is impossible. Now we claim that for all other cases we can always find an assignment. So assume we’ve sorted the intervals by start time.
We can use induction to prove correctness.
- Firstly, assign the first interval arbitrarily (to C let’s say). [base case]
- Now suppose the first i (i >= 1) intervals in sorted order have been assigned successfully [ind. hypothesis]. We want to assign the (i+1)th interval. Observe that this interval cannot intersect with more than 1 interval among {1,2,…,i} otherwise there would be 3 intervals overlapping at s_(i+1) [this is the crux]. If it does not intersect with any interval in {1,2,…i} assign the (i+1)-th interval arbitrarily to C or J. Otherwise, it intersects with some interval j in {1,2,…i}. In this case, assign the task to the person who didn’t do task j. For example, if C did task j, then assign the (i+1)-th task to J or vice versa. In either case, we’ve successfully assigned the first (i+1) tasks. Hence proved by induction.
1 Like
bro tell me where i m wrong
#include <bits/stdc++.h>
using namespace std;
#define loop(i,n) for (int i = 0; i < n; i++)
#define pb push_back
struct interval{
int sta;
int end;
};
bool overlap(interval A,interval B){
return(max(A.sta,B.sta)<=min(A.end,B.end));
}
void totaloverlap(vector<interval>vec , interval A , int &f){
loop(i,vec.size()){
if(overlap(vec[i],A)){
f=0;
return;
}
}
return ;
}
int main() {
int t;
cin>>t;
for(int y=1;y<=t;y++){
int n;
cin>>n;
vector<interval>jwali,cwali;
string ans="";
interval arr[n];
int flag=0;
loop(i,n){
cin>>arr[i].sta>>arr[i].end;
arr[i].end-=1;
if(flag==0){
if(!i){
jwali.pb(arr[i]);
ans+="J";
}
else{
int f=1;
totaloverlap(cwali,arr[i],f);
if(f){
ans+="C";
cwali.pb(arr[i]);
continue;
}
f=1;
totaloverlap(jwali,arr[i],f);
if(f){
ans+="J";
jwali.pb(arr[i]);
continue;
}
else{
ans = "IMPOSSIBLE";
flag=1;
}
}
}
}
cout<<"Case #"<<y<<": "<<ans<<"\n";
}
return 0;
}here is my AC code i don’t know which TC give WA without sorting
#include <bits/stdc++.h>
using namespace std;
#define loop(i,n) for (int i = 0; i < n; i++)
#define pb push_back
struct interval{
int sta;
int end;
int index;
};
bool overlap(interval A,interval B){
return(max(A.sta,B.sta)<=min(A.end,B.end));
}
void totaloverlap(vector<interval>vec , interval A , int &f){
loop(i,vec.size()){
if(overlap(vec[i],A)){
f=0;
return;
}
}
return ;
}
bool comp(interval A,interval B){
if(A.sta!=B.sta)
return(A.sta<B.sta);
return(A.end<B.end);
}
int main() {
int t;
cin>>t;
for(int y=1;y<=t;y++){
int n;
cin>>n;
vector<interval>jwali,cwali;
char ans[n];
string ans2="";
interval arr[n];
int flag=0;
loop(i,n){
cin>>arr[i].sta>>arr[i].end;
arr[i].end-=1;
arr[i].index = i;
}
sort(arr,arr+n,comp);
loop(i,n){
if(!i){
jwali.pb(arr[i]);
ans[arr[i].index]='J';
}
else{
int f=1;
totaloverlap(jwali,arr[i],f);
//cout<<f<<endl;
if(f){
ans[arr[i].index]='J';
jwali.pb(arr[i]);
continue;
}
f=1;
totaloverlap(cwali,arr[i],f);
//cout<<f<<endl<<endl;;
if(f){
ans[arr[i].index]='C';
cwali.pb(arr[i]);
//continue;
}
else{
ans2 = "IMPOSSIBLE";
flag=1;
break;
}
}
}
if(flag)
cout<<"Case #"<<y<<": "<<ans2<<"\n";
else{
cout<<"Case #"<<y<<": ";
loop(i,n)
cout<<ans[i];
cout<<"\n";
}
}
return 0;
}