CF: 546-D2-E-Soldier and Traveling

Problem Link : http://codeforces.com/contest/546/problem/E
Solution Idea:

  • We can solve this problem using maxflow. So at first make a source
  • Make a first group of vertices consisting of n vertices, each of them for one city.
  • Connect a source with ith vertex in first group with edge that has capacity ai.
  • Make a sink and second group of vertices in the same way, but use bi except for ai.
  • If there is a road between cities i and j or i = j. Make two edges, first should be connecting ith vertex from first group, and jth vertex from second group, and has infinity capacity. Second should be similar, but connect jth from first group and ith from second group.
  • Then find a maxflow, in any complexity.
  • If maxflow is equal to sum of ai and is equal to sum of bi, then there exists an answer. How can we get it? We just have to check how many units are we pushing through edge connecting two vertices from different groups.

Using Dinitz Maxflow

Using Ford Fulkerson Maxflow

Advertisements

SPOJ: MKTHNUM – K-th Number

Problem Link: https://www.spoj.com/problems/MKTHNUM/

Solution Idea: (Merge Sort Tree)

  • At first take input and store the input in a pair array where first element of ith pair is the value ai and second element of ith pair is i.
  • Sort the pair array with with ascending order of ai
  • Build a merge sort tree using the second element of each pair of sorted pair array.
  • Now for each query i,j,k at first check how many number in range i to j inclusive are present in left subtree of current node in merge sort tree. Let the value is x. So if x<=k then it's sure that the answer is in the left subtree. So we will go to left subtree of current node with k. Otherwise we will go to right subtree of current node with k-x;
  • In this manner when we reach to a leaf node we can say that this node contains the index of our answer.