CLLEXO EDITORIAL

editorial
, , , , ,
1

PROBLEM LINK

Practice
Contest

Author: Aman Kumar Singh
Testers: Sarthak Manna, Smit Mandavia, Avijit Agarwal
Editorialist: Avijit Agarwal

DIFFICULTY

Easy - Medium

PREREQUISITES

Dynamic Programming, Breadth First Search (BFS)

PROBLEM

You are given N strings, each of length M. Each character of each string can either be a lowercase English letter or the character #. You need to choose N non-empty substrings S_i[l_i, r_i] from each string i (for all 1 \leq i \leq N) such that

  • The final string is obtained by appending the substrings S_{1}[1, a_{1}], S_{2}[a_{1}, a_{2}], S_{3}[a_{2}, a_{3}], …, S_{N-1}[a_{N-2}, a_{N-1}], S_{n}[a_{N-1}, M], where 1 \leq a_1 \leq a_2 \leq a_3 \leq ... \leq a_{N-1} \leq M
  • None of the substrings contain any \# character.
  • The final string is the lexicographically smallest possible obtainable string.

EXPLANATION

This problem is equivalent to a problem where we are given a grid A of size N*M, where each cell of the grid is either a lower case English character or the character # and we need to find the lexicographically smallest string which can be obtained by traversing from A_{1,1} to A_{N,M}, where the resultant string doesn’t contain any # and where we can move only to the right or down cells.

Let us assume the final string to be S.
Then, |S| = N+M-1

To find a character S_l of the final string S, we need to find the smallest character A_{i,j} where:

  • i+j-1=l
  • A_{i,j} is reachable from A_{N,M}
  • A_{i,j} is not the character #
  • At least one of A_{i-1,j} or A_{i,j-1} is same as S_{l-1}

We initially mark all the cells reachable from A_{N,M} in a boolean 2D array using bottom up DP starting from A_{N,M}.

Then we do Breadth First Search (BFS) from the cell A_{1,1}, layer by layer such that in the l^{\text{th}} layer we examine all the cells A_{i.j} where i+j-1=l and are reachable from

  • A_{N,M}
  • the previously visited cells in the (l-1)^{\text{th}} layer

We find the minimum such character in the present layer and mark all the cells which contains this minimum character as visited. We append this minimum character to the answer and repeat this process until we reach the (N+M-1)^{\text{th}} layer.

The required time complexity is \mathcal{O}(N*M)

SOLUTIONS

C++ solution can be found here.
Java solution can be found here.
Python solution can be found here.

20 Likes
2

This is just an amazing problem and an amazing Editorial too xD. Thanks.

10 Likes
3

@sarthakmanna @avijit_agarwal Please tell the test case where my code is failing:
https://www.codechef.com/viewsolution/35689876

4

Why does a queue based bfs solution give TLE??
The time complexity is the same right??
Here is the link
https://www.codechef.com/viewsolution/35686020

Are the time limits too tight or am I missing something here?

5

For anyone who’s interested in how to totally overcomplicate this problem:

First, start by doing the entire thing backwards instead of using BFS. Then realize there’s no way to break ties without O(n + m) string comparison. Think for a while and never make the observation that you don’t have to do it backwards. Instead, come up with a solution that uses polynomial hashing to store the “value” of a string and use that to break ties. Of course, those numbers are on the order of 27^{n + m}, so that will never work.

Now comes the magic: coordinate compression… with a 2 second time limit and bounds of 10^7. Genius, right? So we compress the hashes, computing diagonal-by-diagonal (STILL stubbornly going backwards), and use a weird form of the bottom-up DP, then finally use the computed “ranks” to construct the path.

Test it on some stronger samples. Submit. Get TLE, of course.

Rewrite coordinate compression to get rid of STL, and pass in 640 ms. Even with 10^7 constraints, O((nm)\log(\min(n, m))) still passed comfortably. So what was the point of that constraint? I’m sure you didn’t expect a stupid submission like mine, but what were you trying to block? (@ author)

Besides that, cool problem. I enjoyed the path observation.

9 Likes
6

void solve()
{
ll t;
cin >> t;
while(t–)
{

    int n,m;
    cin >> n >> m;

    vector<string> v;
    for(int i=0;i<n;i++)
    {
        string s;
        cin >> s;
        v.push_back(s);
    }      

    string ans;
    int ind = 0;
    int x = 0;
    int j;
    for(int k=0;k<=m+n-2;k++)
    {
        
        if(ind == m-1)
        {
            break;
        }
        else
        {
            char c = 'z' + 1;
            ind = -1;
            for( j=x;j<n;j++)
            {
                if(k-j<=n-1 && k-j>=0 && k-j>=ind)
                {
                    if(v[k-j][j] < c && v[k-j][j]!='#')
                    {
                       // cout << i << " " << k - i << endl;
                        c = v[k-j][j];
                        ind = j;
                        x = k-j;
                    }
                }
                 
                                   
            }
            ans.push_back(c);
        }
       
    }

    for(int i = x + 1;i<n;i++)
    {
        ans.push_back(v[i][m-1]);
    }

    cout << ans << endl;


}

}

can anyone help why this going to fail

I am just transversing aross diagonally and check condition so that chosen should be smallest and will be left to the previous and next and same string currently
#just_constructive_algo

time complexity O(m*n)
@galencolin @avijit_agarwal

7

orz

1 Like
8

lol, I was on exact same path as you till 1st paragraph. I didn’t know what magic you did but left this approach after 1st para.

1 Like
9

This problem is exactly the same:

For each character ‘#’, just put the cost as 1 and for lower-case characters put 0, then the minimum cost is 0 and output is lexicographically smallest string. However, the submissions are not working(giving WA), @sarthakmanna @avijit_agarwal , please tell whether this approach is correct or not…

1 Like
10

Well, it’s not exactly the same problem…

You haven’t put any code, but I assume it’ll fail on this:

1
3 3
azz
a#z
##z

edit: I really need to stop commenting right after tiring myself out. Sorry, what I’m saying is wrong.

4 Likes
11

This is my code:
https://www.codechef.com/viewsolution/35689876
The output is: azzzz
@galencolin plz help…

12

Why is O(n*m) giving TLE ? Any help will be appreciated.

Approach: Go to the each level i from 0 to n + m - 1 and find the minimum character out of all the places from where bottom-right is visitable.

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

@avijit_agarwal

13

const int N = 1e3+10;
This is the problem I guess because you are declaring string s[N] and taking input but the constraint in this question was on n*m and not on n.

14

This one is still WA:
https://www.codechef.com/viewsolution/35691989

15

@swapnil159 any help here friend?

16

I’m sorry, I did not understand what you are saying. Can you elaborate??

1 Like
17

Even My solution with O(n*m) gives TLE. Just wonder if an explanation exists so that similar mistakes can be avoided in future.

18

Could you help my my queue based solution gives TLE. Are the time limits too strict or I am missing something in my solution. I have pasted link for my solution above. Here it is again.
https://www.codechef.com/viewsolution/35686020

19

Fails for
1
1 1
b

20

can you please have a look at my code also. I am getting WA.
https://www.codechef.com/viewsolution/35692024