PROBLEM LINK:
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 
) . Suggestions are welcomed as always had been. 
