use a tree. For the first N lines, build a tree accordingly. For the
next M lines search the tree. If miss, bump up the counter and add
the node.
On Feb 17, 7:53 am, Akshata Sharma <akshatasharm...@gmail.com> wrote:
> On Unix computers, data is stored in directories. There is one root
> directory, and this might have several directories
> contained inside of it, each with di fferent names. These directories might
> have even more directories contained inside of them,
> and so on.
> A directory is uniquely identified by its name and its parent directory (the
> directory it is directly contained in). This is usually
> encoded in a path, which consists of several parts each preceded by a
> forward slash ('/'). The final part is the name of the
> directory, and everything else gives the path of its parent directory. For
> example, consider the path: /home/facebook/people
> This refers to the directory with name "people" in the directory described
> by "/home/facebook", which in turn refers to the
> directory with name "facebook" in the directory described by the path
> "/home". In this path, there is only one part, which means it
> refers to the directory with the name "home" in the root directory.
> To create a directory, you can use the mkdir command. You specify a path,
> and then mkdir wi ll create the directory described by
> that path, but only if the parent directory al ready exists. For example, i
> f you wanted to create the "/home/facebook/people" and
> "/home/facebook/tech" directories from scratch, you would need four
> commands:
> mkdir /home
> mkdir /home/facebook
> mkdir /home/facebook/people
> mkdir /home/facebook/tech
> Given the full set of directories already existing on your computer, and a
> set of new directories you want to create if they do not
> already exist, how many mkdir commands do you need to use?
>
> Input The first line of the input gives the number of test cases, T. T test
> cases follow. Each case begins with a line containing two
> integers N and M, separated by a space.
>
> The next N lines each give the path of one directory that already exists on
> your computer. This list will include every directory
> already on your computer other than the root directory. (The root directory
> is on every computer, so there is no need to l ist it
> explicitly.)
>
> The next M lines each give the path of one directory that you want to
> create.
> Each of the paths in the input is formatted as in the problem statement
> above. Speci fically, a path consists of one or more lower -
> case alpha-numeric strings (i .e., strings containing only the symbols
> 'a'-'z' and '0'-'9'), each preceded by a single forward slash.
> These alpha-numeric strings are never empty.
>
> Output For each test case, output one l ine containing "Case #x: y", where x
> is the case number (starting from 1) and y is the
> number of mkdir you need.
>
> Note: If a directory is listed as being on your computer, then its parent
> directory will also be listed, unless the parent is the root
> directory.
>
> INPUT
>
> 2
>
> 1 2
> /chicken
> /chicken/egg
> /chicken
>
> 1 3
> /a
> /a/b
> /a/c
> /b/b
>
> OUTPUT
>
> Case #1: 1
> Case #2: 4
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
