ksun48's blog

By ksun48, 5 years ago, In English

Hello denizens of Codeforces once again!

After our last two rounds, Yang Liu (desert97) and I (ksun48) are pleased to announce Codeforces Round #492, which will happen on June 24, 2018 at 19:35 MSK. There will be two versions of the contest, one for users in Division 1 and one for users in Division 2. Both versions will have six problems, with four problems shared between the versions.

The round will feature our friend and superstar member of ACM-ICPC team MIT TWO, Allen Liu (cliu568).

The scoring distribution will be visible once the contest begins. As usual, we'd like to thank our wonderful problem coordinator KAN and Codeforces administrator MikeMirzayanov, as well as the rest of the Codeforces staff for keeping this site an amazing place for competitive programming. Thanks also to our testy testers winger, AlexFetisov, and demon1999.

This round is in honor of uDebug who have supported Codeforces on its anniversary. Thank you, uDebug! uDebug is an enthusiastic community of competitive programmers who help each other out by answering questions on chat, providing hints and solutions to problems from several online judges, furnishing test input and sharing feedback. On uDebug, you can select a problem you’ve coded up a solution for, provide input, and get the "accepted" output. You can visit it by the link.

Good luck! As always, we encourage competitors to read all the problems.

(̶a̶l̶s̶o̶,̶ ̶I̶ ̶s̶e̶e̶m̶ ̶t̶o̶ ̶h̶a̶v̶e̶ ̶h̶e̶a̶r̶d̶ ̶s̶o̶m̶e̶ ̶r̶u̶m̶o̶r̶s̶ ̶f̶l̶o̶a̶t̶i̶n̶g̶ ̶a̶r̶o̶u̶n̶d̶ ̶a̶b̶o̶u̶t̶ ̶a̶ ̶s̶p̶e̶c̶i̶a̶l̶ ̶ ̶s̶u̶r̶p̶r̶i̶s̶e̶ ̶w̶h̶i̶c̶h̶ ̶m̶i̶g̶h̶t̶ ̶b̶e̶ ̶h̶a̶p̶p̶e̶n̶i̶n̶g̶ ̶d̶u̶r̶i̶n̶g̶ ̶s̶y̶s̶t̶e̶m̶ ̶t̶e̶s̶t̶i̶n̶g̶,̶ ̶s̶o̶ ̶k̶e̶e̶p̶ ̶y̶o̶u̶r̶ ̶e̶y̶e̶s̶ ̶p̶e̶e̶l̶e̶d̶!̶)̶

EDIT: And the rumors are confirmed! Go to http://codeforces.com/blog/entry/60176 after the contest is over to discuss the problems or voice your complaints along with scott_wu and ecnerwala!

EDIT: Due to some last minute changes, each version will have six problems, with four shared problems.

EDIT: The Div. 2 score distribution is 500-1000-1500-1750-2500-2750 and the Div. 1 score distribution is 500-750-1500-1750-2250-2500.

EDIT: Congratulations to the winners of the round!

Div. 1:

  1. amiya

  2. Swistakk

  3. Um_nik

  4. bmerry

  5. ainta

Div. 2:

  1. Fortin

  2. Aleks5d

  3. KsCla

  4. hopcroftkarp

  5. davidberard

Thanks to everyone for participating! The editorial is available at http://codeforces.com/blog/entry/60217.

Full text and comments »

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

By ksun48, history, 7 years ago, In English

645A - Amity Assessment

Idea: yummy

One solution is to just brute force and use DFS to try all the possibilities. Alternatively, note that two puzzles can be changed to each other if and only if the A, B, and C have the same orientation—clockwise or counterclockwise—in the puzzle. A third option, since the number of possibilities is so small, is to simply classify all of the 4! = 24 configurations by hand.


645B - Mischievous Mess Makers

Idea: ksun48

Loosely speaking, we’re trying to reverse the array as much as possible.

Intuitively, the optimal solution seems to be to switch the first and last cow, then the second and second-to-last cow, and so on for k minutes, unless the sequence is reversed already, in which case we are done. But how can we show that these moves give the optimal messiness?

It is clear when k ≥ n - 1 that we can reverse the array with this method.

However, when k < n - 1, there are going to be cows that we must not have not moved a single time. Since in each move we swap at most 2 cows, there must be at least n - 2·k cows that we have not touched, with pi = i. Two untouched cows i and j must have pi < pj, so there must be at least pairs of cows which are ordered correctly.

