pabloskimg's blog

By pabloskimg, history, 3 years ago, In English
  • Vote: I like it
  • +88
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I'm washed and only tried the mirror for a bit but here's some sketches

C (didn't code)
D (didn't code)
F
H
I
J
K
L
M
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In problem D, it's possible to keep the answer using only a segment tree with lazy propagation instead of a treap.

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

    Can you post the codes of I, J, M, I have been WA...thk

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

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

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

Are the test cases the official ones? I got AC on problem C with an incorrect solution.

Test case
Polygon image

My AC code (152805814) answers 3, but the correct answer is 1 (and this other AC submission answers 1 152705102)

Edit: And this other test breaks all currently accepted solutions except from 152757395:

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

    They might have fixed problem D's cases because the team that passed it passed with a wrong solution but for the other problems I think it's the same cases.

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

    Thanks for pointing these out, added them to the testset.

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

I'm sorry for my poor English

D
E

problem G I don't know the solution, I just guess

G

problem A I don't know how to solve it,wish somebody could tell me, I guess the key is that for a $$$Ax+By>=S$$$ the different $$$A$$$ and $$$B$$$ is $$$O(n^2)$$$,but I don't know how to solve the condition of simple quadrilateral

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

    Could you explain better what you do when x < 0

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

      let $$$r[i]=nxt[i]$$$,$$$l[i]=i$$$,then the answer will be $$$r[i]-l[i]$$$,for example $$$j=3,nxt[j]=5$$$ and when iterate $$$i=4$$$,assume that we get $$$sum[i]+x<sum[j-1]$$$,now $$$nxt[j]$$$ should be $$$4$$$,so we need to modify all $$$j$$$ that $$$sum[j-1]>C$$$,we can use a segment tree to modify $$$[sum[i]+x,inf]=i$$$,so we use segment tree to record

      $$$cnt[x]$$$ the number of $$$i$$$ in this node

      $$$sumr[x]$$$ the sum of $$$nxt$$$ in this node

      $$$suml[x]$$$ the sum of $$$i$$$ in this node

      my solution https://pastebin.com/RvzgS7n5

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

    I have a question about your proposed solution for problem E. How do we update the segment tree? Because let's say we want the minimum in range $$$[p+1, r]$$$, this minimum depends on a third parameter $$$l$$$ which is outside the range, so if you change $$$l$$$, all the values in the range change.

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

      You can build $$$n + 1$$$ segment trees where you fix $$$l$$$ for each segment tree. Each segment tree has size $$$O(n)$$$ so you have overall $$$O(n^2)$$$ memory in Segment trees.

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

      Oh,my fault,I use $$$O(n)$$$ segment tree to do it, the memory is $$$O(n^2)$$$ here is my solution (https://pastebin.com/Wut9fPYZ)

      let me just expain it

      $$$F$$$ is the same as I mentioned above

      $$$G$$$ and $$$H$$$ are the segment tree

      you can discuss 4 situations and use $$$4 * n$$$ segment tree to update the $$$F$$$

      as the memory limit, so I just use $$$maxm = 8000$$$ instead of $$$maxm = maxn « 2 = 12000$$$ or you can use $$$vector$$$

      btw,as you just want to know a min/max of prefix/suffix,you can use fenwick tree, the memory will be $$$1/4$$$ of the segment tree or std::set maybe also can solve this problem

      I'm sorry I haven't answered your so long

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

One more solution

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

    Did you actually implement that solution? I did it using the complex FFT with double precision. But round-off error kills it. To get enough precision you have to use long double (80 bit) floating point. Is that what you did? Or is there some other trick?

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

      Yes, I implemented a solution using FFT with C++ complex of double datatype (8 bytes) and rounding the real part of the answer to the nearest integer.

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

      Most FFT implementations have shit precision issues simply due to the implementation. Read this comment/blog https://codeforces.net/blog/entry/48465?#comment-325890

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

        Thanks. I got my solution to work just by replacing the computation of w^j. Instead of computing it by multiplying w by itself j times, I did it by precomputing its value at the beginning by using the complex exponential function.

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

          Another option to try is Karatsuba, or a Number Theoretic Transform, both of which stay in integers and thus have no precision issues. Our team tested and both pass problem B if implemented efficiently (Karatsuba passed just barely, it is really close to the Time Limit in the mirror judge).

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

I really liked problem G. Is there a way to encode (e.g. find a unique string/integer sequence to represent it) an undirected, unlabeled tree faster than in O(n*log^2(n)) ( let's say without hashing ) ?

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

    Yes, you can encode any rooted tree in $$$O(n log n)$$$ implementing AHU algorithm carefully. You can read more about it here. Then, using the code for a rooted tree is easy to generalize it for an unrooted one because each tree has at most two centroids. So you can call the algorithm for each centroid and merge both vector/strings.

    It's also possible to have an $$$O(n)$$$ algorithm if we use radix sort in AHU algorithm. Though I have never implemented it with radix sort but I read about it in this comment. But if I wanted a linear algorithm, I would prefer hashing to receive a simple integer to encode the tree. It's somehow similar to hashing a string and I learned it from this wonderful blog and this paper.

    However, I've seen your code for problem G and it seems that you are already familiar with a naive AHU algorithm. So to give you a complete answer I will try to explain how you can go from $$$O(n log^2 n)$$$ to $$$O(n log n)$$$.

    If I'm not wrong, what you are doing to encode a rooted tree is the following algorithm:

    Naive algorithm

    The size of the code is $$$O(n)$$$ but the algorithm is $$$O(n^2 log n)$$$ because for each node you are sorting a vector of size $$$O(n)$$$. However, for an unrooted tree, as you use the centroid, then each level of the tree will have complexity $$$O(n log n)$$$ and there are $$$O(log n)$$$ levels so the overall complexity is $$$O(n log^2 n)$$$.

    Let's optimize it to $$$O(n log n)$$$ for a rooted tree. The problem is that you are storing the complete code for all the subtrees. Instead of that, we can compute something like a "partial code" based only on the children of the node and not on the whole subtree. However, in this new algorithm, we will return a list of integers instead of a string and we're going to process level by level, starting from the deepest level.

    Optimized algorithm

    The code has size $$$2n - 1$$$ because each node will append 0 (so we have $$$n$$$ zeroes) and each node will have its label appended by its parent, except from the root that has no parent (so $$$n - 1$$$ more integers). And the overall complexity is $$$O(n log n)$$$ because the sum of sizes of all the vectors that we sort is $$$O(n)$$$ instead of $$$O(n^2)$$$ in the naive algorithm.

    Here is my implementation to encode a rooted tree (for unrooted tree just encode for each centroid). I hope it helps.

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

        Thank you for devoting your time to answer. The algorithm I came up with is pretty much what you described, except to achieve good complexity what I do is; at each node, I sort all the strings corresponding to small subtrees and merge them, I just dont touch the heavy subtree (if there is one, then I just reuse the string corresponding to heavy subtree without copying it). I think this trick is called just "merge small onto large" or something, I am not sure. Tbh now that I look at my algorithm I think a bound tighter than O(n * log^2(n)) may be possible. I cant come up with a tree when the complexity is as bad as n*log^2(n). Definitely n*log(n) is a lower bound. I feel like n*log(n) is the real upper bound as well.

        What you said totally makes sense though. We can just give ranks to nodes, and compare the ranks of the children, we dont need whole subtrees.

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

      I did the first approach but avoided the $$$n^2\log n$$$ complexity by comparing the strings with hashes as well. I got a pretty bad constant but I think it can be improved.