BledDest's blog

By BledDest, 2 years ago, translation,

1000A - Codehorses T-shirts

Editorial
Solution

1000B - Light It Up

Editorial
Solution

1000C - Covered Points Count

Editorial
Solution

1000D - Yet Another Problem On a Subsequence

Editorial
Solution

1000E - We Need More Bosses

Editorial
Solution

1000F - One Occurrence

Editorial
Solution with persistent segment tree
Solution with persistent segment tree (a bit unreadable but runs faster)
Solution with standard segment tree
Mo-based solution

1000G - Two-Paths

Editorial
Solution
Tutorial of W7 main contest

• +53

 » 2 years ago, # |   0 Can F be solved with a mergesort tree? ( By keeping all the elements which occur once in the nodes, where each node is a sorted vector. Also, merging is easy. )
•  » » 2 years ago, # ^ |   0 How is merging easy? Sounds like at least O(n) if it's two pointers. Let the array be and all the queries are [1, n - 1]. How can you merge nodes fast enough?
•  » » » 2 years ago, # ^ |   0 Damn, sorry.
•  » » 2 years ago, # ^ |   +6 I used merge sort tree keeping for each element the range in which it's not repeated : My submission
 » 2 years ago, # |   +3 I like the fact that you have given different approaches for solving F. Thanks.
 » 2 years ago, # |   0 can anyone explain C.
•  » » 2 years ago, # ^ |   0 he is thinking in terms of path compression if some x in [li,ri] keep coming numerous times or some x always remains outside most of the time from many [li,ri]queries then there is no point in keeping its count directly so we keep (li,1) and (ri+1,-1) seperately,a relative positions.
•  » » 2 years ago, # ^ |   0 You are given n line segments with their starting and ending points. Instead of storing all the points that these line segments, you only use the starting and ending points. So you store li and ri + 1 in a vector 'cval'. Then you sort and store only the unique elements in the vector. For each line segment in the input, you obtain the location of its starting and ending point in 'cval'. Now at the starting point you increase the count of line segments in the array 'cnt' and in the ending point you decrease. Now by obtaining the prefix sums of the values in 'cnt'. At 'cnt[i — 1]' you obtain the number of lines passing through the location i and i — 1 in 'cval'. The difference between cval[i] and cval[i — 1] gives you the number of points and cnt[i — 1] gives you the number of line segemnts passing through these points. By maintaining an array 'ans', we store the number of points with i line segments passing through them.
•  » » » 2 years ago, # ^ |   0 got it thanks a lot.:D
 » 2 years ago, # | ← Rev. 2 →   0 In B that's enough to check a_i + 1 only
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 You don't right.
•  » » » 2 years ago, # ^ |   0 Why not?
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 hmmAm I wrong in the situaton when there are two adjacent points?I didn't think about it because my solution had AC
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +3 Could you give a case please. Because if there are only 2 points the solution would be put nothing
•  » » » » » 2 years ago, # ^ |   +3 No, I meant another thing. It's correct that making a point in a_i-1 and a_i+1 would give the same result. But sometimes it's impossible to put a point in a_i+1(like if there are points with coordinates x and x+1)
•  » » » 2 years ago, # ^ | ← Rev. 3 →   +11 There are some facts I can't prove because of my bad Englsh)) They are not very hard, but I can try to write proofs for them in Russian if you would want)It's enough. If we can put a point in ai + 1 and ai - 1, the result will be the same. So I can be wrong in a situation when we can put a point in ai - 1 but can't in ai + 1. Let's take a look at this. The points must be like ...ai - 1, ai, ai + 1(because we can't make a point at here)... Let's increase i until we find a free ai + 1. What do we get? A sequence of adjacent points. I want to say that the result will be the same if we put a point in the left of this sequence or in the right.If we don't find this i, it means there is a sequence with the end at M. in that case I say that the result will be the same if we put a point in the left or don't put at all.
 » 2 years ago, # |   0 Mo-based solution for problem 1000F - One Occurrence is getting TLEAt first I try to write a solution with help of Mo-based solution Editorial, but I getting TLE, after getting many TLE I submit the code from Editorial exactly, but this also getting TLE...:(
•  » » 2 years ago, # ^ |   +26 We never said Mo-based solution from the editorial gets AC. You still need to optimize things here and there.
•  » » » 2 years ago, # ^ |   +9 See my submission using Mo's approach 39747523
•  » » » » 2 years ago, # ^ |   +5 At last I get AC with a lot of change, but using Mo's approach. Here it is 39751860
•  » » » » » 2 years ago, # ^ |   +3 i have a question with Mo's algorithmwhy use this cmp could get AC bool cmp(const Query &x, const Query &y){ if(x.l/b == y.l/b) return (((x.l/b)&1)?x.ry.r); else return (x.l/b
•  » » » » » » 2 years ago, # ^ |   +6
•  » » » » » » 2 years ago, # ^ |   +1 I learned this trick from meooow. You can check it out here : Link.
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   -8 other cmp will get TLE Accepted with other cmp
 » 2 years ago, # |   +3 Can anyone explain normal segment tree approach for 1000F - One Occurrence ?
