LexicoGraph(keteki)

help
1

In the above question what this line means ?
Print the lexicographical-ly(alphabetically) smallest string possible if the names of the array A are appended one after the other, without spaces, such that they follow any path in the graph.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<string> v(n);
    for(int i =0; i < n; i++){
        cin >> v[i];
    }
    string answer = v[0];
    int grid[n][n];
    for(int i =0; i <n; i++){
        for(int j = 0; j < n; j++){
            cin >> grid[i][j];
        }
    }
    int curr = 0;
    while(true){
        int curr_before = curr;
        for(int i = 0; i < n; i++){
            if(grid[curr][i] == 1){
                answer += v[i];
                curr = i;
                break;
            }
        }
        if(curr == curr_before){
            break;
        }
    }
    cout<<answer<<"\n";
}

for the input :
5
abcdd abcdd kooa olop bbba
0 1 0 0 0
0 0 1 1 0
0 0 0 1 1
0 0 0 0 0
0 0 0 0 0

the above solution give : “abcddabcddkooaolop” but why it is valid as it consider path(0->1->2->3) but if i consider path 0>1->2->4 then resultant string will be “abcddabcddkooabbba” which is lexicographically smaller than other.
@chandubaba

1 Like
2

Plz help anyone :slight_smile: Either question is unclear or i read wrong :thinking:

3

The ans for first test case is wrong according to me. I also mentioned in the comments but no one replied.

1 Like
4

At contest time i was thinking considering all paths and check all string(by contactaenating those string which are present in path) and print smallest lexicographical but…unable to did…so hack 2 TC

5

Unrelated, but did they actually say a DAG is equivalent to a tree?

1 Like
6

and all solution (which are AC) have same type of thing means they consider 0->1->2->3 path even by using this path the resultant string is not lexicographical smaller.

7

I commented too but nobody answered! Codechef should have a “Clarification” button. In the first testcase abcddabcddbbba is smaller than abcddabcddkooabbba but for unexplicable reason the second is the smaller one according to some weird logic I just cannot get! I don’t think I am missing anything they must be wrong, and doing nothing to clarify that!

8

Yeah, wouldn’t the optimal answer be a path of length 1 anyway? Because appending characters to a string makes it lexicographically larger no matter what. The problem specifies any path.

3 Likes
9

Yes…But let’s consider the setter want longest path ok…even if it is wrong

10

What I did -> I started from 0 and out of all nodes connected to 0 (0 -> x), I chose the node which was alphabetically smallest and marked that node as visited and continued the process till I get a node from which I can’t go to any un-visited node which is basically a leaf (kind of dfs only).

11

LOL, you have to assume that? This is the worst statement ever

1 Like
12

I also thought the same thing and this is correct. The question was wrong…considering the test cases…I had to go for another approach.

13

At contest time , I consider setter want me largest path such that the string made by that path is lexicographical (alphabetically smaller)
see in first test case two longest path possible either 0->1->2->3 or 0->1->2->3 string made by first path is “abcddabcddkooabbba” while second path will made “abcddabcddkooaolop” so in sample TC it is correct but my question is what actually setter wanna say ?

14

In ongoing contest we have no other option as many user already said that no one reply :frowning_face:

15

@ssrivastava990
If setter wants the longest path, then what is the problem with the test cases…in that case they are correct.

16

In Question the test cases are correct but when i saw many solutions they just print that path which occur first no need to traverse any other path even some other path (longest too) give optimal result

17

Yes agreed that todays setting was all messy. l apologise. I have for first time tried to set difficult problems in keteki…

I resort to using more time to set problems so that logical and artistic mistakes are not made. I feel mathematically trying to prove solutions and then trying to programmatically prove it wrong should work. Also the problem should have solid theoritical background.

I also found that setting is not just solving… it is more testing and documenting. At testing and documenting internally it is about some form of memory usage. I need practice in that. I will use time and take help of tester next. Harsh raj helps me in testing. And possibly will be able to say if problem is clear enough.

Regarding the question yes i wanted the longest path but the smallest alphabetical string possible till a leaf is reached which i didnt mentioned.

18

That is just because the test cases were highly weak.

2 Likes
19

And yes that too. However regarding documenting the statement, i might still miss mentioning about the leaf node. Even though strong cases are set. It involves both more time usage, of self memory and a tester. Thank you.

2 Likes
20

@akshitm16 @galencolin so how can i find all longest path in given Adajcency matrix help me in this :slight_smile:

1 Like