TRIP2 - Editorial

Thank you very much bro.

1 Like

Can you please help me tell why my solution is not working.
https://www.codechef.com/submit/TRIP2

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

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.
Please check this
https://www.codechef.com/viewsolution/26224804

This appears to give no output for the testcase:

1
2 2
2 1 

Please help me in this problem.
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 

:slight_smile:

Hey
Please help me finding the problem in my code
Thank you :slightly_smiling_face:

#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 :slight_smile:

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 :sweat_smile:

1 Like

Nice one - happy to help :slight_smile: