Edvard's blog

By Edvard, history, 9 years ago, translation, In English

652A - Gabriel and Caterpillar

The problem was suggested by unprost.

Let's consider three cases.

  1. h1 + 8a ≥ h2 — in this case the caterpillar will get the apple on the same day, so the answer is 0.

  2. The first condition is false and a ≤ b — in this case the caterpillar will never get the apple, because it can't do that on the first day and after each night it will be lower than one day before.

  3. If the first two conditions are false easy to see that the answer equals to .

C++ solution

Also this problem can be solved by simple modelling, because the heights and speeds are small.

Complexity: O(1).

652B - z-sort

The problem was suggested by Smaug.

Easy to see that we can z-sort any array a. Let be the number of even positions in a. We can assign to those positions k maximal elements and distribute other n - k elements to odd positions. Obviously the resulting array is z-sorted.

C++ solution

Complexity: O(nlogn).

652C - Foe Pairs

This is one of the problems suggested by Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A.

Let's precompute for each value x its position in permutation posx. It's easy to do in linear time. Consider some foe pair (a, b) (we may assume posa < posb). Let's store for each value a the leftmost position posb such that (a, b) is a foe pair. Denote that value as za. Now let's iterate over the array a from right to left and maintain the position rg of the maximal correct interval with the left end in the current position lf. To maintain the value rg we should simply take the minimum with the value z[lf]: rg = min(rg, z[lf]). And finally we should increment the answer by the value rg - lf + 1.

C++ solution

Complexity: O(n + m).

652D - Nested Segments

The problem was suggested by Alexey Dergunov dalex.

This problem is a standard two-dimensional problem that can be solved with one-dimensional data structure. In the same way a lot of other problems can be solved (for example the of finding the maximal weighted chain of points so that both coordinates of each point are greater than the coordinates of the predecessing point). Rewrite the problem formally: for each i we should count the number of indices j so that the following conditions are hold: ai < aj and bj < aj. Let's sort all segments by the left ends from right to left and maintain some data structure (Fenwick tree will be the best choice) with the right ends of the processed segments. To calculate the answer for the current segment we should simple take the prefix sum for the right end of the current segment.

So the condition ai < aj is hold by sorting and iterating over the segments from the right to the left (the first dimension of the problem). The condition bj < aj is hold by taking the prefix sum in data structure (the second dimension).

C++ solution

Complexity: O(nlogn).

652E - Pursuit For Artifacts

The problem was suggested by Alexey Dergunov dalex.

Edge biconnected component in an undirected graph is a maximal by inclusion set of vertices so that there are two edge disjoint paths between any pair of vertices. Consider the graph with biconnected components as vertices. Easy to see that it's a tree (if it contains some cycle then the whole cycle is a biconnected component). All edges are destroying when we passing over them so we can't returnto the same vertex (in the tree) after leaving it by some edge.

Consider the biconncted components that contains the vertices a and b. Let's denote them A and B. Statement: the answer is YES if and only if on the path in the tree from the vertex A to the vertex B there are an edge with an artifact or there are a biconnected component that contains some edge with an artifact. Easy to see that the statement is true: if there are such edge then we can pass over it in the tree on the path from A to B or we can pass over it in biconnected component. The converse also easy to check.

Here is one of the ways to find edge biconnected components:

  1. Let's orient all edges to direction that depth first search passed it for the first time.

  2. Let's find in new directed graph strongly connected components.

Statement: the strongly connected components in the new graph coincide with the biconnected components in old undirected graph.

Also you can notice that the edges in tree is the bridges of the graph (bridges in terms of graph theory). So you can simply find the edges in the graph.

Not too short C++ solution

Complexity: O(n + m).

652F - Ants on a Circle

The problem was suggested by Lewin Gan Lewin.

The first observation: if all the ants are indistinguishable we can consider that there are no collisions and all the ants are passing one through another. So we can easily determine the final positions of all the ants, but we can't say which ant will be in which position.

The second observation: the relative order of the ants will be the same all the time.

So to solve the problem we should only find the position of one ant after t seconds.

