12506 - Shortest Names

All about problems in Volume 125. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sdipu
New poster
Posts: 23
Joined: Sun May 19, 2013 1:50 am

Re: 12506 - Shortest Names

Post by sdipu » Tue Dec 30, 2014 5:13 pm

I am getting WA in this problem. I am debugging my code for hours, but can't find any mistake in my code. Please help.

My idea is as follows-
I used Trie Tree to store the names. Then I used DFS to find out the total length.

Suppose I am given following names-

Code: Select all

aac 
aad
ace
So my tree will look like this-

Code: Select all

          [:3] 
            |
         [a:3]
        /      \
     [a:2]    [c:1]
    /     \          \
  [c:1]  [d:1]    [e:1]

Here, every node follows this format [character : number of names it occurs]. 
Now I find nodes with number of names == 1. And add the distance of this node from root to the total length.
So total length will be = 3 + 3 + 2 = 8

Is my approach wrong or am I making any silly mistake here?
Check out UVA Arena - a software build for UVA solvers @ http://dipu-bd.github.io/UVA-Arena/

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 12506 - Shortest Names

Post by lighted » Tue Dec 30, 2014 5:33 pm

You can post your code
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sdipu
New poster
Posts: 23
Joined: Sun May 19, 2013 1:50 am

Re: 12506 - Shortest Names

Post by sdipu » Wed Dec 31, 2014 10:56 am

Here is my code

Code: Select all

code removed ;)
Last edited by sdipu on Sat Jan 03, 2015 11:06 pm, edited 1 time in total.
Check out UVA Arena - a software build for UVA solvers @ http://dipu-bd.github.io/UVA-Arena/

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 12506 - Shortest Names

Post by lighted » Wed Dec 31, 2014 12:39 pm

invalid input removed
Last edited by lighted on Fri Jan 02, 2015 6:23 pm, edited 1 time in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sdipu
New poster
Posts: 23
Joined: Sun May 19, 2013 1:50 am

Re: 12506 - Shortest Names

Post by sdipu » Thu Jan 01, 2015 2:59 am

Problem description says-
It is guaranteed that no name is a prefix of another name (as a result, no two names can be equal).
As "a" is a prefix of "aaaaa", doesn't that make above input-ouputs incorrect? Am I missing something?
Check out UVA Arena - a software build for UVA solvers @ http://dipu-bd.github.io/UVA-Arena/

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 12506 - Shortest Names

Post by lighted » Fri Jan 02, 2015 6:26 pm

Yes you are right, i deleted invalid input. I checked your code for many input and it passed them all.

I don't know why it gives WA when you submit it with C++ 4.8.2. But it gives accepted when you submit your code with C++11 4.8.2. :D
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sdipu
New poster
Posts: 23
Joined: Sun May 19, 2013 1:50 am

Re: 12506 - Shortest Names

Post by sdipu » Sat Jan 03, 2015 11:02 pm

Thanks a lot for your help lighted.

I worked with this problem for hours but found nothing and never thought about submitting it in C++ 11. Thanks again for your time.
Check out UVA Arena - a software build for UVA solvers @ http://dipu-bd.github.io/UVA-Arena/

Post Reply

Return to “Volume 125 (12500-12599)”