There is no main character in the statements this time.

Old driver will fire his car!Come on, become candidate master!

LOL it should've been

DONT FORGET TO WRITE AN EDITORIAL

He took part in the onsite event, thus is unable to participate in this round.

Why the fixation on tourist to get top rank? It may be jqdai0815.

a week of Petr

This

666

You watch too much game of thrones.

Petr had registered.

police helicpters?

What did you do?

I also couldn't concentrate on all past 30-50 contests which I participated with missiles falling around me.

I misunderstood the problem in the same way.

That's how I understood it as well. Maybe we're just thinking about it wrong? But that's the only way I can see it.

I think the return of the bus can be neglected.

Bus can go non-integer amount of time.

I still don't understand how you get that low number. The lowest I could get is:
 +   +   = 3 + 1.5 + 0.75 = 5.25

Yes, I also thought so. In fact, according to that, the time only dependes on the last guy and there are some inequalities with the others. It was so weird :c

Students can get off the bus at any point. You are assuming that students gets off the bus only at the end.

When the bus takes some students (or maybe only 1 student) it will be more profitable if it doesn't take them to the final. Think on this a little bit and you will get the second example.

It's not productively always go to end of way by bus.

Там есть решение за O(n), так что ничего удивительного.

Do you mean problem E?

can you elaborate your approach. ?

I failed the same test, I am very curious. Seemed like an easy problem

isn't it "baacdabc"?

I found a counterexample for mine.

6
abcaab

My solution says 4 but correct solution is 3.

Your code finds some interval, not necessarily the shortest one. Consider an example: 8 abcaabbc Your code will first move l from 0 to 4, leaving r=7, and then stop on "abbc" getting 4 whereas the returned value should be 3 (the first three letters "abc").

would you mind explaining a little bit why?

A O(1) mathematical formula exists.

T = el / (ev₁ + v₂ - v₁)

I was thinking that you should drop them off at a point b such that the time remaining after you drop them off multiplied by the walking speed of kids is equal to the remaining length.

http://codeforces.com/contest/701/submission/19348156

5.666644 was coming only if you assumed bus will always reach towards the end of destination. Answer could be reduced if the bus leaves those k persons somewhere in between

ans is 33/7.0 and theres a O(1) formula

Div2 A with N <= 100000 would've been fun.

I can't find any exceptions too... How about changing recursive function to loop? If It still gets TLE, then it will have an exception.(I'm just saying that recursive depth 200000 is dangerous)

Why not both?

I interpreted it the same way. Although I probably wouldn't have been able to do it even if I had interpreted it correctly :P.

WTF!! I came to know now!!

So ... what does it mean in the end ?

Denoted by x the number of rows where no rook is placed, denoted by y the number of columns where no rook is placed. Answer = x*y.

In total (in the beginning) there are n * n cells.
These n² cells can be viewed as n rows of cells and n columns of cells.
When we place a rook, it destroys completely 1 row and 1 column.

Let's keep 2 arrays which will tell us, whether the row/column was destroyed or not:
bool destroyedRows[100000];
bool destroyedCols[100000];

After you place the first rook at cell (r₀, c₀), we can destroy row and column like that:
destroyedRows[r₀] = true;
destroyedCols[c₀] = true;

The amount of alive rows decreases like that:
long long cellsLeft = n * n;
cellsLeft -= n; // for destroyed row
cellsLeft -= n; // for destroyed column
cellsLeft += 1; // because row and column intersect at point where rook stands

If you place the next rook at cell (r₀, c₁), you cannot destroy the row r₀ the second time.
That is why you should first check whether it was already destroyed:
if (!destroyedRows[r₀])
{
    destroyedRows[r₀] = true;
    cellsLeft -= n;
}

The final idea is to accumulate the amount of destroyed rows and destroyed columns till the current rook.
Imagine that you have already processed i - 1 rooks. Now, the i'th rook wants to destroy the row r_i and the column c_i. If the row r_i hasn't been already destroyed, you should destroy it now. But some cells on that row r_i where previously destroyed by i - 1 rooks before the current rook. When they (previous rooks) were destroying there's columns, they also crossed the row r_i! How many times did they cross the row r_i? Well, they should have crossed it when they destroyed their's columns and we should just keep track of the number of columns destroyed (which is  ≤ n - 1). We will use this number to add back the amount of destroyed columns:
...
destroyedRows[r_i] = true;
cellsLeft -= n;
cellsLeft += destroyedColumnsCount; // add back cells that were already destroyed before

That is the general idea. The rest is implementation detail... =)

I think the basic idea is quite easy.
Initially, number of rows(n) = number of columns(m) = n

Then there are only 4 cases:
1. if you have not visited the row and the column both
visit them and reduce them, n-- & m--
output: cout<<(n*m-(n+m-1));
2. if you have not visited the column visit and reduce the column size, m--
output: cout<<(n*m-n);
3. if you have not visited the row visit and reduce the size, n--
output: cout<<(n*m-m);
4. if you have visited both the row and column, there is nothong to do
output: cout<<n*m;

Here is my approach :)

For each query, you have to find number of cells on the board which do not have their row number and column number equal to any of the positions of the rooks placed uptill then. Actually, I did it by solving its complement, i.e. number of cells on the board which have their either their row number or column number or both not equal to any of the positions of the rooks placed and then subtracting this answer from the total number of cells.

Maintain two sets for rows and columns. Denote them by r and c. Total cells -> (n*n)

Cells which their row equal to any of the rooks and column not equal to that of any -> (n-size(c))*size(r)

Cells which their column equal to any of the rooks and row not equal to that of any -> (n-size(r))*size(c)

Cells which their row not equal to any of the rooks and column not equal to that of any -> (n-size(r))*(n-size(c))

Therefore Answer = (n*n) — (n-size(c))*size(r) — (n-size(r))*size(c) — (n-size(r))*(n-size(c))

On further simplification, this turns out to be,

Answer = n*n — size(r)*n — size(c)*n + size(r)*size(c)

Answer = (n-size(r)) * (n-size(c))

Here is my solution: Code

T.T...

I had the same solution to C as yours, but little bit simpler — you don't have to compute maxflow. If for every "deleted" edge, there is no path from s to t consisting only bridges, then we print  - 1.

I didn't code it, but it's O(m²). Isn't it too slow?

I had a solution that didn't need flows and works in .

Get a path from s to t. If none exists, print 0.

This path will consist of at most n-1 edges. Now for each edge in this path, remove it from the graph and construct the bridge tree of the remaining graph. If s and t are in the same block int the bridge tree then removing this edge is of no use to us. Bridge Tree can be constructed in

If s and t are in different blocks find the minimum weight edge on the path from block of s to block of t in the bridgeTree. Now you have two edges, compare their weigths with the current minimum and update accordingly.

Add the removed edge back to the graph and repeat.

Took too much time debuggin but oh well :/ 19347868

let maximum people bus can carry be n and total people is N. So bus can make ceil(N/n) trips. You have to drop people such that last set of people carried by bus reach final point at the same time when the rest of people reach.

I thought of this logic but wasn't able to implement. Am I thinking right?