Hope, history will not repeat because in this contest, there are 22 problem setters and testers.

educate yourself if you want high rating!

No you're not, i also can't open.

I think after this round everything will be ok.

maybe it's just to prevent delay submission during the contest, which participant complaint for each contest lul

Some reason is problem with codeforces api.

Can it be because the API is not working which in turn is to prevent us from seeing questions done by testers.

I'm sorry dude, but it is how cf works in community...
You get tones of downvotes if your rating's low...
You can't hold a contest because your rating's low...
There might be some issues if you hold a contest and your rating's low...
I don't have an idea how to improve my rating after years being on this website, Nor to be better in community. Hope someone help me in some new ways... . And something else, please think about it before starting downvote with millions of account(fake or real :()

It was because you solution was not fast enough to pass the remaining system tests ! during contest only pretests are tested that's why it shows pretest passed ! hope you got it

During the contest, your code is tested on a subset of the final tests, called PRETESTS. After you have passed the pretests, you can lock your solution and then view other participants' codes and try to hack them. Others who have locked their solutions can view your code irrespective of whether or not you have locked your code. Once the coding phase is over, your solutions will be tested on the entire set of tests. This phase is called system testing.

It is the system testing, in the round, the judge runs only about 15 cases on your code, if your code passed you got PREtests passed. And after the contest, they run around another 100 test on your code and give you your final verdicts. You can also learn about hacking a solution.

Why does people downVote your comments without any reason (maybe even without reading your comment) ?

Can you share your solution to E

E is pretty easy. It's a standard fenwick tree problem. I'm ashamed I couldn't solve C though T_T

Disqualified. However, it's better to write such messages in "ask a question" during a contest.

jealous !

1 1 1 1 1

lel. you mean sort(b+1, b+1+k)? or is it not Office Keys problem?

I failed bin search because of l=1=)))

3
10 8 8

Answer is "NO".

there were many!! someone in my room has passesd pretests with this soluion http://mirror.codeforces.com/contest/831/submission/28522407 !!

2 1 2 or 2 2 1

Eagerly waiting for the replies:) Can someone explain there idea please

D is very simple question of basic DP. sort all men and keys on the basis of their positions and then u have dp state as dp[men][key] = min(max(time taken to that men after picking that key , dp[men+1][key+1]) ,dp[men][key+1]). and after all recursive calls ...your final answer is dp[0][0].

I solved D using binary search + Maximum matching

For problem D:

I guess that the chosen key should be a consecutive n keys segment.. I don't know whether it will pass, but it seems pretty simple..

I solved D as follows: It's optimal to use a set of keys that are neighbours. Sort the keys, sort the people. Let the rightmost person go get the rightmost key, etc. Try every key as rightmost key.

Lets say your path starts at 0. Create array for its values (adding a_i). Now make some path value to b_0.

You know b[0] must be after some judge i, so check for every position i, if this could work in linear time

let us get the prefix sum for all A's, now sort them. then get the value of all B's and sort them. now let us say the max value in B is x, now for x to be at position i, the initial value will be x — pref_sum[i]. then using this initial value generate the the array and check whether all numbers come in b.

