### nocriz's blog

By nocriz, 5 years ago,

Writer: RDDCCD

Tutorial

Writer: RDDCCD

Tutorial

Writer: RDDCCD

Tutorial
##### 1261B1 - Optimal Subsequences (Easy Version)

Writer: MikeMirzayanov

Tutorial
##### 1261B2 - Optimal Subsequences (Hard Version)

Writer: MikeMirzayanov

Tutorial

Tutorial

Writer: RDDCCD

Tutorial

Writer: RDDCCD

Tutorial
##### 1261E - Not Same

Writers: nocriz, RDDCCD

Tutorial
##### 1261F - Xor-Set

Writer: nocriz

Tutorial
• +113

| Write comment?
 » 5 years ago, # |   0 Auto comment: topic has been updated by nocriz (previous revision, new revision, compare).
 » 5 years ago, # |   0 The tutorial for 1261B — Optimal Subsequences is not ready, but I feel that it is better I post the tutorial soon! That problem is not by me and I hope the tutorial will be available soon.
•  » » 5 years ago, # ^ |   +11 I can just post the brief solution: The optimal subsequence for a given $K$ contains the largest $K$ values. If the indices with the smallest of these values can be chosen in multiple ways, we want to choose smaller indices. That means we want to sort the sequence of all $(A_i, -i)$. We get the answer to a query by taking the last $K$ pairs, sorting the indices in them and taking the $id$-th of these indices. Easy offline solution: sort queries by $K$, add pairs one by one, build a sorted array of indices in them either using a treap or some sqrt structure.
 » 5 years ago, # |   +3 Qualifying round for Technocup (competitions for CIS schoolchildren), but tutorial in English only. hmm
•  » » 5 years ago, # ^ |   +30 Editorial will be available in Russian soon.
 » 5 years ago, # |   -19 obviously, its' easy and similar words are not appropriate for editorials. I understand that once you know the solution it obvious. There are thousands of people who were didn't found it obvious.
•  » » 5 years ago, # ^ |   0 Which part exactly do you need us to explain? I'll be glad to answer your question.
•  » » » 5 years ago, # ^ |   -22 A-Messy It's easy to construct a valid bracket sequence, I am puzzled if we can construct any valid sequence? If so probably we put all left brackets to left and right to right side, but I think we need to construct K outer brackets. maybe code solution example would help
•  » » » » 5 years ago, # ^ |   +14 65626236 I would recommend you to see tourist's solution.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +10 I think "valid" is supposed to mean "with exactly K outer brackets". The example given in the tutorial is ()()()()((((())))) for say K=5; so you just put K-1 empty brackets first, then all the left brackets, and finally all the right brackets. This will always give you a valid bracket sequence with K outer brackets.
 » 5 years ago, # | ← Rev. 9 →   +15 My $(n + q) \ log \ n$ solution for 1261B2 - Optimal Subsequences (Hard Version) GreedyThe optimal subsequence of length k Must have maximum sum -> it must use k largest value of the array Lexicographically minimal -> we only care about smallest value elements in k choosen value -> Sort given array by minimum value first, if value is the same, element with larger index first, last k element is the optimal subsequence of length k Binary Indexed Tree(BIT)The problem ask you to print the index pos in the optimal subsequence of length k, we know the index of all k element in the original array -> $answer = a[x]$ where x is the $pos-th$ smallest out of all indexMaintain a set, iterate through all k from 1 to n, keep insert element, for all query with k, to find $pos-th$ smallest index in $log(n)$ we can :Use a BIT such that index in array = value in set and let the value in array be count[value] so that we can get number of element smaller than xBinary lifting : iterate from highest bit possible, we can check if we can make current bit = 1, thus we can get the maximum value such that number of smaller element is < x (using the fact that $sum(x, x - (x & -x) + 1)$ can get in $O(1)$ in BIT), then the answer we need is ans + 1Code : 65736937
 » 5 years ago, # | ← Rev. 3 →   0 Why the following statement in Problem F is true? Shouldn't it be $4 \times n^2$? We can prove that the number of both "real" and "auxiliary" segments of any size is not greater than 4 x n.
•  » » 5 years ago, # ^ | ← Rev. 2 →   -10 Consider a access to [l,r] on the segment tree, we would call the segments we accessed and found that the segment is completely in [l,r] real segments, and all segments we visited are auxiliary segments. Since we tried visiting n intervals (All intervals in A or B), and for each visit the segments (nodes) we touched of each depth is not greater than 4, the number of both "real" and "auxiliary" segments of any size is not greater than 4 x n is proved.This is the same with the proof of the complexity of the segment tree, I found this on internet only 4 nodes are processed in a level.Sorry, but I have no idea why it could possibly be $4n^2$.Check out my solution for more information:65749995
•  » » » 5 years ago, # ^ |   0 I can’t see your solution. QwQ
•  » » » » 5 years ago, # ^ |   0
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +8 Oh... finally I understand what the sentences. The reason I didn't understand before is just my English is bad... I mean the size of vector fin in your code should be about $60 \times 4 \times n^2$.
 » 5 years ago, # | ← Rev. 2 →   0 For anyone looking for the solution of 1261B2 - Optimal Subsequences (Hard Version) in Java, you can refer to my solution. I used the same approach as mentioned in the tutorial and used Segment Tree to find the kth smallest element in the set. 65750497
