majk's blog

VK Cup 2018 Round 1 and CF Round #470 (div. 1 & 2) editorial
By majk, history, 7 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial of VK Cup 2018 - Round 1
  • Vote: I like it
  • +164
  • Vote: I do not like it

Comments Comments (49)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

On Div1C/Div2D:

The same approach can be also implemented using multiset, which is probably faster to write, but has an extra multiplicative factor, which may or may not fit into TL.

My solution got AC with maximum execution time of 2917ms. Let's say that I was lucky, or I have to send a dearest thank-you to pragma and synced C++ I/O for making that happened...

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    Sorry. Deleted.

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

    edit please :D Let's say that I was lucky, or I have to send a dearest thank-you to pragma // AND SYNCED C++ I/O FOR MAKING THAT HAPPENED... you didn't use I/O sync in your code))

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

    Can you explain your solution?

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

for div1a/div2b

The solution works in O(N^(3/2)), which is fast in practice

I used to think so, coded it in 36171159 and got TLE :( Perhaps I should learn a normal language

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

    It can be much faster.

    Let the largest prime factor of X be p(X), and q(X) = X / p(X). Given X1, X0 = X1 - p(X1) + 1 = X1(1 - 1 / q(X1)) + 1. Notice that leagl X1's are always composite (not prime) and q(X1) is at least 2. If we find a X1 such that q(X1) = 2, all larger X1's will not produce better answer, and we can stop searching. X0' = X1'(1 - 1 / q(X1')) + 1 ≥ X1'(1 - 1 / 2) + 1 > X1(1 - 1 / 2) + 1 = X0, where X1' > X1 and X0' corresponds to X1'.

    q(X1) = 2 is actually quite common. It just means X1 is double of a prime, and prime is quite common. Since the distance to the next prime after N is roughly , we only need to search X1's. Therefore, the overall complexity is .

    My solution runs in 15ms: http://codeforces.me/contest/947/submission/36159299

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

"Clearly, we can obtain N from any number in interval [N - (P(N) + 1), N] by picking P(N) as the prime, and we cannot obtain N from any other number."

I agree with that, but why is P(N) always the best choice for the prime? Why is not possible to pick a smaller prime factor for X2 and then P(X1) for X1?

And you meant [N - P(N) + 1, N], right?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +24 Vote: I do not like it

    The largest prime factor gives the widest range of possible solutions. For example, if N = 14, the largest prime is 7 so the range is [8, 14] but if you choose the prime 2 the range is only [13, 14].

    I also think it is a typo in authors' range formula.

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

    You can prove it that if you will pick some prime divisor smaller than the largest prime divisors the range, which you will get, of numbers from which we can obtain N will lie in the range given by the largest prime divisor.

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

    Ad first question: The interval of the previous value is always [N - p + 1, N], where p is a prime divisor of N. For any prime, this interval would be contained in the interval [N - P(N) + 1, N], hence it is optimal to consider only the largest prime divisor.

    Ad second question: Yes, I'll fix it.

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

The solution for B has an error in it, the range will be [N-(P(N)-1),N] and not +.

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

    here X(i) >= X(i-1) not just greater than so value should be strictly greater than its previous multiple

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

    x2 = k2p2 — (1) x2 >= x1 — (2) (k2-1)p2 < x1 -> k2p2 — p2 < x1 -> x2 — p2 < x1 by (1) — (3) By (2) & (3) Range of x1 is (x2 — p2, x2] -> [x2 — p2 + 1, x2] where p2 is largest prime factor of x2.

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

Auto comment: topic has been updated by majk (previous revision, new revision, compare).

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

can someone please explain the idea behind this solution : http://codeforces.me/contest/948/submission/36161437

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

    If you have X2 and want to know the range of X1 then you do the following.
    Factorize X2 = p1^k1*p2^k2...pn^kn (p1,p2..,pn are primes), then the range of X1 is (X2-pn+1, X2). Because if you choose a bigger range then we can not obtain X2.
    For example think about X2 = 14 = 2^1*7^1
    The range for X1 will be (14-7+1, 14) = (8,14).
    If we choose the range (7,14) then when we peek x1 = 7 and the prime less then x1 (2 or 5) we can not get the X2.
    the same process is done for finding X0.

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

majk Excuse me, about problem E. How can I figure out the eigenvectors v (and Q, Q^-1) using eigenvalues only rather than proof it after knowing it. Is there any material about this? Thanks.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Answer to Bonus of Div1A/Div2B:

We can precompute P(X) for all X in [1..N] with slightly modified Eratosthenes Sieve in : Each time we run a prime p through the sieve, mark all multiples of p with p. In the end, all numbers are marked with P(X)!

Now, for each query X2, we can find the range of X1 in O(1) by looking at the precomputed table of P(X). According to my another comment, we only need to search X1's. And, for each X1, we can also find X0 in O(1) by lookup.

Putting things together, this algorithms works in .

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

can anyone explain me the solution of problem c

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    The second solution:
    If we make a new pile of snow and subtract all pile of snow, obviously, we will get TLE.
    So, we don't do the subtraction.
    We can use a variable called sum which means the accumulated temperature until now.
    If v[i] <  = sum + t[i], then it will disappear and we can calculate the total volume of melted snow. For those v > sum + t[i], we just add t[i] * num to the answer.
    And there is another problem, the new pile of snow may v[i] <  = sum + t[i], but actually it doesn't disappear. So, we can add sum to every pile of snow in the begin.
    Finally we can use multiset to remove element in log(N).
    Here is my submission 36189438

    UPD: num means the number of pile in the multiset, because v > sum + t[i], so it won't disappear, the volume of melted snow is t[i] * num

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

      Thanks for your explanation and submission, they were very clear!

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

In Primal Sport problem shouldn't the answer be 14 for input of 20.

Assume X0 = 14

If P1 = 4 then X1 = 16 (X1>X0)

If P2 = 5 then X2 = 20 (X2>X1)

Since we got answer 20 with X0 = 14 shouldn't that be the answer.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Problem F can be solved by randomized algorithm:

If you just try random permutation and check if it meets the condition, (as you may know), it fails in test case around 96. However, if you modify this algorithm a bit, you’ll get accepted!

Details are as follows:

•Pick up vertex A which has biggest degree

And repeat this until you find the answer:

•Take one leaf B from the other tree (that is, the tree which doesn’t contain A) randomly and map A to B

•Take Vertex C which belongs to the tree with A and doesn’t connect to A randomly, and Vertex D which connect to B (B is a leaf, so D will be uniquely determined), and map C to D

•Just try random permutation for remaining parts and pray for judge :)

Code :36183744

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Good job!

    What you described is equivalent to the correct way of solving the case where the the highest degree vertex has N-2 neighbours. This was the case that the most "naive" random solutions struggled with — and the antitests were usually of the form G = "almost star", H = "almost path".

    Part of the reason why there weren't too many strong pretests against random solutions is that this might help you tweak the meta parameters until you get accepted. In retrospect, I would put the test 96 in the pretest, so that contestants are at least given a chance to realize that we do not expect randomized to pass.

    In other words, if the contest was full feedback, we would probably require solution by increasing N to 100000. We felt that the task was difficult enough and implementing the required operations on the graph on sublinear time just added implementation time, but was more or less standard.

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

      Thank you for replying.

      Yes, I know it's very hard to implement this solution and pass system test within contest time.... (partly because we only know the result from pretest)

      I'll check O(N log N) solution later, thank you for interesting problem!

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

Can Div2 C is done by segment tree? if Yes please explain it.

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

    It can solve by segment tree, we only need to maintain the snow that melts every day for a volume equal to the temperature of the day.

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

Can anyone elaborate on how to add 1 to a segment by two additions using prefix sums in Div2C/Div1B Producing Snow?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You add 1 to the start of the segment, and add -1 to the end of the segment. When processing points, you add the value in the previously created array to a curr variable, which will always indicate current element.

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

    By using a difference array. You can perform the updates in constant time and access all the updated values at the end in linear time.

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

In the formula I think there must be T[j] not T[i]. Correct me if I am wrong.

Problem 923B producing snow.

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

Can anybody explain how to do this?

To calculate all F[i]'s fast, we can again use prefix sums — adding 1 to interval can then be done by two additions.

Adding 1 to the range by 2 additions?

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

    Check the previous comments. It has just been asked.

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

Can anyone explain the correctness of the trie/multiset solution of 923-C Perfect Security ? I just don't seem to understand why the algorithm mentioned in the editorial is correct.

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

    The question wants the minimum sequence. This means we should find the j that minimizes a[0] ^ b[j], remove b[j] from our list and continue. The structure with operations "minimize a[i] ^ x" over all x in a set and add/remove x is the binary trie.

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

Could anyone find out what is wrong with my program for Div. 2 D? I used a trie like the editorial, but I seem to be off by one for some answers and I have no idea why. Could someone help me out? thanks 36214710

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

There might be a typo in the editorial for problem f.

The editorial says,

"Assume that one of the graphs is 1-star. Without loss of generality let it be G. Denote v the vertex that can be removed to turn G into star, u its only neighbor, and w be the vertex of degree N - 2. In graph H, find any leaf and denote it w'. Let its only neighbour be u'. Furthermore, pick v' a vertex that is not adjacent to u' (such vertex always exists as H is not a star). "

It seems that v' and u' should be swapped.

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

In 923D — Picking Strings, transforming BAAB to BBAABB is possible, as per ac solutions, can someone demonstrate how the transformation is done?

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

    B.A.A.B -> B.BB.A.B -> B.BB.A.AB ->B.BB.A.AAB = BBBB

    B.B.B.B -> B.B.AB.B -> B.B.AAB.B = BBAABB

    I hope you understand my transitions :)

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

What is the tricky case in Test case 11 in Div1D — 923D Picking Strings?

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

How to find Minimum number of Dogs in [948A — Protect Sheep]

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

Could someone please explain how to use dfs and similar in A part(948A) Please!!

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

    Collect all of the cell coordinates/ vertices of the wolves, W.

    Create an edge between every cell and it's left, right, down, up neighbors.

    For each w in W, run DFS and see if it can reach a sheep. If a dog (or another wolf?) is encountered during the search, end that leg of the search.

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

      I used this idea and ran a BFS from every cell containing a wolf and placed a dog if i ever encountered a ship but my program gives MLE. Can you help me where I'm going wrong?

      Code

      I found the error in my code and fixed it, but I can't fully understand why it was an error. Initially i was marking the cell to be visited while popping it from queue, but now i mark it as visited before pushing it in the queue. Can someone please explain why this was causing an error?

      AC code
      → Reply