Yeah. I got TLE on pretest 12 :(

You can preprocess it?

There's a k^2 log k solution though

Pretests are so weak that my solution without sorting passed. And even wasn't hacked :( RIP rating

For Div 1A / Div 2D Not only pretests, I saw a wrong solution passing the system test.

    ll res=INT_MAX;
    sort(a,a+n);
    sort(b,b+k);
    for(int i=0;i<k;i++)
    {
        ll ans=0;
        for(int j=0;j<n;j++)
        {
            ll tmp = abs(a[j]-b[i+j]) + abs(b[i+j]-p);
            ans=max(ans,tmp);
        }
        res=min(res,ans);
    }

It can be seen that for array b index will reach to n+k whereas b can have max index possible till k.

Link to Code

I used bs + max matching

I just did sort :D Use some interval of keys and map each key to people :D

I think your approach is wrong. Try this test.

2 2 1000
1 1000
1 2

Notice that both keys are close to the first "dude" but the second "dude" is far away from keys and he needs to pick one of them.

something similar to

4

1 3 2 3

I also got wa on that.My solution failed because i didn't treat equal numbers correctly,maybe you have same mistake.

No. Informally, for pairs of paths you need triples of paths. Consider following situation: you want to count pairs of non-intersecting paths where both are in the same subtree except one of them touches root and goes down again (to the same subtree). If root is removed, this construction becomes a triple of non-intersecting paths.

C++ is crazy.

Consider the following (more general) problem:

For every T from 1 to K and for every P from 1 to K, calculate how many different sets of P disjoint paths there are in a tree of size T.

It turns out that you can calculate these values easily using answers for smaller trees.

dp[i][j] means number of sets of j disjoint paths in a tree of height i

The final answer is dp[n][1], now to compute dp[i][j] you have to consider many cases:

1- select total of j-1 paths from the left and right subtrees and let the root be the j-th path

2- select total of j paths from the left and right subtrees and either let the root be at start/end of some of the paths or let the root be not involved in any path

3- select total of j+1 paths from the left and right subtrees and merge two paths into one path using the root node as a node between those two paths

Can you please explain the greedy part a bit more in detail. I tried a similar method but then messed up in the greedy to submit a stupid code.

Suppose I am checking whether time 'x' is possible, I just concluded "true" if there are "n" distinct keys which can be collected in 'x' time and "n" people can reach office using come key in 'x' time. "n" is the number of people.

Thanks in advance :)

Basically problem is asking to maximize d such that:

We can do some algebra to get:

The right hand side doesn't depend on d, so basically we can consider it some constant C and just try to find the maximum d such that .

Now, if this were monotonic, we could find d easily using binary search. Unfortunately, it's not, because is decreasing while d is increasing.

The trick here is that there aren't many distinct values of . In fact, for any such a_i there are only such distinct values. Anyway all the possible distinct values are given by i and for all .

So what we can do is get all the possible distinct values of and also the bounds l and r such that l ≤ d ≤ r gives that specific value. Now, intersect all these ranges. (It seems like a lot, but actually it's only about different ranges.) The new ranges will be [l, r] for which all are constant.

Now, for each range, we can now binary search d within the range; since all are constant, we know will be monotonically increasing. Actually we don't even need binary search at this point, but at least binary search requires less thinking. (Make sure to preprocess all the sums for each range before doing the binary search.)

The runtime should be or something along these lines.

If it helps, here's my code. 28521138

I think your solution is correct.

The connected graphs for which the problem doesn't hold are known as Coxeter-Dynkin diagrams.

I didn't have time to finish implementing this though :(

Proof of last sentence:

Let us name the value on the path, from leaf to the v, x_1, x_1+x_2, x_1+x_2+x_3, ...,x_1+...x_n=value(v). Then the sum of score of the edges and vertices on this path is -sum_{i<j}(x_ix_j) = -(value(v)-sum(x_i^2))/2, then the optimal value is -(1-1/n)value(v)/2. It just means (2,2,2), (1,3,3), (1,2,5) or more is YES and otherwise NO.

akvasha and me, as the authors of Div1E problem, are pleased to hear this from you. :)

Moreover, there is strict criterion whether 3-tuple (a, b, c) is good. It will be stated in the editorial.

Regarding to last part. I know that for a particular tree (even any graph) we can check if it is ok by checking if corresponding matrix is positive-definite using Sylvester's theorem, and for a case of (1, 1, k) it can be easily proven manually, so that's some way to prove whole correctness. However I am not fine with your "otherwise not, since we can prove that in the optimal solution, the value on each path will be arithmetic progression." argument. The thing is, "optimal solution" is kinda useless notion here, it is either -infty or 0 and in second case you do not know if 0 is achieved with only zero weights. I also noted during contest that if some value is different than half of sum of its neighbours then we can optimize result by changing only that value, but for vast majority of cases it is not possible to achieve a stable set of values. How your argument goes for trees (2,2,1) and (2,2,3)? You can't achieve local optimality in neither of them, but one is fine other one is doesn't.