10507  Waking up brain
Moderator: Board moderators
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
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

 Learning poster
 Posts: 54
 Joined: Sun May 18, 2003 1:19 am
 Location: Rio de Janeiro, Brazil
 Contact:
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 ?
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
Mauricio Oliveira Carneiro
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
OUTPUT
Good luck to everyone!
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!
Re: 10507  Waking up brain
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.
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.
Re: 10507  Waking up brain
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 dataset.
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"
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 dataset.
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"
Re: 10507  Waking up brain
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?
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?

 Experienced poster
 Posts: 122
 Joined: Tue Apr 16, 2002 10:07 am
Re: 10507  Waking up brain
It is not correct as it has 9 different letters and N = 8.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?
Re: 10507  Waking up brain
Deleted after getting Accepted.
Re: 10507  Waking up brain
I am confused with the sample input given in the problem. Can you please explain me the input. What does 6 in the first line refers to? What are the slept areas initially? There are only 6 areas mentioned: A, B, C, D, F and H. What about remaining 5 areas.
Code: Select all
6
11
HAB
AB
AC
AH
BD
BC
BF
CD
CF
CH
DF
FH