### KAN's blog

By KAN, 6 months ago, translation,

• +127

 » 6 months ago, # | ← Rev. 3 →   +13 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.
 » 6 months ago, # |   0 In problem D, can anyone explain how to decide the number of times to perform iterations.?
•  » » 6 months ago, # ^ |   0 while(!set.empty()){}
 » 6 months ago, # |   0 Help needed in task B Can someone please tell,why m would be arbitarily large if we have no positive difference.
•  » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   0 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?
•  » » » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   -15 For problem C, I think Testcase 2 is wrong. For the following problem: n = 2, m = 7 2 1 2 1 2 1 2 1 2 1 2 1 This is case 33 in 2nd testcase and according to my algorithm the answer is NO which is clearly correct but judge prints Wrong_Answer.
 » 6 months ago, # | ← Rev. 3 →   +31 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)
•  » » 6 months ago, # ^ |   0 can you please explain what you mean by doing dijkstra?
•  » » 6 months ago, # ^ |   0 Thanks, nice explanation.
 » 6 months ago, # |   +1 Is there any dp arroach in C ?
 » 6 months ago, # |   0 In problem D editorial, It is easy to find it using the bad pairs set. How exactly?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 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
 » 6 months ago, # |   0 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.
 » 6 months ago, # |   0 For problem statement B , for input: 3 7 3 4 why (5 1) is W/A?
•  » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   0 only the first element should be less than m ig.
•  » » » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   +3 got A/C thanks!
 » 6 months ago, # | ← Rev. 4 →   +76 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][...] = 0$.We will find that $dp[49][0] \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.
•  » » 6 months ago, # ^ |   0 Thanks a lot for the great explanation!
 » 6 months ago, # |   -11 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"<
•  » » 6 months ago, # ^ | ← Rev. 5 →   +3 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.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 how will that give an incorrect answer? since while taking all m arrays input, previous gets cleared.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 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;
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 okay,i got you!! thank you so much for helping.
 » 6 months ago, # |   0 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.
 » 6 months ago, # | ← Rev. 2 →   0 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[1] = b[1], then we can update all dp on the segment from 1 to right[1] because the minimum on this segment is h[1]. 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
 » 6 months ago, # |   0 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.
 » 6 months ago, # |   0 Can someone plz tell the 29th query of 2nd Test of Problem B
 » 6 months ago, # | ← Rev. 2 →   0 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.
•  » » 6 months ago, # ^ |   0 Thank you for sharing this approach.
 » 6 months ago, # | ← Rev. 2 →   +28 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.
•  » » 6 months ago, # ^ | ← Rev. 6 →   +8 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.
 » 6 months ago, # | ← Rev. 2 →   0 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 ?)
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 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$?
•  » » » 6 months ago, # ^ |   0 Isn't m the modulo here?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 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?")
 » 6 months ago, # |   +31 Wow, I just realized that Gustaw can choose $X$ greater than the number of euros he currently has in D1E ...
•  » » 6 months ago, # ^ |   0 And in particular he can steal money even if he has 0 euros
 » 6 months ago, # |   0 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. :)
 » 6 months ago, # |   0 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...
 » 6 months ago, # |   +3 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."
 » 6 months ago, # |   0 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 ??
•  » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   +3 but the complexity seems not to be correct
 » 6 months ago, # |   +8 Please update problem ratings.
 » 6 months ago, # |   0 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][0] = \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
•  » » 6 months ago, # ^ |   -8 Indeed, some part of the solution was missing. Now it is updated (check that paragraph and the one before that). Also you may find this explanation helpful.
 » 6 months ago, # |   0 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?
