# TRIP2 - Editorial

Thank you very much bro.

1 Like

https://www.codechef.com/submit/TRIP2

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

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
``````

import sys
sys.setrecursionlimit(10**9)

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

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

Yours also fails the testcase:

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

Edit:

You also have a lot of compiler warnings which you should verify aren’t causing a problem:

Compiler warnings
``````rashu1999-TRIP2.cpp:50:28: warning: using the result of an assignment as a condition without parentheses [-Wparentheses]
else if(no = -1 && arr[1] == -1)
~~~^~~~~~~~~~~~~~~~~~~~
rashu1999-TRIP2.cpp:50:28: note: place parentheses around the assignment to silence this warning
else if(no = -1 && arr[1] == -1)
^
(                      )
rashu1999-TRIP2.cpp:50:28: note: use '==' to turn this assignment into an equality comparison
else if(no = -1 && arr[1] == -1)
^
==
rashu1999-TRIP2.cpp:101:35: warning: '&&' within '||' [-Wlogical-op-parentheses]
if(l == 1 && r == 1 || l == 1 && r>2 || l>2 && r == 1)
~~~~~~~^~~~~~~~~ ~~
rashu1999-TRIP2.cpp:101:35: note: place parentheses around the '&&' expression to silence this warning
if(l == 1 && r == 1 || l == 1 && r>2 || l>2 && r == 1)
^
(               )
rashu1999-TRIP2.cpp:101:55: warning: '&&' within '||' [-Wlogical-op-parentheses]
if(l == 1 && r == 1 || l == 1 && r>2 || l>2 && r == 1)
~~ ~~~~~~~^~~~~~
rashu1999-TRIP2.cpp:101:55: note: place parentheses around the '&&' expression to silence this warning
if(l == 1 && r == 1 || l == 1 && r>2 || l>2 && r == 1)
^
(            )
rashu1999-TRIP2.cpp:101:69: warning: '&&' within '||' [-Wlogical-op-parentheses]
if(l == 1 && r == 1 || l == 1 && r>2 || l>2 && r == 1)
~~ ~~~~^~~~~~~~~
rashu1999-TRIP2.cpp:101:69: note: place parentheses around the '&&' expression to silence this warning
if(l == 1 && r == 1 || l == 1 && r>2 || l>2 && r == 1)
^
(            )
rashu1999-TRIP2.cpp:104:40: warning: '&&' within '||' [-Wlogical-op-parentheses]
else if(l == 2 && r == 1 || l==1 && r==2)
~~~~~~~^~~~~~~~~ ~~
rashu1999-TRIP2.cpp:104:40: note: place parentheses around the '&&' expression to silence this warning
else if(l == 2 && r == 1 || l==1 && r==2)
^
(               )
rashu1999-TRIP2.cpp:104:58: warning: '&&' within '||' [-Wlogical-op-parentheses]
else if(l == 2 && r == 1 || l==1 && r==2)
~~ ~~~~~^~~~~~~
rashu1999-TRIP2.cpp:104:58: note: place parentheses around the '&&' expression to silence this warning
else if(l == 2 && r == 1 || l==1 && r==2)
``````

I have corrected that still it fails. This is my updated solution.
https://www.codechef.com/viewsolution/26224804

This appears to give no output for the testcase:

``````1
2 2
2 1
``````

I use algo like this:
count -1 while input
1.) if n = 1,
-> if a[0] = -1 print YES/n k
->else print YES\n cout<<a[0]

2.) else if(count == 0)
->print array as it is

3.) First detect the no -1.
-> if i> 0 and i<n-1, then

…I took var sum = a[i-1]+a[i+1] & var avg = sum/2;

…If sum == 0
a[i]=2; count–

…else if(sum <=k)
a[i]=sum; count–

…else if(sum > k)
if(avg == a[i-1])
if(a[i-1]-1 > 0)
c–; a[i] = avg-1;
else if(avg == a[i+1]){
if(a[i+1]-1 > 0)
a[i] = avg-1; c–;
else
a[i] = avg; c–;

-> else If it is at i = 0, then

``````if(a[i] != -1)
``````

…if a[i+1]+1<=k then a[i] = a[i+1]+1; count–
…else if a[i+1]-1>0 then a[i] = a[i+1]-1 count–

``````else
``````

…a[i]=k; count–

-> else If it is at i = n-1, then
if(a[i] != -1)
…if a[i-1]+1<=k then a[i] = a[i-1]+1 count–
…else if a[i-1]-1>0 then a[i] = a[i-1]-1 count–

``````else
``````

…a[i]=k; count–

->if count != 0
…cout<<“NO”

else
…print YES and array

HELP IN IT

Your code also fails for the testcase:

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

Hey
Thank you

#include <bits/stdc++.h>
using namespace std;
int main() {
int t, l, r;
cin>>t;
while(t–)
{
int n, k, temp;
cin>>n>>k;

``````    vector<int> arr;
for(int i = 0; i<n; i++)
{
cin>>temp;
arr.push_back(temp);
}

if(n<1)
cout<<"NO\n";

else if(n == 1)
{
cout<<"YES\n";
if(arr[0] == -1)
cout<<1<<"\n";
else
cout<<arr[0]<<"\n";
}

else
{
if(k == 2)
{
int pos = -1, no = -1;
for(int i = 0; i<n; i++)
{
if(arr[i]!= -1)
{
pos = i;
no = arr[i];
break;
}
}
if((pos != -1) && (pos % 2 == 0) && (arr[0] == -1))
{
arr[0] = no;
}
else if((no != -1) && (arr[1] == -1))
arr[1] = no;

}

bool chk = true;
// cout<<chk<<"\n";

if(n == 2)
{
if((arr[0]!=-1) && (arr[0] == arr[1]))
{
cout<<"NO\n";
chk = false;
}

// else
// {

// }

}

if(arr[0] == -1)
{
r = arr[1];
if(r == 1)
arr[0] = 2;
else
arr[0] = 1;
}
// cout<<chk;

for(int i=1; i<n-1; i++)
{
if(arr[i] != -1)
{
if((arr[i-1] == arr[i]) || (arr[i] == arr[i+1]))
{
cout<<"NO\n";
chk = false;
break;
}
}
else if(arr[i] == -1)
{
l = arr[i-1];
r = arr[i+1];
if(r == -1)
{
if(l == 1)
arr[i] = 2;

else
arr[i] = 1;
}
else
{
if(((l == 1) && (r == 1)) || ((l == 1) && (r>2)) || ((l>2) && (r == 1)))
arr[i] = 2;

else if(((l == 2) && (r == 1)) || ((l==1) && (r==2)))
{
if(k>2)
arr[i] = 3;

else
{
cout<<"NO\n";
chk = false;
break;
}
}
else
arr[i] = 1;
}
}
}
// cout<<chk;
if(chk)
{
if(arr[n-1] == -1)
{
l = arr[n-2];
if(l == 1)
arr[n-1] = 2;
else
arr[n-1] = 1;
}

cout<<"YES\n";
for(int i=0; i<n; i++)
cout<<arr[i]<<" ";

cout<<"\n";
}
}
}
``````

}

Please format it or link to a solution - the forum software has manged it and it won’t compile

Edit:

It’s now failing for the testcase:

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

70/100 passed
30/100 failed

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

help in it

Your code produces no output for the testcase:

``````1
3 2
-1 -1 -1
``````

Got the mistake. Thanks for help. Tricky cases and silly mistakes

1 Like

Nice one - happy to help