Блог пользователя Magolor

Автор Magolor, история, 6 лет назад, По-английски
Tutorial is loading...
Solution(arsijo)
Tutorial is loading...
Solution(arsijo)
Tutorial is loading...
Solution(Magolor)
Tutorial is loading...
Solution(Magolor)
Tutorial is loading...
Solution(Magolor)
Solution(Kostroma)
Tutorial is loading...
Solution(Magolor,optimized by arsijo)
Solution(000000)
Tutorial is loading...
Solution(arsijo)
Tutorial is loading...
Solution(Magolor)
Solution(Kostroma)

Bonus Problem

It is the previous D1E and its standard solution is hacked. Can you solve it?

Bonus problem
  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

Can someone explain the technique used to hash the convex hull in this solution? http://codeforces.com/contest/1017/submission/41357754

for (int i = 0; i < pA.n; ++i) {
		dA.len[i] = length(pA.p[i + 1] - pA.p[i]);
		dA.rot[i] = angle(pA.p[i + 2] - pA.p[i + 1], pA.p[i + 1] - pA.p[i]);
		hA += log(dA.len[i] * 233.0 + dA.rot[i]);
	}
  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Just because I didn't come up with the idea of doubling the sequence of A (dA) and running KMP...

    At first I thought of multiplying all of these lengths and angles. However, this is obviously incorrect; considering that the multiplication of these numbers can be very large, I used logarithm to convert multiplications into additions.

    In this solution len[i] is the i-th length and rot[i] is the i-th angle (rotation), and these two numbers are correlated. I thought that it's hard that hashes log(len+rot) collide (this implements the multiplication of (len[i]*233+rot[i])), so... that's my solution.

    More specifically, if the two convex hulls don't match, there must be some pairs of data (length, rotation) differ. While pair (length, rotation) changes, hash value (len*233+rot) changes.

    Now I'm working on implementation without doubles :-)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can someone prove why for a unique permutation of hash values (len[i]*233+rot[i])), only one polygon is possible?

    Suppose W, X, Y, Z are hash values of a particular quadrilateral, then prove that there cannot be a quadrilateral with hash values Y, X, W, Z.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    So here is my solution without doubles. It uses another hash function but works as well. 41434197 I just have such struct:

    struct localDesc
    {
        long long d1, d2;
        long long dot, sqr2;
    };
    

    And then this hash function:

    long long gH(localDesc p)
    {
        return p.d1 * 113 + p.d2 * 89 + p.dot * 173 + p.sqr2 * 199;
    }
    

    Where

    • d1,d2 — lengths of two consecutive edges of a convex hull
    • dot — dot product of these edges (casted to vectors)
    • sqr2 — doubled square of triangle built from these edges.

    Works pretty good.

»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Problem F can be solved by precalc answer for n, which are divided by X, where X ~ 200000.

  • »
    »
    6 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

    That is how I did it (41368570). I was very surprised when the other solution in my room wasn't this, since I thought the memory limit was way tighter than it was :P

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

for problem C, why does L=⌊√n⌋ always work? I eventually used that result but only from intuition and writing examples in the paper.. Does L=⌈√n⌉ not work?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    nevermind, got it!

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Can you explain the solution , I did not get what the editorial said.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain it to me?

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        This theorem states that any permutation of a sequence with at least (x-1)^2+1 distinct elements have an increasing/decreasing subsequence of length x. Take any input n and find maximum x such that (x-1)^2+1 <= n, you'll find that ⌊√n⌋ always works. So, just assume LIS (could be LDS) to be ⌊√n⌋ and build the permutation in such a way that minimizes LDS, this lead to the small increasing chunks construction and thus to LDS=n/⌊√n⌋.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I am not able to get the part where you say "⌊√n⌋ will always work". Please be more verbose about it.

          These are the questions I have in mind for your second statement : 1. Take any input n , this is perhaps the length of the permutation, If I am correct ? 2. How will I find the maximum x such that (x-1)^2+1 <= n ? 3. How does the conclusion '⌊√n⌋ always works' is related to the previous findings related to x. Should x be ⌊√n⌋ ?

          I am not able to figure out the concept as whole, little hints might help.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
            1. yes

            2. just try every x=1...+inf . You will see that the maximum x you can use is sqrt(n). Take n=9, for example, (3-1)^2+1 <= 9 is valid (x=3), but (4-1)^2+1 <= 9 is not (as with any other x>3).

            3. yes, x=⌊√n⌋

            If any permutation we make has an increasing or decreasing subsequence of size x (from the theorem) and you have found x=⌊√n⌋, then you know that any permutation you build will have either LIS=⌊√n⌋ or LDS=⌊√n⌋. So just assume one, LIS for example, and make the permutation in such a way that LDS is also minimal.

            Sorry if I can't make it more clear.

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              If LIS is ⌊√n⌋ and we make little chunks of it , as shown in the editorial for example 22 , then LDS would be n/ ⌊√n⌋ . If I am correct ? The question was a very intuitive one , if someone who did not know the theorem already