Let's solve that problem in the following way:

  1. Consider the positions of all the ants after m time units. Easy to see that by the first observation all the positions of the ants will left the same, but the order will be different (we will have some cyclic shift of the ants). If we find that cyclic shift sh we can apply it times.

  2. After that we will have only t ± od m time units.

So the problem now is to model the process for the one ant with m and r ± od m time units. Note that in that time interval the fixed ant will have no more than two collisions with each other ant. So if we model the process with ignoring all collisions except the ones that include the fixed ant, we will have no more than 2n collisions.

Let's model that process with two queues for the ants going to the left and to the right. Each time we should take the first ant in the queue with opposite direction, process the collision and add that ant to the end of the other queue.

Hint: you will have a problem when the fixed ant can be in two different positions at the end, but it's easy to fix with doing the same with the next ant.

C++ solution

Complexity: O(nlogn).

  • Vote: I like it
  • +43
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Hello,

A) Thx for contest .. I loved the problem-set :)

B) I see one of the complexities in Russian in English version [problem 'D'] : "Сложность"

»
9 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Hi Edvard

About C In such a situation: arr: [2, 4, 3, 1] Foe = (2,1), (3,4)

z[0]: {3}
z[1]: {2}

Your solution will work like this :
Initially, ans = 0, rg = 3
ans += 3 , (i=0, rg = 3)
ans += 1 , (i=1, rg = 2)
ans += 0 , (i=2, rg = 2)
ans +=-1 , (i=3, rg = 2)

So your answer is = 3

but clearly the answer is 6
In arr: ((2,2), (4,4), (3,3), (1,1), (2,4), (3,1))
In index: ((2,2), (4,4), (3,3), (1,1), (0,1), (2,3))
Please tell me if I am missing something.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that's because author is using very many redefinitions.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please check the code of the solution. The solution will be more clear for you after that.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      Hi Edvard

      I am quoting the code in the solution. As per the code you shared the solution for this example is 3: arr: [2, 4, 3, 1] Foe = (2,1), (3,4)

      But there are 6 intervals. So either the code is not correct or I am missing something. Please do have a look.

      Thanks

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        In the outer for-loop ,loop variable 'i' is decreasing (from n to 1 ,written as 'nfor' ).

        	nfor(i, n) {
        		forn(j, sz(z[i])) rg = min(rg, z[i][j]);
        		ans += rg - i;
        	}- 
        
        So,
        Initially, ans = 0, rg = 4( rg is initially n) ,i  is index .
        ans += 1 , (i=3, rg = 4)
        ans += 2 , (i=2, rg = 4)
        ans += 1 , (i=1, rg = 2)
        ans +=2 , (i=0, rg = 2)
        finally ans = 6.
        
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution to problem E please!

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everyone . Can someone please Help me in solving Problem A? I have seen several Solution . But failed to understand .

