Codeforces is an international site for all people.

Not only indians

This is an international website. Not only work for you.

Different times are good for different users.

Not sure if perfect for all of us, as some (including me) still have school during the time.

Now I have to decide on whether to do contest or to attend class (most likely I won't :p )

utf-8 ? Do you mean UTC+8 ?

In the blog, 11:05, March 9th, MSK == 16:05, March 9th, UTC+8 .

But in the CONTESTS, it is 17:05, March 9th, UTC+8 .

Obviously, they are different.

And thanks for that you found another difference.

UPD: The problem is fixed.Have fun.

I guess your train trip is over. So why you still haven't sent the notification?

No, there is no MST

There is Strongly connected components of directed graph.

But I'm not sure if my solution correct or not. But pretests were passed

Didn't solve it in time, but I think I had the right idea.

Basically, you create a dependency graph. That is, the vertices in the graph are the datacenters, and you draw an edge from datacenter A to datacenter B if bumping A's time an hour would force you to bump B's time as well. (That is, if an item x is stored in A and B, and B's time is the hour directly after A's time.)

Then, the problem boils down to: I want to find the vertex in this graph, for which, if I pick it, the number of vertices that I am therefore forced to pick is the smallest possible. (In terms of the graph, this means that I want to pick the vertex v, who can reach the fewest number of other vertices.)

So, we can observe that in any dependency chain, or dependency tree, or dependency DAG, we can always just pick some datacenter at the end of the dependencies — i.e. some datacenter, which might have edges coming into it, but no edges coming out. Then, if we pick that guy, we aren't forced to pick anyone else. So our answer is 1.

However, if there are cycles, then it's trickier. If a vertex is part of a directed cycle, then we can't just pick a vertex at the "end of the chain", since there is no end of the chain. Picking any vertex (datacenter) in that cycle forces us to take EVERY vertex (datacenter) in that cycle. More generally, taking any vertex in a strongly-connected component implies that we have to take the whole SCC. So, the problem then boils down to: we want to pick the smallest SCC that has no outgoing edges. We can use Tarjan's or Kosaraju's to get the SCCs of the graph, and then find the smallest SCC with no outgoing edges.

我系渣渣灰

我是美国人

I basically did SCC, and then you know that SCCs make a DAG, so you find the vertex with out-degree 0 in the DAG that has the smallest SCC size.

Note: SCCs are of the graph where (v, w) is an edge if (v, w) share some data and (u[v]+1)%h = u[w]

I did same and my code failed on pretest 5

My solution is also based on SCC as well. I used Tarjan's Algorithm to have the SCCs sorted topologically.

Anyway, it seems like I know what I did wrong, but I'm not so sure (since I couldn't find for myself any cases to prove it). If I was right, the mistake was in my way to choose the correct minimum-size SCC to answer.

Well sadly mine returned the totally correct answer. Should be another case...

Thanks, but my solution won't fail this test. It returns:

2
3 1 3 8
5 2 4 5 6 7

Can you clarify more? Are they 66665 three-digit blocks alternating?

And the answer isn't -1, right?

Here's a kind of hand-wavy explanation

The optimal strategy is to always move the rightmost number.

If you simulate a decently sized example (like n=8), you can note that essentially every odd-indexed number stays where it is, and there's a steadily-moving contiguous "blob" of numbers moving from the right to the left.

Given an index i, we want to find out the index that it originally came from. To do this, first, let's try to find the index that it came from on its most recent jump. Let's say n=8, and we're looking at index 4 (using the 1-based indexing in the problem). (I highly recommended drawing out this example and simulating it. If you've done that, you'll see that the number that ends at position 4 is 7. So we want to find out where 7 was before its last jump.)

Every jump that takes place is of the following form: it's a number leapfrogging from the right of the blob/train to the left. And it's leapfrogging over ALL the numbers in the trainblob.

So, if we can figure out how big the blobtrain was at that point in time, then we can figure out how far our number leapt to get to where it is now. Well, we can note that every number that started to the left of index i has not moved yet. And, every other number besides those must be part of the train. So, the amount of numbers in the train is n — numbers_to_the_left_of_i.

By examination, we can see that there are i/2 numbers to the left of i. So, the amount of numbers in the train that 7 leapfrogged over was n — i/2 = 8 — 2 = 6 (including itself). So the position that it came from was i + (n — i/2). And before the 7 was at that previous position, we can calculate its previous-previous position in the same way. We can iterate that i = i + (n- i/2) calculation until i is odd, which is its starting place. And the value of the number at a given position p is (p+1)/2

edit: Tl;dr read xiaolongbao's comment

How do you do the inverse task?

Same with me .

any logic explanation?)

Anything special about test 7 :D?

Very nice explanation. Thanks.

Just a joke, nevermind.

That's obviously cheating and anyone who can think can catch it.

btw, here are 2 more submissions from the last edu round 36010393 and 36017149.

We aren't robots, we can think and decide wisely :))