»
6 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Another approach for problem F: 41353364

Find all the primes up to and then, using those primes, run the sieve in blocks of size M (here M = 8·220). Even without using bitsets, you can achieve under 1MB of memory usage without sacrificing much of the speed.

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

Another approach for problem D : 41362569
I converted 01 string in binary.
There are atmax 2n (4096) distinct 01 strings stored count of all of them in an array.
Whenever a query is made I first checked this String is already processed.
If no then calculated answers for all values of K in O(n * 2n)
Worst case Time Complexity O(n * 4n) ~ (Edit) (2e8).

»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I don't like the question F to limit my memory use. in fact, I get the answer quickly, but I spent all of my time until the contest end. If we match for algorithm, why limit others?

»
6 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

There is also a O(2^(2N)) solution for D which worked for the given constraints (perhaps even better than the provided solution?), by simply pre-calculating all (s,t) wu results.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Checkout my comment above. Sol : 41362569 Extra n in complexity is included to account for time taken to match two strings. I didn't pre processed but evaluted when only needed.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You code may be faster if you replace map with binary search and sort.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I haven't used map. I'm using array with index as no. as val. So there is no need to sort it also.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    its never supposed to be. At least i can't pass........

    My first submission should be a WA (by simply mistake) but not a TLE

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Solution for G?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

    I was thinking of a HLD solution
    initialize all nodes with -1.
    query 1, add 1 to that node
    query 2. make value of all nodes in the subtree -1.Also if query 3 on this node gives non negative value, add -1*(ans to query 3)-1 to the node
    query 3. find max non empty suffix sum from that element to root. if negative , white otherwise black.

    Can someone validate??

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      It's correct

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      query 3. find max non empty suffix sum from that element to root. if negative , white otherwise black.

      Does this mean that you take all positive values on the chains up to root?

      I would like to understand the HLD solution.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could someone tell me why we should maintain segment-tree like this: mx[v] = max(mx[v<<1^1], sm[v<<1^1] + mx[v<<1]);? This bothered me for a day.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How do you make values of all nodes in subtree of a vertex in HLD?

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Tnx for the great contest Magolor

how to solve G ?!