•  » » 2 years ago, # ^ |   0
 » 2 years ago, # |   0 What will happen in E if the graph is complete graph? there won't be any bridge. so what will be the answer?
•  » » 2 years ago, # ^ |   0 0
•  » » » 2 years ago, # ^ |   0 Ok. Thanks. I read the announcement and finally understood question well.
 » 2 years ago, # | ← Rev. 2 →   0 The problem F is very similar to this problem from BZOJ.Sorry for my poor English.
•  » » 2 years ago, # ^ |   0 But foreigners don't know BZOJ:(
•  » » » 2 years ago, # ^ |   0 Nor can they read Chinese:(
 » 2 years ago, # |   0 Can anyone elaborate 1000D.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 dp[i] is the number of good sequences on the suffix from the i-th element.Then and dp[n + 1] = 1
•  » » » 2 years ago, # ^ |   0 please explain that logic with an appropriate example ...it'll be a great help :)
•  » » » 2 years ago, # ^ |   -8 why are we multiplying with dp[j+1] int the above formula.
•  » » » » 2 years ago, # ^ |   -8 We can choose sequense of length a[i] whith start from i and finish to j ways. After it you solve this problem on the suffix from j + 1 for other way of binom.
•  » » » » » 2 years ago, # ^ |   0 yes thanks a lot :D
•  » » » » » 2 years ago, # ^ |   0 thanks :)
 » 2 years ago, # |   -8 Mo-based solution of Problem F doesn't get AC.
•  » » 2 years ago, # ^ |   0 Thanks for information! It is being discussed 3 comments higher.
 » 2 years ago, # |   0 Can someone explain problem B a bit more? I didn't understand what he's trying to say.
 » 2 years ago, # | ← Rev. 2 →   0 Is it possible to use F's solution to query element that occurs exactly t times on a segment? I think that in this case we would go with persistent ST from right to left (instead of left->right as in editorial). Suppose we are making a version that corresponds to l'th element of an array. We could precompute indices of occurrence of every array element. Suppose array[l] has more or equal than t - 1 occurrences after l: in this case we should update index of t - 1'th position with an index of t'th one or ∞ if such doesn't exist. So, the version l now contains t + 1'th occurrences of t'th elements. Initial version is initialized with negative infinities.Now, the query [l, r] is the range maximum query [l, r] on l'th version. As in editorial one needs to unset t + 1'th position assigning negative infinity to it.I also realized that we could build the tree from left to right and do range minimum queries just as in editorial.Please, tell me if there is an apparent flaw in this solution.
 » 2 years ago, # |   +1 Anyone please explain the solution of Problem 1000F with standard segment tree
 » 2 years ago, # |   0 Why do we need to 'keep only the unique values' in the solution for problem C? I got AC with this and it was pretty straightforward.
•  » » 2 years ago, # ^ |   0 what is the use of "mark" in your code?
•  » » » 2 years ago, # ^ |   0 My bad, that part is redundant, it was for marking the pevents for the small coordinates case. Ignore it here.
•  » » » » 2 years ago, # ^ |   0 Ok.
 » 2 years ago, # | ← Rev. 3 →   0 I got it :) sorry for that comment
 » 2 years ago, # |   +4 We can solve G online with same approach from editorial. Let f(2^i, u) is maximal profit of 2-path from u to 2^i th ancestor of u. f can easily calculated using d' and dp in editorial. Then, we can solve query (u, v) by binary jump on tree (similar to finding LCA).Code: 39743132
 » 2 years ago, # |   0 What does this line mean in solution of B? int tp = (i & 1) ^ 1; 
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 (1&i) corresponds to 1 or 0 depends whether i is odd or even and xoring with 1 inverses the bit. That means if i is odd, i&1 will 1and 1^0 will 0 and if i is even (i&1)^1 will 1therefore if i is odd tp will have 0 and if even tp will have 1
 » 2 years ago, # | ← Rev. 4 →   0 int tp = (i & 1) ^ 1; meaning in B solution code??Can anyone explain
