### KAN's blog

By KAN, 2 years ago, translation,  Tutorial of Технокубок 2021 - Финал    Comments (56)
| Write comment?
 » 2 years ago, # | ← Rev. 3 →   For the second paragraph of 1E (Vabank), can someone explain what exactly the queries are, and what is the analysis for why this results in $2 \log (10^{14})$ queries? I don't quite understand from the description in the editorial.EDIT: I think this makes sense now. Start with $L$ money, and try $L$ then $L + \frac{R-L}{2}$ each time. If $L + \frac{R - L}{2}$ is too large, then this process will decrease the amount of money by $\frac{R-L}{2}$. $\frac{R-L}{2}$ vanishes quickly (i.e. halves at each step), so the balance will never become negative.
 » In problem D, can anyone explain how to decide the number of times to perform iterations.?
 » Help needed in task B Can someone please tell,why m would be arbitarily large if we have no positive difference.
•  » » consider this array- 2 2 2 2 2 --sice c=0,a[i]%m=a[i] for every m >a[i].so m can be any value greater than a[i]. hope it help
•  » » » But according to the editorial if a = {9,7,5,3} m should be arbitrarily large as all the negative differences are same and no positive difference exists.but why?. I haven’t understood this part.Can you please help me?
•  » » » » If $a=[9,7,5,3]$, then the answer could be $c=8$, $m=10$, or $c=9$, $m=11$.Formally, $m > max(a)$, and $c = m + d$, where $d$ is the common difference, if and only if the sequence is an arithmetic sequence with negative common difference. Thus $m$ can be arbitrarily large.
 » 2 years ago, # | ← Rev. 3 →   Not author solutions, but fun solution D, E:Solution D: Let's do a Dijkstra on the moments of deletion. It is clear that a song is deleted later if it has a larger deletion circle number, or if its ancestor is equal, about which it is deleted less. So let's do Dijkstra on these parameters. The first round is a simple simulation, and then you just need to maintain the next active song, which is easily done by a two-linked list. As a result, we take out, check that these songs have not been deleted yet, if we have not deleted them, then add them to Dijkstra, delete the next song, and see if the gcd with the new song is equal to one, and if so, add increasing the circle by 1. As a result, the asymptotic $O (n \cdot (log(n) + log (c))$.Solution E: Let's look at the element with the minimum height in the array, and look at the 2 segments into which it divides the array. Note that we must take the beauty of this element in the answer, and that the two segments into which the array is divided are independent, so we can solve the answer for them independently. The only difference from the original problem is that we can remove the array suffix / prefix for free.Then we implement the recursive function $solve (l, r, t1, t2)$, where $t1/t2$ — can we remove the prefix/suffix for free. Well, you can immediately see the exit condition, if $r < l$, then the answer is $0$, because there are simply no elementsLet $pos$ be the position of the minimum on the segment $(l, r)$, $res1 = solve(l, pos-1, t1, 1)$. $res2 = solve(pos + 1, 1, t1)$. Also, if $t1 = 1$ or $t2 = 1$, then we can say that the answer is at least 0 (because we can just take the entire array for free). If $t1 = 1$, then we can not take $res1 + b[pos]$ (since this is a prefix). If $t2 = 1$, then you can also not take $res2 + b[pos]$ in the response (since this is a prefix). The answer can also be $res1 + res2 + b[pos]$. Well, these transitions are enough, because if we took $b[pos]$ in the answer, then the problem is divided into 2 smaller ones, and we solve them correctly, and if we did not take this element, then we did not take $res1$ or $res2$, which is case considered. As a result, each time we find the minimum element, and we divide the problem into 2 smaller ones, and it is not difficult to show that the complexity of this solution is $O(n \cdot log(n)$, since after each transition, one element becomes less, and one search query is made for $log$ (you can do it for a line, but you need to think)
•  » » can you please explain what you mean by doing dijkstra?
•  » » Thanks, nice explanation.
 » Is there any dp arroach in C ?
 » In problem D editorial, It is easy to find it using the bad pairs set. How exactly?
