10661 - The Perspectographer

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

Moderator: Board moderators

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

GBY wrote:Finding the number of the largest clique is indeed one way to solve the problem.In this problem you needn't find the largest clique of the whole graph but the one which contains current piece(that's enough).So using loops to count is enough.
I don't understand this. By "number" of the largest clique, do you mean something else than size? In the first test case I posted, the largest clique has size 2, yet the output should be 3.

Shamim: greedy won't work; the problem is NP-complete.

GBY
New poster
Posts: 4
Joined: Wed Apr 07, 2004 6:34 am
Contact:

Post by GBY »

Per wrote:
GBY wrote:Finding the number of the largest clique is indeed one way to solve the problem.In this problem you needn't find the largest clique of the whole graph but the one which contains current piece(that's enough).So using loops to count is enough.
I don't understand this. By "number" of the largest clique, do you mean something else than size? In the first test case I posted, the largest clique has size 2, yet the output should be 3.
I mean finding how many independent largest cliques there are by saying "the number".
For example in your (Per's) first case one of the independent largest cliques are AC BD E
So the answer is 3.

dll
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 am

Post by dll »

I output the same as Per's output, but still get WA, anyone post some test cases for me ?
thanks.
Nothing is impossible

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng »

How does one do graph coloring quickly enough for this problem?

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

Post by shuniu »

I used backtracking for this problem.

First assume one color is enough,
then proceed to color each vertex with the color,
each time checking whether the coloring is valid.

If one color does not suffice, assume two colors.
color the first vertex with color 0.
color the second vertex with color 0,
if valid, try to color the third vertex...
color the second vertex with color 1,
if valid, try to color the third vertex...

If two colors not enough, try three colors...

You can limit the bracktracking by assuming color 0 is always first and color N never appears until color (N-1) is already used.

I guess you can also separate the graph into connected components, and then try to color each component separately.

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

Post by shuniu »

Here are some random generated test cases.

Input:

Code: Select all

20
18 143
N I
Q G
N B
J I
H C
B I
R Q
Q O
L I
Q M
D I
A H
Q H
K J
Q E
C N
A E
B L
J R
K O
L C
D Q
O E
K F
G R
L O
G P
I C
D M
J H
G M
J C
N Q
C R
H R
M F
Q P
O P
K Q
J B
I H
F I
L K
F B
F J
L H
O C
D L
E I
N O
F Q
G N
D P
N K
D F
O R
A P
P I
A R
G I
K R
J O
A M
G H
B P
B Q
P R
A Q
R E
D A
B E
M K
F O
M L
M H
J G
M N
K E
F N
P L
D R
D H
C G
A K
O A
F P
C Q
M C
O B
M B
J L
G L
B C
P E
Q J
Q I
P C
R N
J A
H N
K I
L N
C F
M O
P N
D O
R B
H E
G E
R M
F H
B G
P H
E L
C D
O I
E M
A L
J M
B K
O H
I M
E N
A N
M P
C K
L F
A B
F E
R F
G O
I R
D N
E J
D G
G A
N J
B D
P K
L R
K G
L Q
C E
3 1
A B
15 61
O A
G L
L I
M K
F E
N O
I K
I O
J N
H D
A I
J C
J E
L A
E O
G O
L E
L K
K F
G M
B L
O M
E D
J M
N L
J L
D O
B G
M I
D G
E B
I H
C N
G K
G I
F D
I C
J H
C H
B N
J I
D K
H O
M A
K H
L D
N G
B K
F L
L H
N M
H B
D M
G A
K N
A J
L C
C M
C B
B D
K A
3 2
A C
A B
16 112
P C
N J
B F
L J
D B
A K
G F
E H
O M
J P
E C
F C
D N
N H
J E
D I
J B
A H
E O
G L
K N
H G
P N
M G
O H
O I
N C
G B
D A
D E
N M
M D
B I
N F
G A
L B
D H
K B
A I
B O
K P
P B
J D
K F
A P
K I
P E
L H
I F
L K
C A
G P
D L
H J
M C
F L
G N
I H
C K
P D
D O
A L
K D
H M
J C
I G
J F
C I
L P
E N
P H
P I
O N
O L
F O
L C
M L
O G
G E
M B
H C
C G
K H
O P
O J
M A
E A
I J
E I
E K
D C
C B
A N
I L
F A
D F
D G
N L
M P
M E
I M
M K
K G
E B
E L
A B
N I
B N
A O
A J
M F
K J
15 44
M E
D G
I F
K O
K A
B L
F K
G F
C H
E F
I J
H B
A E
M D
E C
G L
F A
G A
O E
L M
M C
M A
K D
G K
I G
G O
O H
O F
D J
A B
B K
M H
F N
M N
K H
C J
D N
H A
I L
N L
E H
C L
I B
H G
12 21
H F
D E
J B
E B
F A
G H
C K
K B
C J
J F
A D
I G
L J
D L
I L
H L
L C
F B
C D
D B
G L
8 4
A E
F H
C E
C D
2 0
17 131
I M
H M
O L
P I
M K
E B
J I
G C
F O
G M
A O
F E
K Q
H O
J N
E G
E A
M A
H F
N A
D K
L Q
H P
F K
J L
J P
N P
F L
M N
F C
E H
L A
J A
B K
M L
P O
G P
F A
A H
J O
P Q
O I
D G
Q E
O M
F B
G K
N B
H Q
Q A
M E
N Q
B L
G Q
E O
F N
H J
Q J
D O
M P
K L
Q I
Q F
D J
O Q
B A
K A
F G
I C
D Q
O G
D N
D F
M B
J M
P D
I E
N L
D B
G N
A C
C L
I B
C N
G A
N E
B O
M F
J B
P K
A D
J K
H G
N K
H D
Q M
C E
H K
H I
J E
I F
K C
H N
I A
L G
I K
N O
O K
D I
L E
P C
C D
P B
G J
F P
M C
N I
C J
H C
L H
B C
H B
O C
Q C
B G
P E
I L
L P
D E
F J
L D
13 9
J M
J C
J A
L A
L M
B L
D B
D G
L G
11 40
A C
D C
J F
C K
B H
B F
B G
G E
F A
D H
D J
F C
A G
J A
G K
C B
D K
G D
G I
J K
H G
K H
J B
J H
H F
D F
F G
A B
I A
D E
I C
F E
F I
I K
C H
A H
J E
J G
E C
B E
6 10
B A
D C
A D
F B
B E
D F
E D
C F
A F
B C
1 0
6 10
A C
C B
E C
E F
F D
A F
A D
F C
C D
A E
5 8
E A
A D
B D
B A
C B
D E
B E
C D
18 21
A H
N R
H Q
J L
F B
P E
K E
M Q
G J
H G
M D
N A
F H
O K
N D
M A
B J
B K
Q N
G F
K A
13 21
I D
F E
H E
F B
K L
I M
K B
K M
E B
C G
I K
C A
J I
L G
A I
L D
C H
D B
J E
B M
A L
14 90
M L
F N
N E
K L
G H
N G
I K
I J
M K
L D
K F
D J
A G
L I
B J
B K
H C
B G
C K
I C
E J
A I
H D
H L
B L
M G
A J
E L
G J
F J
H N
J M
D A
C B
K G
M E
M C
B D
I E
F H
D E
H K
L F
H I
G D
A C
B E
C L
J H
L N
F B
H B
I B
I M
H M
D I
N B
L A
F D
J C
H A
M F
N C
E H
E A
G F
F C
B A
D M
I N
C G
L G
K A
N J
N K
J K
C D
K E
N A
D K
E C
F E
I F
M A
L J
G E
I G
B M
N D
A F
9 21
F G
E B
I E
F D
A G
A I
A B
C H
H E
B C
D I
H B
F B
B I
C G
E G
F H
B D
C F
G B
G D
Output:

Code: Select all

13
2
6
2
12
4
3
2
1
12
2
6
3
1
4
4
3
3
13
4

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng »

Thanks, I got AC now. I looked for the largest clique first and start searching from there.

Post Reply

Return to “Volume 106 (10600-10699)”