### subscriber's blog

By subscriber, history, 3 months ago,
• +124

 » 3 months ago, # |   0 Can someone please explain problem A?
•  » » 3 months ago, # ^ |   +7 U are given some activities (n) starting from 1 upto n. Now u are given m other activities which are other than the previous 1-n ,i.e, n+1 to ahead. When a total new activity comes, u have to remove the oldest activity from back and if after sometime existing activity comes, u don't need to remove anything bcz there's already that activity ongoing.... Obviously 1 to n won't be there in the m activities, so we just have to print what activities still exists (-1 if they do) and if they have left the queue then at what time did they...
•  » » » 3 months ago, # ^ |   0 But what if we are given n activities and there are m new activities but m > n, where in the problem is it mentioned that the m is strictly lesser than n?
•  » » » » 3 months ago, # ^ |   0 It won't matter, when all the previous activities are already out then we have already got our answer in the array with no -1 values.... m>n ain't issue here bcz window is of n size and elements are coming and going
•  » » » » » 3 months ago, # ^ |   0 Ohh completely missed it.Thanks
•  » » 3 months ago, # ^ |   0 You can use set in this question. Iterate the actions from starting and see if the element is present in set then do nothing if it is not present then you have to remove the last post and element in the set. You can use a counter for knowing which is the last element in the recent field.
 » 3 months ago, # | ← Rev. 2 →   +4 I think F can be solved in $O(n*log(n))$. My idea is probably different from the author's one, and I will try to improve the code.Edit: tutorial on $O(N*log(N))$ solution: link
•  » » 3 months ago, # ^ |   +24 I had the same idea and was very surprised with how easy problem F actually was. Like, it's just simple greedy which is easily provable and we don't even need to optimize it with down to $O(NlogN)$.
•  » » » 3 months ago, # ^ |   0 I bet that if they placed it as C or D, a lot of people would solve it
 » 3 months ago, # | ← Rev. 2 →   +93 F can be trivially solved in $O(n \; log^2\; (Wn))$ by simply using linkret trick, well known in Croatia (yes, not China :P).https://codeforces.com/blog/entry/49691
•  » » 3 months ago, # ^ |   +8 how do we know it's not well known in China too XD?
•  » » » 3 months ago, # ^ |   +60 Everything is well known in China, but this is also well known in Croatia as well xD.
•  » » 3 months ago, # ^ |   +21 I think that one is well known for everyone that you can call an "experienced contestant"
•  » » » 3 months ago, # ^ |   +58 TIL I'm an inexperienced contestant
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Ofc it's not a rule, as some people missed that problem. But for people that actually went around learning these tricks from problems, that's a huge problem that I'd be surprised if more people that were active at around 2017-2019 missed that problem than people that know it.Perhaps you're just so good at the basics that you don't look into these weird little tricks.
•  » » » » » 3 months ago, # ^ |   0 Yeah, to be clear I was being (mostly) sarcastic :) I also wasn't especially active on CF until around 2018 and wasn't regularly participating at a Div. 1 level until 2019, so there are still lots of problems that were standard back then that I just haven't run into :p
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 Also well known in China, and it is often called "wqs binary search" in China. :)
•  » » 3 months ago, # ^ |   +18 Looking through your submission history, I noticed that you received WA with the code from this blog (195181117), but got AC with some additional trick(195185134). Do you know why? I am facing simmilar issue, but I don't undestand why in this problem the typical implementation of this trick seems to fail.
•  » » » 3 months ago, # ^ |   +8 You can look at the blog for more details. Essentially the first solution doesn't handle some edge cases well and is less numerically stable because of the use of doubles. The second solution handles those better and uses fractions as well.
•  » » » » 3 months ago, # ^ |   0 I didn't notice Neal's comment at first. Thanks
 » 3 months ago, # |   +6 I’m so mad, I solved E 5 mins after contest ended ;(. I can’t solve anything in contest.
•  » » 3 months ago, # ^ |   0 Don't be upset. You will be successful next time!
•  » » » 3 months ago, # ^ |   0 Thanks :)
 » 3 months ago, # |   +43 Please add the proof of solution of problem C.