•  » » 2 years ago, # ^ | ← Rev. 2 →   Maintain a queue of songs that are known to make a bad pair with the next undeleted song. In the beginning, fill the queue with i-s, where gcd(A[i], A[(i+1)%n] = 1. Then, every time you pop an index i from the queue, if the i-s element is deleted, continue otherwise, find the next undeleted song using the ordered set of songs if the gcd of the two songs > 1, continue otherwise, a) add the undeleted song to the answer vector, b) delete it from the ordered set of undeleted songs, c) push i back to the queue
 » Simple circular linked list solution for Div2 D can be optimised to O(N).110871644AT the time of deletion just manage deletion in a circular linked list plain algorithm one use of set can also be transformed to queue with just a few changes.
 » For problem statement B , for input: 3 7 3 4 why (5 1) is W/A?
•  » » All the elements should be less than m, because a(I) = ( a(i-1) + c) %m and a(1) = s % m You can check the solution (m, c) before printing (3+1)%5!= 7 #wa
•  » » » only the first element should be less than m ig.
•  » » » » Just try to generate the array If you got the same as the input, then your suggestion of (m, c) is correct. Otherwise, the answer is -1
•  » » » got A/C thanks!
 » 2 years ago, # | ← Rev. 4 →   Problem G very nice and interesting! Below is my explanation of the editorial.The first part of solution is trivial. Let's discuss the second part. The first solution in my mind is binary search, but it costs too much queries. The editorial uses a different idea, which is similar to a famous problem: "egg dropping problem". The idea is: If you performed successful try($X \le M$), you will get one more "chance" to try without the risk of getting fired; If you failed($X > M$), you will lose one chance. Although it's a rough estimate, it seems that you can perform a few more "safe" queries to cover the extra cost.(A very informal proof: after each query, the $\Delta$ of "extra cost" drops very fast, so the sum of it will not too large.)So let's define the $size$ of a problem is $R - L + 1$; define $dp[x][y]$ is the maximum $size$ of problem we can solve using $x$ queries and have $y$ "chances" initially. Using the idea above, it's not hard to find that $dp[x][y] = dp[x-1][y-1] + dp[x-1][y+1] + 1$, which is similar to "egg drop" problem. The initial state of dp is: $dp[...] = 0$.We will find that $dp \approx 6 \cdot 10^{13} > 10^{14} - 2^{46}$, so it's enough. So we can use up to $47 + 49 + x= 96 + x$ queries to guess the right $M$, where $x$ is the number extra queries to cover "extra cost". It seems that $x \le 2$ for the test data of problem G, my solution(110886240) uses max $98$ queries.
•  » » Thanks a lot for the great explanation!
 » Here is my code for question-C, i don't know what's wrong here, like my code is not passing pretest-2(giving correct answer for first few testcases,wrong for some and then again correct for rest). But when i tried running those testcases individually, all of them are giving correct answers. idk howz that even possible since i've not used any global variable. Can someone help me with this please? #include #include using namespace std; int main() { int t; cin>>t; while(t--) { int n,m; cin>>n>>m; int x=m; int limit=ceil(m/2.0); bool ans=false; vector a(n+1,0); vector frnd; while(x--) { int avbl; cin>>avbl; int arr[avbl+1]; for(int i=1;i<=avbl;i++) { cin>>arr[i]; } for(int i=1;i<=avbl;i++) { if(a[arr[i]]+1<=limit) { a[arr[i]]++; ans=true; frnd.push_back(arr[i]); break; } } if(ans && x>0) ans=false; else break; } if(ans) { cout<<"YES"<
