EXERCISE - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Hasan

Tester: Roman Bilyi

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Observations, Implementation.

PROBLEM:

Chef exercises for N days and keep record of his exercise time in array A of length N. Also, for each pair of consecutive days, he keeps note whether A_i < A_{i+1}, A_i = A_{i+1} or A_i > A_{i+1}, denoted by ‘<’, ‘=’ and ‘>’ respectively in string S.

Now, some values in array A is erased which is denoted by A_i = -1. Determine if it’s possible to replace -1 such that A and S are consistent with each other. Note that A_i \geq 0 shall always hold. Also, elements not replaced in array A are consistent with string S.

EXPLANATION

Let’s focus on ‘=’ sign first. If both operands are not -1, then we are given that A_i = A_{i+1}. If one of them is erased, then it shall take the same value as the non-erased one. Lastly, if both elements are erased, then both shall take the same value.

In all cases, the presence of duplicates does not affect our other conditions. Let’s merge all consecutive positions, which have only ‘=’ in between.

For example, consider schedule

5 5 -1 -1 -1 10
=<=<=

If we focus only on ‘=’, we can also write A as 5 5 -1 -1 10 10 and now merge these to form 5 -1 10 and the corresponding S be <<

But what if a case occurs 5 -1 10 and string “==”. We can see that no valid schedule exists. Generalizing, we can say that while merging, if there are at least two distinct non-replaced values which we try to merge, there exists no valid schedule. So, we can print NO immediately.

Hence, we can simply remove all ‘=’ from S, so S now contains only ‘<’ and ‘>’

Now, let’s consider every consecutive pair of operators in string S.

  • If the first operator is ‘<’ and the second operator is ‘>’, then we there is no upper limit on value, hence we can set the value in between, if replaced, to some sufficiently large value, say 10^7
  • If the first operator is ‘>’ and the second operator is ‘<’, then we there is no lower limit on value apart from it being non-negative, hence we can set the value, if replaced, to 0 without violating any constraints.

Consider example 1 < -1 > 5 > -1 < 10

The first erased element is greater than both elements adjacent to it, so we can easily assign it some large value without breaking down any constraint.
The second erased element is smaller than both elements adjacent to it, so we can easily see that assigning 0 is optimal, since if v is less than 5, then v-1 is also less than 5, so it’s best to fill this position with minimum allowed value which is zero.

So above example transform into ````1 >

Also, if the very first and last element, if erased, can be assigned values with same logic.

After this, we can see, that if there’s any -1, it is surrounded by either < or > but not both. Hence, now we can split the array into segments such that each segment b has two non-erased elements at both ends, and all in-between elements are erased, and for every element in this segment, either b_i < b_{i+1} for all i or b_{i} > b_{i+1} for all i.

Something like 5 < -1 < -1 < -1 < 10. In this case, we can see the number of elements allowed in between, here we can have 10-5-1 = 4 distinct values between 5 and 10, and the number of erased elements is 3, and 5 < 10 holds, so we can fill this segment successfully.

Cases to think about

5 > -1 > -1 > -1 > 10
5 < -1 < -1 < -1 < 8

TIME COMPLEXITY

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

SOLUTIONS:

Tester's Solution
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 400007;

const int MOD = 1000000007;

const double Pi = acos(-1.0);