is it a HLD problem ?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Could somebody point out to me why this 41374761 gives TLE? Isn't its complexity: (2^n * (2^n + 100) + q * n)?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Your soln — 41375264 . I have replaced n with 15 . It gives AC because Time take to compare i with constant (15) is less that variabe(n)

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you. But shouldn't such complexity pass easily in 2 seconds? what's the difference between my solution and 41356297 The 2 codes are almost identical. Edit: Also seems like it only passed by luck. I resubmitted the exact code you got AC with (with replacement of variable (n) with 15) and I got TLE 41377553

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        As I have mentioned in my comments above. Time complexity is O(n * 4n). For n=12. This is around 2e8. Hence It just passes TL. There are some highly optimised solns with this time complexity which takes around 500 ms.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        No, it shouldn't. It is actually living on the edge.

        But if you used bitmasks/BITSET I think you can cut down runtime dramatically.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          I did use bitmasks. What confuses me the most is that after the contest I got inspired by this 41356297 submission and my 41374761 submission are almost identical except for maybe using vectors instead of arrays. but the AC solution passes in 1300 ms and mine can't run below 2s :/ I really can't spot the difference between the 2 codes.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Try to only run the dp when necessary (whenever you encounter a new mask) and keep track of whichs masks you've seen. It should now cut it to something like a bit over 1 second.

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              I've seen that in other solutions but it's really bothering me how the AC solution 41356297 — which I almost copied — still runs in below 1.3s without having to do that. What's the key for the quick runtime there?

              • »
                »
                »
                »
                »
                »
                »
                »
                6 лет назад, # ^ |
                  Проголосовать: нравится +6 Проголосовать: не нравится

                Speedups/observation:

                Arrays vs Vectors (arrays faster)

                Array Indexing:

                Basically if you look at his code all of the index sizes are increasing order. This actually can run way faster (something with memory access)

              • »
                »
                »
                »
                »
                »
                »
                »
                6 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

                It seems making V a global variable (outside of main) is a big speedup, not sure why though.

                UPD1: http://codeforces.com/contest/1017/submission/41379154

                Got it to pass by using more arrays instead of vectors, increasing index, and making 'v' a global variable.

                This is still far from 1200 ms though.

                UPD2: Found the culprit. You use endl instead of '\n' which is slower becaus it does extra stuff.

                Your code is actually way faster lol: http://codeforces.com/contest/1017/submission/41379280

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Thank you very much for your effort. Much appreciated and noted these things down! never using endl; again! :D

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  You can use #define endl '\n' for that.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    It's because you use cout << ... << endl;.

    endl is a newline and a flush; it's the same as cout << ... << '\n' << flush;. In other words, your code is attempting to write to disk 500,000 times, which is not going to finish in 2 seconds.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In C, why is minimal for a given LIS = L?

  • »
    »
    6 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

    Because you can order the array in L chunks. Depending on if the elements within the chunk are increasing or decreasing, the i'th element of some chunk will be strictly less then or greater than the i'th element of the next chunk.

    So if LIS or LDS is L (amount of chunks), the other N/L (size of chunk)

    Example: 1 2 3 4 5 6, L = 2

    {4 5 6 } {1 2 3}

    4 > 1, 5 > 2, 6 > 3, so it can be clear LDS = 2

    4 < 5 < 6, and 1 < 2 < 3 so the LIS = 3

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      Thanks, the algorithm is clear (I solved the problem exactly this way), but I actually asked a different question. I was wondering how to prove that one cannot construct a permutation with .

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится -10 Проголосовать: не нравится

        Oh, I am sorry for restating the obvious.

        Here it is:

        ([x] is a sequence of x increasing numbers)

        LDS is the amount of chunks [LIS][LIS][LIS]...[< LIS]

        As you can see, the amount of chunks is the LDS, and here the amount of chunks is (amount of [LIS] chunks) + 1

        Amount of [LIS] chunks is "how many LIS fit into N" which is floor(N/LIS), and we also add 1 to include the smaller leftover chunk.

        Among the integers, floor(x)+1 = ceil(x)

        So it's ceil(N/LIS).

        Now imagine it is a perfect square. Then rounding doesn't matter.

        Hope this helps.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

          I think that what he need is a proof of the optimality, but you just provide an algorithm and calculate the [LIS]+[LDS] without proving that this algorithm is optimal.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Assume a permutation with exists. Assign pairs to all elements such that ai denotes the length of a LIS and bi denotes the length of a LDS ending at position i. It follows that all pairs must be different (why?) and we have

        as well as

        .

        Thus, there are less than pairs and two of them must be equal by pigeonhole principle. Contradiction.

        Note: This is the same proof idea used in Erdős–Szekeres theorem.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    and (how, why) always work ?

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      This problem basically simplifies to a much easier problem because A*B = N (you must use all elements 1 to N).

      So imagine you have a number N and you want to minimize A + B where A*B = N.

      Actually in this case A = B = sqrt(N).

      For example:

      A,B values for 16

      (1,16) (2,8) (4, 4)

      The best A,B is in the "middle" of the factors, which is sqrtN.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        how you convert the problem from A + B to A × B ?

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          We want to minimize (A+B) so that A*B = n.

          So for 16, the minimum A+B = 8, because we have A = 4, B = 4, and 4*4 = 16.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            yes, why ?!!

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

              https://codeforces.com/blog/entry/61061?#comment-450032

              Look at the problem discussion. I'm sorry but I can't say much more than "drawing it out".

              You will notice that if you split it into K blocks (with increasing values between blocks) you will notice a LIS is contained within block while LDS is contained across the blocks. (or other way around, either is fine)

              7 8 9 ||| 4 5 6 ||| 1 2 3

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Why A*B=N ?

            I can’t get it.(sad)

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится +2 Проголосовать: не нравится

              Actually, since we have to minimize L + ceil(n/L) (L = length of the LIS)
              So, we have to minimize f(x) = x + ceil(n/x) or simply minimize x + n/x
              Find out it's minima point by differentiation of f(x)
              On solving we get x = sqrt(n).

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              We want to make a permutation of size N, so we can use divide our answer into A increasing blocks of size B. A*B must equal N to use every single numbers from 1 to N.

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