Can Anyone please Help ??

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Let's say we have this input data:

    10 90
    4 1
    

    This means that at 2 PM there is an apple on the tree at height of 90 cm, and at 10 cm height sits the caterpillar. We know, that between 10 AM and 10 PM caterpillar goes higher 4 cm/hour. When it's 10 PM caterpillar goes to sleep and slips down 1 cm/hour, until it's 10 AM again. So we have the process:

    2 PM => 10 PM - goes UP a cm/h
    10 PM => 10 AM - goes DOWN b cm/h
    10 AM => 10 PM - goes UP a cm/h
    ...
    10 AM => 10 PM - goes UP && gets the apple (if he can)
    

    In our case caterpillars movements are:

    10 => 42 (10 + 8h * 4 cm/h) - climbing (day 0)
    42 => 30 (42 - 12h * 1 cm/h) - sleeping
    30 => 78 (30 + 12h * 4 cm/h) - climbing (day 1)
    78 => 66 (78 - 12h * 1 cm/h) - sleeping
    66 => 90 (66 + 6h * 4 cm/h) - climbing (day 2) && got the apple
    

    In the middle of the 2-nd day the caterpillar is high enough to reach the apple, so the answer is 2.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "sleeping" ?? :D Sorry for nitpicking. You clearly meant "slipping".

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        He slips while sleeps :D

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh yeah, you mentioned! I surely ruined the fun out of it! ;) By the way, were you the author of this problem? (I can't find the author information for any particular problem! :| )

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Genius Simply .. I like the Statement & Way of your Derivation .

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought that since the boy's school is closed at 2 pm, so he sees the caterpillar first at height h1 at 2 pm . So, the caterpillar should be at 10 cm height at 2 pm . I think a little more careful problem statement was required in A .

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Any thoughts on problem F?

  • »
    »
    9 years ago, # ^ |
    Rev. 10   Vote: I like it +10 Vote: I do not like it

    You need to make a couple of observations:

    • Since the ants bounce against each other, the relative order never changes.
    • We can plot the movement of the ants by putting the position on the x-axis and time on the y-axis. Then a single ant would be a line with slope  ± 1. What happens when two ants collide? They reverse, but since the lines have slope 1 and  - 1 respectively, you can continue drawing each line. Here's what I mean: image. The best way to look at this is that once two lines cross, the ants on each line 'switch' lines.
    • Based on the above, we can then find all final positions, after all, each line will always contain some ant (not necessarily the initial ant), so the end positions are . You can sort these end positions. Since the relative order of the ants never changes, all you have to do is 'rotate' (as in, cyclical permutation) these final values and you're done. Now comes the hard part: how much will we have to shift the end positions?
    • Fix a specific x position, say x = 1 / 2 (also, just to be clear, we have a cyclical x-axis with 0 and M joined together). Without loss of generality, label the first ant to the right of this position as ant 1. Now imagine a line going straight up from this position (recall that our x-axis was position, and our y-axis was time), and for all lines (or maybe paths would be a better term) calculate all y-positions at which this line intersects with our line at x = 1 / 2 (it's fine to round these y-values up to the nearest integer).
    • Now move forward in time. The first ant to the right of x = 1 / 2 is some ant i (initially ant 1). What happens when a line crosses x = 1 / 2 from left to right? Now the first ant to the right is ant i - 1. From right to left? Ant i + 1. If you keep doing this, eventually you'll reach y = T and you'll know the number of the first ant to the right of x = 1 / 2. We already calculated all the final positions, and since (again) the relative order of the ants doesn't change, we can now trivially give each ant its final position.
    • There is one small problem: T is very large, up to 1018. You can work around this by noting that since all lines have slope 1 or  - 1, after M timesteps they'll end up at the same x-position again. During these timesteps, the first ant to the right of x = 1 / 2 may have changed, but other than that, the situation is exactly the same as it was during t = 0. In other words, after M timesteps the number of the first ant to the right of x = 1 / 2 shifts with some k, so after T / M (integer division) it shifts (T / M) * k (in fact, k is rather easy to find: since all lines will cross our vertical line at x = 1 / 2 exactly once in any interval of M timesteps, k = a - b where a is the number of lines with slope 1, and b the number of lines with slope  - 1). After this, you will have to do another T%M timesteps, but since T%M < M$, every line crosses our vertical line exactly once, so you can just simulate this process (and by simulate, I mean checking the intersections passing our x = 1 / 2 line individually, not simulate all the ants).

    The final complexity is .

    Hopefully that made some sense, it should be enough to solve the problem. Here's my solution by the way: 16961705

    EDIT: Here's an even shorter solution: 16970841. Very simple compared to the one in the editorial :)

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +15 Vote: I do not like it

    Actually it can be solved without any simulation. Time still will be O(n ln n) due to sort.

    1. Let sorted starting positions be p_1, ..., p_n.
    2. As explained in author's solution, we can calculate final positions. Let them be q_1, ..., q_n (also sorted).
    3. Let's calculate total (oriented) speed S of ants. It's some number in [-n, n]. After multiplying it by t we will have total (oriented) movement. There is some trick here: as t is very large, S * t will overflow 64-bit integers. But we can calculate it modulo n * m.
    4. Let's calculate offset O between starting and final position (q_1 — p_1) + ... + (q_n — p_n). We can also calculate it modulo n * m.
    5. Proposal: (S * t — O) is divisible by m. To prove it we need to reсall how q_i was calculated.
    6. Let offset = (S * t — O) / m. Then ant that was on p_1 position on start will be on position q_(1+offset) on finish.
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Very nice! It looks that W4yneb0t implemented that solution.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had troubles understanding this. Could you give a more detailed proof on why this works please?

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Which part needs explanation?

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't understand why this would work. How come ((S*T)mod(N*M)-O)/M = answer.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain why "p_1 is equal to q_(1+offset)" ?

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's not equal, it means that ant from position p1 will move to position q1 + offset. Here is a proof:

        Let ant from position p1 finishes at position q1 + t. Then ant from p2 moves to q2 + t etc. Then total (oriented) movement (total oriented distance traveled by ants) equals

        (q1 + t - p1) + ... + (q(n - t) + t - pn - t) + (q1 + m - pn - t + 1) + ... + (qt + m - pn) = O + tm.

        (last t summands have +m because ant will go full circle before arriving to that position). On the other hand it equals S·t. So t = (St - O) / m.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I don't really understand this idea, could you explain why you add m. Isn't everything already mod m, why would it matter?

          Edit: actually I am more confused now why the left hand side is equivalent to S*t.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Positions are mod m in a sense, but e.g. speeds aren't.

            Left side is S*t because it's total oriented movement. So on the one hand it's speed multiplied by time, on the other — difference between finish and start positions.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              But the offset doesn't seem like enough, for example a single ant can go around the circle many more than 1 time but this doesn't seem to be accounted for in the total oriented movement.

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Another solution without simulation:

    First, relabel the ants such that they are in increasing position with respect to their indices. We can reverse this relabelling at the end.

    Next, imagine that each ant has a sign. When two ants pass each other they exchange signs. Consider the first ant (assume he is going right) — we know where it will eventually end up but we do not know what sign it will hold. Notice however that when the first ant meets another ant, the sign the first ant holds will increase by one. So we simply sum up how many times the first ant meets another ant.

»
9 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Nsqrt(N) giving TLE in problem D :(

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hello,

I got question!

here I made two submitions of problem "D"

Accepted and TLE

The only difference in between them is "map" and "unordered_map" (One of them got TLE second Accepted (TLE with unordered_map))

it was hacked by this generator:

Anyway when I executed it in locale, the unordered_map is faster.

Can somebody please explain the magic behind this? :) Thx

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I was also hacked by this generator, but solution with unordered_map took ~7s and solution with map took ~0.38s on my machine.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm interesting ... I have "0m0.370s" for hash map and "0m0.583s" for map :/

      interesting :)

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 4   Vote: I like it +5 Vote: I do not like it

        Did you decrease the maximum load factor of the unordered_map when testing on your machine? Doing so makes the code faster and even acceptable.

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I'm sorry, I'm afraid I don't understand, what "load factor" means

          I just generated exact input and run it with "g++ -Wall -pedantic -Wno-long-long -std=c++11" (with the codes from above :/ )

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            Rev. 2   Vote: I like it +5 Vote: I do not like it

            You can check it out here. Since you didn't do it, it's pretty interesting that the solution with unordered_map ran faster on your machine.

            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oh, didn't know about this ~ Thx! :)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Visual Studio STL is different from GCC STL (aka libstdc++). For example, the following code

    int main() {
        std::cout << std::hash<int>()(100001) << std::endl;
    }
    

    prints 100001 for GNU G++/GNU G++11 and 1680716807 for Microsoft Visual C++ 2010. Also, unordered_set and unordered_map implementations themselves are probably different. So different STLs require different anti-hash tests. I guess that you are testing your program with Visual Studio while my anti-hash test is designed for gcc STL.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope, I tested under GCC STL (I think 4.7 version — if it can influence anything?)

      anyway interesting (nice hack btw — didn't even know about the possibility ^_^ )

      std::cout << std::hash()(N) << std::endl; returns same numbers as are arguments :O is it right?

      Thx man and have nice day!!

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Nope, I tested under GCC STL (I think 4.7 version — if it can influence anything?)

        Well, if my test doesn't cause slowdown, gcc version must influence something. There are nothing else to blame.

        returns same numbers as are arguments :O is it right?

        Yes (for gcc STL).

»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

It's also possible to solve the problem B in O(n).

Code: 16934709

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I believe this exact same problem exists in codechef's ex Easy section! And I did it the same way!

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we use MO's Algorithm for solving D ?

complexity seems good. but I tried it and I got TimeLimit

I don't know why ? can anyone help me. tanx

»
9 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Here's my solution to Problem E: 16955949

As explained in the editorial, we are interested in all Edge-Biconnected-Components on the path from a to b. Instead of building the EBCC-tree, we can easily obtain all vertices in these EBCCs by adding a new edge between a and b. Since it was given that there is a path between every pair of vertices, there are now two paths between a and b, and hence, they are in the same EBCC. Furthermore, all EBCCs in the original EBCC-tree will be contracted to a single component.

To find this EBCC, I used our normal code to find bridges and biconnected components, together with Union-Find. For every edge that is not a bridge, I merge the two (components) of the endpoints of the edge. Afterwards, I merge the components of a and b separately, because the algorithm fails when there is only a single edge between a and b.

Next, for every edge with an artifact, I check whether both endpoints of the edge belong to the component of a and b (using the Union-Find datastructure we built earlier). If there is such an edge, the answer is 'YES'. Otherwise, print 'NO'.

All together, this solutions requires almost no code apart from reading the input, the Union-Find and Biconnected Components algorithm.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Really brilliant idea to add edge from a-b to make they are in same EBCC.

    btw, if you can find EBCC correctly for multigraph, then only needed work is for any artifacts (u, v) check u.bcc == a.bcc and v.bcc == a.bcc.

    Here is my code: click

    In the code, used 'metParent' variable to handle multigraph(so if u — v have multiple edges, then do not classify as bridge)

»
9 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone please explain C using two pointers..I have been trying for 2 days but all my efforts are in vain.....Please???????????????

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In a sorted array work this rules:

    v[i] <= v[j] if i < j
    v[i] >= v[j] if i > j
    

    So you sort the array, and then build a new one using pair of pointers (1, n) or (1, mid) making one of this sequences:

    1, n, 2, n-1, 3, n-2 ...
    1, mid, 2, mid+1, 3, mid+2 ...
    

    The first one is simpler to implement, considering the case where n is odd

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the quick tutorial. Can you please tag the contest to this tutorial?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there are typos in the explanation of problem A:

In point 2, it should be a<=b instead of a>b.

In point 3, it should be ceil((h2-h1-8*a)/(12*(a-b))) instead of ceil((h2-h1)/(12*(a-b))).

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Shouldn't the complexity of C be at least O(n log n) . See these two for loops : nfor(i, n) { forn(j, sz(z[i])) rg = min(rg, z[i][j]); ans += rg - i; } Can anyone please explain a little bit ?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The total size of all z[i] is O(m). I've fixed the complexity from O(n) to O(n + m).

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      BTW, problems were really nice . Just A's problem statement was tough to understand.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How is the complexity O(n+m) ? If all the z[i]'s contains elements in decreasing order , then the second 'for' loop will have a complexity O(n) .

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem E How to solve if changing the route which originally (a to b) to (a to b then back to a)? Thanks!

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, Can anyone explain the editorial for problem D? I am unable to understand the use of Fenwick Tree for this particular problem. Also I am not sure but there seem to to be some typos in the editorial i.e bj<aj instead of bj<bi in fourth line and bj < bj instead of bj<bi in second last line. Please correct me if I am wrong?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good day to you,

    let's say you have an array (later Fenwinck → complexity) and for every END of segment, you add 1 to the value (I mean => if you have segment [1,5], then you do Array[5]++)

    PS: A necessary here is to make the values lesser (but preserve their order). So from [1,10000000],[3,50000], you would do [1,4][2,3] (otherwise you would not have enough memory for it)

    Now let us sort the array of segments by their beginning.

    Here, for every segment you do following operation:

    I) Sum all values of all elements of array, from 0 to END

    II) Substract END of this segment from array (so for [1,5] you would do Array[5]--)

    Now see, what happened to all segments. The sum of values is the number of ends, which end earlier, than END of current segment. How can we be sure that we didn't include any extra segment? Well it is thanks to (II). Here we already substracted values of ALL segments, which begin earlier, then our current segment (so we are considering only points which begin later and we are searching for those, whose END is earlier, than current END).

    Here you see, that the complexity is O(N^2). It is time to use Fenwick. It has exact property we want! Add/Substract a value of any one element (in logarithmic time) + get the sum of 0→END also in logarithmic time!

    If the explanation was confusing, or not enough, do not hesitate and ask for additional questions :)

    Good Luck man! ^_^

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks man. I got the idea.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to know when to use Fenwick tree ?

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have an alternate solution to F (maybe it's already in the editorial if I didn't read it properly).