•  » » 3 months ago, # ^ |   0 "This problem is trivial and the solution is easy to see"Is probably enough as an editorial in the opinion of the person that approved that problem.
•  » » » 3 months ago, # ^ |   +47 Somehow this is literally the editorial for E.We need proofs!
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 1) Suppose there are only one 'a' and one or more 'b' and no other letters are left. If we consider how words are created depending on the location of a, we can see that the optimal is to place 'a' in the center.2) Suppose there are one 'a' and one or more 'b' and at least one 'c' are left. If a word starts with 'b' and ends with 'a', the optimal (in this case) is to place the remaining symbols in order from the front. Let's prove this word (say w) is optimal. Let x be a position 'c' is appear in w. Suppose that word does not end with 'a'. Then the word must end with 'b', and in order for the word to be less than w, 'a' must be located between position 1 and position x. (Note that positions 1 through x-1 in w are filled with 'b'.) However, when this happens, the word is smaller than its reverse, which is a contradiction.Sorry for my poor English.
 » 3 months ago, # |   0 Can’t E be solved faster by just checking where the two cities would intersect and then connecting cities in each x and y?
•  » » 3 months ago, # ^ |   0 I do operation two times not (n+m) times still accepted in E,I don't know why.
•  » » » 3 months ago, # ^ |   0 Technically 4 because the editorial is referring to filling the y and x as separate conditions. You only need to do it twice, but you don’t know whether to start with the y or x so it’s satisfactory to do it four times to fix orientation. This is because after you fill x or y, if it can be filled it will at most give some new x that also needs to be filled. When it fills x, this will be the last operation given the statements above are true because it will fill every x in each y it added or there would be a gap between the two cities which does not need to be filled. Since it’s doing this on each x in the connected component’s range, it also fixes each y. Same thing vice versa.
 » 3 months ago, # |   +11 Here's how I solved C: Since we can choose any arbitrary permutation of symbols in s, we might just as well sort it. Because we need such a tmax that is bigger than it's reversed counterpart we are going to construct our "almost" palindrome string that it's first half is only slightly bigger than the reversed second half. Iterate over first 2 characters in s, if the characters are equal — add each to the prefix and suffix of our answer string. If after this step we have only one or no more characters left in s — we are happy because we have our palindrome which is the answer. Otherwise, first time we encounter an unequal pair of characters, pretend that they are equal too and add each one of them to the prefix and suffix of our answer again (we have to remember the original character, the substitute one and the position of the replacement at the suffix of our answer). Fill in the rest of our answer with what's left of the sorted string s. Now we have to find the optimal position for our original character which we have substituted (the lesser one), it's either the original position, or s.length() / 2 if the condition that tmax >= reverse(tmax) still holds.
 » 3 months ago, # |   +19 I have found an $O(N*log(N))$ amortized solution to F. Code: 195201483The idea is simple. First, we sort the array in decreasing order.$O(N^2)$: We iterate over to how many elements from the beginning we will apply both operations. After that, we know that there are $n-both$ elements to which we can apply at least one operation. We take $k1-both+k2-both$ greatest elements after $both$ taken elements from the array. Now, we apply operation 1 to all of them. We must apply $k2-both$ operations of type 2, so we choose $k2$ elements with biggest delta $cost2(a_i)-cost1(a_i)$ where $cost1$ and $cost2$ are functions that return an integer after applying operation 1 and 2 respectively. $O(N*log(N))$: note that there are not a lot of changes if we calculate answer for some $both$ and $both+1$. We can use ordered_set of deltas $cost2(a_i)-cost1(a_i)$ in order to maintain to which numbers we apply 1 or 2 operation.
 » 3 months ago, # |   +64 I believe I have a solution to E in $\mathcal{O}(nm)$ which also solves the problem for arbitrarily many cities/components (not just two). It consists of two simple steps: Find the minimum bounding rectangle of the cities, and let this be the preliminary answer. We will try to cut down on this answer by chipping away at the corners. Add each of the four corners of the bounding rectangle to a queue. While there exists a corner which is not part of a city in the original grid, we remove that corner and add any new corners created to the queue. Repeat until no removable corners are left. I claim this is the minimum connected convex cover of the cities (convexity is the property which is equivalent to the Manhattan distance rule), so we are done. Just be careful not to accidentally disconnect the cities again when removing corners, and you should be good. Here's a link to my submission: https://codeforces.com/contest/1799/submission/195179223I haven't thought about a rigorous proof of correctness yet, so I welcome any hacks to my solution if any such hacks exist!
 » 3 months ago, # |   +56 Where's H editorial?
 » 3 months ago, # |   +33 Another way to solve D2 1799D2 - Hot Start Up (hard version), define dp[i][same cpu with i-1 ?] = min timeif use cold, then dp[i][true/false] = min(dp[i-1][true],dp[i-1][false]) + cold[a[i]]if use hot, let t[a[i]] be the a[i] last exist time. if t[a[i]] + 1 == i, dp[i][true] = min(dp[i-1][true],dp[i-1][false]) + hot[a[i]] if t[a[i]] + 1 < i, then t[a[i]] + 1..i-1 is using same CPU, so that dp[i][false] = dp[t[a[i]]+1][false] + sum(cold/hot[t[a[i]]+2..i-1]) + hot[a[i]], the middle sum can be precaculate with prefix sum, in this way there is no need for segtree
