### wuhudsm's blog

By wuhudsm, history, 7 weeks ago,

Thank you for participation and we hope you enjoy this round :)

#### D2A — Shuffle Party

Idea : chromate00

Hint (for thinkers)
Hint (for observers)
Tutorial
solution

Video editorial by aryanc403 https://www.youtube.com/watch?v=lLmVzA49BRM

Idea : wuhudsm

Hint1
Hint2
Hint3
Tutorial
solution

#### D1A — Bitwise Operation Wizard

Idea : wuhudsm

Hint1
Hint2
Hint3
Tutorial
solution

Video editorial by aryanc403 https://www.youtube.com/watch?v=jfcx1Rs8I28

#### D1B — Pinball

Idea : wuhudsm

UPD: It conflicts with https://mirror.codeforces.com/contest/733/problem/E. This is a coincidence. There are no excuses. Very sorry for any inconvenience caused to everyone.

Hint1
Hint2
Hint3
Tutorial
solution

#### D1C — Pokémon Arena

Idea : wuhudsm

Hint1
Hint2
Hint3
Tutorial
solution

Video editorial by aryanc403 https://www.youtube.com/watch?v=ysdozposXkQ

#### D1D — Bitwise Paradox

Idea : Psychotic_D, MagicalFlower

Tutorial
solution

Idea : wuhudsm

Hint1
Hint2
Hint3
Tutorial
solution

#### D1F — Grand Finale: Circles

Idea : chromate00

UPD: The TL was a bit too loose, and unintended solutions with $\mathcal{O}(n \log^2 (1/\epsilon))$ complexity passed during the round. For the sake of the problem itself, I suggest that you try to solve assuming a $1$ second time limit.

Tutorial
solution
• +192

 » 7 weeks ago, # |   0 fast editorial
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +16 ++ fast system testing
•  » » » 7 weeks ago, # ^ |   +4 It seems like it's forzen right now...
•  » » » » 7 weeks ago, # ^ |   0 Why it,s frozen? Do you have any idea ?
•  » » 7 weeks ago, # ^ |   0 kindly help me in this DIV2 -Bint n;void solve(){cin>>n;string u, d; cin>>u>>d;string s = u[0] + d;string c=s;int cnt=0;for(int i=0;i
•  » » » 7 weeks ago, # ^ |   +3 哥们，string 比较大小时间复杂度很高，每次比较大小都是O（n），因此整个时间复杂度是O(t*n^2),so ， This code may exceed the time limit
•  » » » » 7 weeks ago, # ^ |   0 yeah. I got the same problem, so I had to switch the solution entirely. Luckily, I was able to solve it.
•  » » » 7 weeks ago, # ^ |   0 If in terms of string comparison, you can use a hash plus binary search, binary search to find the longest length of the same prefix, the next position is the first different position, and then compare the characters at that position, this only requires O(logn), preprocessing requires O(n). By machine translation, there may be errors,you can continue to ask me.
 » 7 weeks ago, # |   -20 Fast Editoral
 » 7 weeks ago, # | ← Rev. 2 →   -8 Fast editorial! Never seen one posted so fast after a contest.
•  » » 7 weeks ago, # ^ |   +41 if we don't mention um_nik's editorial
•  » » » 7 weeks ago, # ^ |   0 Haven't tried his rounds yet
•  » » » » 7 weeks ago, # ^ |   +5 It's a joke about last div3 https://codeforces.com/blog/entry/126461
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 It was this contest that he accidentally published his screencast 40 minutes before the end of the contest.
 » 7 weeks ago, # |   +11 Great round ! I really enjoyed solving problem B and C. Congrats to the authors !
 » 7 weeks ago, # |   +14 I don't know if I should be happy that I solved div1A+B fast or sad that I spent over an hour on C and didn't get it!!Either way, thank you for the amazing contest! I've just got to read the editorial for C now ^_^
 » 7 weeks ago, # |   -18 fast editorial
 » 7 weeks ago, # |   +13 Interesting problems, but don’t you think that the difficulty of Div.1 is A > B > C?
 » 7 weeks ago, # | ← Rev. 4 →   +59 For problem F I didn't have enough braincells for solving the k=3 case so I simply used the idea from Radewoosh's blog number 5 https://codeforces.com/blog/entry/61710 (binary search for the radius + the blog for finding the intersection after shrinking circles + using golden-ratio search to optimize).Also didn't realize the k=4 case apparently didn't exist, hopefully it's not FST due to time seed.Edit: chromate00 idk if it was you that put that note for F, but doing binary search and ternary search while doing the rest as in the editorial seems fine to me. The expected number of retries in the algorithm is O(log^3N) I'm pretty sure, so in the end it's something like O(log^3N * log^2precision) + O(N).
•  » » 7 weeks ago, # ^ |   0 It should be fine if you do the rest of the blog along with one binary search. I haven't tested with two, though. The $\mathcal{O}(n\log^2(1/\epsilon))$ I was referring to was the nested golden section search where the $\mathcal{O}(n)$ is simply from calling the objective function. Do note though, that we do have a tester solution with $\mathcal{O}(n\log^2(1/\epsilon))$ complexity that passes in ~800ms.
•  » » » 7 weeks ago, # ^ |   0 hmm I just submitted $O(n\log^2(1/\epsilon))$ and it's faster than everyone else's solutions ...
•  » » » » 7 weeks ago, # ^ |   0 I believe it is one of the $\mathcal{O}(n \log^2(1/\epsilon))$ we intended to allow. Most of the $\mathcal{O}(n \log^2(1/\epsilon))$ I meant to block were the ones that do ternary search on both $x$ and $y$, to maximize $r$. In the meantime, a tester's solution using binary search on $r$ with a clever check function passes in about 800ms.
•  » » » » » 7 weeks ago, # ^ |   +20 Ok.Ok. Btw, I tried uncommenting the first random shuffle in the model sol and resubmitting with different random seeds, and they all gave different outputs. So I assume the model sol is not correct.Example code (only difference is the seed):AC: 249100355WA: 249108458249116485249116654
•  » » » » » » 7 weeks ago, # ^ |   0 As far as I believe, the issue is in the precision of the type itself. It can be fixed by implementing a class for $\frac{p}{q}+\frac{r}{s}\sqrt{t}$, so I will consult the coordinator about replacing the model solution with one that uses exact computations. The current version of data was cross-validated with BurnedChicken's binary search solution, which made me believe it is precise enough.
 » 7 weeks ago, # |   0 Is Div2B is possible by doing just simple dfs?
•  » » 7 weeks ago, # ^ |   0 No, it's too slow.
•  » » » 7 weeks ago, # ^ |   0 How?Shouldn't it be 4*10^5?Or I am making miscalculation here,can you give me the tc for a bfs for the test cases?
•  » » » » 7 weeks ago, # ^ |   0 On each position in first string you will have 2 ways you can go, right and down, when you go right you do the same choice, but when you go down you have to go right to the end of the string, so in total you have O(n*(n+1)/2) time complexity, and because you have 10000 tests in one testcase you have n*(n+1)/2*10000 = 200'001'000'000'000 total operations which is obviously too much.
•  » » 7 weeks ago, # ^ |   0 Can you please share the approach , thanks !
 » 7 weeks ago, # |   0 Interesting round! Really like it when there is an interactive problem in the round
 » 7 weeks ago, # |   0 Div. 2 PROBLEM B (Binary Path) video Editorial : YOUTUBE EDITORIAL LINK Audio : Hindi
 » 7 weeks ago, # |   +8 Fast editorial, and...using namespace atcoder; is found in problem 1E !
 » 7 weeks ago, # | ← Rev. 2 →   +3 This Round was really amazing. I really enjoyed this round
 » 7 weeks ago, # |   +18 Why is the system testing frozen?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +2 I am not sure but I think because the problem D1B — Pinball is conflicting
