Codeforces uses Windows. And stdin is a text stream by default. On Windows when data is read from text stream all \r\n are converted to \n automatically.

You may see what fread does on Windows and Remarks in particular on the official site https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/fread?view=msvc-170#remarks . The behaviour is expected.

Nice trick. I usually find inverse modulo $$$m$$$ for all numbers from 1 upto n with $$$i^{-1}=-[m/r] \times (m\%i)^{-1} (mod\, m)$$$ and then multiply them all together to get inverse factorials. (Proof can be found here: http://e-maxx.ru/algo/reverse_element#4 )

Your insertEdge takes too long finding list's tail. Each call takes O(size) time and if all edges are adjacent to same vertex you spend O(n^2) which is too much. You should either store tail or push front.

Pick a pair of special vertexes U,V that are as far from each other as possible. Construct a chain that connects them (these are the points with d(U,W)+d(W,V)=d(U,V) ordered by distance from U). Consider subtrees rooted at each vertex from this chain. We can easily split all vertexes into these subtrees. The distances to each vertex X from X's root Y equals to d(U,X)-d(U,Y). So we may treat roots as special vertexes. Most of subtrees will have only one special vertex — the root. They may be processed in O(N) in total. For the other subtrees we recursively call the same procedure.

This process seems to terminate quickly. On every step each subtree will lose 2 special vertex, but it may possibly generate some new. The more subtrees there are, the faster the special vertexes are lost. It seems all vertexes will be processed in O(K) iterations and problem is solved in O(KN).

It's no good storing vectors in segment tree in this case. It will slow down updates to linear. Second one is not exactly good because you will have to be careful with the order of operations.

What I meant was to get the usual increase interval — get minimum on interval tree to support the array of in-degrees with some values in each node. One value is what the minimal value is, second is where any instance of this value on this segment is located and also you have to store all the stuff for lazy propagation.

Now when you are done changing degrees after processing the node you need to look for unprocessed vertexes with zero degree to add them to the queue. You check that minimal degree is zero and while it is you ask for any instance, set value in tree to inf and put into queue.

You may get global minimum from segment tree and its position. If it is zero then you have found arr[i]=0, if not then there aren't any yet.

Just don't foget to set used arr[i] to inf so that they won't be found again

It will take longest time if it fails to augment the matching. Then it will have to look through all edges in adjacency lists of reachable nodes. So we take a full bipartite graph with n/4 + n/4 nodes and another n/2 nodes connect to any node in the right half, m=n^2/16+n/2. Ignoring the part where we find matching in full part the total number of times we will look at some edge is n/2 (m-n/2+1) = O(nm)

dp[i][j][k] = Is it possible to complete the string after placing first i digits so that placed digits are (j=0 — equal to, j=1 — smaller then) corresponding characters of n and (k=0 — not having, k=1 — having) any non-zero digits.

dp[n][0][1]=dp[n][1][1]=1. Others equal to zero.

There are two or three ways to move from dp[i][j][k] to some dp[i+1]. We may try placing x, y and (if we don't have any non-zero digits) 0.

We now only need to restore answer starting from state [0][0][0].

Solving B with DP was pretty straightforward and had no corner cases. There was no need to solve it greedily.

My solution (http://ideone.com/ahuhnB) is a little different from described here. For each point I generate a set of vectors from it. The number of right and obtuse triangles is equal to number of pairs of vectors with non-positive scalar product. To find it I rotate the vector and support the set of such vectors. Once it becomes co-directional with one vector I increase number of bad triangles by number in the set. Supporting it is quite simple since a vector enters this set from the moment it coincides with one of orthogonal vectors and leaves after it coincides with another. So I put into the set of events for each point 3 events: add point, query result, remove point. I start with vector slightly above vector (-1,0) and make a full circle counterclockwise.

Replace ai and bi with xi=bi and yi=ai+bi . You can restate problem in the following way: for each bet you take you receive xi and in case of proper outcome you pay yi. Now notice that for the chosen subset of bets, you receive sum of their xi and may lose maximal of three sums of yi for W,D,L respectively. Iterate over maximal loss X and pick best subsets of bets with loss <=X. Your dp suits it quite perfectly if you replace a and b with x and y.

The "every ice cream forms a connected subgraph" condition means nothing, unless graph is specific. In case of a clique any pair of vertexes are connected. That means there are absolutely no restrictions. You can easily reduce any vertex coloring to it.

That is not entirely correct :). A graph with only one vertex and no edges is usually considered connected. But you have just proved that it isn't.

My point was that an expression, opposite to graph being connected is "Exist u,v from V such that there is no path between u and v". You can't select anything from empty set thus it is not correct, thus empty graph (if it is really a graph) is connected.

But you can't say that an empty graph is not connected? Unless you can provide two vertexes, that aren't connected by any path.

I doubt that it will be another unknown language round. Why would they open 24-hour hacking for such a round?

You should read capitals first, then edges, not vice versa.

I just happen to know some old problem that is named after this sequence and asks to find exactly it.

I believe this is exactly what you want.

Where is this problem from?

This one http://codeforces.com/contest/724/problem/G is also similar to what you ask. Only in this you have to find sum of all possible values, not the maximal one.

Well, this way of has its pros and cons... I prefer to use it only when solving flow problems. For example, you may want to find quickly the edge, which goes in the opposite direction. If you add edges in pairs, the opposite of E is E^1.

Actually there was an idea for a different solution, one with complexity O(log^2(n) log(n c0) ).

Let's assume that c0<=c1. The tree construction from editorial can be viewed in a different way: We have an infinite binary tree with some cost assigned to the nodes. We assign c0+c1 to the root. The cost for the left child is cost of parent + c0 and cost for the right child is cost of parent + c1. We want to select the subset with minimum total cost, since total cost equals to the problem's answer. For the sake of simplicity, before we proceed let's add (c0+c1)*(n-1) to the answer and subtract c0+c1 from every cost.

Let's do binary search on the biggest cost, that we are going to use. To do so, we will need to be able to count the number of nodes with cost, less or equal to C. To count them we use the fact, that it is never necessary to used more than log2(n) expensive letters. So we may iterate on the number of them and sum up the count. If we denote j as the number of expensive letters, then we will be able to use up to of the cheap ones. Their total count is . This trivially equals to .

Now we know the cost of the most expensive node, we are going to use. How many such nodes are we going to use? n-count(C-1). So now we need to add all nodes, whose cost is less or equal to C-1.

Once again we iterate over the number of expensive nodes j. For taking all the nodes with cost up to C-1 we will have to pay . Probably we may stop at this sum, if we are satisfied with linear solution. To get a fast solution we have to sum it up. After some transformation it may be reduced to

20620974 implements this solution with complexity O(log^2(n) log(n c0) ).

Yes, we can. I prefer the implementation from e-maxx . There is also riadwaw's implementation in second revision of this comment with some fancy C++11 stuff :) . All the usual treap methods are in private section.

And split still works in the usual way. Let's assume we split node into trees with values < x and >=x . We arrive to some node. If it has value other than x, we do the usual. If it has value x, we know, that right subtree is definitely >=x since it has elements greater than or probably some equal to x. Thus root with its right subtree is the right tree for answer and we should split left subtree. Still works in O(height).

Treap can easily answer a query "How many integers are there in range [a,b)?". You just hold count in every node like you would do for treap with implicit key. Then to get answer you split by a, then the rest by b and get count from the middle tree. Then merge everything back together. Getting frequency of x is same as asking number of integers in [x,x+1).

Strange. I was sure, that there could be a problem with balancing since priorities don't actually define the tree structure. If all keys are different and all priorities are different, only one treap can be built. With same keys we may have any tree we like. Probably randomness still help in some way after all.

No, it is absolutely different case. If I have a sorted input, I can still have a balanced tree with height O(log N). But only possible binary search tree for N equal elements seems to be a list, unless we allow equal elements both into left and right subtree.

Probably that depends on the way you treat the equal elements. If you say that all equal go to left / right subtree, than the tree with N nodes with equal keys will degenerate into a list. Thus all the operations will take O(N) time. Maybe there is some other way, but i'd prefer to simply make equal elements different in some way.

Maybe compiler threw away for with j during optimization, since it is never used.

I don't know. Just guessed that there may be problems, when there is no square root of 5 for Fibonacci numbers. And 13 was a suitable one.

If we have a sequence x[n]=A x[n-1], all eigenvalues of A exist and distinct mod P and none of them equals to 0 mod P, then it will definitely be periodic with period that is a divisor of p-1. Thus A^p - 1 = I (mod p). Can't say anything more general.

The "for any matrices" part is not true. For example we may consider Fibonacci numbers matrix F=[1,1;1,0] and mod=13. F^12 (mod 13)=[233, 144;144,48] (mod 13) = [12,1;1,11]. And the least power, for which F^k (mod 13) = [1,0;0,1] is k=28. And it's even not divisible 12.

It may work in this particular problem, but won't work in general.

Ah... I thought you tried remembering answers in your solution. Everything I wrote has nothing to do with your then. :-) Maybe your work in Fib(n) or something similar since on each step when you have a non-isolated house you will either discard one or at least two nodes.

The fourth passed because it is actually if you consider houses in ascending order of numbers and store everything in map. The proof is simple. Let's split masks into two types:

1. Have any houses with number <= n/2. This means we are still processing first houses. And we can process them in ways. Thus there will be only masks of this type

2. Have no houses with number <=n/2. There are only n-n/2=n/2 of those. Thus there are only masks also.

So we will store in map at most masks. And total complexity because of map is as stated.

There was an IPSC problem (H) in 2014 that asked to create a test case that breaks both GCC and OpenJDK implementations of hashset. You may read the solution here

I didn't know about "file" command, but just from looking through file in binary I noticed "/mnt" string. And for me this was a clue that it might be a mountable thing, maybe some file system. So I tried mounting and it worked.

P.S. And this is exactly the way ISO images are mounted here in Linux :)