•  » » 3 months ago, # ^ |   +11 Thanks for sharing this, I was losing my head over my solution! I thought of the same but stupidly used dp[t[a[i]] when I should've been using dp[t[a[i]+1] as you mention; kept thinking of ways to get that working, gave up and just solved D1 instead.
•  » » 3 months ago, # ^ |   0 Can you share me your submission, please?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 195421246key part of the code  rep(i,0,n) { dp[i+1][0] = dp[i+1][1] = min(dp[i][0],dp[i][1]) + cold[a[i]]; if(i && a[i] == a[i-1]){ setMin(dp[i+1][1], min(dp[i][0],dp[i][1]) + hot[a[i]]); }else if(t[a[i]] != -1){ setMin(dp[i+1][0], dp[t[a[i]]+1+1][0] + (pres[i-1]-pres[t[a[i]]+1]) + hot[a[i]]); } t[a[i]] = i; } 
•  » » » » 3 months ago, # ^ |   0 thanks
•  » » 3 months ago, # ^ |   0 you are genius!!
 » 3 months ago, # | ← Rev. 3 →   +138 I have a different $O(n + k)$ solution for the problem 1799D2 - Hot Start Up (hard version).Let's say we currently need to run program $x$ and we want to run it in $hot_x$ seconds. To do this, we can use the same CPU that we used for the previous $x$, and use the other CPU for every program between these two. If the index of previous $x$ is $i$ and current $x$ is $j$, this means $i$ and $j$ will have the CPU 1, and every program in $[i + 1, j - 1]$ will have the CPU 2, or vice versa.So, if we know the answer to finish the first $i$ programs we can calculate the answer for $j$. To calculate the amount of time needed to use the other CPU for the tasks $[i + 1, j - 1]$, we can use prefix sums where the $kth$ program takes $cold_k$ seconds if it's different from the previous program and $hot_k$ seconds otherwise. However, there is something we're missing here. Please try to find it on your own. The IssueWhile calculating the time needed for programs $[i + 1, j - 1]$, we don't have any information about the last program that ran on CPU 2. It could be the same as program $i + 1$ which might change the answer. What To Do?Let's consider the case where the program $i + 1$ is the same as the last program that ran on CPU 2. If we call this program $y$, then CPU usage will look like this:  i j ..., y, ..., x, y, ..., x, ... 2 1 1 2 2 1 Looking at this, we can notice that if we know the minimum amount of time needed to finish programs $[1, i + 1]$, where the program $i + 1$ uses the same CPU as the previous same program, we know the program that ran last on the other CPU. Program $i$ used CPU 1 while program $i + 1$ used CPU 2. Using this, we can calculate the time needed for $[i + 2, j - 1]$ and update the answer for the program $j$ accordingly. How To Implement This?Let's say function $C(l, r)$ calculates the amount of time necessary to run programs [l, r] using prefix sums as I wrote earlier, $a_i$ stores the program number of $ith$ program, and $nxt_i$ stores the next index with the same program as this index.We can keep track of two different $dp$ arrays or one array with dimensions $(n, 2)$. For simplicity, let's keep track of two arrays and call them $A$ and $B$. $A_i$ stores the minimum amount of time to run the first $i$ programs if program $i$ took $cold_{a_i}$ seconds and $B_i$ stores the amount of time if it took $hot_{a_i}$ seconds.If we're at program $i$ and we want to update the next $dp$ values we can do it like this: If $a_i = a_{i + 1}$ $B_{i + 1} = min(B_{i + 1}, min(A_i, B_i) + hot_{a_{i + 1}})$ If $a_i \neq a_{i + 1}$ $A_{i + 1} = min(A_{i + 1}, min(A_i, B_i) + cold_{a_{i + 1}})$ If program $i + 1$ took $hot_{a_{i + 1}}$ seconds $B_{nxt_i} = min(B_{nxt_i}, B_{i + 1} + C(i + 2, nxt_i - 1) + hot_{a_{nxt_i}}$ If program $i + 1$ will take $cold_{a_{i + 1}}$ seconds $B_{nxt_i} = min(B_{nxt_i}, min(A_i, B_i) + cold_{a_{i + 1}} + C(i + 2, nxt_i - 1) + hot_{a_{nxt_i}}$ It's possible to only use one array considering that if we're currently at index $i$ the answer for $i + 1$ will only be $B_{i + 1}$. However, I think it's easier to understand this way.Here is my implementation: 195175862I tried to write it as clear as possible. However, I was in contest so if there is a mistake I'm sorry.Please let me know if you have any questions or if there is any mistake.