•  » » 2 years ago, # ^ | ← Rev. 5 →   It seems that if(ans && x>0) ans=false; else break; has a bug. If ans == false but x > 0, then you break the loop, and skipped some test data, so when you read next text case, you may read wrong data which belongs to previous test case.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   how will that give an incorrect answer? since while taking all m arrays input, previous gets cleared.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   I updated the comment, your code skipped some test data. If you skipped some test data, when you are solving next test case, you may read wrong data(it's belong to previous test case).Upd: sorry, reading array is not the bug code. the real bug is in if(ans && x > 0) ... else break;
 » Thanks for the clear editorial(but a little slower), the contest is really good in general, I really enjoy it!:-)Hope there will be more nice contests like this one on Codeforces.
 » 2 years ago, # | ← Rev. 2 →   My solution in E( almost the same as the author's)For each height — h [i] we will find the leftmost (left [i]) and right border (right [i]) so that min[left [i], i] = h[i] = min[i, right [i]]. OK . this is understood how to do it. one of the ways is this binsearch + sparse table (finding min segment in O(1)).Next, we will use dynamic programming on a tree of segments. in begin all dp equal to -1e18. dp = b, then we can update all dp on the segment from 1 to right because the minimum on this segment is h. Go ahead, to calculate dp [i] — we know that on the segment from left [i] to i, the minimum is h [i], that is, no matter how you choose the last subsegment, min will be H [i]. i.e. dp [i] = max (dp [i], get_max (1, n, 1, lef [i] — 1, i — 1) + b [i]) and do not forget to update all dp from i to right [i] — (j = i, i + 1, right[i]) dp [j] = max (dp [j], dp [i]); this one can be done with a lazy pushFinal asymptotics O (nlogn) My code for more information: 110848133
 » Heh, I feel like problem E from ARC 115 (contest that took place ~2 hours before this one) is very similar to problem E here.
 » 2 years ago, # | ← Rev. 2 →   I used an even simpler approach to C. Do two passes through the data. On the first pass only look at those days where there is only one friend available, and choose that friend, counting the number of times each friend has been chosen. If any friend is chosen more than $\left\lceil \frac{m}{2}\right\rceil$ times then there is no solution. Otherwise, do a second pass through the remaining days, still keeping count, and choosing the first available friend who hasn't been chosen $\left\lceil \frac{m}{2}\right\rceil$ times.This will always give a solution since at most one friend can have been chosen $\left\lceil \frac{m}{2}\right\rceil$ times.My code is here.
 » 2 years ago, # | ← Rev. 2 →   Another way to look at the solution of F: It's somewhat obvious that you're going to do Floyd-Warshall. However, after looking at the problem a bit, one can "spot some similarities" between the first and the second part of the input, with the difference being, that in the second part of the input, the values you are given are values over the paths, whereas in the first part, these are values over edges. With Floyd-Warshall, we can calculate the "first values" over paths aka distances, so why shouldn't we try to apply some sort of a "reversed Floyd-Warshall" on the "second values"? The loop you get is over $i, j, k$ to set $snd[i][j] = max(snd[i][j], snd[i][k] - dist[j][k])$. The only problem left is, at least I wasn't sure in which order to loop over $i, j, k$. I experimented a bit with the order and repeated the procedure three times (because why should this not work?). Then, since we have the "second values" over the edges, we can just compare them with the edge lengths.I just found the aspect of "reversing Floyd-Warshall" too intriguing not to share it. Also, the code is quite short.
•  » » 2 years ago, # ^ | ← Rev. 6 →   That's a funny paper XD. I like this idea a lot, and so I tried to understand why it worked. Turns out my proof is a bit unlike Floyd Warshall.As you did in your code, we first use Floyd Warshall to get the all pairs distance graph $d[i][j]$ the minimum distance from $i$ to $j$, and then aim to create an array $M_3[i][j]$ where $M_3[i][j]$ represents the maximum weight that the edge $i\to j$ can have while still being useful. First, initialize $M[i][j]$ according to the input.Then consider paths $i\to j\to k$. We can compute $M_2[i][k] = \max_{j} M[i][j] - d[k][j].$ After this, $M_2[i][k]$ is the maximum weight that the edge $i\to k$ can be to be on a useful path which uses a useful edge $i\to j$ first, then goes on the shortest path to $k$.Note: Test cases let something like this pass (https://codeforces.com/contest/1483/submission/111041214), but I think this is just a fluke (for example, swapping the $i$ and $k$ indices doesn't pass, but there's not really a difference conceptually as far as I can tell). No proof though.In any case, we can complete the proof with another loop, now considering paths from $s \to i\to k$ $M_3[s][k] = \max_{i} M_2[i][k] - d[s][i].$This is the maximum weight that the edge $s\to k$ can be to first go on the shortest path $s\to i$, then (using what we know about $M_2$) go ​on a path $i\to j \to k$ with $i\to j$ useful.https://codeforces.com/contest/1483/submission/111061937This runs really fast and is quite simple. It may even be possible to improve the time complexity of the max loop computing $M_2$ and $M_3$ with some convex hull stuff. However, because the computation of $d$ is already cubic, this won't improve the overall time complexity.
 » 2 years ago, # | ← Rev. 2 →   Otherwise the modulo has to equal their sum c+(m−c)=m what does it mean ? may any one help me. (c+m-c=m but how can we find modulo by this ?)
