You don't need to find all cycles, just one.

If other cycles in this graph share an edge with this cycle you found, then by removing this edge you break the other cycles and make the graph acyclic. If there are cycles which don't share an edge with the cycle you found, then you of course can't make the graph acyclic by removing just a single edge from the graph.

Therefore it suffices to find just one cycle, as the editorial says.

Also I guess that there can be a lot of cycles in a directed graph, maybe too many to store.

It seems it's about O(2^len).

On each step you either put the digit that is present in this position in b or the greatest digit smaller than it. Like the first possibility lead to the same brute with len - 1 and the other one ends instantly.

I solve it with dfs, too. As a matter of fact, I prefer to considering its complexitiy O(|A|len). 'Cause we have greedy algorithm. First, we choose the maximun digit (also not greater than b₁) for a₁ and do it again and again. For example, if a₁ < b₁，we can disgard the limit of not greater than b₁, and then whatever remains, we just choose the maximun digit. But if a₁ = b₁, we just wait until a_i < b_i.

Can you give the proof of correctness of this solution?

Suppose that there is no 1 edge removal solution. Then your code will surely output NO, there is no way to topsort the edges with only 1 back edge.

Next, suppose that there is a 1 edge removal solution, and let that edge be from node a to node b. At one point, your code will do a topological sort from node b. Consider the result of that sort. Surely we shall have the back edge from b to a, but I claim there will be no others. Suppose a,b,c,d are distinct nodes. If there is a back edge from d to c, then there must be a path from c to d as well (because of how topological sort works). But then this cycle does not use the edge a->b at all, so removing the ab edge will leave a cycle, contradicting our earlier claim.

When your code does the topological sort from b, then, it will find a valid solution and print YES. Hence it is correct.

In each query you will add no more than 1 segment (size of set won't exceed q). And those that you touch when updating, you delete immediately, so it's q deletions at maximum.

t(i) is not made explicitly in the program. it is a model that helps you think about the question. What is important is how to determine v_1, v_2, ..., v_k.

I tried...

Problem E is a simple data structure. What you need to do is to build a Segment Tree. The lenth of it is n(that is, equal to 1e9), but do not build the whole Tree. Only if you want to get some information from the interval, you make it. In a word, that is a dynamic-building Segment Tree.(I don't know what its exact name in English)

Problem E is a simple data structure. What you need to do is to build a Segment Tree. The lenth of it is n(that is, equal to 1e9), but do not build the whole Tree. Only if you want to get some information from the interval, you make it. In a word, that is a dynamic-building Segment Tree.(I don't know what its exact name in English)

My solution (the same as author's):

0) Let's create set < pair < int, int >  > , where we will store all non-working days as {R_i, L_i}. The main rule is that segments should not intersect — then we can merge existing segments with new (or cut segment).

ans = n

1) K = 1, we should add segment [L;R] in our set. Let's find all segments where R_i ≥ L (it means that new segment and these can have intersection). We can find first such segment by lower_bound({L;0}) (remember that set sorted by R_i). While L_i ≤ R we should continue iterating over set, on each iterate we are merging segments:

-make L = min(L, L_i), R = max(R, R_i)

-erase segment {R_i, L_i} from set — now it is contained in our [L;R] segment.

-ans = ans + (R_i - L_i + 1) — formally we erased segment and made days [L_i;R_i] working (but we will change it later).

When we archieved L_i > R or end of the set, we make:

-insert our merged segment {R, L} in set

-ans = ans - (R - L + 1)

-print ans

Example: we had set = ({1, 1}, {5, 2}, {10, 7}, {13, 12}) adding segment with L = 4, R = 9

lower_bound({4, 0}) will find us first pair {5, 2}, 2 ≤ 9:

L = min(4, 2) = 2, R = max(9, 5) = 9

then pair {10, 7}, 7 ≤ 9:

L = min(2, 7) = 2, R = max(9, 10) = 10

then pair {13, 12}, 12 > 10, stopping and inserting resulting segment {2, 10}.

resulting set = ({1, 1}, {10, 2}, {13, 12})

2) K = 2, similar with previous one, but we are cutting stored segments (and insert them back at once) and do not insert something at the end.

http://mirror.codeforces.com/contest/915/submission/34172029

The idea is the following. We simply create an array of size n. array[i] = 1, if i is a working day, and array[i] if not. For each query L R k I update all elements between array[L] and array[R]. The sum of all elements is the answer.

But doing a range assignment / computing the sum takes O(n) time. Way too slow.

Since this are range assignments and range sums, the solution is obvious: lazy segment tree. This will give O(log n) per operations. Much better.

But a lazy segment tree will take O(n) memory. That is too much, since n is really big.

There are two approaches to fix this.

1) The first one is to compress the indices. (This means, if there are only the three queries 1 100 1, 50 150 1, 20 80 2, then the elements 1, 2, ..., 49 don't actually need to be represented by 49 single nodes. We can combine them, since they always have the same value. Similar with the other intervals. I.e. we can create an compressed array that represents the segments [1-19], [20-49], [50-80], [81-100], [101-150]. The first element will switch between 19 and 0 (depending it all elements in that interval are working days or not), the second one between 30 and 0, ... depending if the complete segment consists of working days or not.

2) The second approach is to make a dynamic segment tree. The idea is this: since q is not really big, we will only visit a small part of the tree. Most nodes in the segment tree will never be visited. So we can save quite a bit of memory (and time), if we only create the segments that we really need. We start with only one node [1-1e9]. If we need to go to the children, we simply create them on the fly. I.e. if we want to visit them, we simply create two nodes [1 — 5e8] and [5e8+1 — 1e9]. And if we have to go deeper on the left side, then we create more nodes there. Since one range query only visits O(log n) nodes, we have a total memory and time complexity of O(q * log n). In the implementation each segment will have to pointers pointing to the left and the right child, and which are possible null.

You can check out my implementation: 34199755

I used coordinate compression with normal segment tree with lazy propagation. Very easy solution. https://mirror.codeforces.com/contest/915/submission/83613121

Explanation for F Explanation for G

Edit:updated problem f link

Try to use scanf/printf mine solution too passed by using them.

Same here, I thought flow's best case runs in O(n^1.5) time (biparite graphs), even if a solution exists how come it can fit into the TL?

LOL