I think he mean copying the whole old solution

He said that it's only forbidden to copy a whole solution.

Well, when I am on the onsite contest and can't copy I am angry too.

The idea is fine, the execution will just be difficult. As Xellos mentioned above, how would you make difference between someone who copies old code and modifies it and someone who writes it from scratch? If it is some standard algorithm, say DFS/BFS/Dijkstra/Flow/Segment Trees/etc then my codes will look 95% identical even if I write them weeks apart because I have a specific style of writing them in my head.

And of course, if it is impossible to guess which is a new code and which is an old code, it becomes useless to have such a rule as cheaters won't be effectively punished (without lots of false-positives for non-cheaters).

Idea is fine, execution could be tough. If it is indeed a long contest and time penalty doesn't matter (obviously it shouldn't) allowing use of old codes (as long as they are your codes) should be fine.

I personally rarely use old codes and have no templates at all, so I'm fine with whatever the rule is, but I see why people dislike it :)

Happy Hunger games then !

Just wish God will help you...

of course BOTTOM-25 not TOP-25 :D

As I know, ACM rules is the only avaliable type of gym contests

When writing checker to problem with "find any good/best answer", setter should consider his mistake and do some asserts (not exactly asserts but nvmd) in case of participant having better answer. Here I guess for some tests their program returns -1 (impossible) but there is a solution. So checker validates this solution and says "shit". I guess it is what happened here.

What bothers me more is that there is no administrator (online) for more than 12 hours after start of a contest.

They can be negative. And you should forget about 10⁹ restriction, output large values if you need. Also, I think, all a_i should be integer.

(min lcm) % mod

Interesting question!

Cheating and copying codes is forbidden(even copying your own old code) and you'll be disqualified from the the tournament if we catch you.

So, formally you copied your own code you used on the same problem in other place? :)

I think it is considered cheating cause u r having an advantage over other contestants who don't know where to find the other version of the problem.

If penalty time doesn't matter in this contest, I think it's OK for you to do it (but of course they might have a different opinion).

for C++ just if you want to query for node v then write this line:

cout<<v<<endl;

then read the answer like this:

cin>>v;

it's very simple

WA

I think you should be removed from contest :)

He really wanted to play with her Pepsi Cola...

How do we know that people are knocked out of contest? In standing, on 1st day I see around 140 people, couple of days ago it was around 160-170, right now it is 178.

I don't think it will. But I think we, participants, could after the end prepare a community editorial, as some problems are quite hard for less skilled participants, but also interesting and worth upsolving

You're totally right. But also, it would be a nice idea to add more problems with more difference in difficulties, cause in last 3 days there were only 3 new medium problems and none of them is really hard or easy.

Well in case they actually plan to provide some rewards for top20 it would've been unfair to allow teams :)

It looks like I was removed from contest because I reimplemented that in less than 10 mins.

Actually, most of the people who solved it used c++

It should be "some of its edges", I suppose, since there's "each edge" afterwards.

I don't think so, similiar question has already been asked by someone and still got no official response. But,.I. and me are going to prepare one, along with small hints editorial. However, there's no need to do this if there'll be an official editorial, so I encourage contest hosts to finally answer this question...

What? Why should the competition be extended because someone asks for it? Is that not completely unfair to other competitors?

But why stop there? This contest is so awesome it should be extended at least until New Year! Just need a way to "resurrect" the "dead" and lots of problems.

I agree, that sounds like a great idea, and I will be glad to help

Apologies mate.

I was only a spectator, so I had no way to check if my solution is right.

First of all, we need to come up with any solution. Let's fix a variable X₁ = [a₁, b₁], call it excluded and compute the probability it's k-th (first, second, ..., n - 1st) in order under the assumption that X₁ = s for some fixed .

Everything can be described by the generating function

where t is number of variables whose intervals are strictly left to s and J contains all the intervals such that . We can see that the x^k - 1 coefficient hides the probability of X₁ being k-th when s is fixed.

What if s is uniformly distributed over [a₁, b₁]? X₁ has a probability density function equal to inside its interval and 0 otherwise, so the overall probability is . Only note that the definition of w may change for different values of s (if we move s to the right, some intervals may begin lying strictly to the left of s or contain s). However, such changes are not too frequent (there are only Θ(n) stars/ends of intervals, so there may be only that many changes).

So: for each of n variables with associated interval [a₁, b₁] we find all the intervals where w doesn't change its definition (Θ(n) of them). Then for each of these intervals: compute w for each of them (do Θ(n) multiplications, each of them can be done in Θ(n²)), get the polynomial describing the x^k - 1 coefficient, integrate it in s over that interval. Everything should be doable in Θ(n⁵).

This will probably not be enough, so we need to speed it up. For example, we could probably somehow use multidimensional FFT for multiplication (however, I'm not sure how it works XD). We could also probably avoid so many multiplications and merge some steps. One way is to think that each polynomial behaves properly in intervals between variables starts/ends (call such intervals proper and order them from left to right) computed for each excluded variable. We can then create a matrix M of generating functions; cell in i-th row, j-th columns contains the generating function for excluded variable X_i and in j-th proper interval in order.

Then a factor has to be multiplied with all the generating functions inside either of two rectangles: the first with variables X_j, j < i and proper intervals partitioning [a_i, b_i] and second with variables X_j, j > i and same proper intervals. Probably with some voodoo magic with 2D segment trees it can be done in Θ(n⁴) or even in .

Isn't it... uhm, quite overcomplicated?

Here is a solution that doesn't require knowledge of integration (or integration algorithms).

Consider the simplified case where we know that, for some interval, every competitor is either before the interval (say there are S of these competitors), after the interval, or somewhere inside the interval with uniform probability over the whole interval (say there are K of these). Then if this arrangement happens, each of the K competitors then has a chance to come each of S + 1^th, S + 2^th, ..., S + K^th.

Note also that if we consider all endpoints together and then take the intervals between consecutive endpoints: then for each interval, every competitor will either not cover that interval at all, or will completely cover that interval (and thus if they are in it, they will have a uniform probability of being anywhere in that interval). Also, there are O(N) of these intervals.

This gives us the simple algorithm: for each interval (O(N)), for each competitor i, (O(N)), calculate dp[S][K] = the probability of S other competitors appearing before this interval and K other competitors appearing inside this interval (which we can do in O(N³) with DP). However, this is overall O(N⁵) which is too slow.

So we need to try and calculate "dp[S][K] for all competitors except i", for every i. One idea is to calculate dp[S][K] for all competitors, and then "subtract" each competitor with some maths. Overall this would be O(N⁴). Theoretically this is possible but in practice it is too inaccurate.

Instead we can calculate this with divide and conquer (overall O(N⁴lgN), or buckets . For example, for divide and conquer we can calculate f(l, r) = the dp[S][K] for all competitors outside of the range [l, r), and then recurse on f(l, mid) and f(mid, r). (or maybe my understanding of the divide and conquer method is completely wrong because I did sqrt N buckets and was only told about the divide and conquer method afterwards ¯\_(ツ)_/¯)

Suppose the function F(i, x, r) = probability that the ith player scores exactly x points, and finishes at the rth rank.

Function F can be easily computed by dp in O(n^2) for all values of r fixing i and x.

We can integrate this function for fixed i and r, from x = L[i] to x = R[i] using efficient integration method. (I used simpon's rule but it was very hard adjusting accuracy to pass the time limit)

Mine is N^3/32. Does N^2 solution exist?