## 1229 - Sub-dictionary

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

Moderator: Board moderators

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### 1229 - Sub-dictionary

first i did top sort using dfs
then find the scc
then again did dfs in the top list order and calculate them .

i dont know what is wrong
is it the wrong algorithm or system i applied ???

Last edited by @li_kuet on Tue Jun 05, 2012 12:25 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1229 - Sub-dictionary (Why WA)

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### Re: 1229 - Sub-dictionary (Why WA)

How can i solve this problem ??? @brianfry713

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1229 - Sub-dictionary (Why WA)

DFS
Check input and AC output for thousands of problems on uDebug!

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 1229 - Sub-dictionary (Why WA)

I'm getting wrong answer, what is the output for the test case? The problem is ambigous...it doesn't clearly state what should be the output when multiple solutions exists.

Code: Select all

``````9
d e
e f
f d
a b
b c
c a
g h
h i
i g
0``````
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1229 - Sub-dictionary (Why WA)

AC output for your input:

Code: Select all

``````9
a b c d e f g h i``````
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 1229 - Sub-dictionary (Why WA)

what should be the output for input...
5
a s d f
b d f r
c q w e
f s
g h
0
My code gives...
3
d f s
It's wrong...isn't it ??
I am trying using topological sort ... Can't it be done using topological sort ???

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1229 - Sub-dictionary (Why WA)

Your input isn't valid.
A dictionary must contain the definition for any word that appears in the explanation of another word.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 1229 - Sub-dictionary (Why WA)

Checking...
Last edited by Mukit Chowdhury on Sun Feb 03, 2013 3:27 pm, edited 1 time in total.

Ronok1307
New poster
Posts: 8
Joined: Tue May 29, 2012 7:37 pm

### Re: 1229 - Sub-dictionary (Why WA)

WA.
My algo -
1.use tarjan to find the scc dag
2. build dag graph
3. visit the nodes in the dag in topological order and visit the connected nodes
4. all the nodes in the dag, that act as a starting point for the dfs() call are the answers.
5. list all the nodes of the answers, sort them and show output

is the algo wrong?

Code: Select all

``````#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <sstream>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

struct node
{
int id,low;
bool operator <(const node &a)const
{
return a.low>low;
}
}asd;

priority_queue <node> pq;
char ss[100];
string s,p,arr[105];
map <string,int> mp;
bool v[105],vv[105],vvv[105];
vector <int> dag[105];
vector <string> ans;
stack <int> x;

void clear()
{
while(!pq.empty())
pq.pop();
mp.clear();
memset(v,0,sizeof(v));
memset(vv,0,sizeof(vv));
memset(vvv,0,sizeof(vvv));
for(int i=0;i<dagl;i++)
dag[i].clear();
ans.clear();
while(!x.empty())
x.pop();
}

void rec(int n)
{
pre[n]=post[n]=ll++;
v[n]=vv[n]=1;
x.push(n);
int a,i;
for(i=0;i<l;i++)
{
{
if(!v[i])
rec(i);
if(vv[i])
post[n]=post[n]<post[i]?post[n]:post[i];
}
}
if(pre[n]==post[n])
{
while(1)
{
a=x.top();
x.pop();
vv[a]=0;
dag[dagl].push_back(a);
whichdag[a]=dagl;
if(a==n)
break;
}
dagl++;
}
}

void dfs(int n,int s)
{
dagpre[n]=lll++;
v[n]=1;
int i;
for(i=0;i<dagl;i++)
{
dfs(i,s);
}
dagpost[n]=lll++;
if(s)
{
asd.id=n;
asd.low=dagpost[n];
pq.push(asd);
}
}

