KADR's blog

All-Ukrainian School Olympiad in Informatics: editorial (A,B,C,D,E,F)
By KADR, 14 years ago, translation, In English
The editorial is now completed.

Problem A: Gift (Roman Iedemskyi)

Suppose that the pair (A, B) is an optimal solution, where A is the number of gold coins in a gift and B is a number of silver coins. It is easy to see  that there exist two (probably equal) indexes i and j such that gi = A and sj = B. It is true, because in the other case we could decrease either A or B without changing connectivity of the graph.

Let R(A, B) be the graph in which for all i the following statement holds: .

Let T(A) be the weighted graph in which for all edges gi ≤ A. For each edge i we will assign a weight equal to si. Let's find a spanning tree of this graph, which has the property that its maximal edge is minimal possible. It can be shown that for the fixed A the minimal value of B for which graph R(A, B) is still connected is equal to the weight of the maximal edge in this spanning tree.

Claim. Minimal spanning tree of a graph has the property that its maximal edge is minimal possible among all spanning trees.
Proof. Let L be the minimal spanning tree of a graph. Suppose there exists a spanning tree P in which all edges have smaller weight than the weight of the maximal edge of L. We can then remove the maximal edge from L and add some edge from P to it which will connect the graph back. After that L will have strictly smaller weight, which is impossible because it is a minimal spanning tree.

Let's sort all edges of the graph in ascending order of gi. Then the edges of graph T(A) for the fixed i will be all edges with indexes j ≤ i.

Suppose that for some value of i we have already found minimal spanning tree in every connected component of the graph T(gi). Let's add an edge with index i + 1 into it. If it connects two different components, then after this operation they will be merged into one big component and it is obviously that the spanning tree we have in it is the minimal spanning tree. If i + 1-th edge connects two vertices from the same connected component, then it will create exactly one cycle in the graph. We can find the maximal edge in this cycle and remove it from the graph. It can be proven that the remaining tree will be the minimal spanning tree of this connected component.

We can perform the search of the maximal edge in a cycle as well as the insertion and removal of the edges in O(N). The total complexity is O(NM + MlogM).

Problem B: Mice (Roman Rizvanov)

It is easy to see that the number of closest pieces of cheese for each mouse is not greater than 2.

Let's find the closest pieces of cheese for each mouse to the left and to the right from it. From two directions we will choose the one which gives us shorter way to cheese or both of them if their lengths are equal. If on the chosen way between the mouse and the cheese stands another mouse, then we should exclude this way from consideration, because another mouse will get to the cheese faster. Now all the directions lead to cheese and for each piece of cheese there is at most one mouse which can potentially eat it from each direction.

We will process mice from left to right. If the current mouse can move left and the cheese to the left of it is not chosen by any other mouse or it is chosen by a mouse with the same distance to it, then the current mouse can move to the left and eat this piece of cheese without interfering with other mice. This choice will not affect any choices of the next mice, because only one mouse can go to this piece of cheese from the right (see previous paragraph). Thus, this choice can not decrease the answer. In all other cases the current mouse can not increase the answer by moving left, so it should move to the right if it has such opportunity.

The complexity is O(N + M).

This problem can be also solved using dynamic programming.

Problem C: Mutation (Iaroslav Tverdokhlib)

In the editorial we will replace terms "risk", "genome" and "gene" with "cost", "string" and "character", respectively. Let S be the starting string.

Let M be the bitmask of chars which will be removed. Let's iterate over all possible values of M. For the fixed M we need to find a cost of the string, which remained after removal of M and if this cost doesn't exceed T we will increase the answer by 1. Naive implementation of this idea has the complexity O(2KN).

We can not get rid of iterating over all M, so we will try to optimize a part of the algorithm which finds a cost of the remaining string.

Let's take two indexes l and r from the beginning string l < r. Let M' be the bitmask of all characters which are located strictly between them. It is obviously that if or then l and r can not be neighbours in the remaining string. Hence for the fixed l there are not more than K possible candidates for r, which means that there are O(NK) pairs of such potential neighbours. We will call such pairs "good".

We want to find out what form should have the set M that after its removal indexes l and r became adjacent. It is easy to see that the following two conditions should be true:

1.
2.

Let's iterate over all good pairs of l and r and for each of them we will find the set M'. For each triple (a, b, P) we will store the sum of costs of neighborhood of all pairs l and r for which Sl = a, Sr = b, M' = P. After that for the fixed M we will iterate over all pairs of characters (a, b) and its subsets P and add all their costs together. Also we need to add the cost of removal of M and the resulting sum will be the cost of the string which will left after removal of M. The complexity of such solution is O(3K * K2 + NK).

We will optimize the previous solution by decreasing a factor near 3K. Let's look at the following (incorrect) algorithm:

We will iterate over all good pairs l and r and for each of them we will find M'. Let's create an array v in which for each mask P we will store the sum of costs of neighborhood of all pairs l and r for which M' = P. For the fixed M we will find a sum of all values from v for all submasks of M, then add the cost of removal of M to it and the resulting sum will be the cost of the remaining string.