•  » » 2 years ago, # ^ | ← Rev. 2 →   When you have the positive difference $c$ and the negative difference $m - c$, the modulo $m$ is simply the sum of the two, as noted: $c + m - c = m$.Did you mean to ask about $c$?
•  » » » Isn't m the modulo here?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   Yes, as I also mentioned in my comment.I was trying to figure out what exactly they tried to ask about since they copied the exact part that showed how to find $m$. ("Did you mean to ask about $c$ instead?")
 » Wow, I just realized that Gustaw can choose $X$ greater than the number of euros he currently has in D1E ...
•  » » And in particular he can steal money even if he has 0 euros
 » It's amazing that 1C and ARC115 E (just about 2 hours before this contest) need similar tricks to improve DP. I suggest those who are trying to solve 1C solve both of them together since I tried ARC115 E and felt it great for my DP skill. :)
 » For Problem C, I try to maintain a struct as (value, las). The 'las' means the friend where it was last seen. And I think it can provides a ability to undo the previous operation (when it more than $\lceil \frac{m}{2} \rceil$). Through continuous withdrawal operations, I think if it has vaild case, it can be found.But I wrong answer on test 4. I can't find the hack data, here is my code: Code.My English is not good...very sorry...
 » in div2F/div1D...can anyone explain these lines in details ( mentioned in editorial )"It can be done using Dijkstra in O(n^2) if we initialize the distance to all ui with -li. After we are done for all vertices v, there only remains to check for each edge whether it has been marked useful for any vertex v."
 » how to solve problem C with flows(this is in tag)?? Who solved C with flow ... pls .. can you pls explain how did you solve ??
•  » » it is a blog use flows.CSDNBut it is writing by Chinese.The key is using bipartite graph to build model, the left is days, the right is friends. I think you can read the code and know why it can be solved by flows.
•  » » » but the complexity seems not to be correct
 » Let $dp[x][y]$ equal the maximal $d$ so that it's possible to find the answer on $[l,l+d]$ having $y⋅l+d$ money initially. One can show that $dp[k] = \binom{k}{[k/2]}$. It implies that $k≤49$. This adds up to 97 queries. Can someone please explain this in more detail? Thank you!KAN
 » In problem C's editorial, it is written that: There is only one case when this is not possible: if f is the only friend who can play in more than ceil(m/2) days How can we prove this?
 » In problem E-Skyline Photo Can someone explain why I'm getting WA in test case 7? here is my code#include using namespace std; using ll = long long; const int N=3e5+5; const ll INF=1ll<<60; int n; ll t[4*N], st[4*N]; void assign(int i, ll x, int u=1, int s=0, int e=n-1){ if(s>i or ee or re or r nearest_min_in_left(vector a) { int n = a.size(); vector ret(n); memset(t, 0, sizeof(t)); for (int i = 0; i < n; ++i){ ret[i] = rmx(0, a[i]); assign(a[i], i+1); } return ret; } int main(){ ios::sync_with_stdio(0), cin.tie(0); cin >> n; vector h(n); for (int i = 0; i < n; ++i){ cin >> h[i]; h[i]--; } vector b(n); for (int i = 0; i < n; ++i){ cin >> b[i]; } vector l = nearest_min_in_left(h); reverse(h.begin(), h.end()); vector r = nearest_min_in_left(h); reverse(h.begin(), h.end()); for (int i = 0; i < n/2; ++i){ swap(r[i], r[n-1-i]); } for (int i = 0; i < n; ++i){ r[i] = n-1-r[i]; } memset(t, 0, sizeof(t)); for (int i = 0; i < 3*N; ++i){ st[i] = -INF; } make_greater(0, r, b); assign(0, b); for (int i = 1; i < n; ++i){ ll dp_mx = rmx(max(0, l[i]-1), i-1); if (l[i]==0) dp_mx = max(dp_mx, 0ll); make_greater(i, r[i], dp_mx+b[i]); assign(i, at(i)); } cout << at(n-1) << "\n"; return 0; }