Problem statement: Given a complete bipartite graph K_N, N with weights W_uv assigned to each edge uv, find a perfect matching with minimal sum of edge weights among all perfect matchings.

Is there any easy to code polynomial algorithm for this problem? I know an easy way to solve it using subset dp in O(N²2^N), and i also think that it is possible to modify the Hungarian Algorithm to solve this problem. But is there any easier algorithm considering it is always a complete bipartite graph? I don't care too much about the time complexity as long as it is polynomial.

Thanks in advance!

Today the ACM ICPC 2016 Brazil Sub-Regionals contest was held, featuring 12 problems and having more than 600 teams trying to advance to the Latin America Regional Finals that will happen in November. I created this thread so we can talk about the problems in the contest. The problems can be viewed in this link (Portuguese): http://maratona.ime.usp.br/maratona.pdf

A — Simple ad-hoc

B — Dynamic programming on DAG, binary search, square root decomposition

C — Shortest Paths Modelling (i have a tutorial on this: http://codeforces.me/blog/entry/45897)

D — Simple maths

E — DP over subsets (bitmask dp)

F — Graphs

G — Range Sum Query 2D

H — Simple palindrome check

I — Greedy algorithm

J — Sweep line

K — DP, geometry

L — DFS to check connected components

My team solved 7 problems (A,C,D,G,H,I,L), we also tried to solve B and J but failed. Btw we have advanced to the regional finals! :D

Shortest path problems are really common. There are uncountable problems that can be reduced to some shortest path problem on graph. In this post i will show some different problems that require some extra thinking because they are not the usual shortest path problems (there are additional constraints to the problem). For most high rated coders this is still common stuff but i hope i can help some newcomers out there.

About Graph Modelling

Sometimes we face a problem that asks us to find some shortest path in a graph, but there are additional constraints to the problem. If we are not used to this kind of problem, we may come up with the idea of changing Dijkstra's algorithm so it will work in the specified problem. But usually this will not work. Instead, we must change our graph so that the traditional shortest path algorithm will solve the problem with added constraints. This is called graph modelling.

State Graphs

What we want to build is a state graph. In this graph, every vertex will store additional information, representing some state of the problem, and the edges represent transitions between states. We can see it like a finite state machine and we are going to compute the shortest path from the initial state to some final state. The construction of the state graph is usually the challenge in this kind of problem, and after the graph is built we will have a good time using Dijkstra's algorithm. Now we are going to see some examples of shortest path modelling problems and how to build the state graphs.

Problem 1

Statement: You want to travel from city A to city B. There are N cities and M bidirectional roads connecting cities. Your car can store up to C liters of fuel and the tank is initially full. each road (i, j) has a value W_ij that represents the amount of liters of fuel to cross this road. Also, in every city you can buy fuel, at a price of C_i dollars per liter. You must compute the minimum amount of dollars spent with fuel to travel from A to B.

Solution: The first thing we must do is to build the state graph. In this problem, a state represents a pair (city, currentFuel). So, we are going to have NC states. There are two kinds of edges in our state graph: at any moment we can charge a liter of fuel (unless the tank is full), so we can go from state (i, f) to state (i, f + 1) with cost C_i, or we can go to another city, so we can go from state (i, f) to state (j, f - W_ij) for every city j that is adjacent to city i. This second type of edge has cost 0, because remember that we want to compute the amount of dollars spent, not the amount of liters. Now that our graph is done, we can model our problem as finding the shortest path from vertex (A,C) to any vertex (B,*), which can be done with usual Dijkstra's algorithm.

The image below is an example of what is said above. It's a small test case just to show how the state graph is built. The graph on the left is the original graph, and the graph on the right is the state graph. The max fuel capacity C is 3. The gray edges represent recharging the fuel tank. Edge costs are omitted because the drawing is messed up enough (love paint!)

My code for reference: http://pastebin.com/Kv9XdAfq

Now if you look at the code, there is a catch. You don't need to explicitly build the state graph! You can build the adjacency list for the original graph, and model the state graph using the distance array computed in Dijkstra's algorithm. The idea is that you only need the transitions of the original graph in order to be able to traverse in the state graph, so you can build the original graph but instead of traversing the adjacency list in Dijkstra's you will traverse the state graph transitions. The time complexity will not change but we are going to save a lot of memory and the coding will also become easier. This trick will be used in all modelling problems.

Problem 2

This one appeared in a regional contest here in Brazil last year. Unfortunately my team wasn't able to solve it during the contest even though it was an easy problem, and this was my initial motivation to study about graph modelling.

Statement: You are given an usual undirected graph, and you want to find the shortest path from A to B, but there is an additional constraint: you must use an even amount of edges.

Solution: We are going to build the state graph for this problem. Now each state will represent a pair (vertex, parity), meaning we will have 2N states. The transitions are really simple: for every vertex v adjacent to vertex u, we can go from state (u, even) to state (v, odd) and from state (u, odd) to state (v, even). Now we can simply find the shortest path from state (A, even) (because we start with a path of length 0) to state (B, even), and once again this is done with usual Dijkstra's algorithm.

My code for reference: http://pastebin.com/gqNJk9yN

Another cool trick that you might not know: if you look at the code i don't do any fancy conditionals to go from an even state to an odd state. We can represent even as 0 and odd as 1, and if you XOR current state with 1, you get to the opposite state! Just look at the XOR truth table and you will see that and . This trick is really useful and is used in a lot of algorithms like binary heap and iterative segment tree.

Practice

UVA 10269 is another problem in which you have to compute shortest paths in some state graph : https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1210

UVA 11492 is a problem from a past ACM ICPC Latin America, a really beautiful problem on this topic : https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2487

If you know more problems on this topic i will be really grateful if you can post them here!

Short problem statement: Given T < 200 binary strings S (|S| ≤ 10⁵), find the size of the shortest pattern that doesn't match S for all input strings.

Examples :

S = 011101001, answer = 3 (doesnt match '000')

S = 11111, answer = 1 (doesnt match '0')

My current solution is building a suffix automaton for S and searching all patterns of size i (i=1, i=2, ...) while the number of matches of this size equals 2ⁱ. When i find some k such that matches(k) < 2^k, this is the answer. This is O(|S|) for building suffix automata plus for matchings, which i think is always small but still relevant.

This solution gets TLE. Can anyone help me with a faster solution for this problem? Thanks in advance.

EDIT 2: Solved the problem using the strategy below. I will leave the blog here any way because this problem looks interesting so i want to share the solution in case any one is interested :)