•  » » 5 years ago, # ^ |   0 Btw no need to binary search on seg tree queries, you can use this trick, (ctrl-f for find_kth)
•  » » » 5 years ago, # ^ |   0 Thanks a lot, exactly what I was looking for. It decreased the time complexity from log(n)^2 to log(n). Thanks a lot.
 » 5 years ago, # |   +1 Thank you so much for the contest and editorials! I'm just wondering if anyone has a solution which runs under $O(n^2)$ for Div1A/Div2C (Messy)? Or alternatively, is there a way to show that it is not possible to do this with better time complexity?Thanks!
•  » » 5 years ago, # ^ |   0 I was wondering the same.After spending 5 mins thinking about a solution, I noticed n^2 can also pass but it looked like it can be solved in better complexity too.
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 There are several ways to implement a solution that runs under $O(n^2)$.Both operations explained in the editorial can be implemented in $O(log(n))$ using treap: codeAlso, you can notice that in this problem, reversing a range is only going to change the value of two positions (start and end of the range). So you can implement the reverse operation with a simple segment tree (by updating both ends of the range only). Finding the first position to the right equal to a value can be done in more than one way using the same segment tree. For example: Binary search over prefixes starting in each position in $O(log^2(n))$: code. Descending over the nodes of the segment tree, achieving $O(log(n))$: code. I didn't explain every detail in case someone wants to think about them. I'm not sure whether a $O(n)$ solution exists. Feel free to ask anything :)
•  » » 5 years ago, # ^ | ← Rev. 4 →   +11 Actually it can be done in $O(n)$. Here is my code: 65767515The main idea is to create pointers first_opened and first_closed for first ( and ) in s and just update them. The solution is similar to the solution in the editorial. But every time when $s[i] \neq t[i]$, look at the substring s[i..max(first_opened, first_closed)]. It is either (..() or )..)(. Reverse can be done in $O(1)$ and after that you have to fix pointers, it is $O(n)$ total (details in the code).Also, I'm pretty sure that there is no $o(n)$ solution :)
•  » » » 5 years ago, # ^ |   0 My solution works in O(n) time which I think is a bit different than yours. 67442807
 » 5 years ago, # |   0 I saw solutions for B1, B2 using Segment Tree and BIT. How can we find kth smallest element in set using those 2 data structures? I solved it using ordered_set (PBDS in GNU).Also, is insertion operation also supported with this trick (with the use of BIT/SegTree)?
•  » » 5 years ago, # ^ |   +1
•  » » » 5 years ago, # ^ |   0 Thank you :)
 » 5 years ago, # |   0 You can do the hard version of optimal subsequences with online queries using sortings and a mergesort tree. Here is my solution: https://codeforces.com/contest/1262/submission/65675557
•  » » 5 years ago, # ^ |   0 Also you can compute persistent segment tree for each prefix that will store for each value count of it. And you will just go down in this tree in O(log n) to find min prefix with sum >= k.
 » 5 years ago, # | ← Rev. 3 →   0 The issue is solved.
 » 5 years ago, # | ← Rev. 2 →   0 Can somebody please explain why we should multiply the answer by k^(n-t) in div1D/div2F i think the n-t other answers have fewer possibilities
 » 5 years ago, # |   0 Sorry, but I have tried hard but still can't understand the given solution of 1261E ,I wonder what's the meaning of operations for {4,1} and the later stuff? Looking for your reply (:
•  » » 5 years ago, # ^ |   0 I'm sorry if the editorial is hard to understand. {4,1} means that we currently iterated through two elements in A, namely 4 and 1. If the next element in A is 1, then there are three numbers we handled, {4,1,1}. Be careful not to mix it up with the "compressed set".
 » 5 years ago, # |   0 I solved problem E using the concept entropy, you can see it here.