•  » » 2 years ago, # ^ |   0 tp is 1 if i is even and is 0 otherwise
 » 2 years ago, # |   0 Can anyone suggest a good resource for understanding and implementing bridges in a graph ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   -8
 » 2 years ago, # |   0 Is this some kind of hashing of edges? y = A[h] ^ B[h] ^ x; in Farhod_Farmon's solution for 1000G.
 » 2 years ago, # | ← Rev. 2 →   -8 There's another way to do problem D that might make the code simplier. Maintain a dp[][] where the first dimension is the index you are at and the second dimension is the number of integers you have to choose to include before you can open another good sequence.dp[i][k] is simply the sum of: dp[i — 1][k] (you didn't chose the current index to be included in the subsequence) dp[i — 1][k + 1] (you chose the current index to be included in the subsequence) dp[i — 1][0] if arr[i] = k and k isn't 0 (you open a new good sequence) At the beginning, dp[0][0] = 1. At the end, the answer is dp[n][0] — 1 (because empty subsequence isn't allowed)This is the code:http://codeforces.com/contest/1000/submission/39787639Opps and forget my dfs function it's not part of the solution.
 » 2 years ago, # |   -8 My solution for Problem B — Light it uphttps://coolforces.blogspot.com/2018/06/1000b-codeforces-light-it-up-solution.html
 » 2 years ago, # |   0 We don't necessarily have to answer the queries offline in 1000G.
 » 2 years ago, # |   +11 Another cool dp for G: You can use the dp i -> i, and another one called "dpBestToRoot" which saves the best path to root (which is basically the best detour downward + the bestPathToRoot of your parent + the weight between you and your parent — your part in the detour of your parent).Now you just do dpBestToRoot[u]+dpBestToRoot[v]-2*dpBestToRoot[lca]+dp[lca]. (http://codeforces.com/contest/1000/submission/39811424)
 » 2 years ago, # | ← Rev. 2 →   0 I think more straightforward solution for G is to count dpv than build heavy light decomposition with prefix sums of ways where value for each node would be dpv - ev, u - max(dpu - 2 * ev, u) where v is node and u is child of v that lying on the same way(you know this ways in HLD) 39742958
 » 2 years ago, # |   0 In fact, problem C can be solved with O(n) complexity,I think :P
•  » » 2 years ago, # ^ |   0 Sorry,my fault,sorting costs O(nlogn) too :P
 » 2 years ago, # |   0 In solution B , what we are actually doing in this step? for(int i = int(a.size()) - 2; i >= 0; i--) { f[0][i] = f[1][i + 1]; f[1][i] = (a[i + 1] - a[i]) + f[0][i + 1]; } 
 » 2 years ago, # | ← Rev. 2 →   0 Anyone Plz HELP me for 1000C — Covered Points Count I am implementing the same logic as describes above but getting WA for Test Case 4 For Points Covered by 1 Segment. My Code — 39936831 THANKS IN ADVANCE
 » 2 years ago, # |   0 In G, since wi > 0, does it matter if we remove the "twice" constraint in the statement?
 » 2 years ago, # |   0 Hi guys,I was looking at A and wondering if we could read in the strings of the old and new shirt sizes, store them in different vectors, use algorithm sort and then go through everyone of them to compare if they are the same. Given all the constraints, it looks like this should work. However, I must be missing something because it failed the submission. 40068499Can anyone point out what I'm missing out on?Thanks!
•  » » 2 years ago, # ^ |   0 I found the reason on the main contest page. Thanks guys!
 » 5 months ago, # |   0 In problem E, what is being asked in the question and why the answer for that is equal to the diameter of the bridge tree instead of the total number of bridges?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +5 I also did not understand at the beginning. In the problem they ask to find two vertex such that the number of bridges between them is maximum The task does not give specific starting and finishing positions, you need to find such that the number of bridges between them is maximum (shortest path)
•  » » » 5 months ago, # ^ |   0 Understood. Thanks for the help
 » 4 months ago, # |   0 For problem F, I used a mergesort tree to get online queries in $O(\log^2 n)$ (barely snuck under the time limit).Let each element in the array be a triple $(l, r, x)$, where $x$ is the value of that element, $l$ is the index of the previous occurrence of value $x$ in the array $+1$, and $r$ is the index of the next occurrence of value $x$ in the array $-1$. If there is no next or previous occurrence, then just use $+\infty$ or $-\infty$ or something.Now, to query an interval $[a, b]$, we would like to know if there exists any triple $(l, r, x)$ in the array between indices $a$ and $b$, such that $l\leq a$ and $r\geq b$. If any such triple exists, we return $x$.Now, we build a mergesort tree on the triples $(l, r, x)$ (sorted by $l$). Each node of the segment tree will store a sorted list of the triples on some interval, as well as a list of pairs $(r, x)$ which denote prefix maximums in terms of $r$ (and $x$ just gets copied over from whichever element had the largest $r$), on that sorted list.Next, using normal segment tree tactics, we can make it so that for a query interval $[a, b]$, we only need to examine $O(\log n)$ nodes to try and find some valid $x$. For each node, we binary search the sorted list of triples to get a prefix such that $l\leq a$, and then take the corresponding $(r, x)$ at the end of that prefix, which gives us the largest possible $r$ on that prefix. If \$r