int main()
{
//freopen("in.txt","r",stdin);
int a,b,c,i,j,k,n,t;
while(1)
{
sscanf(gets(ss),"%d",&n);
if(!n)
break;
l=0;
while(n--)
{
getline(cin,s);
stringstream line(s);
line>>p;
if(mp.find(p)==mp.end())
{
mp[p]=l;
b=l;
arr[l]=p;
l++;
}
else
b=mp[p];
while(line>>p)
{
if(mp.find(p)==mp.end())
{
mp[p]=l;
a=l;
arr[l]=p;
l++;
}
else
a=mp[p];
}
}
dagl=ll=0;
for(i=0;i<l;i++)
{
if(!v[i])
rec(i);
}
memset(v,0,sizeof(v));
for(i=0;i<dagl;i++)
{
for(j=0;j<dag[i].size();j++)
{
a=dag[i][j];
for(k=0;k<l;k++)
{
}
}
}
lll=0;
for(i=0;i<dagl;i++)
{
if(!v[i])
dfs(i,1);
}
memset(v,0,sizeof(v));
while(!pq.empty())
{
asd=pq.top();
pq.pop();
a=asd.id;
if(!v[a])
{	dfs(a,0);
for(i=0;i<dag[a].size();i++)
ans.push_back(arr[dag[a][i]]);
}
}
sort(ans.begin(),ans.end());
printf("%d\n",ans.size());
for(i=0;i<ans.size();i++)
{
if(i)
printf(" ");
cout<<ans[i];
}
printf("\n");
clear();
}
return 0;
}``````

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 1229 - Sub-dictionary (Why WA)

There is one space character(' ') at the last of each input line in the sample input.
Should we consider this for every input?

Can anyone clarify this issue?

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

### Re: 1229 - Sub-dictionary (Why WA)

What is the output for this:

Code: Select all

``````7
a b f
b a
f e
e f
g a f
d e
c f``````
My out put is

Code: Select all

``4 a b e f``
So, my algo is to obtain the DAG and report all the SCCs with cardinality >= 2 or with indegree 0. Still WA.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1229 - Sub-dictionary (Why WA)

For input:

Code: Select all

``````7
a b f
b a
f e
e f
g a f
d e
c f
0``````
AC output:

Code: Select all

``````4
a b e f``````
Check input and AC output for thousands of problems on uDebug!

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

### Re: 1229 - Sub-dictionary (Why WA)

Ah, what about these random-generated ones:

Code: Select all

``````13
yzkg vcjqig
wsd w lzjshhp omol
w wsd urhfyb atde lzjshhp unqqc urhfyb
urhfyb wsd vcjqig nupe nupe
lzjshhp wsd gkh ygjd wsd ygjd
atde qyy vcjqig omol urhfyb ygjd
nupe wsd atde
vcjqig unqqc unqqc qyy wsd urhfyb yzkg
ygjd lzjshhp omol atde lzjshhp wsd nupe
qyy wsd omol atde w
gkh nupe unqqc urhfyb vcjqig lzjshhp atde
unqqc ygjd lzjshhp
omol vcjqig
11
euzrg ilnt q lfmlpj
vcs lfmlpj
aielg xacto t
q vzkpwai ilnt
vzkpwai ldgny
xacto vzkpwai
zxfh q euzrg t
ilnt xacto
lfmlpj q vzkpwai
ldgny zxfh lfmlpj aielg
t euzrg xacto euzrg zxfh
6
gaxw cm kx ovxnwit
ovxnwit gaxw gaxw
zfpvtiy gaxw bch
cm kx zfpvtiy zfpvtiy
bch gaxw gaxw
kx ovxnwit bch gaxw
3
h vl
vl jdqig
jdqig vl
5
apa tvrrct
fir lyaj eaxpf
tvrrct apa eaxpf
lyaj tvrrct
eaxpf apa
16
zerjobh inwppwu njbc
xamjdn idzmr sxdc xxh
njbc pe xxh pe
idzmr hb ya zerjobh xamjdn ij xxh sobk g
kwoewkd hb gpp
sxdc g pe inwppwu njbc xxh
gpp inwppwu
ya xamjdn zerjobh ij idzmr inwppwu gpp gpp
pe g sobk kwoewkd ya idzmr xamjdn sobk g
hb xamjdn g kwoewkd sxdc xamjdn
inwppwu gpp kwoewkd pe idzmr ij xamjdn g
z sxdc sxdc g ij xamjdn
sobk zerjobh inwppwu ij zerjobh idzmr
g njbc kwoewkd ya njbc ya sobk sxdc inwppwu
xxh kwoewkd gpp g z gpp
ij xamjdn gpp inwppwu inwppwu inwppwu
21
ydenvz q dwvfcfk q ajisxdk gpi dwvfcfk gecbyf zrml
zrml ggvz khdjq n
ajisxdk zrml ufwczaf n ukdrcnj dwvfcfk mwe ufwczaf rlgmvfx sayif
ukdrcnj g
ggvz mbapnqs gpi mwe rlgmvfx
p n ajisxdk khdjq snv mwe zrml mbapnqs
khdjq sqrkihw snv sayif gpi ajisxdk q mwe gecbyf dwvfcfk
gpi mbapnqs dwvfcfk b dwvfcfk rlgmvfx
b rlgmvfx g rlgmvfx ydenvz sqrkihw
gecbyf n p g ufwczaf ggvz sqrkihw ydenvz snv ajisxdk
sayif ajisxdk gpi gecb[code]``````
yf n gpi mwe ufwczaf rlgmvfx ydenvz mwe
q snv khdjq ukdrcnj b ydenvz g
mwe dwvfcfk dwvfcfk sayif ggvz ufwczaf gpi
mbapnqs ydenvz
dwvfcfk rlgmvfx n zrml rlgmvfx
g gpi
rlgmvfx g p sayif ydenvz g zrml
ufwczaf sqrkihw sayif p gpi mbapnqs p
sqrkihw gpi b sayif gpi n mwe ajisxdk mbapnqs
snv n g ggvz mbapnqs rlgmvfx sayif zrml q
n snv p sayif mbapnqs ukdrcnj sayif ufwczaf sayif sayif mwe
0[/code]

