Timus Online Judge - 1500 Pass Licenses

[skinnyguy]

I need help with this problem. the link to it is
http://acm.timus.ru/problem.aspx?space=1&num=1500

I am trying all combinations of K and then running union-find for checking connectivity from 0 to 1 on the combination. but that is giving me TLE. please suggest a faster algorithm or any optimization if i am missing it. complexity of my algorithm is O(N*N*(2^K))

thanks

[andmej]

I first tried Dijkstra's algorithm with the state = <node, used_c> where node is the node being visited and used_c is a bitwise mask telling which licenses I have bought so far. However, this approach got Memory Limit Exceeded (The limit is 16MB).

From state <node, used_c> you can go to:

<neighbor(node), used_c> buying 0 extra licenses if the category of the edge is included in used_c.
<neighbor(node), used_c | (1 << edge_category)> buying 1 extra license if the category of the edge is not included in used_c.

Then I tried brute-forcing all possible combinations of licenses (again using bitwise) and for each combination, I checked if node 0 and 1 are connected, using BFS. But this got Time Limit Exceeded too.

There must be a way to check if nodes 0-1 are connected using a faster approach.

Now we need some help from the gurus to solve this good problem

[skinnyguy]

just adding to the ideas i used (but inevitably still TLE on)
the number of nodes are limited to 30. i use bitwise to store the connectivity for each color, but updating them for each combination still required N*N iterations. so still TLE.

by the way, i found on the net that this problem is a "Minimum Color s-t Path Problem" on a colored graph. some where it says that the problem can be solved in O(N*(2^K)). but i am unable to find anything faster than O(N*N*(2^K) by myself

[andmej]

by the way, i found on the net that this problem is a "Minimum Color s-t Path Problem" on a colored graph. some where it says that the problem can be solved in O(N*(2^K)). but i am unable to find anything faster than O(N*N*(2^K) by myself

I had never heard of that problem before. Where did you read that?

[skinnyguy]

http://www.math.tau.ac.il/~segevd/Paper ... -25min.pdf

this presentation, points out the definition of the problem that is very similar to this problem. note that they even consider weights of colors, and the problem is stated as, optimize the selection of colors such that the weights of the colors chosen, sum up to the minimal. googling for "Minimum Color Path Problem" gives many links for research on this problem for use in connectivity/design of efficient Networks. unfortunately at my college, access to much of those papers is not provided, otherwise i would not have minded learning a few new tricks

Of course, all this goes too far away from the purpose, of maybe just solving this problem on Timus

I was able to get accepted in a very indecent time using an optimized O(N*N*2^K) finally. but the best times are still way better than the time i got, and i was wondering how to improve on that.

[andmej]

I was able to get accepted in a very indecent time using an optimized O(N*N*2^K) finally.

Can you tell me how did you optimize your solution? I haven't got accepted yet.

[skinnyguy]

The trick i think is,
making 2D arrays and accessing them requires more time,
than making a 1D array and then store the adjacency matrix - each row in the form of a 30 bit integer.
Also, i used a simple recursive DFS, nothing fancy.
This gave me AC in 2.64 seconds.

also, i suggest searching for "Timus Online Judge 1500 Pass Licenses" at forums.topcoder.com
there has been some discussion of the problem that helped me get this done.