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

×

COEX04-Editorial

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

akashdeep_uiet's gravatar image

0★akashdeep_uiet
102
accept rate: 0%

edited 28 Mar '16, 17:08

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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