In fact, if we follow the above process, we get that pi = (n + 1) - i for the first k and last k cows, while pi = i for the middle n - 2·k cows. From this we can see that the both i < j and pi < pj happen only when i and j are in the middle n - 2·k cows. Therefore we know our algorithm is optimal.

An O(k) solution, therefore, is to count how many incorrectly ordered pairs (i, j) are created at each step and add them up. When we swap cow i and (n + 1) - i in step i, this creates 1 + 2·(n - 2i) more pairs. So the answer will be .

We can reduce this to O(1) by using our earlier observation, that every pair except those pairs are unordered, which gives total pairs (i, j). Note that this does always not fit in a 32-bit integer.


645C - Enduring Exodus

Idea: GlebsHP

First, observe that the k + 1 rooms that Farmer John books should be consecutive empty rooms. Thus we can loop over all such sets of rooms with a sliding window in linear time. To check the next set of rooms, we simply advance each endpoint of our interval to the next empty room. Every time we do this, we need to compute the optimal placement of Farmer John’s room. We can maintain the position of his room with two pointers—as we slide our window of rooms to the right, the optimal position of Farmer John’s room should always move to the right or remain the same. This solution runs in O(n).

Alternatively, we can use binary search or an STL set to find the best placement for Farmer John’s room as we iterate over the intervals of rooms. The complexity of these approaches is .


645D - Robot Rapping Results Report

Idea: abacadaea

The robots will become fully sorted if and only if there exists a path with n vertices in the directed graph defined by the match results. Because it is guaranteed that the results are not contradictory, this graph must be directed and acyclic—a DAG. Thus we can compute the longest path in this DAG via dynamic programming or a toposort.

We now have two cases. First, if the longest path contains n vertices, then it must uniquely define the ordering of the robots. This means the answer is the time at which the last edge was added to this path. Otherwise, if the longest path has fewer than n vertices, then multiple orderings satisfy the results and you should print  - 1. Note that this algorithm runs in O(n + m).

Another solution to this problem binary searches on the answer. For some k, consider only those edges that were added before time k. We can determine if the robots could be totally ordered at time k by running a toposort and checking if the longest path covers all n vertices. This might be more intuitive for some, but has a complexity of .


645E - Intellectual Inquiry

Idea: yummy

For simplicity, let’s represent the letters by 1, 2, ..., k instead of actual characters. Let a[i] denote the number of distinct subsequences of the string that end in the letter i. Appending the letter j to a string only changes the value of a[j]. Note that the new a[j] becomes —we can have the single letter j, or append j to any of our old subsequences.

The key observation is that no matter what character j we choose to append, a[j] will always end up the same. This suggests a greedy algorithm—always appending the character j with the smallest a[j]. But how do we know which a[j] is minimal while maintaining their values modulo 109 + 7?

The final observation is that if the last occurrence of j is after the last occurrence of j' in our string, then a[j] > a[j']. This is true because appending j to the string makes a[j] larger than all other a[i]. So instead of choosing the minimum a[i], we can always choose the letter that appeared least recently. Since the sequence of letters we append becomes periodic, our solution runs in . Of course, we can also find the least recently used letter with less efficient approaches, obtaining solutions with complexity O((L + n)k).


645F - Cowslip Collections

Idea: desert97

After each query, the problem is essentially asking us to compute the sum of for each choice of k flowers. One quickly notes that it is too slow to loop over all choices of k flowers, as there could be up to choices of k species.

So how can we compute a sum over terms? Well, we will definitely need to use the properties of the gcd function. If we figure out for each integer a ≤ 106 how many times occurs in the sum (let this be g(a)), then our answer will be equal to overall all a.

It seems that if d(a) is the number of multiples of a in our sequence, then there are k-tuples which have gcd a. Yet there is something wrong with this reasoning: some of those k-tuples can have gcd 2a, or 3a, or any multiple of a. In fact, , the number of gcds which are a multiple of a.

We will try to write as a sum of these . We’ll take an example, when a ranges from 1 to 4. The sum we wish to compute is g(1) + 2g(2) + 3g(3) + 4g(4) which can be written as

(g(1) + g(2) + g(3) + g(4)) + (g(2) + g(4)) + 2(g(3)) + 2(g(4)), 


