This is a problem I was given back when I'm training for APIO Vietnam team selection.
"There are n (n ≤ 600) factory that is planned to be built on a line, number from 1 to n. There are m (m ≤ 100000) restriction, each restriction has form uv, meaning that if both factory u and v is built, xu + 1 = xv. There are another p (p ≤ 100000) restriction, each restriction has form uv, meaning that if both factory u and v is built, xu ≤ xv. (xi mean coordinate of factory i, if it's going to be built)
Your task is to pick an appropriate coordinate for each factory, such that no restriction is violated, and the number of different coordinate is maximum. (If there's no way to do this, print "-1")
I didn't understand the solution to this problem well back then. And now I'm trying to solve this again, but I can't think of any good idea. Can anyone give me a hint? Thanks in advance.
UDP1: Sorry about the mistaken objective. The correct objective is "the number of distinct point", not "factory". UDP2: The problem I'm asking is the same with this POI problem (Thanks Swistakk for informing me this). I've updated the statement summary in the blog.