•  » » 7 weeks ago, # ^ |   +10 Issue from the server side.
 » 7 weeks ago, # |   0 https://codeforces.com/contest/1937/submission/248965536Why is this giving tle? It is nlogn
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +2 You're keeping n strings in map, all of which have length more than n, so O(n^2) memory and even bigger time complexity.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 The first thing I can observe in your solution is that you should use unordered_map when the type of keys is string. It uses hashed keys so that the problem due to the comparison time of string values can be resolved.Edit: Similarly, you can use unordered_set instead of set
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 Also you are deleting first charachter of a string and you are doing that n times so only that is O(n^2) which is too slow.
•  » » » 7 weeks ago, # ^ |   0 But isnt deleting the character an O(1) operation?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Nope, deleting character from a string is O(n)
 » 7 weeks ago, # |   +6 I love D1A = D2C. Very Beautiful problem!
•  » » 7 weeks ago, # ^ |   0 Why do we try step 3 in Div2 C? Do we need to find the smallest one?
•  » » » 7 weeks ago, # ^ |   0 When you ask a question it uses bitwize or, but for answer you need bitwize xor
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Yes. A xor B = (A or B) - (A and B), and the candidates obtained after completing the step 2 satisfy the condition that the bit in a particular digit has a value of 1. It is because maximal value of pi or pj is 111...111(2) form.
•  » » » » 7 weeks ago, # ^ |   0 Yeah, I see. But I think when I finished the step 1, I can get the position of n-1. And then I don't understand why step 2 is needed. Assum that the position of n-1 is x. I think we can get the position of candidate that can make px^pk maximum without step 2. What is the mistake? This is my code but I got wrong answer. https://codeforces.com/contest/1937/submission/248971409 Please let me know the reason.
 » 7 weeks ago, # |   0 Super fast editorial
 » 7 weeks ago, # |   0 This is hard!
 » 7 weeks ago, # |   -9 In Div 2 B, how to prove that if a=b, then it's optimal to move to the right?
•  » » 7 weeks ago, # ^ |   +10 If you go right, you always have the chance to go down.There by you can have minimum among those both
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   -12 Thank you! I thought it won't always be optimal and therefore tried to solve it by dp
 » 7 weeks ago, # |   0 why is ffush giving idleness, but changing all to cout.flush() is AC
•  » » 7 weeks ago, # ^ |   +4 Because you have "ios_base::sync_with_stdio(false);" in your code so fflush doesn't affect cout.
•  » » » 7 weeks ago, # ^ |   0 Thank you for replying, I didnt know that.
 » 7 weeks ago, # |   0 for problem D2B — Binary Path ...you can also use dp for counting number of paths. Submission
•  » » 7 weeks ago, # ^ |   0 3d dp is too much to understand. I better stay away from it.
•  » » 7 weeks ago, # ^ |   0 also possible with 2d dpcode
•  » » » 7 weeks ago, # ^ |   0 The first dimension is just the combination of two arrays the array for visited checking dp[0] and the array for the answer itself dp[1]This doesn't increase the time complexity of the code; in fact, it optimizes the time complexity by avoiding the need to reassign the entiredparray as not visited for each test case. Instead, I only need to check whether theidof the current state is equal to the current test'sid. If it is, then the current state has already been visited during the current test case.This is why there's a difference between our time complexities of our codes Spoiler I use array instead of vector and I don't reassign it at each test case
 » 7 weeks ago, # | ← Rev. 3 →   0 Can anybody explain this bigotry. 248984409 Global Dp arrays passes easily.248971939 Dp arrays passed by reference gives MLE. Is pass by reference soooo bad ????? Exactly the same solution. The little rating points that I had are now gone. :(
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 In your submission with the DP-array passed as reference you accidentally create an n*n array instead of 2*n. :/
•  » » » 7 weeks ago, # ^ |   0 I'll go slap myself a couple hundred times. Thanks a lot for answering.
 » 7 weeks ago, # |   0 F: "Using nested ternary searches does not help very much. The time complexity will be $O(n \cdot log^{2}(1/ϵ))$, but the constants are large due to multiple function calls and floating point operations" lol 3 out of 4 accepted submissions use nested ternary searches