int main(int argc, char* argv[])
{
	// freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	int t;
	cin >> t;
	FOR(tt,0,t)
	{
	    VI A;
	    int n;
	    cin >> n;
	    FOR(i,0,n)
	    {
	        int x;
	        cin >> x;
	        A.push_back(x);
	    }
	    string s;
	    cin >> s;

	    VI R = A;
	    FOR(i,0,n)
	        if (R[i] == -1)
	            R[i] = INF;

	    FOR(i,1,SZ(A))
	    {
	        if (A[i] == -1 && R[i - 1] != INF)
	        {
	            if (s[i - 1] == '>')
	            {
	                R[i] = R[i - 1] - 1;
	            }
	            if (s[i - 1] == '=')
	            {
	                R[i] = R[i - 1];
	            }
	        }
	    }
	    RFOR(i,SZ(A) - 1, 0)
	    {
	        if (A[i] == -1 && R[i + 1] != INF)
	        {
	            if (s[i] == '<')
	            {
	                R[i] = min(R[i], R[i + 1] - 1);
	            }
	            if (s[i] == '=')
	            {
	                R[i] = min(R[i], R[i + 1]);
	            }
	        }
	    }

	    FOR(i,0,n)
	    {
	        if (R[i] == INF)
	        {
	            if (i == 0)
	                R[i] = INF / 2;
	            else
	            {
	                if (s[i - 1] == '=')
	                {
	                    R[i] = R[i - 1];
	                }
	                else
	                {
	                    if (s[i - 1] == '<')
	                    {
	                        R[i] = max(INF / 2, R[i - 1] + 1);
	                    }
	                    else
	                    {
	                        R[i] = min(INF / 2, R[i - 1] - 1);
	                    }
	                }
	            }
	        }
	    }

	    

	    bool ok = true;
	    FOR(i,0,n - 1)
	    {
	        if (s[i] == '=' && R[i] != R[i + 1])    
	            ok = false;
	        if (s[i] == '>' && R[i] <= R[i + 1])    
	            ok = false;
	        if (s[i] == '<' && R[i] >= R[i + 1])    
	            ok = false;
	    }

	    FOR(i,0,n)
	    {
	        if (R[i] < 0)
	        {
	            ok = false;
	        }
	    }

	    if (ok)
	    {
	        cout << "YES" << endl;
	        // FOR(i,0,n)
	        // {
	        //     cout << R[i] << ' ';
	        // }
	        // cout << endl;
	    }
	    else
	    {
	        cout << "NO" << endl;
	    }


	}  

	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;

	
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class EXERCiSE{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni();
	    int[] a = new int[n];
	    for(int i = 0; i< n; i++)a[i] = ni();
	    String s = n();
	    
	    int[] b = new int[n];
	    int cnt = 0;
	    b[cnt++] = a[0];
	    StringBuilder t = new StringBuilder("");
	    boolean valid = true;
	    for(int i = 1; i< n; i++){
	        if(s.charAt(i-1) == '='){
	            if(b[cnt-1] == -1)b[cnt-1] = a[i];
	            else if(a[i] != -1)valid &= b[cnt-1] == a[i];
	            continue;
	        }
	        t.append(s.charAt(i-1));
	        b[cnt++] = a[i];
	    }
	    int INF = (int)1e7;
	    
	    for(int i = 0; i+1 < cnt-1; i++){
	        if(t.charAt(i) != t.charAt(i+1)){
	            if(b[i+1] != -1)continue;
	            if(t.charAt(i) == '<')b[i+1] = INF;
	            else b[i+1] = 0;
	        }
	    }
	    if(b[0] == -1){
	        if(t.charAt(0) == '<')b[0] = 0;
	        else b[0] = INF;
	    }
	    if(b[cnt-1] == -1){
	        if(t.charAt(cnt-2) == '<')b[cnt-1] = INF;
	        else b[cnt-1] = 0;
	    }
	    
	    for(int i = 0; i< cnt-1; i++){
	        if(b[i] == -1 || b[i+1] == -1)continue;
	        if(t.charAt(i) == '<')valid &= b[i] < b[i+1];
	        else valid &= b[i] > b[i+1];
	    }
	    for(int i = 0, j = 0; i< cnt; i = j){
	        j++;
	        while(j < cnt && b[j] == -1)j++;
	        int inbet = j-i-1;
	        if(i+1 == j)continue;
	        if(t.charAt(i) == '<'){
	            valid &= b[j]-b[i]-1 >= inbet;
	        }else{
	            valid &= b[i]-b[j]-1 >= inbet;
	        }
	    }
	    pn(valid?"YES":"NO");
	}
	//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 EXERCiSE().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:

3 Likes

Liked your approach but how to do the merging part?

I saw the accepted solution of the user ‘kriophoros’ . There , with n=3 , A being [0 -1 -1] with S [ => ] is printing “YES” . Instead ,this test case should be printing “NO”.

Consider A being 5 -1 6 and string ‘==’ The expression is 5 = __ = 6 Here we cannot fill the empty space without violating at least one comparision. Answer is NO in this case.

Consider A being 6 -1 -1 5 -1 -1 and string ‘>===<’ The expression is6 > __ = __ = 5 = __ < __ We know we need to fill all blanks with 5 except last. Our expression after merging is 6 > 5 = 5 = 5 = 5 < __ Now, equal signs serve no purpose, so we can write it as 6 > 5 < __ and continue as above.

Last case -1 -1 -1 -1 and string ‘>=<’ Suppose second blank is filled with x, our expression become __ > x = x = < __ which can be written as __ > x < __

For implementation, refer my solution.

Oh, It’s weird…

1 Like