### pabloskimg's blog

By pabloskimg, history, 23 months ago,
• +88

| Write comment?
 » 23 months ago, # |   +27 I'm washed and only tried the mirror for a bit but here's some sketches C (didn't code)Just BFS over $(x, y, time)$ pairs, the clouds all leave after at most $100$ so the answer is small and you can just do whatever. D (didn't code)Work with the prefix sum array $s_0, s_1, \dots, s_n$ so you add $x$ to some suffix and the happiness is the number of subsegments $s[l..r]$ such that $l < r$ and $\min(s[l..r]) = s[l]$. For each index $l$ compute the smallest $f(l) > l$ such that $s_{f(l)} < s_l$, so the number of segments that start at $s_l$ is exactly $f(l) - l$ unless the suffix you add $x$ to starts at some $i$ with $l < i \le f(i)$. Sweep the starting point from right to left and keep the answer updated, you can do this with a treap. F$2^k > 1 + 2 + 4 + \dots + 2^{k - 1}$ so $A$ always gets $n$ and $B$ always gets $n - 1$, then $B$ can get anything else that's in the same connected component as $n - 1$ if you delete $n$ and nothing else. HCompute the cost of placing each odd-indexed city in each feasible position and then run min cost matching. INotice that if you start on Monday, Wednesday or Friday then you get back to the same position after 91 days, then just simulate. JTurns out it's impossible if and only if there are two pairs of points with endpoints on the border that are arranged like $A, B, A, B$, so it reduces to checking if some pair of intervals intersects which is easy. KJust code it lol LIterate over the number of easygoing people that end up seating next to another easygoing person. Once you fix this the entire rest of the process is fixed and you can compute the total happiness easily, and computing the probability is easy math. MAssuming you start at time $0$ doing the tasks greedily by increasing order of deadline works. Then you can check if you can place a certain task at the start in $O(1)$ by using some prefix maximums. Then just delete the smallest task you can place and recurse.
•  » » 23 months ago, # ^ |   0 In problem D, it's possible to keep the answer using only a segment tree with lazy propagation instead of a treap.
•  » » 22 months ago, # ^ |   0 Can you post the codes of I, J, M, I have been WA...thk
 » 23 months ago, # |   0 Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).
 » 23 months ago, # | ← Rev. 2 →   +15 Are the test cases the official ones? I got AC on problem C with an incorrect solution. Test case5 5 6 5 1 N 8 5 6 10 6 10 3 5 3 5 4 6 4 6 5 5 5  Polygon imageMy 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 case3 3 4 3 1 E 4 2 4 3 4 3 2 2 2 Correct answer: 1 
•  » » 23 months ago, # ^ |   +8 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.
•  » » 23 months ago, # ^ |   +8 Thanks for pointing these out, added them to the testset.
 » 23 months ago, # | ← Rev. 5 →   +14 I'm sorry for my poor English Dget the prefix sum, for every $i$ count $sum[i]$, then the anser is the number of pairs $[l,r]$ such that $sum[l-1] = min(sum[l-1]......sum[r])$ ,so we get the the nxt[i] which means the first position that $sum[nxt[i]]=i$, and we get the anser that ignoring the xwe add x on position p, we will affect the i that $nxt[i]>=p$ && $i-1<=p$,wo when we iterate form $n$ to $1$,when we enter $nxt[i]$,we modify the contribution of $i$,and when we leave $i$,we also modify the contribution of $i$, then we get a corrct solution when $x > 0$ because when we add $x$ on $p(p<=nxt[i])$,the first position $nxt[i]$ will only move from left to rightbut when $x<0$ the $nxt[i]$ will move from right to left,we should modify all $i$'s $nxt[i]$ to $p$ such that $sum[i-1]>sum[p]+x$ ,I don't know the easy way to do this, I use a segment tree to get the $nxt$ array and another segment tree to modify the $nxt$ array Elet $F[l][r][0/1]$ be the min cost when we start from $l/r$ $F[l][r][0] = min(max(F[l][k][1],F[k][r][0])+D[k]+dist[k])-dist[l]$ when iterate k from $l$ to $r$ there will exist a $p$ such that $k$ in $[l,p]$ $F[k][r][0]>F[l][k][1]$ $k$ in $[p+1,r]$ $F[k][r][0]=S$ the different $A$ and $B$ is $O(n^2)$,but I don't know how to solve the condition of simple quadrilateral
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 Could you explain better what you do when x < 0
•  » » » 23 months ago, # ^ | ← Rev. 3 →   0 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]+xC$,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 nodemy solution https://pastebin.com/RvzgS7n5
•  » » 22 months ago, # ^ |   0 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.
•  » » » 22 months ago, # ^ |   +3 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.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 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 treeyou 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 problemI'm sorry I haven't answered your so long
 » 23 months ago, # |   +6 One more solution BTo find the maximum sum, first sort arrays $F$ and $C$ in non-decreasing order. When $k=N$, the answer is $\sum_{i=1}^{N}F[i]×C[i]$.For $k •  » » 23 months ago, # ^ | ← Rev. 2 → +12 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? •  » » » 23 months ago, # ^ | 0 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. •  » » » 23 months ago, # ^ | +8 Most FFT implementations have shit precision issues simply due to the implementation. Read this comment/blog https://codeforces.com/blog/entry/48465?#comment-325890 •  » » » » 23 months ago, # ^ | +15 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. •  » » » » » 23 months ago, # ^ | +3 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).  » 23 months ago, # | +16 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 ) ? •  » » 22 months ago, # ^ | +14 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 algorithmYou are recursively encoding the subtree rooted at node$u$as a string as follows. If$u$is a leaf, return "[ ]" Otherwise, you encode all the children of$u$and put each string in a vector. Then you sort the vector and combine all these strings into a code$ans$and finally return "[$ans$]" 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 algorithmFor each level, each node will have an integer label that represents the order of the codes (i.e. the nodes that have the lexicographically smallest code will have label 1, the next nodes will have label 2 and so on). We will distinguish 2 phases in this algorithm (though they can be implemented in parallel).Phase 1) Label Assignment For each level$L$(from the deepest level). Traverse all the nodes$u$of this level and for each of them build the sorted vector from the labels of their children. Call this vector$childrenCode[u]$Then sort all the nodes of level$L$based on$childrenCode[u]$Finally, using this sorted order, assing the labels to the node of this layer (starting from 1). Phase 2) Code generation:We will build a code of size$2n - 1$as follows Set$code = []$(empty vector) For each level (from the deepest level). Traverse all the nodes$u$of this level using the sorted order of their labels (from phase 1). And append all the labels of$childrenCode[u]$to$code$. Also append a special integer to separate the "partial codes" of each node. We can append 0 as we haven't used this integer. 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. •  » » » 22 months ago, # ^ | ← Rev. 3 → 0 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. •  » » » 15 months ago, # ^ | 0 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.