tmwilliamlin168's blog

Problem from Taiwan Regional Contest
By tmwilliamlin168, history, 7 years ago, In English

I've been thinking for one month and I still don't know how to solve this problem:

There is a park of size (A<=100)x(B<=100) (consider it as a grid), with (1, 1) as the top-left corner. There are C<=1000 trees on the park, all of which have distinct locations. You want to place as many VIP lounges on the park as possible, such that every VIP lounge is adjacent to a tree on its top, bottom, left, or right. But because of privacy issues, a VIP lounge cannot be adjacent to another VIP lounge (including diagonally). Note that you cannot place a VIP lounge on a tree.

For example, consider the following park of size 9x7:

The "T"s represent the trees, the grey shaded areas represent possible locations for VIP lounges. If there were to be a VIP lounge on where the "V" is located, then the "x"s represent the locations where there cannot be VIP lounges.

Time limit: 1s

Samples

My thoughts:

Finding the maximum independent set of a bipartite graph can be done in polynomial time. Create a graph in which the possible VIP lounge placements are nodes and there are edges between 2 nodes if the 2 VIP lounges are adjacent. The maximum independent set of this graph is the answer. Notice that this graph is quadripartite (all combinations of x, y mod 2). Maybe there is also a way to find the maximum independent set of a quadripartite graph efficiently.

Or maybe I'm thinking too much and there is a greedy solution.

  • Vote: I like it
  • +45
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

I'm also curious about the official solution of this problem. I ever thought on this problem for a full night and didn't get any idea. But you should know... sometimes, the quality of problems in Taiwan is terrible. It may be an open problem.

→ Reply
»
7 years ago, # |
  Vote: I like it -7 Vote: I do not like it

In fact, it is a planar graph. Unfortunately, maximum independent set on planar graph is still NPC.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    First, showing the graph in a problem is planar and the fact that MIS on planar graph is NP-hard don't imply this problem is NP-hard. (As it may only encounters a certain kind of planar graphs, e.g. MIS on trees)

    Second, it's NOT planar graph.

    TTTTTT
XXXXXX
XTXXTX
XTXXTX
XXXXXX
TTTTTT

    All "X" should be a node, and it's not planar. (you can find K_5 as a minor)

    → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What is the time limit of this quesion? My team just practiced with the 2014 TaiChung problem set, and now my attitude is pretty much — "Does it has a 60s Time Limit? YEAH JUST GO AHEAD BRUTE FORCE TILL WE GET CHAMPION".

Or maybe it just have some really weak test cases — https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=5014

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for mentioning it, the TL is 1s.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    To clarify, the problem described in the post is actually from a programming contest for high school student in Taipei city in Taiwan not from ACM-ICPC Taiwan regional.

    Though some problems from Taiwan regional actually has weak test cases, I'm not sure whether that is a correct example. Some problems uploaded to ACM-ICPC Live Archive has only included sample tests(or some random permutation of it). But, those problems indeed have stronger tests during the official contest. For example, some problems from the daejeon regional in 2016 contains only sample tests.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tmwilliamlin168 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it -20 Vote: I do not like it

tmw orz

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

tmw orz

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

tmw orz

→ Reply
»
13 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve this?

→ Reply