wuhudsm's blog

By wuhudsm, 5 months 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

Idea : wuhudsm

Hint1
Hint2
Hint3
Tutorial
solution

Idea : wuhudsm

Hint1
Hint2
Hint3
Tutorial
solution

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

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

 » 5 months ago, # |   0 fast editorial
•  » » 5 months ago, # ^ | ← Rev. 2 →   +16 ++ fast system testing
•  » » » 5 months ago, # ^ |   +4 It seems like it's forzen right now...
•  » » » » 5 months ago, # ^ |   0 Why it,s frozen? Do you have any idea ?
•  » » 5 months 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
•  » » » 5 months ago, # ^ |   +3 哥们，string 比较大小时间复杂度很高，每次比较大小都是O（n），因此整个时间复杂度是O(t*n^2),so ， This code may exceed the time limit
•  » » » » 5 months ago, # ^ |   0 yeah. I got the same problem, so I had to switch the solution entirely. Luckily, I was able to solve it.
•  » » » » 3 months ago, # ^ |   0 What's this, 混合双语解答问题吗，I don't think anyone can understand this :(
•  » » » » » 3 months ago, # ^ |   0 你不就understand了嘛qwq
•  » » » 5 months 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.
 » 5 months ago, # |   -20 Fast Editoral
 » 5 months ago, # | ← Rev. 2 →   -8 Fast editorial! Never seen one posted so fast after a contest.
•  » » 5 months ago, # ^ |   +41 if we don't mention um_nik's editorial
•  » » » 5 months ago, # ^ |   0 Haven't tried his rounds yet
•  » » » » 5 months ago, # ^ |   +5 It's a joke about last div3 https://mirror.codeforces.com/blog/entry/126461
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 It was this contest that he accidentally published his screencast 40 minutes before the end of the contest.
 » 5 months ago, # |   +11 Great round ! I really enjoyed solving problem B and C. Congrats to the authors !
 » 5 months 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 ^_^
 » 5 months ago, # |   -18 fast editorial
 » 5 months ago, # |   +13 Interesting problems, but don’t you think that the difficulty of Div.1 is A > B > C?
 » 5 months 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://mirror.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).
•  » » 5 months 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.
•  » » » 5 months ago, # ^ |   0 hmm I just submitted $O(n\log^2(1/\epsilon))$ and it's faster than everyone else's solutions ...
•  » » » » 5 months 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.
•  » » » » » 5 months 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
•  » » » » » » 5 months 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.
 » 5 months ago, # |   0 Is Div2B is possible by doing just simple dfs?
•  » » 5 months ago, # ^ |   0 No, it's too slow.
•  » » » 5 months 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?
•  » » » » 5 months 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.
•  » » 5 months ago, # ^ |   0 Can you please share the approach , thanks !
 » 5 months ago, # |   0 Interesting round! Really like it when there is an interactive problem in the round
 » 5 months ago, # |   0 Div. 2 PROBLEM B (Binary Path) video Editorial : YOUTUBE EDITORIAL LINK Audio : Hindi
 » 5 months ago, # |   +8 Fast editorial, and...using namespace atcoder; is found in problem 1E !
 » 5 months ago, # | ← Rev. 2 →   +3 This Round was really amazing. I really enjoyed this round
 » 5 months ago, # |   +18 Why is the system testing frozen?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +2 I am not sure but I think because the problem D1B — Pinball is conflicting
•  » » 5 months ago, # ^ |   +10 Issue from the server side.
 » 5 months ago, # |   0 https://mirror.codeforces.com/contest/1937/submission/248965536Why is this giving tle? It is nlogn
•  » » 5 months 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.
•  » » 5 months 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
•  » » 5 months 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.
•  » » » 5 months ago, # ^ |   0 But isnt deleting the character an O(1) operation?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Nope, deleting character from a string is O(n)
•  » » » » 2 months ago, # ^ |   0 deleting the last $m$ characters is $O(m)$, but deleting the first letters is like moving the rest to the front, which is $O(n)$.
•  » » » » » 2 months ago, # ^ |   0 Appending is the same way.
 » 5 months ago, # |   +6 I love D1A = D2C. Very Beautiful problem!
•  » » 5 months ago, # ^ |   0 Why do we try step 3 in Div2 C? Do we need to find the smallest one?
•  » » » 5 months ago, # ^ |   0 When you ask a question it uses bitwize or, but for answer you need bitwize xor
•  » » » 5 months 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.
•  » » » » 5 months 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://mirror.codeforces.com/contest/1937/submission/248971409 Please let me know the reason.
 » 5 months ago, # |   0 Super fast editorial
 » 5 months ago, # |   0 This is hard!
 » 5 months ago, # |   -9 In Div 2 B, how to prove that if a=b, then it's optimal to move to the right?
•  » » 5 months ago, # ^ |   +10 If you go right, you always have the chance to go down.There by you can have minimum among those both
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -12 Thank you! I thought it won't always be optimal and therefore tried to solve it by dp
 » 5 months ago, # |   0 why is ffush giving idleness, but changing all to cout.flush() is AC
•  » » 5 months ago, # ^ |   +4 Because you have "ios_base::sync_with_stdio(false);" in your code so fflush doesn't affect cout.
•  » » » 5 months ago, # ^ |   0 Thank you for replying, I didnt know that.
 » 5 months ago, # |   0 for problem D2B — Binary Path ...you can also use dp for counting number of paths. Submission
•  » » 5 months ago, # ^ |   0 3d dp is too much to understand. I better stay away from it.
•  » » 5 months ago, # ^ |   0 also possible with 2d dpcode
•  » » » 5 months 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
 » 5 months 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. :(
•  » » 5 months 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. :/
•  » » » 5 months ago, # ^ |   0 I'll go slap myself a couple hundred times. Thanks a lot for answering.
 » 5 months 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
•  » » 5 months 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.
 » 5 months ago, # |   0 Problem B can also be solved by dp. My submission https://mirror.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).
 » 5 months 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.
 » 5 months 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; } 
 » 5 months 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
