You are not logged in. Please login at www.codechef.com to post your questions!

×

# COEX04-Editorial

 0 PROBLEM LINKS: Practice:https://www.codechef.com/COEX1601/problems/COEX04 Contest:https://www.codechef.com/problems/COEX04 DIFFICULTY: MEDIUM PREREQUISITES: Strings PROBLEM: Given a number of words, check if it is possible to arrange them in an order such that the last alphabet of the word is the first alphabet of the word that follows it. EXPLANATION: Step 1: Store all the starting and ending alphabets of the given ‘n’ words in two character arrays, say start and end respectively. Step 2: If the end alphabet of the word is the first alphabet of the word that follows it, let’s call such a combination a link. Step 3: flag array is used to keep track of all used alphabets in start. Used alphabets are marked 1 and unused ones are marked zero. Step 4: Starting from the first index of end, all the indexes of start are searched for the matching alphabet. Step 5:If matching index is found, then we check that it does not belong to the same word, and also that it has not been used first by checking flag for it. If it has not been used first and does not belong to the same word,we use the start of this word and repeat the Step 4 after flagging this word and incrementing links by 1. Step 6: If matching index belongs to same word or has been flagged, we search the subsequent indexes for a match. If found, step 5 is followed. Step 7: If no matching index is found, we use the next end index and repeat step 4.  for(k=0 to k=n-1 increment by 1) { i=start.find(end[index]); if(i!=index && flag[i]!=0) { flag[i]=0; index=i; links=links+1; } else if(i==index) { i=start.find(end[index],i+1); if(flag[i]!=0) { flag[i]=0; index=i; links=links+1; } else break; }  AUTHOR'S AND TESTER'S SOLUTIONS: Author's solution can be found here. Tester's solution can be found here. This question is marked "community wiki". asked 25 Mar '16, 17:24 10●2 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,871
×2,658
×355
×3

question asked: 25 Mar '16, 17:24

question was seen: 475 times

last updated: 28 Mar '16, 17:08