10507 - Waking up brain

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

Moderator: Board moderators

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

Post by sergio » Mon Jun 23, 2003 1:39 am

This is my test case.

8
0
TYJ
10
20
ABC
AB
BC
CD
DE
EF
FG
IJ
FI
IC
DA
BJ
FJ
AC
DF
HI
HB
GA
GF
BG
CH
6
14
ABC
AB
AC
BC
AD
BD
CD
AE
BE
CE
DE
FB
FC
FD
FE
8
16
XYZ
ZA
AX
BY
BZ
CX
CY
DZ
YD
XE
ZE
XY
YZ
ZX
EF
CA
BD
7
12
JOM
PO
PJ
LM
PM
NO
NP
QP
QN
NM
QJ
LJ
LP
3
0
IUH
6
9
ABC
AD
BD
EC
ED
EA
FE
FA
FB
DC
6
9
ABC
AD
BD
CD
EC
ED
EA
FD
FC
FA

And my answer is:

THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 2, YEARS
THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 0, YEARS
WAKE UP IN, 3, YEARS
WAKE UP IN, 2, YEARS

S

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Mon Jun 23, 2003 6:01 am

And here is the correct output for your input :

THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 2, YEARS
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 3, YEARS
WAKE UP IN, 0, YEARS
WAKE UP IN, 3, YEARS
WAKE UP IN, 2, YEARS


Notice in the 6th line, we have different outputs !! Hope this helps. Which university are you from ?
[]s
Mauricio Oliveira Carneiro

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

Post by sergio » Mon Jun 23, 2003 1:25 pm

The 5th line is different, not the 6th :P

I study at Federal Universty of the Rio Grande do Norte

I was with a stupid error in the range of my loop, but now it's ok and e got accepted :)

Thank's a lot :)

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon May 16, 2005 4:57 pm

Here are several test cases ( to summarize the test
cases found here / in this thread / PLUS some more ).
The output is from an ACC program of course.

I hope they will be useful to someone.


INPUT

Code: Select all

6
11
HAB
AB
AC
AH
BD
BC
BF
CD
CF
CH
DF
FH

5 
0 
ABZ

5 
6 
ABC 
AD 
AE 
BD 
BE 
CD 
CE 

3 
0 
ABZ 

4 
0 
ATJ 

11
12
ABCD
AB
BC
CD
BE
AE
AF
AG
AH
AI
AJ
AK
KJ

8 
0 
TYJ 

10 
20 
ABC 
AB 
BC 
CD 
DE 
EF 
FG 
IJ 
FI 
IC 
DA 
BJ 
FJ 
AC 
DF 
HI 
HB 
GA 
GF 
BG 
CH 

6 
14 
ABC 
AB 
AC 
BC 
AD 
BD 
CD 
AE 
BE 
CE 
DE 
FB 
FC 
FD 
FE 

8 
16 
XYZ 
ZA 
AX 
BY 
BZ 
CX 
CY 
DZ 
YD 
XE 
ZE 
XY 
YZ 
ZX 
EF 
CA 
BD 

7 
12 
JOM 
PO 
PJ 
LM 
PM 
NO 
NP 
QP 
QN 
NM 
QJ 
LJ 
LP 

3 
0 
IUH 

6 
9 
ABC 
AD 
BD 
EC 
ED 
EA 
FE 
FA 
FB 
DC 

6 
9 
ABC 
AD 
BD 
CD 
EC 
ED 
EA 
FD 
FC 
FA

OUTPUT

Code: Select all

WAKE UP IN, 3, YEARS
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 1, YEARS
WAKE UP IN, 0, YEARS
THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 2, YEARS
THIS BRAIN NEVER WAKES UP
WAKE UP IN, 3, YEARS
WAKE UP IN, 0, YEARS
WAKE UP IN, 3, YEARS
WAKE UP IN, 2, YEARS

Good luck to everyone!

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 10507 - Waking up brain

Post by tryit1 » Wed Sep 03, 2008 12:00 pm

i solved this problem using simulated vertices and then if any group(graph) non simulated vertex is connected to group(graph) of simulated vertices then increment current years.
After sometime (years < 26) either all vertices are simulated or they are not , this is because the longest path in the graph is less than 26 (26 -3 or so )


how to solve this problem using union find . i don't get the idea quite.

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 10507 - Waking up brain

Post by vsha041 » Sat Feb 22, 2014 6:11 am

There are two tricky cases to consider:

1. Remember that all the specified areas of the brain should be awake. For example in the case below there are 5 areas. However after doing the analysis you will realize that 4 areas are awake - three already and then W. But that doesn't mean that the answer is one year. The answer here is "THE BRAIN NEVER WAKES UP" because the 5th area never wakes up. The fifth area alphabet is not even mentioned in the input data-set.

5
3
XYZ
WX
WY
WZ

Answer is "THE BRAIN NEVER WAKES UP"

2. Another case is to remember when all the areas of the brain are already awake. For example:

3
1
XYZ
XY

In this case the answer will be "WAKE UP IN, 0, YEARS"

rcanepa
New poster
Posts: 6
Joined: Thu Feb 26, 2015 4:59 pm

Re: 10507 - Waking up brain

Post by rcanepa » Fri Mar 13, 2015 8:47 pm

How can this input be correct?
8
16
XYZ
ZA
AX
BY
BZ
CX
CY
DZ
YD
XE
ZE
XY
YZ
ZX
EF
CA
BD

It says 8 slept parts but the connections (letter pairs) shows that there are 9 (9 different letters) parts. What should I do with this kind of inputs? Should I work with the first 8 letters and forget about awake the rest?

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Re: 10507 - Waking up brain

Post by Zyaad Jaunnoo » Sun Jul 17, 2016 6:54 am

rcanepa wrote:How can this input be correct?
8
16
XYZ
ZA
AX
BY
BZ
CX
CY
DZ
YD
XE
ZE
XY
YZ
ZX
EF
CA
BD

It says 8 slept parts but the connections (letter pairs) shows that there are 9 (9 different letters) parts. What should I do with this kind of inputs? Should I work with the first 8 letters and forget about awake the rest?
It is not correct as it has 9 different letters and N = 8.

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 10507 - Waking up brain

Post by lnr » Tue Oct 15, 2019 8:53 am

Deleted after getting Accepted.

Post Reply

Return to “Volume 105 (10500-10599)”