TRIP2 - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Hasan

Tester: Teja Vardhan Reddy

Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given an array A of length N where each value is either -1 or in range [1, K] for a given K, find a way to replace -1 with some positive values in range [1, K] such that no two consecutive values are same or determine that no such way exist.

EXPLANATION

Let’s consider K = 2 first.

Since there are only two values, the only valid sequence can be either of the following.

1 2 1 2 1 2 . . .
2 1 2 1 2 1 . . .

If the already assigned values match either of the above at all corresponding indices, we can assign the remaining values from the above sequence.

For example, sequence 1 -1 2 do not match either of the above, but sequence 1 -1 -1 2 matched the first sequence. So, we can answer 1 2 1 2 for this case.

Now we have K \geq 3.

We can guarantee that answer always exists in this case, as any unassigned position can have at most two neighbors. Therefore, the current position can be forbidden to take at most two values. So trying a set of three distinct values, it is guaranteed that at least one value shall satisfy our constraints.

Consider example 1 -1 2 again. Previously, due to K = 2, we had no choice, but with K \geq 3, we can assign any value in range [3, K] to the unassigned position, thus finding a valid assignment too.

TIME COMPLEXITY

The time complexity is O(N) per test case.

SOLUTIONS:

Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int a[123456],b[123456];

int main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int k;
		cin>>k;
		int i;
		rep(i,n){
			cin>>a[i];
		}
		if(k==2){
			int flag;
			rep(i,n){
				b[i]=i%2+1;
			}
			flag=0;
			rep(i,n){
				if(a[i]==-1)
					continue;
				if(b[i]!=a[i]){
					flag=1;
					break;
				}
			}
			if(flag==0){
				cout<<"YES"<<endl;
				rep(i,n){
					cout<<b[i]<<" ";
				}
				cout<<endl;
				continue;
			}
			rep(i,n){
				b[i]=(i+1)%2+1;
			}
			flag=0;
			rep(i,n){
				if(a[i]==-1)
					continue;
				if(b[i]!=a[i]){
					flag=1;
					break;
				}
			}
			if(flag==0){
				cout<<"YES"<<endl;
				rep(i,n){
					cout<<b[i]<<" ";
				}
				cout<<endl;
				continue;
			}
			cout<<"NO"<<endl;
		}
		else{
			cout<<"YES"<<endl;
			rep(i,n){
				if(a[i]!=-1)
					continue;
				if(i==0){
					if(a[i+1]==1){
						a[i]=k;
					}
					else{
						a[i]=1;
					}
				}
				else if(i==n-1){
					if(a[i-1]==1){
						a[i]=k;
					}
					else{
						a[i]=1;
					}
				}
				else{
					if(a[i-1]==1){
						if(a[i+1]==2)
							a[i]=3;
						else
							a[i]=2;
					}
					else if(a[i-1]==2){
						if(a[i+1]==1)
							a[i]=3;
						else
							a[i]=1;
					}
					else{
						if(a[i+1]==2)
							a[i]=1;
						else
							a[i]=2;
					}
				}
			}
			rep(i,n){
				cout<<a[i]<<" ";
			}
			cout<<endl;	
		}
	}
	return 0;   
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class TRIP2{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), k = ni();
	    int[] a = new int[n];
	    for(int i = 0; i< n; i++)a[i] = ni();
	    if(n == 1){
	        pn("YES");
	        if(a[0] == -1)a[0] = 1;
	        pn(a[0]);return;
	    }
	    if(k == 2){
	        int p = -1;
	        while(p+1 < n && a[p+1] == -1)p++;
	        if(p == n-1)a[p] = 1;
	        else if(p>=0)a[p] = 3-a[p+1];
	        while(--p>=0)a[p] = 3-a[p+1];
	        
	        for(int i = 1; i< n; i++){
	            if(a[i] == -1)a[i] = 3-a[i-1];
	        }
	        boolean possible = true;
	        for(int i = 1; i< n; i++)possible &= a[i] != a[i-1];
	        if(possible){
	            pn("YES");
	            for(int i:a)p(i+" ");pn("");
	        }else pn("NO");
	        return;
	    }
	    
	    pn("YES");
	    for(int i = 0; i< n; i++){
	        if(a[i] != -1)continue;
	        if(i == 0){
	            a[i] = 1;
	            if(a[i+1] == 1)a[i]++;
	        }else if(i == n-1){
	            a[i] = 1;
	            if(a[i-1] == 1)a[i]++;
	        }else{
	            a[i] = 1;
	            if(a[i-1] == 1 || a[i+1] == 1){
	                a[i] = 2;
	                if(a[i-1] == 2 || a[i+1] == 2)a[i] = 3;
	            }
	        }
	    }
	    for(int i:a)p(i+" ");pn("");
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new TRIP2().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