In problem C, how does Dilworth's theorem relate to LIS and LDS in a permutation?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    I have the same question!

    Trying to understand the relationship between LIS and LDS with Dilwort's theorem I found this paper (http://math.mit.edu/~cb_lee/18.318/lecture8.pdf).

    Theorem (Dilworth 1950): Let P be a poset. Then there exists an an-tichain A and a chain decomposition C satisfying |C|=|A|.

    Someone can explain the relationship between the theorem, LIS and LDS?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What is an an-tichain A and what is chain decomposition , sounds greek to , can some one please care to explain , if they are related to problem c.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think I got it.

      Let's assume that we are given some permutation of numbers 1 ... N.

      Then let's define a relation

      i«j

      as "i is smaller than j and it occurs earlier in the given ordering".

      Then we apply the Dilworth theorem in terms of this relation. A longest antichain corresponds to the longest decreasing subsequence. If LDS has length L then by the theorem statement we know that the partially ordered set cannot be partitioned into fewer than L chains. Chanis correspond to increasing subsequences and thus LIS cannot be shorter than ceil(N/L).

      We are supposed to come up with the construction algorithm and the Dilworth theorem helps prove that it matches the lower bound for LDS+LIS.

      IMO this problem was more difficult than its score! :\

»
6 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Problem C

Looking at Erdos lap number the other day and came through this theorem.

https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Edros Theorem says any permutation of n^2 + 1 distinct numbers has a increasing/decreasing sub sequence of n+1.

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

And one more solution for D: 41376803 It has O(22n + q * n) complexity and the most interesting part — it doesn't use that k is relatively small.

First, as in mouse_wireless's solution, we want to count Wu value for all possible masks and create a vector prew containing pairs (Wuvalue, mask). Then we sort this vector in increasing order and now we are ready to another precalc)

For each possible string t we build a vector based on prev: we just change mask to (), which will represent s string needed to get this mask. Now we have to iterate over new vector once again to do following: we will change second value in every pair (ex-mask and ex-()) to number of string in S, for which Wuvalue doesn't exceed current Wuvalue (in current pair). We can do this by simple dp.

Now, for answering a query, all we need is binary search a vector related to given t. It is the part which has a O(q * n) complexity.

Unfortunately, during the contest I got TL4 with this solution beacause of slow IO. Thanks to SHAMPINION, who advised me to add two stirngs of code, which make IO faster and after that the solution passed in 1.7 s.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I had a similar solution to D, with two differences:

    1) Rather than sort the list of (Wuvalue, mask) tuples, it's actually possible to use a Dijkstra-like approach to save a sorting step. This is only a minor speedup though, since computing this list only needs to be done once.

    2) Rather than use binary search, I sorted the queries by k and then iterated in order of increasing Wuvalue's and k's. This saves quite a bit of memory, since you don't have to memoize the results.

    AC in 607ms! 41379365

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In problem E, I have understood that after getting the hulls of the 2 engines, we will represent each hull using a string of edge lengths and angles. After this, Double one of the two strings, and then check that the string which is not doubled exists in the doubled string.

Edge lengths would not change between 2 isomorphic hulls, but angles could change. So, how to normalize angles of the two hulls such that their KMP matching becomes rotation invariant?