There are really small Linux LiveCDs. Like 50 MB distributions or less.

Yes, it works on these tests. They are not hard actually.

The main idea is that after you decide what the debt Y will be after you pick all with zero utility, the first and second part become nearly independent. What is left to do is to partition all tasks into these two sets such, that debt after processing the first one will reduce from X exactly Y and the sum of utility after processing second one with initial debt Y is maximal. That is what we need DP for. On each step we decide whether we solve the task in first part (it must have zero utility then) or in the second.

My solution is O(nx³). It is obvious, that we should start by solving tasks, that will add 0 to utility. Only after that we will start solving other ones. The order doesn't matter for the first part and for the second part we should solve the one with higher a. Now, let's just iterate over the debt X after first part and calculate the best result with DP[i][j][k] — best utility that we can get by solving tasks starting with i, so that we reduce debt for the first part to j and to k for the second part having the debt after the first part exactly X.

No, it's not reasonable at all. The program either compiles or doesn't regardless of the testcase.

You are from Crimea, so they won't even show you the rules that say you can't participate ;-) Unless...

Well... It seems that A is expected number of dances if we assume that when bad situation happens we immediately stop. And B[i][j][k] is the probability that we will run into a bad situation. So the result A[N][M][0]/(1-B[N][M][0]) becomes pretty much like yours :)