•  » » 3 months ago, # ^ |   +23 Thanks for explaining so well. Your example helped clear it up for me, I was stuck on the same issue and dropped this idea mid-contest in order to solve D1 in time.
 » 3 months ago, # | ← Rev. 2 →   0 what is wrong with this submission? failing on test case 8https://codeforces.com/contest/1799/submission/195211040
•  » » 3 months ago, # ^ |   +6 nevermind got it my solution does not guarantee that all elements are same at the end
 » 3 months ago, # | ← Rev. 2 →   +15 I also have a different O(n + k) solution for D2 with a very simple implementation: 195175038If you are interested, you can watch my video: https://www.youtube.com/watch?v=oOyPQL16x1M
 » 3 months ago, # | ← Rev. 2 →   0 What's intended for problem G? I solved it by counting it directly using DP, but everything that I know about solutions like this points to this dp being O(N^4), is it possible that it is O(N^3)?https://codeforces.com/contest/1799/submission/195217087Edit: I think that I managed to prove it being O(N^3). Basically for the transition at the first state being "i", we have at most (a[i] + 1) * (b[i] + 1) transitions. The sum of a[i] * b[i] is at most O(N^2). For each i, dp[i][j] has at most O(N) valid j's, so it ends up being O(N^3).
•  » » 3 months ago, # ^ |   0 Could you elaborate a bit more on your DP solution?
•  » » » 3 months ago, # ^ |   +8 I'm not sure if tfg did the same, but I just upsolved it without inclusion-exclusion and I used dp too. I calculated $dp_{i,j} =$ number of ways to vote if we only use the first $i$ groups and among the first $i$ groups $j$ people voted. To make transitions you want to know two things: how much people will vote for the new group that are also from the prefix, and how much people from the new group will vote for someone who is already on the prefix. In total there are $4$ loops, so it might look like it's $O(n^4)$, but $\sum_{i=1}^n sum_i*sz_i \leq n^2$, so the $3$ internal loops are actually $O(n^2)$ and the solution is $O(n^3)$. You might want to see my code.
•  » » 3 months ago, # ^ |   +10 My solution is $O(n^2)$ or $O(n\log^2 n)$(using divide and conquer FFT). I use inclusion–exclusion principle and calculate ways under $k$ fixed invalid votes.I'm a little confused with the constraint...
 » 3 months ago, # | ← Rev. 2 →   0 For E, you could do the “filling” as stated in the editorial last and find the intersection point first. You can just put a # there and then fill it. 195194226
 » 3 months ago, # |   +8 Why is the title of question B in the English answer in Russian?
•  » » 3 months ago, # ^ |   0 Isn't it "Equalize by Divide"?
 » 3 months ago, # |   -32 Bad problem ABC
 » 3 months ago, # |   0 Why is the constraint of the G problem so small? I thought this problem could be solved using formal power series in $\mathrm{O}(N\log^2N)$.my submission:https://codeforces.com/contest/1799/submission/195220905