EDIT: Never mind, I got it.

»
6 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

For problem E, Magolor's solution differs from Kostroma's solution in this input:

4 4
1 1
1 2
2 3
2 2
1 1
1 2
2 1
2 0

Output should be "No", since reflection is not allowed.

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +36 Проголосовать: не нравится

For 1017E - Сверхзвуковая ракета, many of the accepted submissions (around one-third?) actually fail on this test case:

4 4
0 0
1 0
1 1
2 1
0 1
1 1
1 0
2 0

I wrote up a detailed explanation of what's going on in this post: https://codeforces.com/blog/entry/61086

Can we add this case to the practice version of the problem?

EDIT: Looks like ivanzuki above has the same idea and I was a bit slow. That's what I get for writing a long post :)

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

For problem D,I use O(q × 2n) "solution" and passed it.
my code:http://codeforces.com/contest/1017/submission/41379865

»
6 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

I think that Problem F can also be dealt with easily should one know about the technique of Extended Eratosthenes Sieve.

That is, we can even solve the problem for n ≤ 1011 without the memory limit. :)

My code: 41366266

By the way, Problem E can also be done by finding the minimal string rotation of two convex hulls and compare them with brute force.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please briefly explained problem B.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do you understand the problem statement? Let everyone know and we may have further explanation.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes but I couldn't understand the solution in tutorial.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится +4 Проголосовать: не нравится

        Let me explain an intuitive and naive solution this way.

        There are some notes:

        • The bitwise OR operator (assume it is A | B = C) will make the result become 1 if A or B is 1 or both A and B are 1.
        • There must be a pair of two elements with two different values at two different places to form a change (i.e. swap) that changes the "appearance" of the binary number. In another word, a change (or swap) consists of two different elements.

        Look at these two binary numbers:

        A = 0011
        B = 0101
        

        Notice that, in each column of the representation of the two numbers above, if you make a pair of one element from number A and one from B, you will have these "vertical" pairs: 00, 01, 10, 11 (assigning names p00, p01, p10, p11)

        The first digit in each pair comes from A, and the second digit in each pair comes from B.

        Because the problem is about swapping two different elements in A so that it makes change when OR is done, in each pair above, the first digit will be the one which is swapped with another first digit in another pair, and the second digit will stay still.

        Also by the notes, when we make a change (i.e. a swap of two different elements in A), the one digit we take has to be different from the other digit we take to perform the swap, otherwise the swap become nonsensical because no any elements are changed. In another word, for a pair of positions, there must be a pair of different elements in A, or both A and B. So we can say that the swap for these p make sense:

        p00 with p10

        p00 with p11

        p01 with p10

        p01 with p11

        p10 with p00

        p10 with p01

        p11 with p00

        p11 with p01

        Notice that we have to put each p vertically in actual representation.

        Look more closely at such pairings above, by notes again, we notice something redundant in some pairs:

        p00 with p10 (OK: OR = 01 before & 10 after swap)

        p00 with p11 (OK: OR = 01 before & 11 after swap)

        p01 with p10 (OK: OR = 11 before & 10 after swap)

        p01 with p11 (NO: OR = 11 both before & after swap -> no change)

        p10 with p00 (OK: Same as the first one)

        p10 with p01 (OK: Same as the third one)

        p11 with p00 (OK: Same as the second one)

        p11 with p01 (NO: Same as the fourth one)

        Now that we get these pairs left and they are OK:

        p00 with p10

        p00 with p11

        p01 with p10

        Therefore the result as shown by the tutorial writer.

        I hope this would help you.

        Sorry for my English because this may not such a long explanation like this.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

I came up with the solution of A~G but I made mistakes in my segment tree and failed to pass G...

My solution of problem D~G:

D:

Let f(i, s, k) be how many can be gotten by changing s[i, n) with a cost not greater than k.

When k < 0, f(i, s, k) = 0, otherwise:

f(n, s, k) is the count of s in S;

When i < n, .

The answer of a question is f(0, t, k).

Complexity: O(2nnk).

E:

The problem is equivalent to checking if two point sets' convex hull is the same by shifting and rotating one of them.