I might suggest a way to improve binary search solution by removing the binary search :). Let's assume dp[N][M][0] equals to some unknown X. Now in all formulas for dp we can use X instead of dp[N][M][0]. Thus dp[i][j][k] will be of the form A[i][j][k]+ X B[i][j][k]. The only thing left is to find X from equation X = A[N][M][0] + X B[N][M][0] which is trivial. Essentially binary search tries solving exactly it.

For some reason I can see myself in this list, despite not being onsite. Is it OK?

P.S. Nevermind. It seems every contest participant can see himself even if he is not in the list.

Well, if you put it that way... Your code on my notebook runs in one and a half minute. And it can be further reduced by half a minute by replacing set with priority queue. And did you compile it with optimisations ? Without them it indeed runs in 7-8 minutes.

Well, you can speed up your solutions K times by noticing that you can actually split coloring vertexes with even and odd distances to root and thus eliminate one of the parameters — the color of current node.

I heard this kind of problem can be dealt with in the following way: Let's not subtract r from l :-) . We may define h=r-l and halve it after each step. The while condition will be h>eps.

But I only heard about it and never used it. Iterative search seems more reliable...

Nice trick. I wish I'd come up with that. Instead I decided that it is possible to compare the angles by comparing there respective cos. The bigger the cos, the smaller the angle. And cos(a,b) = dot(a,b)/|a||b|. |a| contains sqrt, so instead we can compare sign(cos(a,b)) * cos(a,b)^2. This way we will no longer need doubles. The only problem is that numerator would be of order 10^16 and so would be the denominator. Because of this I had to resort to using big integers...

