Gerald's blog

By Gerald, 13 years ago, translation, In English
It was enough for solving this problem to calculate for each letter: ac - amount of occurrences of letter c in first and second strings in input, bc - amount of occurrences of letter c in third string in input. If the answer is "YES" else "NO". 

Let's bust the "level" 0 ≤ i ≤ 106, in which assumedly the stone could hit. Let’s find the minimal number of square on this level. Then we can understand, how many squares there are on this level: one or two. Then we check with one or two ifs (if on this level two squares) if the stone is in corresponding square or not. If the stone is inside then output the answer. If we didn't find any square, where the stone is, output "-1".  

Let's sort the pairs (namei, ai) by ascending of ai. If there is an index i: 0 ≤ i < n that ai > i, then answer is "-1". Otherwise the answer exists. We will iterate through the array of sorted pairs from left to right with supporting of vector of results res. Let on the current iteration ai = n - i, then we must transfer the current man in the position ai. It can be done in C++ with one line: res.insert(res.begin() + a[i], man); 

Let's generate the weighted directed graph of all ramps. The graphs' vertexes are the important points on the line Ox, there are points: 0, L, xi - pi, xi + di. The graphs' edges are the possible ramp jumps: transfer from point xi - pi to point xi + di or transfer from vertex in neighboring vertexes (neighboring means that we get the next and previous important points on the line). The weights of these edges are correspondingly pi + ti and xv + 1 - xv, xv - xv - 1. We must note that in the transfers we can't get in the negative part of Ox, and we must delete this transfers.

Then we must find and output the shortest path in this graph from vertex 0 to L. This can be done, for example, with Dijkstra's algorithm for the sparse graphs. 


In this problem we must find the minimum spanning tree, in which the half of edges are marked with letter 'S'.

There are  n - 1 edges in this tree, because of it if n is even then the answer is "-1".

Let's delete from the given graph all S-edges. And there are cnt components in obtained graph. For making this graph be connected we must add cnt - 1 edges or more, that's why if cnt - 1 > (n - 1) / 2 the answer is "-1". Then we find cnt - 1 S-edges, that we must add to the graph, so that it become connected. If cnt - 1 < (n - 1) / 2 then we will try to add in this set of edges another S-edges, so that the S-edges don't make circle. We must do all of this analogically to Kruskal's algorithm of finding a minimum spanning tree. If we could get a set of S-edges of (n - 1) / 2 elements, that there are exactly cnt - 1 edges and no S-circles, then the answer exists, Then we must add to this set (n - 1) / 2 M-edges, that forms with our set of edges the minimum spanning tree, it must be done analogically with Kruskal's algorithm.

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

| Write comment?
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
It would be nice to see a proof why does such an algorithm work for problem E.
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It's easy to prove as well.
    If this algorithm outputs -1 then there are three ways:
    1) odd number of edges in the tree, that works correct
    2) () then there doesn't exist edges of first color that doesn't make a cycle
    3) You can't connect the graph with second type of edges, then you can't connect it at all, so it's correct
    So if output is -1, then answer doesn't exist.
    Why if output is not -1, then answer exists and correct?
    So you get cnt components, then you add cnt - 1 edges of second type, then you just add remaining second type edges (all counted as ), that all second type edges doesn't make a cycle.
    But you say there are the cycles that contains, two types of edges, when cycle appears you just remove one first type edge from the cycle. So the graph that you built is correct and it contains everything asked in the problem statement.
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      This is not complete, there is also another situation when you output -1. Let's say: we added all M-edges and got a spanning tree (none of your 1), 2), 3) conditions applies), but there is still a possibility for the answer to be -1.
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Ah.. Yes
        I have to change 3)
        You can't connect graph with second type of edges or you can't get second type of edges that doesn't make a cycle.
        Then it's -1 and it's correct.
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          Ok, but it is not clear if the algorithm checks this condiction correctly. I mean it chooses some S-edges which make the M-forest into a spanning tree and then until there are less then (n-1)/2 s-edges it adds new s-edges in such a way that no s-cycle appears. But why the success of such a procedure doesn't depend on the chosen (at the beginning) s-edges? Etc., etc. It's not as obvious as you say.
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it
            OK, what you say it's mistake when answer exists, but algorithm doesn't find it. And it's 3). (it outputs -1)
            Firstly, if you can't connect the components, but the answer exists.
            So if you add all the s-edges, then the components will stay the same, so if you can't connect the graph, then you can't connect it at all.
            Secondly, if you have m-edges, that doesn't make a cycle, you certainly will find and add them, because you firstly connect components, it doesn't matter what edges to connect with, since it's matroid (there will always exist and edge, that doesn't make a cycle, if there's larger set of edges, that doesn't make a cycle)
            so you just add the edges one by one until there are  m-edges. so you get m-edges set and s-edges set, you can remove some edges from s-edges set to get the tree.
            • »
              »
              »
              »
              »
              »
              »
              13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Ok, now it looks much better. The keyword here is "matroid". Thank you.
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can someone explain solution for problem C ?
sorry, but it is very unclear from the tutorial
  • »
    »
    13 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    OK, lets do it in English.

    Make vector q, where we will place people in right order, that will be an answer. Sort input people by decreasing of a, give them height from n to 0, place them in array m and go from begining of this array to the end. When m[i].a=0, just place them in vector q by decreasing of h. Notice, that they are the highest people. It means, that if we place some element in vector q on place ai, before him will be ai people, higher than he, that meets the problem.
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
There are n - 1 edges in this tree, because of it if n is even then the answer is "-1".
That would normally be correct, but here we can have roads that start and end at the same hut, so we can add such a road without changing the connectivity, can't we?
2 2
1 2 S
1 1 M
For this case, isn't the solution to clear both roads?
  • »
    »
    13 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    "between any two huts should exist exactly one simple path along the cleared roads". That case results in 2 paths from 1 to 2. Hence, we can't clear roads which connect the same hut.

    UPD: I misunderstood it. Your opinion seems correct based on the problem statement.

  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think, there is a path 1-1 which is not simple, therefore answer is -1.
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      There are always paths that are not simple: 1-2-1. Edges are bidirectional
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        The problem statement states that there is exactly 1 simple path. 1-2-1 is not simple so we don't need to count it.
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Ye, that was my point. 1-2-1 and 1-1 are not simple paths so they do _not_ invalidate the conditions.

          Either the author of the problem meant to say something else or the official solution is just wrong. I am betting on the second possibility.
          When I read that you can have a road starting and ending at the same hut, I was sure that this was added just to make it a little more tricky. Otherwise, what's the point?
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            I think the roads which begin and end in the same hut are useful to adjust one nearly right answer to a right one.

            for example, if I got S=10 M=9, and one road 2->2 is M, I can choose this road so that S=M=10.

            between any two huts should exist exactly one simple path along the cleared roads

            and the rule above is satisfied, too. because 2->2 is never used, for when it's used nd 2 appeared twice. so whether to choose 2->2 is not important.

            To conclude, the solution for problem E is wrong || the problem statement needs change.