•  » » 7 weeks ago, # ^ |   +5 We tested nested ternary searches, but not golden section search. That was why I didn't see that coming. This is entirely my fault for not having considered.
 » 7 weeks ago, # |   0 Problem B can also be solved by dp. My submission https://codeforces.com/contest/1937/submission/24898172.First we create most optimal string and then apply dp for how many ways we can create this string.(Basically number of paths).
 » 7 weeks ago, # |   0 I used a similar approach to solve problem D2B: I'll explain it here to hopefully help someone. There are only n possibile way we can go from (1,1) to (2,n), that are characterized by the point in which it goes downward. We want to remember this point. To find the lexicographically shortest path, it is enough to choose of going downward if down = '0' and right = '1' or if we are in position (1,n), otherwise we continue on the right. To count how many path of the same type are there, startig from the point in wich it goes downward, we increment a counter until the char in position (1,i) == (2,i-1), for each decrementing i. This means that turning down before we did wouldn't have modified the path. Time complexity: O(n).My submission as reference: 248990348.
 » 7 weeks ago, # |   -8 Please can somebody tell me why this is giving TLE? #include using namespace std; #define ll long long #define ull unsigned long long int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tt; cin >> tt; while (tt--) { int n; cin >> n; vector> board (2, vector(n, ' ')); for (int i = 1; i <= 2; ++i) { string s; cin >> s; for (int j = 1; j <= n; ++j) { board[i-1][j-1] = s[j-1]; } } vector> dp1 (2, vector(2, "")); for (int j = 0; j < n; ++j) { for (int i = 0; i < 2; ++i) { if (i == 0 && j == 0) { dp1[j][i] = board[i][j]; continue; } if (i - 1 >= 0) { if ((int)dp1[j%2][i].size() != i + j + 1) { dp1[j%2][i] = dp1[j%2][i-1] + board[i][j]; } else { dp1[j%2][i] = min(dp1[j%2][i], dp1[j%2][i-1] + board[i][j]); } } if (j - 1 >= 0) { if ((int)dp1[j%2][i].size() != i+j+1) { dp1[j%2][i] = dp1[(j+1)%2][i] + board[i][j]; } else { dp1[j%2][i] = min(dp1[j%2][i], dp1[(j+1)%2][i] + board[i][j]); } } } } cout << dp1[(n-1)%2][1] << '\n'; vector> dp2 (2, vector(2, 0)); for (int j = 0; j < n; ++j) { for (int i = 0; i < 2; ++i) { if (i == 0 && j == 0) { dp2[j][i] = 1; continue; } dp2[j%2][i] = 0; if (dp1[(n-1)%2][1][i+j] == board[i][j]) { if (i-1 >= 0) dp2[j%2][i] += dp2[j%2][i-1]; if (j-1 >= 0) dp2[j%2][i] += dp2[(j+1)%2][i]; } // cout << i << ' ' << j << ' ' << dp2[i][j%2] << '\n'; } } cout << dp2[(n-1)%2][1] << '\n'; } return 0; } 
 » 7 weeks ago, # |   +10 There is a square-root decomposition solve for bitwise paradox in $O(n\sqrt{n} + qlogn\sqrt{n})$, assuming DSU is $O(1)$. By breaking the array down into sqrt blocks, we can merge in ascending values of $a_i$ in each block and store the maximum prefix, suffix, and subarray OR in each block for such $a_i$. We can now simply binary search for a value $x$, merging blocks from left to right, keeping track of the current longest suffix and checking if the maximum subarray OR $\geq v$. Submission: 248991851
•  » » 7 weeks ago, # ^ |   0 I tried same solution for Div1D, but I got some memory trouble and failed to solve within the contest time..... (I used 4 * 4 * N * sqrt(N) 8bit integers, which seems too large) My submission: 248971206
•  » » » 7 weeks ago, # ^ |   +10 I made the blocks a bit bigger so my solution would take less memory, but my solution is still very tight on memory.
•  » » 4 weeks ago, # ^ |   0 Same thing can be done using segment tree to reduce the memory to NlogN and complexity to NlogN 251321474
 » 7 weeks ago, # |   0 Can B be done with string hashing? After getting the best possible string, we can just try all possible paths in O(1) each?