What do you mean by "got rid of path compression". It still seems to be in find, isn't it? And if you have path compression, you are guaranteed to be at most O(log N) on average per query.

I used different tree. It could perform three operations: add V to segment, get minimal value and count its frequency. As you can see, reversing values just wouldn't do the trick.

Anyway, it is always nice to know different approach :).

I know how to solve the rectangle union area. I think I even solved it once :).

I was just curious if we can calculate the length of segment's union directly. At least I got the impression that it was a proposed solution after reading the explanation. Maybe I misread it somehow....

Really nice editorial. I was just looking for something like that. But I would like to make some remarks

Why would we count 4 points, if we pick B as a center? There are definitely 5 points on that line, aren't there? Maybe the problem is that you sort points by the angle in range (-pi, pi] and it corresponds to sorting points by rays, not by lines. The angle between the line and x axis lies in range [0,pi) or (-pi/2, pi/2] whatever you like more. This doesn't affect the result at all, it is just not a reason to complain about solution not working properly, since you actually implemented the different one :)

Do you know some special segment tree, which will be able to get the necessary sum for "Rectangle union area"? I only know about a segment tree which can calculate exactly the opposite thing, i.e. the length of segments, that are not covered by any rectangle on the line.

I couldn't understand what kind of problem is being solved in "Don't mess with the circles". The part "determine the minimum radius circle of a fixed radius R" is really hard to understand. I suppose the "minimum radius" is not meant to be there :)

I came up with same approach, so I will try to explain how it works. You know, that F(n,0)=S(n,0)+1=n+2=C(n+2,1); F(n,n)=S(n,n)+1=n+2=C(n+2,1)=C(n+2,n+1). We know, that F has the same recurrence relation as C. Let's try calculating some other values. For example F(2,1)=F(1,0)+F(1,1)=C(1+2,1)+C(1+2,1+1)=C(3,1)+C(3,2)=C(4,2). So the good guess would be F(n,k)=C(n+2,k+1). You can prove it by induction.

Actually I am prone to disagree that recurrence relation will necessarily result in combination(i+a, j+b) as a solution. It really depends on boundary values. It could have been twice the combination of some values or even not a combination at all. But it always seems to be some sum (finite or infinite) of combinations

I guess it must be pretty similar solution. Let's have an array of bits pos[N]. pos[i] equals one iff a thief can be at position [i]. After an attempt to find him at v we set pos[v]=false. and pos on next step equals to (pos<<1 or pos>>1). He will get away if there is at least one non-zero bit after all steps. The complexity is N^2/64.

Well... I noticed that this problem was similar to one on Timus when it was too late to change anything. I've actually solved both these problems long time ago, though it seems I have not-so-beautiful solution with bitmasks for the second one.

Maybe i'm missing something, but what about A=true, B=false, C=true, D=true? Then we will get 4 calls. Why isn't it possible?

No, you wouldn't. It changes: 3 2 1 5 4 -> (3 1)(2)(5 4) -> 3 1 2 5 4

Oh, but it passes :). Just change cin,cout to scanf,printf and send to Visual C++ 2010 B-). For some reason other combinations don't work.

Isn't it just a stack, that will have at most n elements pushed and hence at most n elements popped?

I guess you are right. The thing is the expression never contains square root of five. So we don't really care whether it even exists. It is nice if it does, but it is totally unnecessary. For example my program (link) can calculate Fibonacci numbers modulo 3^6*7^2=35721. And there is no x such that x*x=5 mod 35721. The trick is to work with numbers, similar to complex, with only one difference that i*i=5, not -1.