•  » » 3 months ago, # ^ |   0 Actually I have an $O(N^2)$ solution with (quadratic)polynomial convolution, but can be improved to $O(NlogN)$ with NTT, this is my submission 195224839
•  » » 3 months ago, # ^ |   +39 I think any time there's a question of why bounds aren't higher, the answer is usually that increasing the bounds doesn't make the problem more interesting, just more tedious, so then it's polite to keep it lower. I also solved the problem with inclusion-exclusion, and my code can be easily turned from $\mathcal O(n^3)$ to $\mathcal O(n \log^2 n)$ by iterating more precisely over sum of $c_i$ per team and copy pasting some FFT templates, but that doesn't make the problem more interesting and is not the main idea of the problem imo.
 » 3 months ago, # | ← Rev. 2 →   +3 Hi guys you can check video editorial forProblem A , Problem B, Problem C, Problem D here — https://youtu.be/AGIrdT_cQuY
 » 3 months ago, # |   0 I think the solotion for E maybe $O(nm)$?Actually, we can use $2$ times filling operation to make a connected component meet the requirements.Here's my submission.
 » 3 months ago, # |   0 How do you approach Problem G?
•  » » 3 months ago, # ^ |   0 You can refer to this comment
 » 3 months ago, # |   0 Problem B simple approach using Queue : submission195227819
 » 3 months ago, # | ← Rev. 3 →   0 why does the following solution for problem A give a runtime error :195227711 but if I change all int to long long error is removed
 » 3 months ago, # |   +11 Passed E with $O(nm^4)$ and some Chinese kung fu(small constant) again! Can it be hacked?
 » 3 months ago, # |   0 Can anybody explain to me why my code won't give a correct output for D1? I'm stuck on it for hours and can't convince myself why it is wrong. my submission for D1
 » 3 months ago, # |   0 E,How to prove (i1,j1),(j2,j2) any Manhattan shortest path is right
 » 3 months ago, # |   0 In f, why can’t just pick k1 biggest elements to apply halve, then pick k2 biggest elements to apply subtract?
 » 3 months ago, # | ← Rev. 2 →   +55 Here's how I solved problem G.In such problems with some restrictions, using inclusion-exclusion often helps us. In this problem, we have the condition that people cannot vote for someone from the same team. Suppose $s[i]=\sum_{j=1}^{i} c_j$, where $s_0=0$.First of all, let's see what valid voting looks like. Assume that we have put $n$ boxes such that number $i$ is written on the boxes at positions $s_{i-1}+1$ to $s_i$ from the left. Notice the boxes having the same numbers are indistinguishable. Suppose $b_i$ is written on the $i-$th box from the left. Consider a permutation $p$ of length $n$ such that $p_i$ cast his vote in the $i-$th box. In a valid voting, $p_i$ and $b_i$ should not belong to the same team.So our restriction is that $p_i$ and $b_i$ should not belong to the same team. Suppose $dp[i]$ gives the number of permutations $p$ such that $p_j$ and $b_j$ belong to the same team at atleast $i$ indices.Now calculating $dp[i]$ is easy. Suppose set $S_t$ denotes the players of team $t$. Assume $V(S_t)=\sum_{x \in S_t} c_x$. So there are $V(S_t)$ boxes containing the number of team members $t$. How many ways are there to cast a vote, such $l$ people from team $t$ cast their votes in $l$ boxes belonging to people from the same team? It is $\binom{|S_t|}{l} \cdot \binom{V(S_t)}{l} \cdot l!$. Let us denote this by $W(S_t,V(S_t),l)$. How to get this? First, we decide which $l$ people out of $S_t$ to take. We get $\binom{|S_t|}{l}$ for that part. We must select $l$ boxes out of $V(S_t)$ boxes. We get $\binom{V(S_t)}{l}$ for that part. Now we can permute these $l$ people in any way, as all $l!$ permutations satisfy our condition. We are not focussing on the remaining $S_t-l$ people right now.So $dp[i]=(n-i)! \cdot \Pi_{t \in T} W(S_t,V(S_t),f_t)$, where $T$ denotes the set of available teams and $\sum_{t \in T} f_t = i$. How to get this? First of all, according to our definition of $dp[i],$ atleast $i$ people should vote for people from the same team. $\Pi_{t \in T} W(S_t,V(S_t),f_t)$ gives us the number of ways such that exactly $i$ people vote for people from same team. Now $n-i$ people are left. They can cast their vote without any restriction. Note that $n-i$ boxes are left. So we can permute $n-i$ people over $n-i$ boxes. Thus we get $(n-i)!$ for this part.Suppose $ans[i]$ gives the number of permutations $p$ such that $p_j$ and $b_j$ belong to the same team at exactly $i$ indices. Now $ans[i]=dp[i]-\sum_{j=i+1}^{n} \binom{j}{i} \cdot ans[j]$. Now how to get this? So $dp[i]$ gives us the number of permutations for all atleast $i$ indices. We need to remove the permutations in which more than $i$ people vote for people from the same team. Suppose $d$ is a permutation of length $n$ such that $d_k$ and $b_k$ belong to the same team at exactly $j$ indices. How many times would we have counted $d$ in $dp[i]$? We would have counted it $\binom{j}{i}$ times. So we got $\sum_{j=i+1}^{n} \binom{j}{i} \cdot ans[j]$ this way. Are we done? Not yet. Did you notice that the boxes with the same numbers are indistinguishable? We would have overcounted. So if $final[i]$ denotes the number of votings such that exactly $i$ person(s) vote person(s) from same team, $final[i]=\frac{ans[i]}{\Pi_{i=1}^{n} c_i}$. Our answer is just $final[0]$. Time complexity is $O(n^2)$(thanks to AbdelmagedNour for pointing it out). Codevoid solve(){ ll n; cin>>n; vector c(n+5),t(n+5); for(ll i=1;i<=n;i++){ cin>>c[i]; } for(ll i=1;i<=n;i++){ cin>>t[i]; } vector S(n+5,0),V_S_t(n+5,0); for(ll i=1;i<=n;i++){ S[t[i]]++; V_S_t[t[i]]+=c[i]; } vector dp(n+5,0); dp[0]=1; for(ll i=1;i<=n;i++){ vector adp(n+5,0); for(ll lft=0;lft<=n;lft++){ if(dp[lft]==0){ continue; } for(ll cur=0;cur<=S[i];cur++){ ll ways=(nCr(V_S_t[i],cur,MOD)*nCr(S[i],cur,MOD))%MOD; ways=(ways*fact[cur])%MOD; //ways correspnd to W(S_t,V(S_t),cur) adp[lft+cur]=(adp[lft+cur]+ways*dp[lft])%MOD; } } swap(dp,adp); } for(ll i=0;i<=n;i++){ dp[i]=(dp[i]*fact[n-i])%MOD; } vector ans(n+5,0); for(ll i=n;i>=0;i--){ ans[i]=dp[i]; for(ll j=i+1;j<=n;j++){ ans[i]-=nCr(j,i,MOD)*ans[j]; ans[i]%=MOD; } ans[i]=(ans[i]+MOD)%MOD; } vector final(n+5,0); for(ll i=0;i<=n;i++){ final[i]=ans[i]; for(ll j=1;j<=n;j++){ final[i]=(final[i]*inv_fact[c[j]])%MOD; } } cout<