This algorithm is incorrect, because some costs of neighborhood are added to the total cost, but in fact the respective l or r are removed. Let's use inclusion-exclusion principle and make the following at the phase of filling array v:

v[M'] +  = cost

With such filling of v the algorithm described above is correct and the total complexity becomes O(3K + NK).

This is still not enough for the full solution, but we are almost there. We only need to find a fast way of finding the sum of the values of v for all submasks of all masks M. We will use the following iterative algorithm for this purpose:

Before the first iteration we have an array v in which the starting values are stored. After iteration with number i in v[mask] we will store the sum of all the values from the original array v for all submasks of mask for which the first K - i bits are equal to the respective bits of mask. On iteration with number i for all masks in which the i-th bit is equal to 1 (bits are numbered from 1) we will perform the following: v[mask] +  = v[mask\{i}]. It is easy to see that after the K-th iteration of this algorithm we will have the values we were looking for in array v.

The complexity is O(2KK + NK).

Problem D: Plus and XOR (Daniel Neiter)

Let's take a look at some bit in X, which is equal to 1. If the respective bit in Y is equal to 0, then we can swap these two bits, thus reducing X and increasing Y without changing their sum and xor. We can conclude that if some bit in X is equal to 1 then the respective bit in Y is also equal to 1. Thus, Y = X + B. Taking into account that X + Y = X + X + B = A,  we can obtain the following formulas for finding X and Y:

X = (A - B) / 2
Y = X + B

One should also notice that if A < B or A and B have different parity, then the answer doesn't exist and we should output -1. If X and (A - X) ≠ X then the answer is also -1.

Problem E: Points (Daniel Neiter)

Let's regroup summands and split the sum of squares of distances we are looking for into two sums:


Now we need to rewrite each of these sums in the following way (it will be shown for the first sum):


This formula allows us to find an answer in one pass through the array. The complexity is O(N).

Problem F: Tourist (Ilya Porublyov)

We can get to the event j from the event i if the following statements are true:

  • ti ≤ tj
  • |xi - xj| ≤ |ti - tj|· V
We can represent all the events as points on a plane with coordinates (xi, ti). Now we can reformulate the two statements written above in the following way:

From the event i we can get to the event j if the point (xj, tj) lise inside an angle pointed to the top with its vertex in (xi, ti) and its sides form an angle arctg(V) with vertical axis. Let's make coordinate transformation according to which the point with coordinates (xi, ti) will transform into the point (pi, qi), where
pi =  - xi + ti * V
qi = xi + ti * V

Now we can get to the event j from the event i if pi ≤ pj и qi ≤ qj. Let's sort all points in ascending order of p. If several points have the same p we will sort them by q. The second subproblem of our problem can be solved by finding a longest increasing subsequence by q in this array. It can be done in O(NlogN).

To solve the first subproblem we can add dummy event with coordinate 0 and time 0 (if it is not present in our set of events yet) and force tourist's start from it.

The total complexity if O(NlogN).
  • Vote: I like it
  • +30
  • Vote: I do not like it

Comments Comments (22)
| Write comment?
14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Thanks very much, I think E's solution is genial. I understood it now, but it would be very difficult for me to come out with a similar thought :)
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Hi,

I would like to ask about problem F. Is there a particular reason why you sort by p first before you sort by q? If not, will sorting by q and then by p for tiebreak change the solution? If not, may I know if you can prove so? I can understand how you make the transformation and why the transformation is correct, but I am not convinced that you can get the optimal solution just by sorting and finding the LIS (Do you mean the longest non-decreasing subsequence? From what I understand, I think you first label the vertices according to the time when they appear. If they appear at the same time, then they have the same label.) Can you please give a proof or explanation why it works?

Thanks in advance!
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    If some two events have the same time then it is impossible to visit them both, so we are not interested in their relative order in the sorted array (after performing the transformation).

    After the transformation we can get from the point (pi, qi) to the point (pj, qj) iff pi ≤ pj and qi ≤ qj. After performing the sorting described in the editorial all points reachable from the point (pi, qi) will have greater indexes in the array. This automatically means that the sequence will be non-decreasing by pi, so we only need to care about qi. The longest non-decreasing sequence by qi is the sequence we are looking for.
    → Reply
  • 6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Hi,

    Now we can get to the event j from the event i if pi ≤ pj и qi ≤ qj. Let's sort all points in ascending order of p. If several points have the same p we will sort them by q. Can you please explain it for me?

    → Reply
    • 6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you want to be explained? Why "Now we can get to the event j from the event i if pi ≤ pj и qi ≤ qj."? Or what "If several points have the same p we will sort them by q." mean? Or what?

      → Reply
    • 6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Here is more detailed tutorial. It's in Ukrainian, but you can Google-translate it (result is poor, but some things are still correct) and look at figures and equations.

      I CAN try to reply on more concrete questions, but I don't want to translate the whole text...

      → Reply
      • 6 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        Well, What are the significances of p, q axes and angle arctg(v)? What do they represent?

        What I understand before, as I mentioned in another comment's reply was as below: to go to j from i: abs(xj - xi) / tj - ti <= v so,

        xj + v*tj >= xi + ti*v and -xi + v*ti >= -xj + v*t

        → Reply
        • 6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Axis $$$p$$$ is the direction, where the tourist moves (in plane $$$(x,t)$$$), if his speed is ($$${-}v$$$), i.e.maximal by absolute value and directed to left. Its positive ray is the left-bottom border of the area where the tourist can get in time, starting from the origin of the $$$(p,q)$$$ coordiante system. Similarly, $$$q$$$ is the direction, where the tourist moves (in plane $$$(x,t)$$$), if his speed is ($$${+}v$$$), i.e. maximal by absolute value and directed to right; its positive ray is the right-bottom border of the area where the tourist can get in time, starting from the origin of the $$$(p,q)$$$ coordiante system.

          It's not very obvious to look at these axes... But, from other hand, it's not unnatural: we need some effective checking of where the tourist can get in time and where he cannot, so let's try: what, if we'll consider borders of the "reachable-in-time" area as coordinate axes?

          → Reply
          • 6 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I hope this is my last query:

            If tourist needs to go from i to j where xi > xj, that time the velocity is negative. Right? And, the velocity can not be positive and negative at a time,

            But why do we check

            pi < pj and qi < qj ?

            Why not 

            pi < pj or qi < qj?
            → Reply
            • 6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              The axis directed from bottom to top is $$$t$$$ (time). The tourist cannot travel in time as he wants and/or change time flow direction. All what he can is to choose

              1. whether to stay at place with zero velocity (= move in direction of $$$t$$$, which is exactly in the middle between positive direction of $$$p$$$ and positive direction of $$$q$$$);

              2. or to move with velocity ($$$-v$$$), negative and maximal by absolute value, which is exactly positive direction of $$$p$$$;

              3. or to move with velocity ($$$+v$$$), positive and maximal by absolute value, which is exactly positive direction of $$$q$$$;

              4. or to move with velocity $$$0<w<v$$$ (where $$$v$$$ is $$$v$$$ from input data, and $$$w$$$ is actual tourist's velocity), which is in the same quadrant of the $$$(p,q)$$$-system (both $$$p$$$ and $$$q$$$ positive), but $$$q$$$-projection is bigger that $$$p$$$-projection; in other words, $$$0<w<v$$$ corresponds to $$$0<p<q$$$;

              5. or to move with velocity $$$-v<w<0$$$ (where $$$v$$$ is $$$v$$$ from input data, and $$$w$$$ is actual tourist's velocity), which is in the same quadrant of the $$$(p,q)$$$-system (both $$$p$$$ and $$$q$$$ positive), but $$$q$$$-projection is smaller that $$$p$$$-projection; in other words, $$$-v<w<0$$$ corresponds to $$$0<q<p$$$;

              Whereas $$$(q_i > q_j)$$$ (for moving from $$$i$$$ to $$$j$$$) requires either moving with speed $$$w$$$ which is $$$-\infty\leq w < -v$$$, or even moving in reverse direction of time. Similarly, $$$(p_i > p_j)$$$ (for moving from $$$i$$$ to $$$j$$$) requires either moving with speed $$$w$$$ which is $$$v<w\leq\infty$$$, or even moving in reverse direction of time. So, it's required to have both $$$(p_i\leq p_j)$$$ and $$$(q_i\leq q_j)$$$

              → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i dont understand the transformation of (xi,ti), how does it work??? can anyone tell me the answer?

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
"It is obsiously that if or then l and r can not be neighbours in the remaining string."
What is "P"?
It seems that "P" hasn't been metioned before.
I really cannot understand this sentence.
And may "absiously" means "abviously"?

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It was a typo. "Obsiously" should be, of course, "obviously".

    Also I occasionally used P instead of M'. It is fixed now, thanks for pointing this out.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D is right?

I doubts it, for expleam, A=14 and B=4

then X=(14-4)/2=5  Y=5+4=9

and A>B and A and B have some parity and A-X=Y

but X^Y=5^9=12  
This is my doubts. And I think  (A-B)/2=X&Y .
But I don't know the specific X and Y values

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Quote from the editorial:
    "If X and(A - X) ≠ X then the answer is also -1."
    Here X=5 and A-X=9. 5 and 9 = 1, which is not equal to 5. So the answer is -1 here.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I was wrong,
      and is &

      But I saw many wrong program still through the test,

      and thank you very much for your patience solutions
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I'm sorry, X is smallest, but I'm think if the answer doesn't exist, should add a condition:  X^Y=B
    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain the question Gift in this question it is asking for the minimum coins such that every road's gold coin and silver coin constraints are satisfied then if (A,B) is a valid solution then we can make A=infinite and B=infinite so that there will be always a solution also won't A=max(all gi's) and B=max(all si's ) where gi=minimum gold coins for ith road and si=minimum silver coins for ith road (this is what i have understood from the question can anyone tell what's wrong in my understanding )?

→ Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Problem D has weak testcases. My solution gets AC despite giving an incorrect answer on the testcase '10 6'.

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Shit. This was 8 years ago.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A without MST??

Here's my approach
→ Reply