disclaimer : I do realise this request is not related to the conventional coding contests | problems asked here, but still hope to find people of similar interests, who would like to help.

I have been into Machine Learning and Deep Learning for a while now and it's been going smoothly. There is however a catch, that it's hard for me to verify the working of complex structures due to the limit's of my hardware compute (quad-core i5-processor, no Nvidia -> no Cuda). I've recently implemented Deep-Q-Network reinforcement learning algorithm, and it's taking eternity to converge (seriously it's hard to wait that long without results, or at-least a little sign that I was heading in the right direction). What I'm hoping from the community is that little sign, weather I'm heading in the right direction :) , or my implementation is wrong ;-; .

It would be cool if you could verify the source, and validate it. Even awesome if you could post results after training it.

Link to github repo : https://github.com/rsampaths16/dqn-game-bot clone github repo : [email protected]:rsampaths16/dqn-game-bot.git

I'm looking forward to any feedback you might have. You could give it here, even better as issues over there.

Thank You All;

Generally while modeling Max-Flow problems to solve through Ford Fulkerson we consider edges to be directional. When we consider an edge (A,B), we consider it to be a flow-edge from A -> B. We have to observe that the case of having two directional flow-edges (A,B) and (B,A) is different from have one Bidirectional edge (A,B).

Case (i) We have two Directional edge (A,B) and (B,A). Them being two separate edges they have their own capacities C[A][B] and C[B][A]. As the flow through one edge does not affect capacity of the other, we can model the graph by spliting either of the edges using a third vertex , say C. The edges (A,B) and (B,A) can be transformed into (A,B) , (B,C) and (C,A) where the maximum capacities of (B,C) and (C,A) is the same as that of (B,A). In the implementation we show both the Flow and Residue in the same Adjacency Matrix, and Capacities in another Matrix.

Case (ii) We have an Bidirectional edge (A,B) and through symmetry we would also have the edge (B,A). The problem arises when we take their capacities into consideration. The capacities of (A,B) and (B,A) are always equal ,i.e, they have the same capacity caps (or) flow through one direction obstructs the flow through the other. For these types of edges we can model them as conditionally directed. We can have three separate Matrices in this case, Flow-Matrix : flow, Residue-Matrix : resi, and Capacity-Matrix : capa. Here we set the condition that the direction of the edge is always opposite to that of the Positive Residue. There are two conditions while modeling it this way.

Case (A) When there is no flow through edge (A,B) initially , i.e flow(A,B) = flow(B,A) = resi(A,B) = resi(B,A) = 0 and capa(A,B) = capa(B,A) = max_capa(A,B). Considering positive flow in the direction A -> B , flow(A,B) and resi(B,A) increase while both capa(A,B) and capa(B,A) decreases.

Case (B) When there is a flow in one direction (A,B) initially (say A -> B), i.e flow(A,B) = resi(B,A) = +Z , flow(B,A) = resi(A,B) = 0 and capa(A,B) = capa(B,A) = max_capa(A,B) - flow(A,B). Here there is already an established direction A -> B, and we can observe that the Residue is in the opposite direction. Residue in the same direction resi(A,B) is 0. From these observations we can tell the direction of the edge that is in consideration. Forward when there is Residue in the backward direction, and Backward when there is forward residue.

Condition to check while trying to add flow in A -> B direction

Augment(A,B):
    if capa[A][B]>0 and resi[A][B]==0 : Edge direction is A -> B or there is no direction yet
        Decrease capacity in both directions : capa[A][B]--,capa[B][A]--
        Increase flow in same direction : flow[A][B]++
        Increase residue in reverse direction : resi[B][A]++


    if capa[A][B]>0 and resi[A][B]>0 : Edge direction is B -> A
        Increase capacity in both directions : capa[A][B]++,capa[B][A]++
        Decrease flow in reverse direction : flow[B][A]--
        Decrease residue in same direction : resi[A][B]--

Thank You.

P.S : This is a solution I thought about while solving the problem Total Flow from Spoj. I would appreciate other approaches to these type of cases.

About a month ago in Augest-Long-Challenge[2016] a question — "Funny — Genome" was asked in CodeChef. Although no Official Editorial was released for it , "wodahs_cc" suggested that we need to use "Four Russian Method" to solve for the problem in the forum. I've searched the Internet and also gone through the Video for it, but I could not find a proper implementation to it, So I've Implemented it with my own understanding of the algorithm but still got "Time-Limit-Exceeded" error for some test cases. I don't know what I did wrong. I request you people of Code-Forces community to kindly provide an Implementation for the Four-Russian-Method. I thank you all in advance.

P.S : A Link to my Implementation.