•  » » 7 weeks ago, # ^ |   0 Spoiler, it does work:(used kactl hashing) 249355708
 » 7 weeks ago, # |   0 Thanks for the organizers, hated this contest
 » 7 weeks ago, # |   0 At div1 C, can't you just have edge from X[rank[i]] to i with cost 0, meaning that you defeat the pokemon i?
 » 7 weeks ago, # |   +4 The solution to problem 1D is really similar to problem 1004F.I modified about 3 lines of code and added a ST table and got accepted :(
 » 7 weeks ago, # | ← Rev. 5 →   +52 For problem D1A — Bitwise Operation Wizard, we can actually reduce the number of queries needed to at most $2n$. Here's how.From the editorial, we can see that we have $3$ steps, where the first step is finding first number (the editorial encourages us to find the maximum for this one) with $n-1$ queries, the second step is finding candidates for second number by finding maximum OR value with $n-2$ queries, and the third step is finding minimum from the candidates (since the minimum produces maximum XOR with the first number, the proof is left to the reader as exercise) with $sz-1$ queries, where $sz$ is the number of candidates and $sz \leq n$. This optimization mainly focuses on the first step.Now, let $2^k < n \leq 2^{k+1}$ for some integer $k \geq 1$ (since $n = 2$ is pretty trivial lol). If we do our observation correctly, we'll notice that $p_i \oplus p_j \leq 2^{k+1}-1$. Funnily enough, we can reduce the number of queries in the first phase to $2^{k+1}-n$ queries. This can be done by realizing that any number from $2^{k+1}-n$ to $n-1$ are always valid candidates for the first number $p_i$, since they always have a second number $p_j \leq n-1$ such that $p_i \oplus p_j = 2^{k+1}-1$. And so, we only need to use $2^{k+1}-n$ queries to find any number that is $\geq 2^{k+1}-n$ (by knowing that the number is larger than at least $2^{k+1}-n$ other numbers).From my calculation, from all of the possible permutations of $[0 \dots n-1]$, the third phase actually uses at most $n-2$ queries if $n = 2^{k+1}$ and at most $n - 2^k - 1$ queries otherwise, since the number of queries actually depends on the size of the candidates.I believe the worst case can only happened at $n = 2^k+1$ and $n = 2^{k+1}$, where both only spent $2n-4$ queries. And thus, this problem is solved using $\leq 2n$ queries.Edit: I found this during the round testing and suggested to add it as a hard version of the problem, but they refused lmao.Edit 2: If anything seems wrong in this message, please let me know :3Edit 3: Credit to MCYang for the concise upper bound for the step $3$ and some corrections to the comment ^w^
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0
•  » » 7 weeks ago, # ^ |   0 Interesting idea overall, though I think one of the steps needs some clarification.In the explanation of step 3, when you mentioned that "$m$ is the number of active bits in the number $a$," $a$ actually comes out of nowhere. Does it mean a number we found at step 1? If so, why do you restrict the range of $a$ to $2^k\leq a •  » » » 7 weeks ago, # ^ | 0 thanks man, will fix it :3  » 7 weeks ago, # | 0 https://codeforces.com/contest/1937/submission/249016789 Why is this giving tle at 10th test case? •  » » 7 weeks ago, # ^ | +3 you did string assigning ans = temp$n$times, which results in$O(n^2)$complexity since string assigning is$O(n)$. •  » » » 7 weeks ago, # ^ | 0 Thanks! Is there any way i can optimise that approach? •  » » » » 7 weeks ago, # ^ | +3 hint: notice that everytime, you only need to change one character inside the temp string, which means that when you need to change ans, you can do so by only changing one character inside of it •  » » » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 :_), yea that makes sense. Thanks edit- still tle. •  » » » » » » 7 weeks ago, # ^ | 0 else if(temp==ans) x++; is$O(n)$since temp and ans are strings of length$O(n)$. This makes your code$O(n^2)$. •  » » » » » » » 7 weeks ago, # ^ | 0 Fixed that, got AC. Thanks!  » 7 weeks ago, # | 0 can anyone help me in this DIV2 -Bint n;void solve(){ cin>>n; string u, d; cin>>u>>d; string s = u[0] + d; string c=s; int cnt=0; for(int i=0;i •  » » 7 weeks ago, # ^ | 0 May be the way you are checking s •  » » 7 weeks ago, # ^ | 0 I uploaded to Youtube a video in English explaining the solution of Div2-B  » 7 weeks ago, # | 0 248985883Can you help me? I am getting TLE. But my code is supposed to be in NlogN time only.  » 7 weeks ago, # | 0 can anyone prove/justify Step 3 of editorial of D2C/D1A.why minimum need to be choosen. •  » » 7 weeks ago, # ^ | 0 Cause the minimum is the one that does not have any bit in common with n-1, therefore maximazing the XOR.  » 7 weeks ago, # | +8 I will share my solution for D1F.First, binary search for$r$. The maximum circle has radius at least$r$is equivalent to the$n$circles with their radius decreased by$r$have a non-empty intersection. If the intersection is non-empty, the intersection is convex.Then do binary search for$y$. For$y=k$, one of the following is true: The line$y=k$crosses through the intersection. The intersection is entirely in the$y>k$half-plane. The intersection is entirely in the$yk$half-plane. There are many ways to check this.  » 7 weeks ago, # | 0 Problem D can be done in$O(\log V\log\log V)$per query of type 1 and$O(\log n)$per query of type 2. The idea is to maintain all minimal good intervals$[l,r]$(good intervals such that neither$[l+1,r]$and$[l,r-1]$are good) in sorted order using a BBST. Type 2: Query min of a range in the BBST. Type 1: Erase all$O(\log V)$intervals in the BBST crossing$i$, then find all$O(\log V)$intervals crossing$i$, then insert them back into the BBST. To find the intervals quickly we can maintain a separate vEB tree for each bit, allowing us to find the closest index$j$greater or less than$i$such that$b_j$has a certain bit set.  » 7 weeks ago, # | 0 My Screencast for A and B problems: https://youtube.com/live/IU6Zqy5LGB4 This was private during the contest. Hope it helps someone. •  » » 7 weeks ago, # ^ | 0 Bro no one is interested in seeing you struggling in problem A, so stop spamming the commemt section under every blog post •  » » » 7 weeks ago, # ^ | 0 I apologize, bro. I understand that my struggle with problem A, taking 3 minutes to solve (which may seem slow to you for someone "green"), might not be of interest to everyone. I acknowledge that I need to improve, and I'll work harder in the future.Regarding your statement that 'no one wants to watch,' I must respectfully disagree. I get over 30 (sometimes 100) watch hours on these videos in total, indicating that there is indeed interest. However, if my content doesn't resonate with you, you're welcome to unsubscribe and find content that better suits your preferences. Criticizing someone's honest efforts without constructive feedback isn't fair or productive. •  » » » » 7 weeks ago, # ^ | 0 why are you specifically mentinoning "green". making fun of someone's rating without constructive feedback isn't fair or productive. •  » » » » » 7 weeks ago, # ^ | 0 I was talking about me... i am green so it will take time to solve. •  » » » » » » 7 weeks ago, # ^ | 0 oh, I thought you were teasing me. Sorry  » 7 weeks ago, # | ← Rev. 2 → 0 Round 930 div 2 problem C: code -> 249045846Idleness limit exceeded on test 1 why? what's wrong? Please identify the mistake and let me know •  » » 7 weeks ago, # ^ | 0 If you read interactive problems guidelines, you shouldn't do this #define endl "\n"  » 7 weeks ago, # | 0 Problem D1B Pinball can be done in O(n)` time: No need to binary search for the proper endings, as they are changing monotonically as you go from one query index i to i+1. 249059259  » 7 weeks ago, # | 0 In the editorial for D2B , I think the initial value of 'max_down' should be (n-1). correct me if I am wrong  » 7 weeks ago, # | +1 The influence of clash of D1B is quite big. it appears just following the beginning problem and people soon finds the clash, as you can see a originally *2400 problem(733E) passed by a lot of people. my advise is just make this round unrated if possible.  » 7 weeks ago, # | 0 Good idea hh  » 7 weeks ago, # | ← Rev. 2 → 0 I am not able to understand problem D ??? Div2  » 7 weeks ago, # | ← Rev. 3 → 0 In F I solved the 3-circle case like this: I applied an inversion at one of the intersection points of 2 circles and found a circle inscribed between an arc and 2 segments with Sawayama theorem. Unfortunately after inversion the picture becomes heavily dependant on the point configuration, and I think my code that passed doesn't quite work (though I don't understand how), as it sometimes finds no circles between the given 3 at allEdit: Also now it works insanely fast without hypotl calls  » 7 weeks ago, # | 0 How to get pupil rank?  » 7 weeks ago, # | 0 For the problem D, at the end of the editorial, they said : It is not difficult to observe that we can use prefix sum to store the sum of indices, and then quickly calculate the time when the pinball moves.And to calculate the pinball moves the precalculate two arrays: IDr[i]=IDr[i-1]+i*(s[i-1]=='>'); IDl[i]=IDl[i-1]+i*(s[i-1]=='<'); and for case s[i-1] == '<' && countright(1,p) > countleft(p+1,n), the ball should go at the end, from leftk to boundary. But the moves was got in such a way:2*((IDl[n]-IDl[i])-(IDr[i]-IDr[k-1]))+i+(n+1) with k the last movemement before go out.  » 7 weeks ago, # | 0 In D1C，why add Y node？ edge x -> Pokémon node with a value of 0？  » 7 weeks ago, # | 0 Can someone please help me in finding the mistake in the following code? Here , I have first calculated the index , which means that the substring b starting from index to n-1 is lexicographically smaller or equal to the substring a from index+1 to n.Submission  » 7 weeks ago, # | 0 Can someone pls review my code and tell me in which test code my code is getting error :) https://codeforces.com/contest/1937/submission/249344544  » 7 weeks ago, # | 0 Can someone please explain how do we derive the formula for Problem D? I'm so confused!  » 7 weeks ago, # | ← Rev. 2 → 0 Problem c sucks!!  » 7 weeks ago, # | 0 What is line segment tree mentioned in div 1 D?  » 5 weeks ago, # | +10 Did the tutorial of Div.1 E missed some factorial notations in the final transform formulas of$f$?For example$f_i = -\sum_{j=0}^{last_i} f_j \cdot A_{i-j-1}^{P_i-j-1} = -(P_i-i)^{-1} \sum_{j=0}^{last_i} f_j \cdot (P_i-j-1)$, I think it should be$f_i = -\sum_{j=0}^{last_i} f_j \cdot A_{i-j-1}^{P_i-j-1} = -((P_i-i) {\color{red}!} )^{-1} \sum_{j=0}^{last_i} f_j \cdot (P_i-j-1) {\color{red}!}$.And if this is correct, how can we do D&C + FFT with$(P_i-j-1)!$in the formula? •  » » 5 weeks ago, # ^ | ← Rev. 2 → +3 Thx,typo fixed.You can read https://mirror.codeforces.com/blog/entry/18842 for D&C + FFT tricks(in DIV1E). •  » » 4 weeks ago, # ^ | +10 I had the same question as you, because the editorial made me think that the formula$f(i) = h(i)\sum f(j)g(p_i-j)$can be written in the form$f(i) = h(i)\sum f(j)g(i-j)$somehow. This is not true. Instead, when performing the convolution step, you compute$F(i) = \sum f(j)g(i-j)$and then take$f(i) = h(i)F(p_i)$. Note that unlike the example 553E - Kyoya and Train that wuhudsm referenced, in the convolution step you may be performing a convolution of vectors of very different sizes. Due to$p$being an increasing function from$0$to$n$, the time complexity works out correctly in the end (in my opinion, the editorial would be improved if it explained this part).  » 5 weeks ago, # | 0 Thanks wuhudsm for the great tutorial for problem div2 E (Pokemon Arena).However, I think there's a typo in the first line of the tutorial. It makes more sense to be like that, Then the problem is essentially finding the shortest path from$1$to$n$and not from$n$to$1\$ as written in the tutorial.Please correct me if I am wrong.
 » 5 weeks ago, # |   0 D1E, am I right that last_i = max(j
 » 5 weeks ago, # | ← Rev. 3 →   0 Div1D can support range update and only use one segment tree if we design our node to have logV merge. See 251321474 See node in struct MinGood, it will have a bit more memory O(NlogN) (logN per node) but that still fits.
 » 2 weeks ago, # | ← Rev. 2 →   0 Solution to Div 2 problem E reminds me of the graph construction we do for proving NP-Completeness of certain problems. Can someone suggest problems to get good at thinking like this?