PETERSEN - Editorial

Difficulty: Simple

Pre-requisites: DFS, BFS, Graph traversal

Problem:

Given a graph G, its vertices have been numbered from 0 to 9. Some letters have also been assigned to vertices of G, as can be seen from the following picture:

Given a string S. Your task is to determine whether there is a walk W which realizes a given string S in graph G, and if so, find the lexicographically least such walk.

Explanation:

Let’s consider the picture from the statement carefully. The key observation is that there’s no vertex V in G such that it’s connected with two other vertices with the same letter written on them.

In other words, if we are looking for a way to continue the current walk from a vertex V and the next letter in S is C then two options are possible:

1. V is not connected with vertices labled with C, so it’s impossible to continue the current walk;
2. V is connected with exactly one vertex U labled with C, so there’s only one way to continue the current walk.

The next observation is that there are only two possible vertices to start our walk. After that observation we are ready to compose the whole solution:

1. Choosing the starting vertex of the walk;
2. Trying to complete the walk by moving to the corresponding vertices(if possible);
3. Finding the lexicographically least valid walk. It’s sufficient to compare paths only by their starting vertices.

There is an interesting fact that the only situation when there are two valid paths is when S consists of one symbol concatenated several times with itself. For example, there are two valid paths 3838 and 8383 for S = DDDD.

Complexity is O(N) per a testcase.

6 Likes

The solutions can’t be accessed.

Submitted over 10 times, tried covering all corner cases, still couldn’t resolve the NZEC error, any leads? Any test cases to fail the code?

http://ideone.com/0buFbJ
(I put the code in ideone after the contest, hence not violating any rules)

1 Like

My solution passed even though my code outputs “5050” for AAAA. Weak TCs?

4 Likes

@djvdm123 First of all please mark your solutions secret or private on ideone from next time to avoid plagiarism

Well secret doesn’t work (read the contest rules again) and if he made his solution private, he couldn’t link it here…

LOGIC

4 Likes

The ideone snippet was created after the contest ended, so it shouldn’t be a problem.

3 Likes

I have a dp solution which is not getting submitted (WA). I’ve input many test cases and it is working fine for all of them.

Approach:

Since we know the letters, we just need to know whether it is taken from the inner or the outer ring.

Let 1: outer ring, 2: inner ring

dp1[i] = 2 tells that we are now at outer ring(1) and previous node was in the inner ring(2). Similar is the case of dp2[i].

``````So considering consecutive letters
if they are same, we are switching levels
dp2[i] = 1;
dp1[i] = 2;

if the modular difference between the two node is 1
we have moved in the outer ring
dp1[i] = 1;

if it is 2
we have moved in the inner ring
dp2[i] = 2;

dpX values are set only if previous nodes are reachable ie dpX[i-1] != -1
Later, the path is calculated by tracing back from dp1[n] and dp2[n] considering the letter at each position.
``````

Order is checked only by the first node. Its giving correct answer for cases like “AAAA”(0505), “ABBECCD”(0169723), “D”(3), “AAB”(501), “AAAB”(0501).

What am I missing?

pastebin.com, really? Why?

I did not understand your approach with modular arithmetic thing, for example difference AA is 5, difference AD is 3…

``````2
AABD
AABE
``````

only

``````-1
``````

Hi during the testing I created list of basic test cases:

Solution is @Shashwat.delhi’s I just modified it such, that when line starts with ‘#’ I print this line and continue with next - it’s easier to navigate in test cases then…

I missed that “lexicographically least” part completely, but fortunately no problem…

Hi, I considered as two graphs one as outer and other as inner. There can by only one path after that we can determine after examining 1st three vertices in the string.Can someone please help me to find out where i am missing?

here is my solution link: http://www.codechef.com/viewsolution/5452717

I replaced the picture with the one from problem statement, it seems to me, that origin URL is not reachable… If it was different picture, please fix the link.

The NZEC might be due to stack overflow. Try a bottom-up approach without any recursion.

@nisargshah95:
I tried AAAA…(5000 times) to check for stack overflow on ideone, runs perfectly fine, guess that’s not it.

@kostya_by: any thoughts? Could you provide test cases used now that the contest is over?

I have checked for all corner cases…My solution passed all test cases generated by betlista… Could somebody help me where i am missing? Or provide the test cases used for evaluation?

Please tell where does my code fails…

I have tried all corner cases.

try:

``````1
CEA``````
//