If two convex hulls' size are different, the answer is NO. Otherwise, let k be their size, and number the points of each convex hull 0, 1, ..., k - 1 clockwise. Let Pi be point i in the first convex hull and Qi be point j in the second convex hull.

Enumerate which point Qi is corresponding to point P0, and check if for each j = 0, 1, ..., k - 1:

The answer is YES if and only if there is an i satisfying this condition.

To avoid floating point operations, we use

instead of $\lvert P_{i}P_j\rvert$ and , among them Pi(xi, yi). The absolute value of these numbers are not greater than 2 × 1016, we can use 64-bit integer to store them.

I use string hash to solve it. Initialize the prefix and suffix hash value of sequence

Then checking one i costs O(1) time.

After calculating the convex hulls, the complexity is O(n). The total complexity is .

F:

Let P = {p1, p2, ...} be the prime set(pi < pi + 1). The answer is

When $p\le\sqrt{n}$, we can calculate by brute force.

When , , so now we need to calculate .

Consider Eratosthenes sieve, let f(n, m, k) be the sum of k-th power of the rest numbers after deleting all pix (i ≤ m, , x > 1) from 2, 3, ..., n, while 0 ≤ k ≤ 3.

Obviously, , it can be calculated in O(1) time.

If pm2 > n, f(n, m, k) = f(n, m - 1, k).

Else, , .

Then we can get the sum of k-th power of the primes in , it's (pm2 > n). Summing up and we can get the answer.

Because the first parameter is always , , and pm2 ≤ n, the time complexity of calculating f is . Scrolling the array can optimize the memory.

Time complexity: .

Memory complexity: .

G:

Let f(v) be how many operations 1 are operated on vertex v, then f(v) = max{f(pv) - 1, 0} + c(v), c(v) is the count of direct operation on v, i.e. "1 v".

If f(v) > 0, v is black, otherwise v is white.

We can use heavy-light decomposition and segment tree to maintain f. Consider a chain 0 - 1 - 2 - ... - n, if the status of 1, 2, ..., n is known, f(n) can be described as a function of f(0): f(n) = max{f(0) + a, b}. When using segment tree to maintain the heavy-light decomposition, each node storages the a, b of its interval. Then for an operation "3 v", we can query the value of f(v) in time.

For single vertex v (leaves of the segment tree), at first its a =  - 1, b = 0. After an opeartion "1 v", increases its a, b by 1.

After an operation "2 v", decreases v's a, b by f(v) (current value), and restore the subtree v (not contain v) to a =  - 1, b = 0. Because the value of f(v) is increasing before restoring, this algorithm is correct.

Complexity: .

UPD: H can be solved simply by Mo's algorithm, but I didn't open this problem at all...

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is Dilworth's Theorem? How do I learn it? Do I need to know anything else before learning it?

»
6 лет назад, # |
Rev. 5   Проголосовать: нравится +11 Проголосовать: не нравится

Another simple way to check convex hull isomorphism in problem E is to simply check the relations between consecutive triplets of points (as if you are checking triangles congruency). In this way, angles will be implicitly considered.

//v1 and v2 are the two convex hulls.
if(sz(v1) != sz(v2))	NO;
n = sz(v1)

for(int k = 0; k < n; k++)	//v1[0] will coincide with v2[k]	
{
	bool can = true;
	for(int i = 0; i < n; i++)
	{
		p11 = v1[i], p12 = v1[(i+1)%n], p13 = v1[(i+2)%n]
		p21 = v2[(i+k)%n], p22 = v2[(i+1+k)%n], p23 = v2[(i+2+k)%n]

                //Congruency check
		if(dist(p11,p12)!=dist(p21,p22) || dist(p12,p13)!=dist(p22,p23) || dist(p11,p13)!=dist(p21,p23))
		{
			can = false;
			break;
		}
	}
 
	if(can)	YES;
}

Otherwise: NO;

This code is not O(N^2), because matches between triplets cannot be dense, and the inner loop will not take so long before it breaks. However, I couldn't formally prove it.

Edit: From the reply of Kostroma
This code is O(N*M), where M is the maximal number of equal edges in a convex polygon, which can't be that big due to the constrains on the coordinates.