6 Likes

Now I understand how hard is it to code than to explain. Wasted half the time of the contest in this question, but finally got a 100.
Anyways, the approach is similar, dividing the code mainly into 2 parts,

  1. k = 2;
  2. k >= 3.

Feel free to check my horrible solution.

3 Likes

https://www.codechef.com/viewsolution/26189842
Above is the link to my solution…can u please help out with some corner cases…I am getting only 70

Here: try this case
5 2
-1 -1 -1 1 -1
your answer is NO but the actual answer is 2 1 2 1 2

5 Likes

@tushar_2018
Try this test case :
4 2
-1 -1 -1 1
Expected O/P :
YES
2 1 2 1
Your’s O/P :
NO

1 Like

My solution is quite readable:

[https://www.codechef.com/viewsolution/26190884]

#include<stdio.h>
int main(){
int t;
scanf("%d",&t);
while(t–){
int n,k,i,j,flag=0,s,r;
scanf("%d%d",&n,&k);
int a[n];
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
if(a[0]==-1){
if(k!=2){
for(i=1;i<=k;i++){
if(a[1]!=i){
a[0]=i;
break;
}
}
}
else{
for(i=0;i<n;i++){
if(a[i]==1){
s=i;
r=1;
break;
}
if(a[i]==2){
s=i;
r=2;
break;
}
}
if(s%2==0){
a[0]=r;
}
else{
if(r==1){
a[0]=2;
}
else{
a[0]=1;
}
}
}
}
for(i=1;i<n-1;i++){
if(a[i]==-1){
for(j=1;j<=k;j++){
if(a[i-1]!=j&&a[i+1]!=j){
a[i]=j;
break;
}
}
}
}
if(a[n-1]==-1){
for(i=1;i<=k;i++){
if(a[n-2]!=i){
a[n-1]=i;
break;
}
}
}
for(i=0;i<n;i++){
if(a[i]==-1){
flag=1;
break;
}
}
if(flag==1){
printf(“NO\n”);
}
else{
printf(“YES\n”);
for(i=0;i<n;i++){
printf("%d “,a[i]);
}
printf(”\n");
}
}
}

My logic only works for the sample testcases but it gives the WA after submission. Will anyone help me to get out of it !!!
i have check the elements with -1 and then i used a loop and increments the value with all the legal values of k from 1 and checks whether it does not matches with its neighbours .
will anyone help me …
here my code
https://www.codechef.com/viewsolution/26191137

https://www.codechef.com/viewsolution/26190821
Above is the link to my solution…can u please help out with some corner cases…I am getting only 70

Why is my backtrack solution getting NZEC. Can you please help out with some test case?
https://www.codechef.com/viewsolution/26191853

This is the link to my solution in python3.

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

@aryan12

Can u help me out with my solution , it gives 30 points and i could not get which case i am missing , while i have tried many cases and all gives right answer .

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

please help , give any case for which wrong answer come…

and i also want to ask that when we get 70 points and when 100

try the following
n=3 k=2
-1 -1 2
-1 -1 1

in one of the following your code will fail

2 Likes

You get 70 points when your code gets accepted on a test case based upon the original constraints and fails on the subtask of 30 points,
For the constraints of each sub-task, check the link out.
You get 100 points when your code gets accepted in both, the 30 points and 70 points sub-task.

You are getting wrong answer on the following test case

5 3
1 -1 2 -1 3

The answer should be:
YES
1 3 2 1 3

Your answer is:
NO

I won’t say where is the bug in your code in this comment. But if you still can’t find the bug, you are most welcome to revert back to me for the bug. It is a request to please try doing it yourself first before asking me. Hope this helps :slight_smile: :slight_smile:.

2 Likes

Looks like a large testcase will trigger a maximum recursion depth error:

  <snip>
  File "./foxsgiven0-TRIP2.py", line 32, in helper
    if (helper(arr, k)):
  File "./foxsgiven0-TRIP2.py", line 32, in helper
    if (helper(arr, k)):
  File "./foxsgiven0-TRIP2.py", line 32, in helper
    if (helper(arr, k)):
  File "./foxsgiven0-TRIP2.py", line 32, in helper
    if (helper(arr, k)):
  File "./foxsgiven0-TRIP2.py", line 32, in helper
    if (helper(arr, k)):
  File "./foxsgiven0-TRIP2.py", line 32, in helper
    if (helper(arr, k)):
  File "./foxsgiven0-TRIP2.py", line 32, in helper
    if (helper(arr, k)):
  File "./foxsgiven0-TRIP2.py", line 32, in helper
    if (helper(arr, k)):
  File "./foxsgiven0-TRIP2.py", line 32, in helper
    if (helper(arr, k)):
  File "./foxsgiven0-TRIP2.py", line 32, in helper
    if (helper(arr, k)):
  File "./foxsgiven0-TRIP2.py", line 23, in helper
    if (not findEmptyLocation(arr,posList)):
  File "./foxsgiven0-TRIP2.py", line 4, in findEmptyLocation
    for i in range(len(arr)):
RuntimeError: maximum recursion depth exceeded in comparison

(Edit: at least on my laptop - maybe Codechef’s stack limit is higher)

Consider:

1
3 2
-1 -1 2 

Too much of If - Else, sigh
Here is the solution for k=2 (Python 3.6)
30pts

Here is the 100pts solution:
100pts

I just extended 30 pts code, in the second solution.
Warning : Messy solution.
Happy Coding

Plz check why my code is wrong
problem code TRIP2

#include
using namespace std;

long int check( long int a[] ,long int k , long int n )
{
long int j;
long int q=a[1];
if(n==1)
{
return k;
}
for(j=1;j<=k;j++)
{
if(j!=q)
break;
}
return j;
}

long int ch(long int a[] , long int k , long int i)
{
long int j;
for(j=1;j<=k;j++)
{
if(j!=a[i-1] && j!=a[i+1])
break;
}
return j;

}

long int chh(long int a[] , long int k , long int n)
{
long int j;
for(j=1;j<=k;j++)
{
if(j!=a[n-2])
break;
}
return j;

}

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
long int n,k;
cin>>n>>k;
long int a[n],i;
for(i=0;i<n;i++)
{
cin>>a[i];

    }
    for(i=0;i<n;i++)
    {
        if(a[0]==-1) a[0]=check(a , k , n);
        else if(i>0 && i<n-1 && a[i]==-1)            a[i]=ch(a , k , i);
   
        else if(a[n-1]==-1)                       a[n-1]=chh(a , k , n);
    }
    
    for(i=0;i<n;i++)
    {
       if(n==1) i=1; 
      else if(a[i]==a[i+1] || a[i]==k+1 )
        break;
    }
    if(i!=n)
    {
        cout<<"NO"<<endl;
    }
    else {
        cout<<"YES"<<endl;
        for(i=0;i<n;i++)
        cout<<a[i]<<"\t";
        cout<<endl;
    }
    
}
return 0;

}

can someone please give a case for which my code isn’t working.
https://www.codechef.com/viewsolution/26195971

Here’s my solution, by the way - hopefully more readable than the Editorial ones :wink:

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