•  » » 3 months ago, # ^ |   +20 I want to say that your solution is not $O(n^3)$, actually it's better. It's only $O(n^2)$.Why that's true?In calculation of dp, you have 3 loops, the first go from $1$ to $n$, the second go from $0$ to $n$, but the third doesn't always go to $n$. It goes from $0$ to $S[i]$, and sum of $S[i]$ overall values of $i$ is exactly $n$.So the complexity is only $O(n^2)$.
•  » » » 3 months ago, # ^ |   +8 Oh yes, thanks for mentioning it. I have edited my comment.
 » 3 months ago, # |   0 My doubt is related to problem A. In sample test case number 8. There are 16 unique new posts. And in my code I printed "-1" n-set.size() times (4-16 times which actually should not print "-1" at all). But it is giving TLE. When I printed the value n-set.size() in my terminal. It prints the value 18446744073709551604. Shouldn't it print -12 ?
•  » » 3 months ago, # ^ |   0 If you use size_t or other unsigned type for n, then n - set.size() is also unsigned, and subtraction overflows yielding $2^{64} - 12$.
•  » » » 3 months ago, # ^ |   0 But I stored n in intwhich is by default a signed container.
•  » » » » 3 months ago, # ^ |   +5 but set.size() is an unsigned int; when you perform an operation with an unsigned and a signed int, the latter casts to the unsigned type
•  » » » » » 3 months ago, # ^ |   0 Okay got it. Thankyou :)
 » 3 months ago, # | ← Rev. 2 →   0
 » 3 months ago, # |   0 can someone elaborate on why we pick the smallest and largest elements greedily at each step in problem B
 » 3 months ago, # |   +39 Where is tutorial for problems G & H?
 » 3 months ago, # |   0 Can anyone pls explain problem C with some more detailed explanation with c++ code
 » 3 months ago, # | ← Rev. 2 →   +13 I found C to be a lot more intuitive when solved recursively.My idea was first, sort the string lexicographically from least to greatest. Then, iterate over every 2 characters. $s = c_0 c_1 \dotsc c_n$Let $f(x)$ return the minimum of $\text{max}(x,\text{reverse}(x))$ (in other words, the problem statement; we want $f(s)$ )Let our answer $a$ be an empty string for now. If $c_0 = c_1$, then it's clear that $a = c_0 \underbrace{\dotsc \dotsc \dotsc \dotsc}_{\text{remaining characters}} c_1$ minimizes the lexicographic maximum because any other arrangement would have one orientation be clearly greater. For example, if $s = aabbb$ then placing any character on the ends other than $a$ would be worse than just placing $a$ on both ends.So, the problem now recurses, we need to find the minimum of $\text{max}(c_2c_3\dotsc c_n,c_nc_{n-1}\dotsc c_2)$ to fill in the remaining characters of $a$, aka $f(c_2c_3\dotsc c_n)$So, our answer in this case would simply be $f(s) = c_0 + f(c_2c_3\dotsc c_n) + c_1$, where $+$ is string concatenation.Now, if $c_0 > c_1$, then we have two choices. We can either haveCase 1. $a$ = $c_1 c_2 c_3 \dotsc c_n c_0$, because $\text{max}(a,\text{reverse}(a)) = a$Case 2. $a$ = $c_1c_3c_4 \dotsc c_0 \dotsc c_nc_2$I claim that case 2 will only be better if and only if there are exactly two different letters left and $c_1 = c_2$. Let's take an example $s_1 = abbbbb\dotsc b$We can write case 1 as $a_1 = bbb\dotsc ba$, and case 2 as $a_2 = bb\dotsc a \dotsc b$Let's look closely as my claim for case 2 being better than case 1. $c_0 > c_1$, only two types of letters, and $c_1 = c_2$. This immediately tells us that $c_0$ is the only letter of its kind. If it wasn't, then $c_0$ can't be greater than $c_1$. We can also deduce that there are at least two letters of the second kind, since $c_1 = c_2$ (we assume $c_2$ exists in this context).Let's call $c_0 = a$ and $c_1 = c_2 = \dotsc = c_n = b$ to make things a bit more clear.If we use up our only $a$ and delegate it to the back of our answer, then we won't be able to use it anywhere else (this should be obvious, since we only have 1 $a$, we should treasure it). $\text{max}(c_0 c_1 \dotsc c_n,c_n c_{n-1} \dotsc c_0)$ will just be the side starting with $b$, and our $a$ will only be in use at the end. So our string in case 1 will just end up looking like $bbbbb\dotsc bbba$We can clearly do better. Since $\text{max}(c_0 c_1 \dotsc c_n,c_n c_{n-1} \dotsc c_0)$ is going to start off with a $b$ anyway, why not just place $b$ on both sides and use our precious $a$ when it really counts. Well, we get one shot with using it and we want to put it in the best spot such that no matter if the string is reversed, it'll be as close to minimum as possible. If we decide to place our $a$ early up (suppose $bbbabbbbbbb\dotsc b$), then it's clear that $\text{max}(a_1,\text{reverse}(a_1))$ will just be $bbbbbbbabbb$, which is definitely far from the smallest we can do. Seeing that we want to minimize the worst that we can do, it makes sense to place our $a$ smack dab in the middle, so that no matter whether the string is reversed, it won't be significantly worse than our original. $f(s_1) = \underbrace{bbbb\dotsc}_{\lceil{\tfrac{s_1\text{.size()} - 1}{2}}\rceil} \underbrace{a}_{1} \underbrace{bbbb\dotsc}_{s_1\text{.size()} - 1 - \lceil{\tfrac{s_1\text{.size()} - 1}{2}}\rceil}$195387468
 » 3 months ago, # |   +13 Turns out H is just basic dynamic programming over a tree's edges in $O(N \cdot 3^K)$. For each edge with direction, which defines a subtree, we find the number of ways to assign a subset of the $K$ operations to some edges in its subtree, then we find the number of ways to assign all $K$ operations for each possible root of the final subtree. Merging two such DP rows for two edges from the same vertex takes $O(3^K)$, and if we want to assign an operation to a specific edge, it just has to come after all operations "below" it, so accounting for that takes $O(K \cdot 2^K)$.
 » 3 months ago, # |   +19 Auto comment: topic has been updated by subscriber (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 2 →   0 195483879 My solution for D1 is giving TLE. For each index i, i am maintaining pairs of programs run of cpu1 and cpu2. i have used unordered_map for storing the values. Can anyone please help?UPDATE: AC
 » 3 months ago, # | ← Rev. 3 →   0 I tried problem D1 with dp using two states of cpu1 and cpu2. Here is my recursive code with memoization. Please let me know why this is giving TLE in test case 4https://codeforces.com/contest/1799/submission/195531673
 » 3 months ago, # |   +11 Since F was tagged with flows, can someone explain their flows solution? Curious which insights from the editorial solution (if any) are needed to make it work.
