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

pminkov
New poster
Posts: 8
Joined: Wed Oct 17, 2001 2:00 am
Location: Bulgaria, Sofia

10661 - The Perspectographer

Post by pminkov » Mon Jun 07, 2004 8:04 pm

Hi,

Isn't the solution here just to find the largest full subgraph?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Jun 07, 2004 8:16 pm

No, it is graph coloring.
The size of the largest full subgraph gives you just a lower limit on the number of colors needed.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Tue Jun 08, 2004 8:07 am

Adrian Kuegel wrote:No, it is graph coloring.
The size of the largest full subgraph gives you just a lower limit on the number of colors needed.
Well, isn't it goal of problem ?
Your task is to compute the smallest number of levels ...

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Tue Jun 08, 2004 9:07 am

I find chromatical graph number (minimum number of colors).
But my program got WA every-time.
Can some one give tricky Input/Output ?

Thanks in advance

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Jun 08, 2004 9:19 am

Edit: Forget my old post :oops:
Last edited by Adrian Kuegel on Tue Jun 08, 2004 10:06 am, edited 1 time in total.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Tue Jun 08, 2004 9:35 am

Adrian Kuegel wrote:You misunderstood the problem. You shouldn't find lower bound. Otherwise 0 would be also a solution for all test cases, or why not?
Assume graph with vertex as pieces and edge between vertex means
this two pieces overlapped.
Ok ?
So I need to find minumum number of colors to color graph in such a way
that two adjacent vertex haven't same color.
Right ?
The number of color is number of level (that is chromatical graph number)
So you should output a number of levels, with which it is possible to assign each adjacent pieces to different levels. And the minimum of these values is not chromatic number, it can be higher.
May be I something misunderstood.
Can you give the example where chromatical number isn't answer to problem ?

Thanks in advance

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

Post by Per » Tue Jun 08, 2004 9:44 am

You should find a lower bound, but you must find that very special lower bound which also happens to be an upper bound. :)

I think there's just some confusion in terminology here. The chromatic number of the graph is the minimum number of colors needed to color it, which at least is what my AC solution outputs.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Jun 08, 2004 10:04 am

Sorry, my mistake.
Of course chromatic number is the solution.
I meant, that size of largest clique is not solution.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Tue Jun 08, 2004 10:07 am

Adrian Kuegel wrote:Sorry, my mistake.
Of course chromatic number is the solution.
I meant, that size of largest clique is not solution.
Hmm, can you give some tricky i/o ?

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

Post by Per » Tue Jun 08, 2004 10:40 am

Not sure it's very tricky, but you could try:

Code: Select all

4
5 5
A B
B C
C D
D E
E A
5 0
5 1
D E
10 15
A B
B C
C D
D E
E A
A F
B G
C H
D I
E J
F H
H J
J G
G I
I F
Output:

Code: Select all

3
1
2
3

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Tue Jun 08, 2004 10:55 am

Per wrote:Not sure it's very tricky, but you could try:
THanks, Per.
It is enough for me.
I understand my mistake. :)))

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Het Got AC

Post by sumankar » Thu Jun 10, 2004 9:03 pm

Well thabks Farid and Per!
Farid for your response (BTW: my code wasn't wrong, the initialization routine was :-))
And Per for your i/o- that was GREAT!
Regards
Suman
Last edited by sumankar on Fri Jun 11, 2004 11:49 am, edited 1 time in total.

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Thu Jun 10, 2004 10:32 pm

I think your algo isn't correct enough. It finds only a correct coloring, but not the minimal coloring.
I know an algo where:
1. you find a correct coloring:
at each step you try to color a vertex with a minimal possible color.
if you don't find minimal possible then you increase color count.
2. try to change color at the vertex with maximal color
to do it first try to change colors (change by possible greater color value) of adjancent vertexes.
if you cannot do anything above then you've the minimal color count.

Thanks.
_____________
NO sigNature

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

Post by GBY » Fri Jun 11, 2004 10:42 am

I think some people who replyed misunderstood the initial poster's meaning.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.Hope it'll be helpful.
ps.The graph is defined as follows:If two peices are unnecessary overlapped there is an edge between them.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Jun 12, 2004 9:43 am

I am getting WA, I get Per's sample correct.

I used greedy, that is try to see in which level can i place A( starting from 1), and then for B and so on.


[cpp]
Wrong Algorithm
[/cpp]
Last edited by shamim on Sat Jun 12, 2004 2:22 pm, edited 1 time in total.

Post Reply

Return to “Volume 106 (10600-10699)”