Here is my accepted submission: 41392476

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    actually the convex hull with integer points will only have in size, so the complexity of checking the same would be O(C)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      I am really interested in this conclusion. Could you provide proof or more detail about it?

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

        I learned it from a competitive programming camp.

        I couldn't memorize the proof well, but it's just something like every adjacent edges won't be colinear, so there won't be too much points on the convex hull.

        p.s. why downvoting me...

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -31 Проголосовать: не нравится

    This code IS n^2. It's just weak tests.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      Wanna give a test or just unproven cock-a-rats? I believe it works in O(n·M), where M is maximal number of equal edges in a convex polygon, which can't be that big with these constraints on coordinates surely.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Maybe I'm misunderstanding his solution, but IMO if the two polygons are the same, except one vertex, then it will have O(N^2) running time.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I think that almost all iterations of the outer loop will be short, because there can't be many long equal parts in two convex polygons with vertices in integer points.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            In my understanding, his solution checks if the triangles created by 3 adjacent vertices are coincident.

            If that's what it does, then by having the same polygon twice, just moving 1 vertex by a little, the inner loops running times will be 1,2,3,...,n which summed is O(N^2).

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          If the two polygons are the same (except for maybe one side), the inner loop will NOT be O(n) for all the iterations of the outer loop.

          Because if the two polygons look similar when v1[0] corresponds to (coincides with) v2[0], it doesn't mean that they will look similar when v1[0] correspond to v2[1].

          The only exception is when the two polygons are somehow close to regular polygons, as many matches will occur no matter how you rotate the polygon's vector. In this case the code will really be O(N^2). However, you cannot have a regular polygon with many sides given the constrains of the problem.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain the solution of problem D in the editorial? I solve D with another solution, but didn't understand the provided solution. Why f[S1][S2][j], and what is it going to do with g[S][k]?

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

The complexity in F is just too BS. Setting the limit of N to just 1e8 would make a lot of us see that this complexity works, but 3e8 just makes alot of people says: It's not gonna pass.

»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Вот бы завезли более подробный разбор на русском языке

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I think problem G can be solved by using Segment Tree Beats. This is my solution: https://codeforces.com/problemset/submission/1017/41447852

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could somebody point out to me why this gives TLE? https://codeforces.com/contest/1017/submission/41443492

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Failing G on test 6, but can't seem to find my bug. Could someone help? Thanks in advance!

http://codeforces.com/contest/1017/submission/41515637

UPD: Accepted.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In div2C: I want to answer why sqrt(n) will always work: I won't talk about the statement that: if lis = L then optimal lds = n/L (1) Because it has been proved severel ways. But lets for now believe the above statement(1) and use it. We know that secret_number = lis + lds = lis + n/lis. Then we have secret_number as a pure function in lis. Now we want rewrite as f(lis) = lis + n/lis Know we want to minimize the above function. In other words we need the optimal lis that minimizes f(lis). And here some calculus will answer us : differentating a function is equavelent to getting its slope of tangent to the function curve wrt to its independent variable(lis), we may notice that when a tangent to a curve is parallel to x-axis at some point x then: at this x the function is at a peek (minimum or maximum). So we set the function derivative to zero (slope is 0 when tangent is parallel to x-axis) and solve for Lis, the obtained lis is the one that minimzes the function. F'(lis) = 1 + n / (lis^2) Setting f'(lis) = 0 ===> lis = sqrt(n).

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

In problem E, the first official solution fails on this case:

4 4
0 0
1 0
1 1
2 1
0 1
1 1
1 0
2 0

which is actually test case #55 in the judge system (so weird).

The solution outputs YES, when the answer is NO.

This is due to all cross products of consecutive sides being the same (1 or -1), and the sequences of sides' square length are 2,1,2,1 and 1,2,1,2 respectively. So when we duplicate the second-one (without losing generality), we get 1,2,1,2,1,2,1,2 and it can be seen that it contains the first-one as a substring (starting on position 2).

I think this is because of the use of the cross product. I think dot product should be used instead, because it will characterize the angle between two consecutive sides of the hull better than the cross product, which is in fact characterizing the area of the triangle.