•  » » 3 months ago, # ^ |   +8 (I'm sorry that you're receiving notifications for this reply) Is there any way to follow a comment thread in CF? It'll really help if I could get notified if someone replies with a flow idea to this comment thread. I had to visit this comment a few times today checking for updates, and it's a bit inconvenient. I know I can mark this comment as a favorite, but I'm not sure if that'll notify me of any new updates.
 » 3 months ago, # |   0 Can someone help where did my code/logic go wrong in D1 submission 195189579
 » 3 months ago, # |   0 Is $sz_v$ in solution H means the size of the subtree after removing parts appeared in current mask? If it stands for the size of the subtree, then there could be some operation-valid edges missed(consider this case: edges:{{1, 2}, {1, 4}, {2, 3}, {4, 5}, {5, 6}}, s:{5, 4, 2}, where edge{1, 4} can be removed as operation 3, yet neither $n - sz_4$ nor $sz_4$ is 2)
•  » » 3 months ago, # ^ |   0 Turns out it is(at least it can be).Code in Java: 196355197
 » 3 months ago, # | ← Rev. 2 →   0 Can someone explain the difference in the complexity of the two codes? Thanks.
 » 3 months ago, # |   0 if anyone looking for B solution. https://codeforces.com/contest/1799/submission/197846551
 » 2 months ago, # |   -10 In problem D1 , I've made several submissions but all of them received TLE and here is one of them TLE. But when I just changed the variable MLong from (2**63-1) to (2**62-1) , it was accepted . I usually make MLong assigned to (2**63-1) since it's equivalent to sys.maxsize but I dont't know why it gives TLE .Is that because of using of Big integers in python or another issue ?
