When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Magolor's blog

By Magolor, history, 6 years ago, In English
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
  • Vote: I like it
  • +28
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nevermind, got it!

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

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

      Can you explain it to me?

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

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it
            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 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              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 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

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 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

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

          aryanc403 I have also done the same thing but I get TLE, can you tell how to improve it. I precalculate the result for all (s,t) pairs 84729180 .

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

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for G?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It's correct

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

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think I see. This can help to maintain max suffix sum.

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

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

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

        HLD is also a Euler tour.

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

          Don't understand you. As I assume, HLD is a set of paths with a data structure built on each. What does it have to do with Euler tour? Elaborate pls.

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Tnx for the great contest Magolor

how to solve G ?!

is it a HLD problem ?

»
6 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

    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 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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 years ago, # ^ |
                  Vote: I like it +6 Vote: I do not like it

                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 years ago, # ^ |
                Rev. 3   Vote: I like it +6 Vote: I do not like it

                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 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

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

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it +13 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          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 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          This is brilliant. Can't thank you enough!

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

    and (how, why) always work ?

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yes, why ?!!

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              Rev. 3   Vote: I like it +6 Vote: I do not like it

              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 years ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                thanks so much, now i understand somehow

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

            Why A*B=N ?

            I can’t get it.(sad)

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it +2 Vote: I do not like it

              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 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

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

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +43 Vote: I do not like it

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 years ago, # |
Rev. 3   Vote: I like it +36 Vote: I do not like it

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 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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

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

    Can you explain your solution please? And also I cannot view the code and I don't know why.

»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please briefly explained problem B.

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

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

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

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

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 4   Vote: I like it +4 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Thanks for your very good explanation ....

»
6 years ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

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

        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 years ago, # ^ |
      Vote: I like it -31 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

    Can you tell me what pii lz[N<<1] do ?

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

      you can search info about it before asking me

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

      each node in my segment tree doesn't maintain the value of 1 range. A node has value if only if its range is a position

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

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

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.