•  » » 3 months ago, # ^ |   0 Let f is the only friend who can play in more tren ceil(n/2) days => we choose him more than ceil(m/2) times. In other case we can chose f in ceil(m/2) days and onother people in others days.
 » 6 months ago, # |   0 For problem C, you could also have sets of friends that are available at each day, sort by the days with fewest people, then greedily pick any friend that isn't at the cap yet, increasing someones frequency when picked.I had a little trouble convincing myself that it should work tho, did someone else do it this way?
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 I am also doing the similar way except for choosing randomly choose the one which is selected least time. getting runtime error for some reason so not able to verify :(
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 accepted now
•  » » » » 3 months ago, # ^ |   0 Can you tell me what did you do to resolve runtime error? Even I am getting runtime error . my code passes the same tests sometimes and sometimes not (segmentation fault) if I repeateadly run same input.
 » 6 months ago, # |   0 In problem C-D2, how O(n*m*t) solution can pass the time limit?It is guaranteed that the sums of n and m over all test cases do not exceed 100000. It's guaranteed that the sum of all k[i] over all days of all test cases doesn't exceed 200000. Can anyone explain this line
 » 6 months ago, # |   +8 For the last problem, I submitted something that's quite obviously at least O(number of all pairs satisfying just the first two conditions). It passed easily. Is there a clear general small upper bound on this number?
 » 6 months ago, # | ← Rev. 5 →   0 Problem: C — Basic DiplomacyAccepted finally!!. Passing all test cases. Submission Link #include using namespace std; #define tf_lower(m) transform(m.begin(),m.end(),m.begin(),::tolower) #define tf_upper(m) transform(m.begin(),m.end(),m.begin(),::toupper) #define REP1(start,end) for(int i=start;i> t; while(t--) { // n: number of friends // m: number of days int n,m; cin >> n >> m; vector ans(m,-1); string verdict = "YES"; vector> vec(m); REP1(0,m) { int total_friends_on_day_i; cin >> total_friends_on_day_i; vec[i] = vector(total_friends_on_day_i); REP2(0,total_friends_on_day_i) { int x; cin >> x; vec[i][j] = x; } } vector freq2(n+1,0); REP1(0,m) { if(vec[i].size() == 1) { REP2(0,vec[i].size()) { if(freq2[vec[i][j]] < (m+1)/2) { ans[i] = vec[i][j]; freq2[vec[i][j]] = freq2[vec[i][j]] + 1; } } if(ans[i]==-1) verdict = "NO"; } } REP1(0,m) { bool pushed = false; if(vec[i].size() > 1) { REP2(0,vec[i].size()) { if(freq2[vec[i][j]] < (m+1)/2) { ans[i] = vec[i][j]; pushed = true; freq2[vec[i][j]] = freq2[vec[i][j]] + 1; } if(pushed) break; } if(ans[i]==-1) verdict = "NO"; } } cout<
•  » » 5 months ago, # ^ |   0 Could You explain the solutoin, because I don't understand the first the proof behind the first line the tutorial?
 » 5 months ago, # | ← Rev. 2 →   0 Division 1C/division 2E Why am i getting a wrong answer in test case 7? can someone please help me debug? I can't find any tangible error.code for the same is https://pastebin.com/2wXqwyHf EDITED: https://codeforces.com/contest/1483/submission/114439147refer this one for a clearer picture
•  » » 5 months ago, # ^ |   0 https://codeforces.com/contest/1484/submission/110848133 you can refer the test cases here
•  » » » 5 months ago, # ^ |   0 My solution passes now.I found the mistake however, I am not sure what caused the mistake in the first place. Changing LLONG_MAX to some very big number works. What can the reason be?https://codeforces.com/contest/1483/submission/114440495 the code has been attached. It would really be helpful if you can help me. why this happened?
 » 5 months ago, # |   0 Can anyone explain B, like how you got the intuition of doing what you did to solve B. Please help I'm clueless. Thanks in advance:)
 » 4 months ago, # |   0 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[0], b[0]); assign(0, b[0]); 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; } 
•  » » 4 months ago, # ^ |   0 dont necro
 » 4 months ago, # |   0 Can anyone suggest how to solve Div.2-D(Playlist) using DSU Approach??
 » 4 months ago, # |   +1 [user:KAN] How to do problem D using dsu?