DR. ECCO 2023

Login Register

Partitioned Peace

Deep Mehta and Yajur Ahuja - Team Omniheurist



In a peaceful city, there are 2 civilized communities, red and blue. People participate in all of the events held by their community and have a great time. They like their communities so much that they have painted their houses based on their community color. However awesome these communities may be, there is a long rivalry amongst them. The rivalry is so intense that if a person from the blue community is spotted anywhere near a red house, things get messy. In order to avoid a fight, the smart leaders of both the communities have decided to relocate the houses and change the existing layout of the roads such that everyone from a red house can visit all other red houses without going through a blue house; and similarly for blue. To successfully achieve this task within a specified budget, the leaders have hired you for the job.

  • Given a N x N grid of alternating colored houses, you have to come up with a minimum cost solution such that all red houses can reach other red houses without needing to cross a blue house and similarly for blue.
  • To achieve this, you have the following options:
    1. Build a new road between 2 houses (the road can be a bridge – i.e. it can go on top of other roads, but NOT intersect)
    2. Swap 2 houses
  • Your score (cost) is calculated by:
    • The cost of building a new road is the Manhattan distance between houses you want to connect by building the road
    • Each house swap costs s, which will be significantly higher than building a new road
    • The total cost is calculated as: Sum of all road costs + Number of swaps * cost of 1 swap
  • There is also a maximum limit to how many roads you can create


If you want to play, press popup