CareerCup

Well, it's ugly and brute-force, but:

using System;
using System.Collections.Generic;

namespace CityRoads
{
    public class City {
        public List<int> cityRoads = new List<int>();
        public int reached;
    }

    public class Road {
        public int mask;
        public int city1;
        public int city2;
        public int type;
        public int originalType;

        public Road(int i, int c1, int c2, int t){
            mask = 1 << (i - 1);
            city1 = c1;
            city2 = c2;
            type = t;
            originalType = t;
        }
    }

    class MainClass
    {
        static Dictionary<int, City> _city = new Dictionary<int, City>();
        static Dictionary<int, Road> _road = new Dictionary<int, Road>();

        public static void Main(string[] args)
        {
            // For the sake of brevity, just load the input values directly.
            _road.AddRoad(1, 2, 3, _city);
            _road.AddRoad(2, 3, 3, _city);
            _road.AddRoad(3, 4, 3, _city);
            _road.AddRoad(5, 3, 2, _city);
            _road.AddRoad(5, 4, 1, _city);
                           
            // Which roads can be removed?
            var allowedRemovals = _road.GetRemovalMask(_city);

            int max = 0;
            for (int remove = (int)Math.Pow(2, _road.Count) - 2; remove > 0; remove--)
            {
                if ((remove & allowedRemovals) == remove)
                {
                    foreach (City c in _city.Values)
                    {
                        c.reached = 0;
                    }

                    _city.Crawl(1, remove, 1, _road);
                    _city.Crawl(1, remove, 2, _road);

                    if (_city.AllReached())
                    {
                        //Console.WriteLine(
                        //    "Can remove {0}.", 
                        //    Convert.ToString(remove, 2)
                        //);
                        max = Math.Max(max, popCount(remove));
                    }
                    else
                    {
                        //Console.WriteLine(
                        //    "Can't remove {0}.", 
                        //    Convert.ToString(remove, 2)
                        //);
                    }
                }
                else
                {
                    //Console.WriteLine(
                    //    "Not allowed: {0}.", 
                    //    Convert.ToString(remove, 2)
                    //);
                }
            }

            Console.WriteLine("Can remove {0} roads.", max);
        }

        private static int popCount(int i)
        {
            int count = 0;
            while (i > 0)
            {
                count += (i & 1);
                i >>= 1;
            }

            return count;
        }
    }

    public static class Extensions 
    {
        public static void AddRoad(this Dictionary<int, Road> road, int c1, int c2, int type, Dictionary<int, City> city)
        {
            // Use a one-based index so that we can "remove" roads with a bitmask.
            int i = road.Count + 1;
            road.Add(i, new Road(i, c1, c2, type));

            // add refs back to this road from the cities it connects
            if (!city.ContainsKey(c1))
            {
                city.Add(c1, new City());
            }
            city[c1].cityRoads.Add(i);

            if (!city.ContainsKey(c2))
            {
                city.Add(c2, new City());
            }
            city[c2].cityRoads.Add(i);
        }

        public static int GetRemovalMask(this Dictionary<int, Road> road, Dictionary<int, City> city)
        {
            int mask = 0;

            foreach(Road r in road.Values)
            {
                // A road is required if it is the only road
                // servicing either of the cities it services.
                if ((city[r.city1].cityRoads.Count > 1) &&
                    (city[r.city2].cityRoads.Count > 1))
                {
                    mask |= r.mask;
                }
            }

            return mask;
        }

        public static void Crawl(this Dictionary<int, City> city, int cityIndex, int remove, int type, Dictionary<int, Road> road)
        {
            if ((city[cityIndex].reached & type) == type)
            {
                return;
            }

            city[cityIndex].reached |= type;

            foreach (int roadIndex in city[cityIndex].cityRoads)
            {
                var r = road[roadIndex];
                if (((r.type & type) == type) && ((r.mask & remove) == 0))
                {
                    city.Crawl(r.city1, remove, type, road);
                    city.Crawl(r.city2, remove, type, road);
                }
            }
        }

        public static bool AllReached(this Dictionary<int, City> city)
        {
            bool rv = true;

            foreach(KeyValuePair<int,City> kvp in city)
            {
                rv &= (kvp.Value.reached == 3);
                if (kvp.Value.reached != 3)
                {
                    //Console.WriteLine("\tCan't reach city {0}", kvp.Key);
                }
            }

            return rv;
        }
    }
}

Can you please tell the logic ? I think you are checking by removing each road.
I use the idea of kruskal minimum spanning tree. First I tried to build roads with type 3 as both can access. If a road form a cycle,then that can be taken as extra road which can be remove. Similary for men tried to build road with type 3 & type 1 , for women type 3 & type 2. While building for men & women the type 3 road would have been already built.

Can you explain the example? I have trouble understanding why the output would be 2.

- If you remove the 1-2 road, then no one can go from 1 to 2.
- If you remove the 2-3 road, then no one can go from 2 to 3.
- If you remove the 3-4 road, then neither women nor men can go from 3 to 4 or vice versa.
- If you remove the 5-3 road, then women can't go from 5 to 3.
- If you remove the 5-4 road, then men can't go from 5 to 4.

Unless you're allowed to change the type of roads, no road can be removed without blocking traffic.

If this problem didn't have the sexual discrimination part, I think you could solve it using a disjoint-set. For all cities to be connected, they should all exist in one set, AKA have the same 'parent' city. Therefore, for each edge (x,y), If both x and y already share a parent (in other words, if find(x)==find(y)), then the road provides a redundant connection. If they aren't connected, do union(u, v) and increase count of roads.

I'm not totally sure about this, but I think to solve the sexism part you could keep two sets. One set for male connectivity and one set for female connectivity. For two cities (x, y) to be connected, they need to satisfy find(x, y) for both male and female sets. Like before, you throw away a road if both x, y are already connected, and do union on sets that need connecting (for type 3 do both sets).


There is an additional stipulation that if your new road is type three and the previous connection was made using two roads, you can replace the two sexist roads with a type 3 road (resulting in a count--). But how do you know if the old connection was made using sexist roads? You could keep a data structure to keep track, but I think an easier way of doing it is to sort the input to handle all the type 3 roads first, then do type 1/2 roads.


At first glance I think this would work but I wouldn't be surprised if there was a problem.