TRIP2 - Editorial

@aryan12

Thnakyou so very much , i was unable to find the case where it was failing .
Thank you :innocent::innocent::innocent::innocent::innocent:

Thankyou so much , it got submiited , their was a error of one character , i CHANGED + TO - AND BOOM !!!

1 Like

yes! Stacks size seems to the problem. Thank you for pointing out.

1 Like

What’s wrong ??

https://www.codechef.com/viewsolution/26200425

Thanks for actually linking your solution :slight_smile:

It fails for the following testcase:

1
5 2
2 -1 -1 -1 -1 

I get a 403 error when trying to access your solution :confused:

That is not the link to your solution XD The correct link is: CodeChef: Practical coding for everyone

Consider the testcase:

1
10 2
-1 -1 -1 -1 -1 2 -1 -1 -1 2 

Please help me i don;t know at which case it’s failing

//Chef and Trip
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

void print(int o,int t,int n)
{
int start;
if (o == -1 && t == -1)
start = 1;
else if ( o != -1)
{
if (!o%2)
start = 1;
else
start = 2;
}
else if ( t != -1)
{
if (!o%2)
start = 2;
else
start = 2;
}
for (auto i = 0; i < n; ++i)
{
cout<<start<<" ";
(start == 1) ? ( start += 1):(start -= 1) ;
}
cout<<endl;
}

int my_find_if(int k1,int k2 = 0)
{

vector<int> v = {1,2,3};
for (auto i = v.begin(); i != v.end() ; ++i)
{
	if (*i != k1 && *i != k2)
		return *i;
}
return 0;

}
int main()
{
int t , c;
ll n , k;

cin>>t;
while (t--)
{
	cin>>n>>k;
	vector<int> v1(n);
	for (int i = 0; i < n; ++i)
	{
		cin>>c;
		v1[i] = c;
	}

	int oneth_pos = -1;
	int twoth_pos = -1;
	bool x = 1;
	if (k == 2)
	{
		for (int it = 0 ; it < n ; ++it)
		{
			if (v1[it] == 1)
			{
				if (oneth_pos == -1)
				{
					oneth_pos = it ;
				}
				else 
				{
					if ((it - oneth_pos) & 1)
					{
						x = 0;
						break;
					}
					else
						oneth_pos = it;
				}
			}
			else if (v1[it] == 2)
			{
				if (twoth_pos == -1)
				{
					twoth_pos = it;
				}
				else 
				{
					if ((it - twoth_pos) & 1)
					{
						x = 0;
						break;
					}
					else
						twoth_pos = it;
				}
			}	
			if (oneth_pos != -1 && twoth_pos != -1)
			{
				if (abs(oneth_pos - twoth_pos)%2 != 1)
				{
					x = 0;
					break;
				}
			}		
		}
		if (!x)
		{
			cout<<"NO\n";
		}
		else
		{
			cout<<"YES\n";
			print(oneth_pos,twoth_pos,n);
		}
	}
	else
	{
		for (int i = 0; i < n; ++i)
		{
			if (v1[i] == -1)
			{
				if (i == 0)
				{
					v1[i] = my_find_if(v1[i+1]);
				}
				else if ( i < n - 1)
				{
					v1[i] = my_find_if(v1[i-1],v1[i+1]);
				}
				else
				{
					v1[i] = my_find_if(v1[i-1]);
				}
			}
		}
		cout<<"YES\n";
		for (auto i = v1.begin() ; i != v1.end() ; ++i )
		{
			cout<<*i<<" ";
		}
		cout<<endl;
	}
}

}

See my post above :slight_smile:

It’s even passing the testcases like
4 2
-1 -1 1 -1

please help me

Please help me bro
i tried all the test cases that you have mentioned above , it is working fine

Well, no it isn’t, which is why I posted it :slight_smile:

Your program seems to output

YES
2 1 2 1 2 1 2 1 2 1

for the testcase

1
10 2
-1 -1 -1 -1 -1 2 -1 -1 -1 2 

which is not a valid answer.

I’ll “superimpose” the input array and your output array to hopefully make things clearer :slight_smile:

-1 -1 -1 -1 -1  2 -1 -1 -1  2  <-- The input array
 2  1  2  1  2  1  2  1  2  1  <-- Your output

Thank you very much bro.

1 Like

Can you please help me tell why my solution is not working.

Can anyone tell me what’s wrong with my backtrack code? It is quite readable.
My submission
Thank you in advance.

That’s not a link to your solution!

Here is a link to your solution.

This also fails the testcase:

1
10 2
-1 -1 -1 -1 -1 2 -1 -1 -1 2 

@ankit9437

There’s an out-of-bounds access at the line:

    if(arr[curr]==arr[curr-1] && curr>0)  return false;

given the testcase:

1
43 2
-1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 

which is probably interfering with the results. (This is likely not the only problem).

This fails the testcase:

1
10 2
-1 -1 -1 -1 -1 2 -1 -1 -1 2 

add the following in your code

import sys
sys.setrecursionlimit(10**9)

This question is a classic example of Implementation being the hardest part.

https://www.codechef.com/viewsolution/26188055

Please help out with some cases. My solution gets only 70