Nevertheless you can actually use this formula to calculate Fibonacci numbers modulo any odd number. You just need to calculate it not with the help of doubles, but numbers of the form . They have properties similar to complex numbers. For example the product of two numbers equals .

And because of special structure of this formula, the answer is , where Im takes the part right next to square root of five (I called it so because of similarity with complex numbers). So you only need to be able to divide by two and that can be done modulo any odd number.

It seems your program fails on this test:

1
1 3
2  
ABC
ABC
CBA

My DFS solution runs in time. I built it based on simpler solution, that runs in: O(3ⁿ) time. Let's start with sorting nodes by number, given in input. We encode our state as pair i,j — means that we have considered first i nodes, some of them connected and mask j contains all nodes, that have no parents. First note that i is redundant, since the last one in mask is obviously the last node considered, so i equals last bit +1. Let's consider all subsets of this mask and pick each that have at least two bits set and required sum. It is known that total amount will be 3^n. And if we precalc all sums and bitcounts, we will be able to solve problem in O(3ⁿ)

Now let's remove all leafs from mask. Then we will have state i,j — we considered some first nodes and now we have i leaves without parents and inner nodes described in mask j.

It won't do. Once you try to increase element, there is no reliable way to determine the new value for all intervals, which contain it. You can only decrease elements in this case.

Upd. Sorry, didn't notice min(a[i],x) in topic

I suppose you can solve it with

dp[i][j][k][l] — can you build an i-digit number with sum of digits j, sum of digits of number, multiplied by D so far equals to k and we have l carry in that number.

The idea is that we build the first number and simultaniously build the second one. And since the second one can be one digit greater than first, we must store that additional digit l.

Upd: Sorry :) forgot to count the complexity and it turns out 900^3

I guess mincost flow is much easier for this problem than dp

It's not. Your input is wrong, since it is impossible to generate it in the way, described in statement.

int pow(int a,int b,int m)
{
  if(b==0) return 1;
  else if(b%2==0) return pow(a*a%m,b/2,m);
  else return pow(a,b-1,m)*a%m;
}

actually 10^9 is 10 digits, so your arrays are too small.

It is impossible input since numbers must be in non-decreasing order

Maybe code will speak better than words? http://pastebin.com/XEjuaB7w

No, it is not like this. We store for each node of segment tree 5 values: left and right value of segment, their frequences and answer for this segment. With this information we can merge consequent segments in a simple way. Now, if we need to answer query, we select the nodes of segment tree, which cover the interval, and merge them left to right.

Your idea is correct. But you mistyped on rows 108-109. At least there are some small mistakes. By the way it is not important which number is the most frequent in whole segment

Yes it is :)

DSU is "disjoint set union" ( wikipedia ) :)

Hm. I haven't thought about that, because merging segments wasn't difficult. And there may be some problems with not counting some segment twice if you just find the largest segment.

I've just solved this problem offline with the help of DSU and segment tree, which supports adding of arithmetical progression to interval and get sum on interval. The tree was used to count the number of intervals of particular length.

I don't know any way to count SCC other than to find them all with the help of algorithms you mentioned in your post.

even faster and in C:

len=sprintf(buf,"%d",x);

With the help of MB (by the way it is useless, since MB is just transposed MA ) you may check if there are paths TO starting vertex. If there is a path in MB from A to B, then in real graph there will be path from B to A.

This algo will not help you to find SCC, only to check if graph in whole is strongly connected.

You can try solving http://acm.timus.ru/problem.aspx?space=1&num=1198&locale=en . I can't remember any other link to problem, related with SCC.

I didn't really understand why should the algo, that you described, work. I think both conditions must be satisfied. In my opinion algo should be like this:

Select some vertex A. Run dfs from A in matrix MA and count the number of vertices. Then run dfs from A in matrix MB and also count the number of vertices. Both numbers should be equal to number of vertices in graph.

This algorithm will work, since we may build the following path from U to V: U -> A -> V. And the check of number above will guarantee that from every vertex we can reach A and from A we can reach V.

The cone can be nicely intersected with parametrized line: x=x1+t*(x2-x1) . And the segment is parametrized line of form above with t in [0,1]. I hope this helps