Hi All!!

I am learning max-flow these days..I got a problem from 2008 ICPC Beijing regionals that am finding hard to solve.Could anyone please help..Problem statement is as follows.

Gabiluso is one of the greatest spies in his country. Now he’s trying to complete an “impossible” mission — to make it slow for the army of City Colugu to reach the airport. City Colugu has n bus stations and m roads. Each road connects two bus stations directly, and all roads are one way streets. In order to keep the air clean, the government bans all military vehicles. So the army must take buses to go to the airport. There may be more than one road between two bus stations. If a bus station is destroyed, all roads connecting that station will become no use. What’s Gabiluso needs to do is destroying some bus stations to make the army can’t get to the airport in k minutes. It takes exactly one minute for a bus to pass any road. All bus stations are numbered from 1 to n. The No.1 bus station is in the barrack and the No. n station is in the airport. The army always set out from the No. 1 station. No.1 station and No. n station can’t be destroyed because of the heavy guard. Of course there is no road from No.1 station to No. n station. Please help Gabiluso to calculate the minimum number of bus stations he must destroy to complete his mission.

Constraints:

(0 < n ≤ 50, 0 < m ≤ 4000, 0 < k < 1000)

In short::Remove minimum number of vertices in graph such that shortest path from source to destination is of length greater than K..

Hi,I am trying to solve this problem on Spoj.

I have implemented simple Dinic's algorithm only,but am getting TLE.Here is the solution link solution .Am I doing anything wrong?

Please help!!

Edit:Got AC!!

I was unable to solve a problem in onsite coding round of iiit allahabad.

Given N numbers.Then Q queries of the form L R D, How many number from index L to R are divisible by D

1<=L<=R<=100000

1<=D<100000

N<=100000

Q<=100000

input:

N-number of integers then N integers, Q qeuries of form L R D eg-

10

4 6 3 5 18 9 2 4 7 22

2

1 3 2

2 5 3

output

2

3

Hi, how is this question solved?I thought it was a Markov chain problem where adjacency matrix divided by degree gives the transformation matrix.But the solution is different.It uses a dp approach.Please help

how to solve this question.I tried to understand the russian version of editorial by googlle translator,but it wasnt clear to me

How to solve this problem ??

hi,how can i solve this problem.I read the editorial but i couldnt understand it properly.How a modified dijkstra can be applied to it

Hi i was trying to solve this problem.In editorial it meant indexing the vertices so that segment tree could work.How to index the vertices in such a way??

Hi, I tried to understand bipartite matching from here But it was different from the normal max-flow code.(Dinics for example).What is its proof of corectness and its complexity?

Thanx

Hi how to solve this question.

how can i solve this problem.No editorial available

Hi,I tried to solve this problem during the contest but could not.Contest is over.Please Help

Basically it states that there are N numbers in an array A

initially sum=0

if i choose a number A[i] then i will add minimum of (A[i-1],A[i+1]) to my sum and will discard A[i] off the array,

Find such the maximum sum that can be obtained.Example

Input

5

1 1 4 2 5

Output

6

First of all, second element (1) will be removed. 1 will be added into the account, as min(1,4)=1. Remaining chips would be arranged as : 1 4 2 5.

Then fourth element (2) will be removed and 4 will be added into account. Remaining chips : 1 4 5.

Similarly proceed further. Final credits will be : 1+4+1 = 6.

Hi, I tried to solve this question,but could not. I looked at the solutions but didnt get much.

How to solve this problem efficiently!!

Hi,There are certain queries like [l,r] where every element is maked between array indexes l to r; and all queries i want to know the total number of marked numbers.

Is there any faster way to do it besides iterating for each query from l to r and finally counting number of marked values?

eg- query=3 1 2 4 5 2 4

final array = 1 1 1 1 1 0 0.... ans=5