•  » » 5 months 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
•  » » » 5 months 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.
•  » » 5 months ago, # ^ |   0 Same thing can be done using segment tree to reduce the memory to NlogN and complexity to NlogN 251321474
 » 5 months 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?
•  » » 5 months ago, # ^ |   0 Spoiler, it does work:(used kactl hashing) 249355708
 » 5 months ago, # |   0 Thanks for the organizers, hated this contest
 » 5 months 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?
 » 5 months 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 :(
 » 5 months 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^
•  » » 5 months ago, # ^ | ← Rev. 2 →   0
•  » » 5 months 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 •  » » » 5 months ago, # ^ | 0 thanks man, will fix it :3  » 5 months ago, # | 0 https://mirror.codeforces.com/contest/1937/submission/249016789 Why is this giving tle at 10th test case? •  » » 5 months ago, # ^ | +3 you did string assigning ans = temp$n$times, which results in$O(n^2)$complexity since string assigning is$O(n)$. •  » » » 5 months ago, # ^ | 0 Thanks! Is there any way i can optimise that approach? •  » » » » 5 months 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 •  » » » » » 5 months ago, # ^ | ← Rev. 2 → 0 :_), yea that makes sense. Thanks edit- still tle. •  » » » » » » 5 months 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)$. •  » » » » » » » 5 months ago, # ^ | 0 Fixed that, got AC. Thanks!  » 5 months 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 •  » » 5 months ago, # ^ | 0 May be the way you are checking s •  » » 5 months ago, # ^ | 0 I uploaded to Youtube a video in English explaining the solution of Div2-B  » 5 months ago, # | 0 248985883Can you help me? I am getting TLE. But my code is supposed to be in NlogN time only.  » 5 months ago, # | 0 can anyone prove/justify Step 3 of editorial of D2C/D1A.why minimum need to be choosen. •  » » 5 months ago, # ^ | 0 Cause the minimum is the one that does not have any bit in common with n-1, therefore maximazing the XOR.  » 5 months 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.  » 5 months 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.  » 5 months ago, # | 0 My Screencast for A and B problems: https://youtube.com/live/IU6Zqy5LGB4 This was private during the contest. Hope it helps someone. •  » » 5 months ago, # ^ | 0 Bro no one is interested in seeing you struggling in problem A, so stop spamming the commemt section under every blog post •  » » » 5 months 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. •  » » » » 5 months ago, # ^ | 0 why are you specifically mentinoning "green". making fun of someone's rating without constructive feedback isn't fair or productive. •  » » » » » 5 months ago, # ^ | 0 I was talking about me... i am green so it will take time to solve. •  » » » » » » 5 months ago, # ^ | 0 oh, I thought you were teasing me. Sorry  » 5 months 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 •  » » 5 months ago, # ^ | 0 If you read interactive problems guidelines, you shouldn't do this #define endl "\n"  » 5 months 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  » 5 months 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  » 5 months 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.  » 5 months ago, # | 0 Good idea hh  » 5 months ago, # | ← Rev. 2 → 0 I am not able to understand problem D ??? Div2  » 5 months 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  » 5 months ago, # | 0 How to get pupil rank?  » 5 months 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.  » 5 months ago, # | 0 In D1C，why add Y node？ edge x -> Pokémon node with a value of 0？  » 5 months 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  » 5 months ago, # | 0 Can someone pls review my code and tell me in which test code my code is getting error :) https://mirror.codeforces.com/contest/1937/submission/249344544  » 5 months ago, # | 0 Can someone please explain how do we derive the formula for Problem D? I'm so confused!  » 5 months ago, # | ← Rev. 2 → 0 Problem c sucks!!  » 5 months ago, # | 0 What is line segment tree mentioned in div 1 D?  » 5 months 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 months 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 months 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 months 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 months ago, # | 0 D1E, am I right that last_i = max(j  » 5 months 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.  » 4 months 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?  » 2 months ago, # | 0 Another solution for Div1C with segment tree.Let's say we want to process a pokemon$i$. Where could the path possibly come from? Let's assume the path comes from trait$j$, then either the path comes from a pokemon with more strength (1) or a pokemon with less or same strength (2). If it comes from a pokemon with more strength (1) (let's say pokemon$p$), then$dist_i = dist_p + a_{p,j} - a_{i,j} + c_i$. If it comes from a pokemon with less or same strength (2), then$dist_i = dist_p + c_i$, since we don't have to raise the stats of pokemon$i$. But, what if the shortest path to$p$also used trait$j$? Let's call$q$the parent of$p$. Then our path looks like$q$->$p$->$i$. However, we could take the path$q$->$i$and get a lower cost. So this case never happens. More generally, we will never use the same trait twice in a row.But how do we consider all possible$p$at once? To cover case 1, we want the lowest value of$dist_p + a_{p,j}$across all$p$where$a_{p,j} > a_{i,j}$. If we sort$a$so that all$p$form a contiguous segment, this turns into a range min query. To cover case 2, we take the lowest value of$dist_p$across all$p$where$a_{p,j} \le a_{i,j}$, also a range min query.So we can store two segment trees for each$j$, each with size$O(n)$, to quickly determine the shortest path assuming all nodes with lower cost are already processed. All that is left is to determine processing order, and that can be done with priority queue/Dijkstra. The time complexity is$O(nm \log(nm))\$.
 » 2 weeks ago, # |   +8 did you write div1e tutorial code so that it couldn't be read by normal people