10661 - The Perspectographer

[pminkov]

Hi,

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

[Adrian Kuegel]

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]

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]

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]

Edit: Forget my old post

[rotoZOOM]

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]

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]

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

[rotoZOOM]

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]

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]

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

THanks, Per.
It is enough for me.
I understand my mistake. ))

[sumankar]

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

[Farid Ahmadov]

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.

[GBY]

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.

[shamim]

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]