•  » » 3 weeks ago, # ^ |   +5 Apologies for the necropost, but in case you still want to know, it was because there were some points in the code where the 2**63-1 limit was temporarily exceeded (i.e. by dp+hot and dp+cold). Changing 2**63-1 to 2**63-1-10**9 works, while changing it to 2**63-10**9 does not.This addition overflow issue is also why many coders choose their "infinities" to be less than half the maximum value.
•  » » » 3 weeks ago, # ^ |   +10 I got the answer from conqueror_of_tourist. Anyway , Thank you bro and I appreciate it :)
 » 3 weeks ago, # | ← Rev. 3 →   0 Ugly alternative solution to problem F (but easier to prove?): For the block of elements $\geq 2b$ (in increasing order), it's optimal to use both operations $1$ and $2$ on a suffix. For the block of elements in $[b+1, 2b-1]$, it's optimal to use operation $1$ on a suffix, and operation $2$ (in order of priority) on a suffix of the remaining elements, and on a suffix of the whole block. For the elements $\leq b$, it's optimal to use operation $2$ on a suffix, and operation $1$ on a suffix of the remaining elements. Moreover, it's never optimal to operate on elements $\leq b$ if you can still operate on elements $\geq 2b$. So, you can iterate over the number of moves of both types applied to the block $[b+1, 2b-1]$, and the rest is uniquely determined.AC submission: 206143039