majk's blog

By majk, history, 6 months 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  

»
6 months 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...

»
6 months 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

  • »
    »
    6 months 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.com/contest/947/submission/36159299

»
6 months 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?

  • »
    »
    6 months 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.

  • »
    »
    6 months 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.

  • »
    »
    6 months 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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 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."

    Can you please explain this statement

»
6 months 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 +.

  • »
    »
    6 months 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

  • »
    »
    6 months 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.

»
6 months 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).

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months 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.

»
6 months 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.

»
6 months 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 .

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain me the solution of problem c

  • »
    »
    6 months 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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks got it

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what do you mean by this " add t[i] * num " .

      here num means???

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        sorry, I didn't define it clearly. It means the number of pile which v > sum + t[i](already in multiset) And multiset has already sorted all element, so we can do it from the being of the set.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why you add sum+t[i] always???

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Because sum means the accumulated temperature. Instead of subtracting all piles every time, we can just see sum to decide whether the pile disappear or not

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
6 months 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.

»
6 months 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

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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!

»
6 months 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.

  • »
    »
    6 months 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.

»
6 months ago, # |
Rev. 5   Vote: I like it -11 Vote: I do not like it

I get WA on test case 4 for question "producing snow"...Please help...Thanks in advance... Here's the link to my solution (http://codeforces.com/contest/923/submission/36195419)

»
6 months ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

Can anyone please tell me what is the problem in my 948A: https://imgur.com/a/DYoBP. Judge says Changed (1,2) from S to D. But it doesn't look like that. UPD: I found it. I considered it as a 1 based indexing first. Sorry!

»
6 months 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?

  • »
    »
    6 months 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.

  • »
    »
    6 months 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.

»
6 months 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.

»
6 months 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?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check the previous comments. It has just been asked.

»
6 months 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.

  • »
    »
    6 months 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.

»
6 months ago, # |
  Vote: I like it -7 Vote: I do not like it

36157666

Why RE?

»
6 months 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

»
6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 months 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?

  • »
    »
    6 months 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 :)

»
6 months 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?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    AAA BBAAA 1 1 3 1 5

    Answer is 0.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How would you solve Div2A if you were to minimize the number of walls being built?

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Thank You.Nice Editorial.solved C...First approach :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain priority queue method in div2c??

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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