•  » » 5 years ago, # ^ |   0 Can you give a brief explanation of your solution? How have you used entropy here?
•  » » » 9 months ago, # ^ |   0 First, I don't have a proof for my solution, but I can explain the process to let you understand what I'm thinking. First, change the original problem to this: Make $n$ subsets of ${1,...,n+1}$,call them $T_1,...,T_n$. And, these should hold: $|T_s|=a_s$, for any $i\neq j\in [1,n+1]$, ${k|i\in T_k}\neq{k|j\in T_k}$. This means, we should use $n$ sets to tell $n+1$ elements apart. And now, there comes the entropy. If you have some sets $T_1,...,T_s$, then you use these $s$ sets to make the $n+1$ elements some classes $C_1,...,C_q$, and the entropy of this state is: $S(T_1,...,T_s):=-\sum_{t=1}^q[|C_q|/(n+1)]\log[|C_q|/(n+1)]$and the goal is to make $S(T_1,...,T_n)=(n+1)\log[n+1]$. Until now, there is nothing unproved. To achieve the goal, I choose greedy. Say, I already have $T_1,...,T_s$, how do I choose $T_{s+1}$, the way I use is to maximize $S(T_1,...,T_s,T_{s+1})$ without change the choice of $T_1,...,T_s$.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 I found that I was stupid. The proof for this is really easy, and, the proof will lead to a much easier way to solve the problem. I didn't read the tutorial, but I guess the solution tutorial is the "much easier way". Because for each $s$, there is at least one way to choose the $T_s$, so the number of classes will add one.
 » 5 years ago, # |   0 Problem : Arson in Berland ForestHow to do "add value on a rectangle" (using prefix sums)" ?
 » 5 years ago, # | ← Rev. 3 →   0 .
 » 4 years ago, # |   0 What if we want to minimize number of operations in 1261A?
 » 4 years ago, # |   0 How to solve 1261 C if we should also minimize the initial number of burnt trees for a particular maximum value?
 » 4 years ago, # | ← Rev. 3 →   0 1261C (Arson in Berland Forest) is doable in $O(nm)$ time by finding the largest square with lower-right corner at each cell, and then applying the skyline algorithm twice (once vertically, once horizontally on the result of the vertical). Normally the skyline problem is solvable only in $O(n\log n)$ time, however in this case we don't have any "nested" segments (i.e. a pair of segments s.t. one is higher the other and also contained within it), so I was able to solve it using a deque rather than a priority queue (as would normally be used to solve skyline). This allows us to generate a table M s.t. M[i][j] is the size of the largest square which contains the cell (i, j). Now just find the smallest positive element of M and that's the answer. (From here, finding a valid set of initial points is trivial)My code here: 74775877
•  » » 4 years ago, # ^ |   0 emorgan Can you explain how have you used skyline to create M[i,j]? Hard to understand from your code.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 First, I build a table sz where sz[i][j] is the size of the largest square with lower-right corner at cell (i, j). This is a classical problem solved by dynamic programming.Then, I consider each row one at a time. For each index j, I would like to update the values of sz to the left of j, in a way that makes it such that the value in each cell corresponds to the size of the largest square containing that point, with lower-right corner somewhere in that row. To do this, I simply consider all such squares (i.e. all values in that row), and perform range max updates on that specific row on the interval covered by each square. The skyline algorithm actually allows us to do this in $O(n)$ time. The way it works is quite complicated, and I don't think I know how to explain it at a basic level.Then, we just do the same thing on columns instead of rows, and sz now holds the values of the desired array M which i mentioned in my previous comment.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 Thanks emorgan! Your this line makes sense to me — "update the values of sz to the left of j, in a way that makes it such that the value in each cell corresponds to the size of the largest square containing that point, with lower-right corner somewhere in that row". Some print statements in your code helped me to understand the while loops in skyline algo. As per my understanding, use of the first, second while loop is as per image1, image2 respectively.image 1 — https://www.dropbox.com/s/ixjh6pbje3tbv0j/pic1.jpg?dl=0But why are we doing skyline columnwise as well? After rowwise operation we already have max square which contains (i,j).
•  » » » » » 4 years ago, # ^ |   0 After the row-wise operation, sz[i][j] stores the size of the largest square which contains (i, j), and also has lower-right corner in that same row. However, we need to consider squares from lower rows as well. So we perform a second column-wise pass to propagate the values from lower rows upwards. The end result is that each cell storing value $s$ updates an $s$ by $s$ square up and to the left, rather than just to the left along the row.
 » 4 years ago, # |   0 D2 can be solved very easily using ordered_set (for c++) https://codeforces.com/contest/1227/submission/88584680
 » 4 years ago, # |   +3 I did Arson in Berland Forest by using (inventing ^_^) 2-dimensional sweepline algorithm. Have a look : 92480981
 » 4 years ago, # |   0 In DIV2E/DIV1 C, the wording of this statement could have been better You are sure that all burnt trees are shown on the map. All the trees outside the map are undamaged. " are undamaged " should have been replaced with " should be undamaged "
 » 3 years ago, # |   0 I tried to solve problem D2 of Div-2 using segment tree, where I am just assigning new indexes discovered in queries(sorted) to 1 and finding the pos-th 1. But it is giving WA on test 10. Can anyone please help me in finding what I did wrong. Thanks.https://codeforces.com/contest/1262/submission/110093210