Like in the editorial, we reduce the problem to finding the location of a single ant after x time units.

We plot the lines for each of the ants on the Cartesian plane, and "repeat" them with period m so that we have all the necessary lines. By necessary, I don't mean all infinity lines, because we only care about and will only query for up to m time units. This means that for the second sample input:

4 8 6
6 R
5 L
1 R
8 L

The lines for the ant 5 L are y=-x-3, y=-x+5 and y=-x+13. All other lines are irrelevant, because we can never reach them.

Now, notice that for any ant, it follows a path on the lines, and each time it reaches an intersection, it swaps — it jumps to another line. We can observe that this means that if the ant starts at the k-th lowest line, it always stays on the k-th lowest line.

So since we have all necessary lines, we can find the value of k, and then find the k-th lowest y-coordinate to find the final location of the ant.

We can use this algorithm to find the cyclic shift per period, as well as the final movement of the ant.

Accepted solution: 17126112

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am trying to understand the complexity of the below submission for problem E (Its a nicely written code, btw).

http://codeforces.me/contest/652/submission/16927126

Especially the below line in dfs

    if (res == curIdx) {
      if (std::find(stack.begin() + curIdx, stack.end(), final) != stack.end()) {
      <more code>
      stack.resize(curIdx);
    }

The find method takes O(N). How to prove that the overall solution will not have O(N^2) for some worst case scenario?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! I wanted to share my solution for the problem D, using order statistics tree (see this article for more info about the data structure): My solution

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

dalex could not understand your solution for problem D. Please explain.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try this:

    1. Consider a plane (L, R). Each segment is a point (L[i], R[i]) on this plane. This is only for better understanding.
    2. If segment (a, b) is inside segment (x, y), x < a < b < y, it means that point (a, b) is to the right and to the bottom of (x, y).
    3. The problem is reduced to very standard problem: for every point on the plane count the number of points to the right and to the bottom of it.
    4. This is usually solved by sorting points by one coordinate and maintaining a fenwick tree by the other coordinate.
    5. Of course, first you need to compress coordinates, so all of them are in [0, 2*n-1].
    6. Iterate over points sorted by R, when you meet point (a, b), increase tree[a] and then count the sum tree[a+1] + ... + tree[2*n-1]. Here, tree[x] is 1 if we have seen the point with first coordinate equal to x, and 0 otherwise.
    7. This sum contains the number of points that have greater first coordinate (because you start summing from a+1) and less second coordinate (because points are sorted by R, so only points to the bottom of line y=b are summed).

    My solution is available in my last submits.

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem E Pursuit for Artifacts, is it always possible to have a path from A to B passing some artifact edge E if all of them are in same biconnected component?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    It's true, but it's not that easy to be proved. Every biconnected graph can be constructed as follows: first we have a loop, and each time we add a path on it. We choose a loop that contains an artifact edge E, then we can construct a path passing the edge E, by moving vertex A and vertex B to older paths or loop in the structure above.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. Let (u,v) be the artifact edge. Suppose for every path p1 from A to u and p2 from B to v inside the component p1 and p2 have common edges. You can see that there exists a certain edge e* in the component for which every such pair of paths p1' and p2' pass through, otherwise you can construct disjoint paths. This edge e* separates the biconnected component in two which leads to a contradiction.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem E, what is the proof that if a single bi-connected component (let's call it $$$A$$$) has a 1-edge, then you one can go from any point in $$$A$$$ to any other point in $$$A$$$ that travels this 1-edge and never visits the same edge twice?