TRIP2 - Editorial

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

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: