RESTORE is not the problem I'm in charge of, though I think it has already been fixed till now.

Seems that m2.codeforces.com had periodically been unstable during contest. Why is that?

(Had it been accessible, I would perhaps have one more problem Pretest Passed... sad story)

On sorting of strings, I think quicksort can handle the job in O(sum(length) log n) in expectation, even if comparing of strings A and B costs O(|A|+|B|). Mergesort can give the same complexity (without randomness) if comparing costs O(min(|A|,|B|)).

On the complexity of binary heap (under the assumption that comparing is O(min(|A|,|B|))), let's consider two cases: 1. pop: After each comparing, one of the operands will take a step up in the heap, and let's count the cost in the element who goes up. 2. push: Similarly, with each comparing one operand goes up. The only exception is the last comparing. We count all these costs in the inserted element.

It's not hard to prove that each element can only be counted O(log) times.

It depends on the vector's content. For example, vector < int > has complexity_of_comparing=O(1).

Yes.

map < int , vector < int > > insertion has complexity O(log(map_size)+vector_size).

sort(vec.begin(),vec.end()) has complexity O(vector_size*log(vector_size)*complexity_of_comparing).

Well, strictly speaking, the complexity of calling mp[ver] or insert(vector,int) can be as high as log(N)*max_vector_length_in_mp, as c++ standard only guarantees O(log(N)) times of comparing, while not specifying which elements will be compared.

This is also related to how the compiler implements < between vectors. If comparing A and B costs O(|A|+|B|) instead of O(min(|A|,|B|))(as we would normally implement it), complexity can reach log(N)*max_vector_length_in_mp as well.

However, the two scenarios mentioned above are not so likely, so I guess for most compilers that complexity will be O(M*log(N)). Don't rely on that too much though, as priority_queue in GCC has already turned out to have used a rather strange(and counter-instinct) implemention, which makes the complexity of inserting a vector into it become log(N)*max_vector_length_in_mp.

Ah, I see. Thanks a lot!

On the O(n^3 log n) solution for H:

(points are labeled A-B-C-D-E in clockwise order)

I don't think "lying in the intersection of some half-planes" is sufficient to being a legal B(or E) if you have determined ACD, as this cannot prevent A from lying on the wrong side of segment BE.

Or did i misunderstood something?

Problem E is really not so friendly...

In Chinese statement for SFXPAL we're told to modulo the answer with 1e9+7 instead of M. Luckily I guess most participants have noticed the extra number M in the input.

Will t-shirts be sent according to address on codechef profile ... or email queries on the address?

Seems that editorial writer had made a small mistake in Div1 Hard.

A clever way to compute these values is based on the following recurrences:
T(n,1) = n(n+1)/2
T(n,p) = T(n,p’) – p*T(n/p,p), where p’ is the biggest prime smaller than p, or 1 if there is no such prime

Instead of

T(n,p) = T(n,p’) – p*T(n/p,p)

It should be

T(n,p) = T(n,p’) – p*T(n/p,p-1)

As there can be multiple p in a number's prime factors.

With a lot of useful built-in tools and plugins

Drugs or medicine bring too much side effect, which is certainly not worthy if you just want concentration.

Acceptable to me though, being a night owl (o_o)

Seems that this year's number of registrants has dropped, in comparison to previous ones. Is it because of IPSC's being late this year?

Another non-hashing O(nlogn) solution for div1D : My submission

--------------------------------------------------------

The point is to determine whether a element in the initial array must appear in a LIS. My solution is to find the "leftmost" and "rightmost" LIS, and their intersection are the necessary elements which must appear in any LIS.

Definition on the leftmost LIS:

During the process of finding a LIS, for every element E=array[i] we have to find its predecessor P, which is the element before E in a LIS of the subsequence [1...i] containing E as its(refers to the LIS) end.Thus, if we take the leftmost P (which has the smallest index) every time, the final LIS that we get is the "leftmost" LIS.

The rightmost LIS is defined similarly.

Proof on the correctness:

Let's denote the leftmost LIS with L, and the rightmost one with R. Let P be a element in both L and R.

Obviously the index of P in L and that in R are the same. Otherwise there would be a longer increasing subsequence than L or R.

If P's predecessor in L is the same as that in R, it means there can be no other candidates for P.

On the other hand (pred_in_L(P)!=pred_in_R(P)), different predecessors lead to the same P, then it is more inevitable that P is the only candidate!

--------------------------------------------------------

Well, I know this isn't quite a scientific proof, but the solution passed all the tests after all... Waiting for a more rigorous one :)

Well, the second program outputs "1 5" in my environment (64bit windows, tdm-g++ 4.9.2 64bit compiler, dev-c++) ,which is correct.

CodeLite. It is free and open source and light-weight and cross-platform and supports C,C++,PHP and Node.js(just like codeblocks), and it has updates frequently (as for codeblocks , it has not had updates for years) , so it supports new standards (for example , c++17 code-completion features) while codeblocks doesn't. (BTW, you can use it as a editor for other languages , because it supports code highlighting for countless languages) I've used both codeblocks and codelite , and I think codelite is more "considerate". For example , it has pre-installed stl_printer for gdb (so that you can see inside STL templates while debugging), and its code-completion & code-highlighting & parentheses-matching&... are smarter. Try it out ,and you will see. The only problem is that, there isn't much introduction about using it on the internet(in my native language) , so it may be extremely difficult to use at the beginning.

upd: I use codelite on 64-bit windows , and it seems that the only c++ compilers which codelite supports perfectly , are mingw64 compilers. As for others , you can't debug STL with them . :(