My output is:

Code: Select all

``````13
atde gkh lzjshhp nupe omol qyy unqqc urhfyb vcjqig w wsd ygjd yzkg
10
aielg euzrg ilnt ldgny lfmlpj q t vzkpwai xacto zxfh
6
bch cm gaxw kx ovxnwit zfpvtiy
2
jdqig vl
3
apa eaxpf tvrrct
16
g gpp hb idzmr ij inwppwu kwoewkd njbc pe sobk sxdc xamjdn xxh ya z zerjobh
21
ajisxdk b dwvfcfk g gecbyf ggvz gpi khdjq mbapnqs mwe n p q rlgmvfx sayif snv sqrkihw ufwczaf ukdrcnj ydenvz zrml
``````
Thanks.

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

### Re: 1229 - Sub-dictionary (Why WA)

...and also this huge one:

Code: Select all

``````100
ubghztqgvtenc prxdpnwyaamtb
btxbiiajcsjlp goqotulirejot lteqzvhspkijh
oactcxkkhzknr mlfjeeclhjghq
qmgveexsmxljo cqdlmpkzqopcg bgpckbjshokeg fwsugvvnmizit pzltzvinsbvsf
cxbtstcuiqvqo nyhfqbpvuwmwj vdmulrwscqhau acdvznnlaynbz tcgdnnvqgkfgh
pchvcgicjqibi hznfhjrruazow albgzwdhytdqq
zqtrwwrhxtend vdmulrwscqhau qmgveexsmxljo pznqhvyssmriv uxbymubhllxgg
pgymtffwmzodc pznqhvyssmriv cxbtstcuiqvqo xqnxcbvccjeeo
qeyjqryrpjydh xwcjtptzjmvcl
zbegdwrgnswqj zapaymhftdwkc qfpcuypankzbv debxlysqpelsl
wguoztswjobgy qeyjqryrpjydh
tiafbvyamsrlx tcgdnnvqgkfgh gqlvyuyutqlto albgzwdhytdqq
ajfbmitlingmm umheuosxrdkdt pznqhvyssmriv azmquwwimmezt wguoztswjobgy
lgxcwllcjmsmz albgzwdhytdqq nyhfqbpvuwmwj
mlbeuthxurwlg asbockbpozgch lhelcmixssdfi
nbydwtaqkojua kwxxnzbauaqqp
crnjyyqytmqwa inwuuzfdizily benbwvwklbewe
gqlvyuyutqlto rzofjdouzegmo xqnxcbvccjeeo
qcvatiubegura thgqrjqshfgoj xwcjtptzjmvcl xuxnukzvmtfkv
txfvscvgmhppl gppqlxapdekkr
kwxxnzbauaqqp ebyrzvogiuguw
ulgomyurpfpqe ecopphcjubpxu crnjyyqytmqwa thgqrjqshfgoj ebyrzvogiuguw
mlfjeeclhjghq ogtizuwzpfapd uxbymubhllxgg nizrljlengcvs ybadtcarvceaa
pkjjuhofzkmcg ubghztqgvtenc eiyxcaopyzllp
tflrnitabzfnz cbilbbdzadhaa zbooocfpqdckx orvovgypyhuyu
vhagonhgehbph ogtizuwzpfapd
uwvcsxqdboyuh lgxcwllcjmsmz cxbtstcuiqvqo pgymtffwmzodc
iixkovsruazed qeyjqryrpjydh
umheuosxrdkdt inwuuzfdizily aasfivpcwyipd mlfjeeclhjghq inwuuzfdizily
ztnuechsheqku yjnfphzsowtht pgymtffwmzodc
nyifpkxldrurc gppqlxapdekkr vtazguibbzhvb ogtizuwzpfapd uxbymubhllxgg
edbexrfgreelz sauwuiraoffhw entehhsqmaxpb bgpckbjshokeg uwvcsxqdboyuh
xuxnukzvmtfkv uwvcsxqdboyuh cbilbbdzadhaa nvnaiyfujtdeu
vdmulrwscqhau tcgdnnvqgkfgh mlfjeeclhjghq
imjnevtmmbkgj mlfjeeclhjghq btxbiiajcsjlp ajfbmitlingmm
fwsugvvnmizit goqotulirejot uwvcsxqdboyuh ecopphcjubpxu hznfhjrruazow
ecopphcjubpxu edbexrfgreelz mlbeuthxurwlg
cbilbbdzadhaa lgxcwllcjmsmz ogtizuwzpfapd tflrnitabzfnz nvnaiyfujtdeu
nyhfqbpvuwmwj nyifpkxldrurc goqotulirejot cbilbbdzadhaa benbwvwklbewe
benbwvwklbewe nbydwtaqkojua rzofjdouzegmo mlfjeeclhjghq
nvnaiyfujtdeu mlbeuthxurwlg xwcjtptzjmvcl oactcxkkhzknr
vlulvfhpmgptc thgqrjqshfgoj goqotulirejot iixkovsruazed
debxlysqpelsl vlulvfhpmgptc rzofjdouzegmo zapaymhftdwkc
ogtizuwzpfapd vdmulrwscqhau pgymtffwmzodc
gncrfpuzojnww ecopphcjubpxu xqnxcbvccjeeo
ocdgcshulfxln edbexrfgreelz vtazguibbzhvb vlulvfhpmgptc
ebyrzvogiuguw vdmulrwscqhau
eiyxcaopyzllp jukvzvgnmtuml wguoztswjobgy bgpckbjshokeg
xqnxcbvccjeeo nyifpkxldrurc
azmquwwimmezt pgymtffwmzodc pchvcgicjqibi
zapaymhftdwkc debxlysqpelsl
inwuuzfdizily uxbymubhllxgg cbilbbdzadhaa vlulvfhpmgptc
rdxlergeasqdq btxbiiajcsjlp nyifpkxldrurc
gppqlxapdekkr nizrljlengcvs qmgveexsmxljo tflrnitabzfnz
xcpgrqjklazbj cbjomnzyhzvgc
pzltzvinsbvsf vdmulrwscqhau prxdpnwyaamtb vhagonhgehbph prmawlqznszgn
tcgdnnvqgkfgh prmawlqznszgn
bgpckbjshokeg ubghztqgvtenc thgqrjqshfgoj
acdvznnlaynbz nyhfqbpvuwmwj
oewnxntfmkuto cbjomnzyhzvgc nizrljlengcvs
pfeziugdkrpaj qmgveexsmxljo qmgveexsmxljo xqnxcbvccjeeo
goqotulirejot albgzwdhytdqq ubghztqgvtenc btxbiiajcsjlp
prmawlqznszgn mlbeuthxurwlg
jukvzvgnmtuml thgqrjqshfgoj pznqhvyssmriv
kvdwmyjceqjen vhagonhgehbph
pgsmruldpissz lhelcmixssdfi rdxlergeasqdq mlbeuthxurwlg
zmhxajwjeoavn qqxizcqsqcadw umheuosxrdkdt ubghztqgvtenc imjnevtmmbkgj
pznqhvyssmriv kdbuetpgiadrj inwuuzfdizily kleqqltrhhmib
entehhsqmaxpb iixkovsruazed
rzofjdouzegmo zbooocfpqdckx
lteqzvhspkijh pzltzvinsbvsf kwxxnzbauaqqp pchvcgicjqibi acdvznnlaynbz
orvovgypyhuyu rdxlergeasqdq qqxizcqsqcadw ubghztqgvtenc vhagonhgehbph
prxdpnwyaamtb aasfivpcwyipd
asbockbpozgch goqotulirejot edbexrfgreelz cqdlmpkzqopcg
zbooocfpqdckx debxlysqpelsl
aasfivpcwyipd uwvcsxqdboyuh ubghztqgvtenc qcvatiubegura kleqqltrhhmib
uxbymubhllxgg iqapxifxgtxgc
yjnfphzsowtht aosaqoktravpb vtazguibbzhvb xhfnttjdlamxb
aosaqoktravpb tcgdnnvqgkfgh zqtrwwrhxtend pznqhvyssmriv
tstujakgxsimh debxlysqpelsl ogtizuwzpfapd xuxnukzvmtfkv
cqdlmpkzqopcg benbwvwklbewe mlbeuthxurwlg lteqzvhspkijh orvovgypyhuyu
cbjomnzyhzvgc lteqzvhspkijh uwvcsxqdboyuh cqdlmpkzqopcg
dzazbgmmpfvlg gppqlxapdekkr qeyjqryrpjydh rdxlergeasqdq hznfhjrruazow
qfpcuypankzbv nyifpkxldrurc tiafbvyamsrlx
kleqqltrhhmib ulgomyurpfpqe oewnxntfmkuto
nizrljlengcvs imjnevtmmbkgj ajfbmitlingmm pznqhvyssmriv nbydwtaqkojua
zjeudvttofebs qeyjqryrpjydh qeyjqryrpjydh ebyrzvogiuguw
qqxizcqsqcadw eiyxcaopyzllp zmhxajwjeoavn pznqhvyssmriv
xhfnttjdlamxb qcvatiubegura
hznfhjrruazow zbooocfpqdckx aasfivpcwyipd
lhelcmixssdfi oewnxntfmkuto oactcxkkhzknr
sauwuiraoffhw gppqlxapdekkr lteqzvhspkijh azmquwwimmezt kleqqltrhhmib
xwcjtptzjmvcl pchvcgicjqibi oewnxntfmkuto
vtazguibbzhvb vdmulrwscqhau prxdpnwyaamtb
thgqrjqshfgoj gqlvyuyutqlto
iqapxifxgtxgc asbockbpozgch
albgzwdhytdqq bgpckbjshokeg xcpgrqjklazbj qmgveexsmxljo nbydwtaqkojua
0``````
[/size]