Run BFS in suffix automata starting from root node until we find some node that has less than 2 links. Let p be the length of the path from root to this node. This node represents some pattern of length p+1 that doesn't appear in the string S. So the answer is p+1.

Hello!

Today i coded a nondeterministic solution for Problem C (Fashion Police) and got AC verdict using it, which led me to qualify to Round 2. Since it is a very different "paradigm", i wanted to share my solution here so it can maybe be useful for someone in the future :)

My solution relies on a random outfit subset generator. Inicially we are going to set a precision r, the number of times our generator is going to run. I empirically chose to use 10000 random generations because that led my code to run in about ~2 minutes, enough to solve the downloaded input. In each step, it generates a random outfit subset in the following manner:

  solution = {}
  choose a value p, the probability that some outfit will be discarded (in my code i used p = 10%)
  for each possible outfit o:
    if you can include o in the solution without violating the Fashion Police rules:
      choose a random number n in the range [1,100]
      if n > p:
        include o in the solution

You can argue that this subset probably won't be maximal, but that's no problem! After we generate the random subset, we can simply iterate over all possible outfits and include every missing valid outfit until the solution is maximal! This will be efficient because there are only J*P*S (max 27) such outfits.

So we are going to generate r maximal random outfits. Now we just pick the biggest and hope that it will really be the optimal value! We can use this RNG-based solution and expect that it will produce the correct output because there are 2^27 possible subsets, but only 27 possible answers (remember that any answer with the correct value is optimal, so consider them to be the same). Since we are only generating maximal subsets, the chance that some iteration will hit the optimal value is huge.

My code : http://pastebin.com/nTxWKyJH

Hello!

I am solving a problem where a rooted tree with N vertices is given, each vertex has a value V <= 10^9, and i have to answer M queries. Each of the queries has the format (V,K), and i have to answer which is the K-th smallest value in the subtree rooted in vertex V. The limits for N,M are 10^5.

My current approach solves almost every instance of the problem (O(N log N) average) but fails when the tree degenerates to a linked list (O(N^2 log N) worst case). I store every query so i can answer all them after i run my algorithm. I process the tree from the leaves up to the root using topological sort, and when i am processing some vertex, i merge the leaves' subtrees values using heapsort (found it to be faster than mergesort, but still slow if the tree is a linked list), and answer every query related to this vertex. After every vertex has been processed, i iterate over the answer array and print the results.

Can anyone help me with a better approach, or point some property that can help my solution so it doesn't get TLE verdict?

Thanks in advance.

EDIT : problem solved, used the idea given by ffao.

Original statement : https://www.urionlinejudge.com.br/judge/en/problems/view/1695

My code : http://pastebin.com/ncWeC102

I am solving a problem where a set of N K-bit integers is given (N <= 10^4, K <= 50). I am allowed to do a single operation: choose two numbers A,B from the set and insert A xor B into the set.

The problem asks if it is possible, for the given set, to generate all numbers from 0 to 2^K - 1 using only this operation, as many times as i want.

I read that this can be solved using Gaussian Elimination, but i don't know how to do it. Can any one help me with this problem? Thx in advance :)

EDIT : I solved the problem. Thanks to Enchom for the awesome algorithm! To the ones interested, here are the original problem statement and my solution:

https://www.urionlinejudge.com.br/judge/en/problems/view/1942

http://pastebin.com/aXmLB8Ud

Problem description : https://www.urionlinejudge.com.br/judge/en/problems/view/1476

My code : http://pastebin.com/9X29pLcf

I have been trying to solve this problem for a while. I'm not sure if my idea is correct (LCA with dfs preprocess and segment tree queries), but i think it is. I have found a test case that breaks my program, and i know the reason my program fails in this case, but i don't know how to fix it because i don't have a lot of experience with LCA algorithm.

Explanation : i want to determine the bottleneck edge in the path from vertex A to vertex B. The query in my segment tree returns the smallest weight, but it considers all vertexes that were visited between A and B in the dfs, and some of these vertexes are not included in the path from A to B.

Any help will be much appreciated! Thanks in advance.

Bad test case:

6 5 8

4 1 39

2 4 80

6 1 29

4 5 35

3 1 21

4 2

4 6

5 1

5 4

4 2

3 4

3 4

5 1

Expected output:

80

29

35

35

80

21

21

35

My program output:

39

29

35

35

39

21

21

35