In general, we want to find coefficients pi such that we can write as . Equating coefficients of g(a) on both sides, we get that . (The mathematically versed reader will note that pi = φ(i), Euler's totient function, but this is not necessary to solve the problem.)

We can thus precalculate all pi in using a recursive formula: . We can also precalculate for each l ≤ 200000, so in order to output after each query we should keep track of the values of the function d(i), the number of multiples of i. When receiving ci flowers, we only need to update d for the divisors of ci and add . If we precompute the list of divisors of every integer using a sieve or sqrt checking, each update requires O(divisors).

Thus the complexity of this algorithm is or preprocessing, and O((n + qmax(divisors)).


645G - Armistice Area Apportionment

Idea: yummy

Thanks to amiya and Petr for sharing a solution with me that is much more intuitive than the one I originally had in mind! It works as follows:

First, let’s try to solve the smaller case where we only have two points. Let be the line passing through xi and xj. We want to compute the difference of relative to P and Q. Define P as the reflection of P over . By the triangle inequality, we have |PX - QX| = |PX - QX| ≤ PQ. Equality can be achieved when X, P and Q are collinear—that is, when X is the intersection of and line PQ. (If and PQ are parallel, we can imagine that they intersect at infinity.) Therefore, the difference of a line relative to P and Q is the distance from P to Q.

We can also think about P in a different way. Let Ci be the circle with center xi that pases through P. Then P is the second intersection of the two circles Ci and Cj. Thus our problem of finding a line with minimum difference becomes equivalent to finding the intersection among {Ci} that lies closest to Q. This last part we can do with a binary search.

Consider the problem of checking if two circles Ci and Cj intersect at a point within a distance r of Q. In other words, we wish to check if they intersect inside a circle S of radius r centered at Q. Let Ai and Aj be the arcs of S contained by Ci and Cj, respectively. Observe that Ci and Cj intersect inside the circle if and only if the two arcs overlap, but do not contain each other. Thus we can verify this condition for all pairs of points with a radial sweep line along the circle. Due to the binary search and the sorting necessary for the sweep line, this solution runs in , where P is the precision required.

One might also wonder if precision will be an issue with all the calculations that we’re doing. It turns out that it won’t be, since our binary search will always stabilize the problem and get us very close to the answer.

Here’s my original solution using a projective transformation:

We begin by binary searching on the the minimum possible difference. Thus we wish to solve the decision problem "Can a difference of k be achieved?" Consider the hyperbola |PX - QX| = k. Note that our answer is affirmative if and only if a pair of outposts defines a line that does not intersect the hyperbola.

Our next step is a reduction to an equivalent decision problem on a circle through a projective transformation. We express this transformation as the composition of two simpler operations. The first is an affine map that takes the hyperbola |PX - QX| = k to the unit hyperbola. The second maps homogenous coordinates (x, y, z) to (z, y, x). Under the latter, the unit hyperbola x2 - y2 = z2 goes to the unit circle x2 + y2 = z2.

Because projective transformations preserve collinearity, a line intersecting the hyperbola is equivalent to a line intersecting the circle. Thus we want to know if any pair of the outposts' images defines a line that does not intersect the circle. We now map the image of each outpost to the minor arc on the unit circle defined by its tangents. (We disregard any points lying inside the circle.) Observe that our condition is equivalent to the existence of two intersecting arcs, neither of which contains the other. Verifying that two such arcs exist can be done with a priority queue and a radial sweep line in .

The total complexity of our solution is therefore , where P is the precision that we need. It turns out that the implementation of this algorithm is actually pretty neat:


Full text and comments »

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

By ksun48, 10 years ago, In English

351E - Jeff and Permutation

Here is an alternate, simpler, solution to the one given in the editorial.

First, let's consider pi and pj in positions i < j. Let's first assume that |pi| ≠ |pj|. When will this be an inversion?

If |pi| > |pj|, then it is an inversion when pi is negative, and not when pi is positive, because  - |pi| <  - |pj| ≤ |pj| < |pi|. Thus our choice of pj does not affect if (i, j) is an inversion.

Similarly, if |pi| < |pj|, then the choice of pi does not matter.

Thus for each element pk, we can choose its sign by looking at the count of the |pi| < |pk|, with i < k and i > k. If there are more with i < k, we make pi positive, and otherwise, we make pi negative.

But wait! What if |pi| = |pj|? Then whether or not (i, j) is an inversion depends on both values. Fortunately, this is not a problem, as if we do the above algorithm, if |pi| = |pj|, then the algorithm will make pi ≤ pj, so (i, j) will not be an inversion.

This is because there cannot be more elements with absolute value at most |pi| left of i than right of i, and at the same time less elements with absolute value at most |pi| left of j than right of j.

This algorithm can run in O(n2) time, and uses O(n) memory (with no DP at all, only greedy). With some sorting and a data structure, I believe we can improve this to time.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it