My output is

Code: Select all

``````82
aasfivpcwyipd acdvznnlaynbz ajfbmitlingmm albgzwdhytdqq asbockbpozgch azmquwwimmezt benbwvwklbewe bgpckbjshokeg btxbiiajcsjlp cbilbbdzadhaa cbjomnzyhzvgc cqdlmpkzqopcg crnjyyqytmqwa cxbtstcuiqvqo debxlysqpelsl ebyrzvogiuguw ecopphcjubpxu edbexrfgreelz eiyxcaopyzllp entehhsqmaxpb fwsugvvnmizit goqotulirejot gppqlxapdekkr gqlvyuyutqlto hznfhjrruazow iixkovsruazed imjnevtmmbkgj inwuuzfdizily iqapxifxgtxgc jukvzvgnmtuml kdbuetpgiadrj kleqqltrhhmib kwxxnzbauaqqp lgxcwllcjmsmz lhelcmixssdfi lteqzvhspkijh mlbeuthxurwlg mlfjeeclhjghq nbydwtaqkojua nizrljlengcvs nvnaiyfujtdeu nyhfqbpvuwmwj nyifpkxldrurc oactcxkkhzknr oewnxntfmkuto ogtizuwzpfapd orvovgypyhuyu pchvcgicjqibi pgymtffwmzodc prmawlqznszgn prxdpnwyaamtb pzltzvinsbvsf pznqhvyssmriv qcvatiubegura qeyjqryrpjydh qmgveexsmxljo qqxizcqsqcadw rdxlergeasqdq rzofjdouzegmo sauwuiraoffhw tcgdnnvqgkfgh tflrnitabzfnz thgqrjqshfgoj txfvscvgmhppl ubghztqgvtenc ulgomyurpfpqe umheuosxrdkdt uwvcsxqdboyuh uxbymubhllxgg vdmulrwscqhau vhagonhgehbph vlulvfhpmgptc vtazguibbzhvb wguoztswjobgy xcpgrqjklazbj xqnxcbvccjeeo xuxnukzvmtfkv xwcjtptzjmvcl ybadtcarvceaa zapaymhftdwkc zbooocfpqdckx zmhxajwjeoavn
``````
[/size]

And also, can there be input like this:

Code: Select all

``````2
a
b``````
In this case, do we report zero or one?

EDIT: No, there are no words with empty definition, checked it with assert().