Uva 10779 Collector's Problem

 Uva 10779 Collector's Problem

Maximum Flow - Implemented with Dinic’s algorithm O(V^2E)

Time: 0.069

Language: CPP

The basic idea of the solution presented here is to look the vertices as cards and edges as trades. To build the graph, imagine all the possibilities of exchange of each different card. Bob can only exchange cards with his friends. Take the card with number 1. For each friend, how can i trade the cards. After that, take the card 2 and card 3 and so on. Remember that a card can only go to one friend one time. Creating a vertex LineIN and LineOUT, you can limit the exchange of one card to a specific friend. After build the possibilities, connect the cards of BOB to the respective vertices, the capacity is the number of cards. The cards are connected to sink (t) with capacity equals to 1(counting the number of different cards). Output the Maxflow.

The code here
Keep coding
Forgive my bad english

Uva 11167 Monkeys in the Emei Mountain

 Uva 11167 Monkeys in the Emei Mountain

Algorithm: MaxFlow with Dinic's algorithm O(V^2E)
Time 0.227s UVA 11167.
Language: CPP

1 Introduction

Getting WAs? try hard, read the problem statement again, review your considerations about the problem. If the WA persist come back here again and continue reading.

(....)

Well, i hope that you solved it.

Now, i'll show my observations and solution(stupid solution, you'll see why).

2 Solution
This problem presents two nice challenges: build the graph and retrieve the solution.

So,  imagine a lake, where monkeys drink water. A monkey can drink water from time a to b. Ex: a = 2, b = 3, a monkey can drink 1 unit of water.
With a=2 and b=4, a monkey can drink 2 units of water 2 to 3 and 3 to 4 and so on.

In this lake, m monkeys can drink water at the same time.
Ex: if m=1 , monkeys cannot drink water together(same time).
if m>1, m monkeys could share the water.

A monkey m1 needs to drink v units of water. You can imagine v as a capacity for the intervals of m1. An interval has length b-a. If m>1, m monkeys could share this moment, so, looking the interval it has a capacity of m*(b-a).

Modeling: s(source)[Vertex] -> cap = v(units of water)[Edge] -> monkey m1[Vertex] -> cap=len (Max a monkey can drink)[Edge] -> interval[Vertex] -> cap=(m*len)[Edge] -> t(sink)



Happens that b<= 50000, so build the graph for all the periods is quite disturbing, we have to compress the intervals.

Imagine a monkey m1 that can drink water from a=0 to b=1 and v=1.
I can create an interval called (0, 1), i know that a monkey m1 needs to drink v1=1 units of water. If m=1, a monkey m2 with a=0 and b=1 cannot drink water with m1. But if m=2, they can share the interval (0,1).

Now try to think in many intervals of monkeys and intersections. Those intersections must be converted in new intervals.

m=2
m1, a=0, b=3 v=1.
m2, a=0, b=3 v=2.
1 interval (0,3), 1 intersection (0,3)

m1, a=0, b=1 v=1.
m2, a=1, b=2 v=1.
m2, a=2, b=9 v=2.
3 intervals (0,1), (1,2) (2,9)
No intersections.

Example c:
m1, a=0, b=3 v=1.
m2, a=2, b=5 v=1.
m2, a=4, b=9 v=2.
5 intervals (0,2), (2,3), (3,4), (4,5), (5,9)
2 intersections (2,3),(4,5)

Note that, an intersection divides an interval in at most 2 new intervals.
Those intervals must be linked to the sink(t) as mentioned.

I, with my ignorance, created 2 arrays, sum and mul to get the intervals.

The example c shows that monkey m1 can drink water (0,2) (2,3), so, the arrays sum[0] = sum[1] = sum[2] = mul[0] = mul[1] = mul[2] = m1;
and (2,3), sum[2] = sum[3] = m1+m2; mul[2] = mul[3] = m1*m2;
because they share the interval (2,3) and we must separate.

with the intervals you can build the graph as mentioned here and use MaxFlow algorithm.

Now, you must retrieve the intervals for the monkeys. Note that if maxflow = sum_of_v(sum of Vs), there is a solution.

To get the solution, you must look the residual network, if res[interval][monkey] > 0, the monkey drank. But if another monkey shared the interval, be carefull with the interval length.

Ex: An interval(2,5) with length = 3, monkey Ma taked 2 units (2,4) or (3,5) or (2,3) and (4,5). If monkey Mb taked 3 units, he started at 2 and drank (2,5) and not out.
Store the start for the next monkey.

Now sort the intervals to combine them and print.

My solution(stupid) is here ->
https://github.com/Masterlemos/algorithms/blob/master/UVA/Uva.11167.Monkeys.in.the.Emei.Mountain%5BDinic%5D.cpp



Obs: You can build the intervals without mul and sum. Put the start and end of each interval in vector v;
sort v;
apply unique and erase to get a vector without repetitions;
Search the intervals of monkeys in v and store the positions.

Forgive my bad english.
Keep coding.