### jeroenodb's blog

By jeroenodb, 7 months ago, 1818A - Politics

Editorial
Solution

1818B - Indivisible

Editorial
Solution

1817A - Almost Increasing Subsequence

Problem idea: dario2994
Preparation: jeroenodb

Editorial
Solution

1817B - Fish Graph

Problem idea: jeroenodb
Preparation: jeroenodb

Hint 1
Hint 2
Hint 3
Editorial
Solution

1817C - Similar Polynomials

Editorial
Solution

1817D - Toy Machine

Preparation: jeroenodb

Editorial
Solution

1817E - Half-sum

Editorial
Solution

1817F - Entangled Substrings

Editorial
Solution Tutorial of Codeforces Round 869 (Div. 1) Tutorial of Codeforces Round 869 (Div. 2) Comments (125)
 » Thanks for fast tutorial!
 » Light speed tutorial sheeeesh!
 » so fast
 » So fast! Noice
 » Why is it impossible for a python solution to pass div1C/div2E?
 » For Fish Graph, can you do a DFS-Tree like thing with which you can find the node with degree >=4 in a cycle and get to O(N+M) or am I missing something?
•  » » degree >= 4 won't ensure that that the tail of fish don't lie inside the cycle.
•  » » » Refer to editorial, if you still think it is not enough then try to make a counterexample and prove that it is impossible
•  » » » » Sorry. The editorial came so fast that I thought I was replying on announcement blog.
•  » » » It does. If a fish tail is inside the cycle, then use that tail to make a smaller cycle instead. The edge that used to be in the old cycle but isn't in the new cycle will be a correct tail outside the cycle.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   i don't know what is wrong here, firstly i found every cycle and then check if it can be used as fish graph. but getting WA every time. Can anyone tell me what is wrong here? https://mirror.codeforces.com/contest/1818/submission/203991640
•  » » » » I guess your solution will not work if the graph is not connected because you are calling DFS only for vertex 1
•  » » » » » Ohh, i missed it! thanks a lot!!
•  » » What if we form a bridge tree ( biconnected component decomposition) and then do dfs on the new tree and find a node with degree >=3 (as here we squeezed all cycles into a single node).
•  » » » That works, however, you don’t really need to do condensation on the graph.You only need to check if there exists $u$ such that $deg(u) \ge 4 \land \text{size}(\text{BCC}[u]) > 1$. Then you can find the cycle with a DFS (similar to CSES Round Trip).
•  » » » » Cool
•  » » do you mean a tarjan approach?
 » For problem Div2.D I don't know this approach is correct or not:For each vertex with degree >= 4, find the shortest cycle through it, add those edges to answer, find another 2 vertices that are not in the found cycle, include those 2 edges as well.The wrong submission, the system verdicted WA, wrote that I'm using an edge twice, while I check again the output, it doesn't seem like that. 203958546
•  » » Nvm, I forgot to output the number of edges, dumb mistake, thank you the board for answering my question
 » 1818B - Indivisible seems to be repeated question
•  » » i felt the same.
•  » » what is the original problem?
 » Problem Similar Polynomials...and for the coefficient near $d−1$ we should note that $[x_{d−1}](x−x_1)\dots(x−x_n)=−(x_1+\dots+x_n)$, thus...What happenes on the next line?
•  » » UnderstoodGet back to Lagrange formula. Write it as $\sum_{i=0}^{d}y_i\Pi_{j \neq i}(x - x_j)\Pi_{j \neq i}\frac{1}{x_i - x_j}$. We have $x$ only in first product — $\Pi_{j \neq i}(x - x_j)$. We want to get its $[x^{d-1}]$. Its minus sum of its roots. So we get $[x^{d-1}]f(x)=\sum_{i=0}^{d}y_i c_i \cdot -\sum_{j \neq i}{x_j}$.
 » 7 months ago, # | ← Rev. 2 →   Alternative solution for 1817D - Toy MachineIf the bottom left part of the toy is full, and it contains $k$, you can win using LDRU. To get this configuration, use DLUL $3n/10$ times, then simulate $1000$ random moves.AC submission: 203960705
 » Little note: for E, you can tighten the bound to $\frac{n}{2} \pm \frac{\log(MAX)}{2}$ (possibly with some off-by-one).
 » For problem Similar PolynomialsI changed the input from scanf() to getchar().The running time changed from 4000+ms (203942742) to 1590ms (203961795).Can I request to skip this TLE result 203942742?
•  » » TLE results that were non-trivial, i.e., you had to change ur code even the slightest, they don't regrade it.
•  » » » Well, you remind me.I tried the same code and got AC now, it's really a judge fault.
•  » » » » Well, my fault.I tried the same code with different compiler.GNU C++17 for AC, GNU C++20 (64) for TLE.Bad luck for me :(
•  » » » » » 7 months ago, # ^ | ← Rev. 3 →   C++17 has been patched on CF to make scanf faster. See this blog . It isn't uncommon to see scanf users submitting using C++17 for this reason.I think the best thing to do is to use cin/cout and use C++20(64 bit). Using cin/cout is the intended way to parse input in C++.
•  » » Using cin/cout and C++20(64 bit) brings it down to 841 ms 204067531
•  » » » Thanks for the tips.It seems that it is time to embrace the new century.
 » Toy Machine was fun. The web page was a great addition!
 » Really enjoyed the problems. Good work by the authors!
 » Is there a constructive way to figure out B? Or was it just observation?
•  » » I have used the brute force approach to generate all possible answer to see any answer for each test case follow some pattern. bool check(vector& a,int n){ for(int i=0;i>n; cout << "n: " << n << '\n'; vector a(n); loop(0,n-1){a[i]=i+1;} do{ if(check(a,n)){ print(a); } }while(next_permutation(all(a))); cout << '\n'; } if you run this code for small test, like from 1 to 11, you will observe that answer exist if n is even and if n==1, and for each n(keep in mind that it is even) there is permuatation which follow some pattern like2 1 4 3 6 5 ..... n-2 n-3 n n-1you can try the above code and check it out yourselfThe only problem is that this brute force will work till n=11, after that it will take very long time to produce answer. So, we cannot check it for large test cases.Also n=1 is the only odd number that produce valid answer which is 1 only.
•  » » » After 1 hour of trying, this is what I did to find the pattern.
•  » » First, I think it helps a lot if you realize that solutions of odd length are impossible (with N=1 as the sole exception) because the sum of 1..N is always divisible by N. The fact that the sample data shows N=3 is impossible suggests this also. ProofFrom the formula for triangular numbers, sum 1..N = N(N + 1)/2. When N is odd, i.e. N = 2k + 1 for some integer k, then N(N + 1)/2 = (2k + 1)(2k + 2)/2 = (2k + 1)(k + 1) = N(k + 1) which is a multiple of N.Then, a good solution approach is to try to generate solutions manually. For N=4, you can observe that you can never have "13" or "24" or "123" or "234" or any permutation of these as substrings (since e.g. 1+2+3=6 is a multiple of 3), so that means 2 and 3 must go at the ends and 1 and 4 in the middle, leaving only "2143" and its reverse "3412" as possibilities.Now you might have already noticed that "2143" is an extension of the solution for N=2 ("21") but if you didn't, it's natural to try and see if you can build the solution for N=6 by adding 5 and 6 somewhere to the previous solution. You cannot add "56" (because 3+5=8) but "65" works to build "214365".At this point it seems like a safe guess that you can always add a pair of numbers to the end. There is a formal proof in the editorial but I ended up writing a brute-force solution to double-check the answers and spot-checked a few other numbers.
 » F can be solved with suffix automaton in $\mathcal{O}(n)$.
•  » » Hi, could you share some details please?
•  » » » I solved it in $O(n)$ time using suffix array/tree; after building the suffix tree with suffix links, solving each chain can be done with two pointers instead of segment tree. I think it's the same with suffix automaton, since the suffix links of a suffix tree essentially form the suffix automaton of the reversed string.https://mirror.codeforces.com/contest/1817/submission/203993098
 » 7 months ago, # | ← Rev. 2 →   what is the point from problems like div2B ? problems that depends on a pattern/sequence is pointless
•  » » Observing patterns over time is important because it: utilises the students' natural curiosity and observational skills, promoting deeper curiosity and engagement. supports a more scientific approach to observation, looking beyond the obvious features.
•  » » » that seems like chat gpt answer
 » I believe D could be solved in O(n+m) Via DSU. To check if it is possible to reach a node from another would be O(1). And to erase edges, we would simply connect the nodes to a virtual node that sits independent from the graph. But I am not sure. .
•  » » You can also solve in $O(n+m)$ by finding bridges and running one BFS or DFS to print the cycle.
•  » » » Thank you, could you please elaborate on the bridges part? I am not really familiar with bridges and articulation points
•  » » » » An edge is a bridge if removing that edge splits its component into two. There is an $O(n+m)$ algorithm to find all bridges in a graph.Once you have found all bridges, you can iterate through all nodes with degree at least $4$. For each node $v$, if all of its incident edges are bridges, then it does not lie on a cycle. If there is an edge that is not a bridge, then $v$ does lie on a cycle.Let's say the non-bridge edge is between $v$ and $u$. To find a cycle, simply run a BFS from $u$ but block the edge back to $v$. Since the edge $u-v$ is not a bridge, there must be another path from $u$ to $v$, which the BFS will find. Adding the edge $u-v$ to the path found forms a cycle. And any two other edges incident to $v$ can be added to make a fish graph.Note this would not be a valid fish graph if any of the extra two edges incident to $v$ connected $v$ to a vertex already in the cycle. But this will never happen, since the BFS will always find the shortest path from $u$ to $v$ without traversing the edge $u-v$, so there cannot be a diagonal edge that cuts through the cycle, since that would imply a shorter path exists. This is also explained in the editorial.
•  » » » » » Amazing, thank you so much!
•  » » » Yes can you please elaborate?
 » Nice contest! Although my B failed the system test.
 » I used the same approach you mentioned in problem d fish graph , but it shows wrong answer. Here's my solution https://mirror.codeforces.com/contest/1818/submission/203940101 , I can't find wats wrong
 » 7 months ago, # | ← Rev. 2 →   If there were no constraints that required the club president to remain in the club (that is, if we were just trying to maximize the number of remaining members), would problem div2 A still be solvable?
•  » » Wouldn't it then be the max number of strings that are the same?
•  » » » I see, that seems to work. Thanks!
 » Problem Div1A can be solved another way. Let’s think how the subsequence is organized. It can be created greedy: let the last included integer be a[i]. 1) if a[i+1] > a[i], so the next subsequence’s number will be a[i+1]. 2) else we need to find the first j such that a[j] < a[j+1], and the next subsequence’s numbers will be a[j] and a[j+1]. This observation can be used to calculate next[i]. So the answer is built by jumping from l to next[l], next[next[l]]… while <= r. To answer queries fast we can just count binary jumps on next[] array.
 » 7 months ago, # | ← Rev. 2 →   i think there's some problem in Problem D test cases. according to the statement, 1 <= m, n <= 2000 but in test 12, m = 0 in many testcases, that makes my submission 203956585 got WA.
 » Why is the leading coefficient of B(x-s) in 1C equal to 1? I think it's k.
•  » » On the third line of the editorial.
 » 7 months ago, # | ← Rev. 3 →   In the tutorial of D1C, Indeed, if we denote by S an operator such that SA(x)=SA(x+1) It should be "SA(x)=A(x+1)"
•  » » Thanks for noticing! I will fix it soon.
 » 7 months ago, # | ← Rev. 2 →   jeroenodb thank you very much for interesting problems !I would like to share the solution of problem D in O(N + M). We can divide all vertices according to the components of the edge biconnection, and solve the problem for each vertex (v) in 3 cases:1) Check that V has 2 or more edges to the vertices of other components (take them as 2 tails), and at least 2 edges to the vertices of its own component (find a cycle)2) Check that V has 1 edge to the vertex of the other component (take as 1 tail), and at least 3 edges to the vertices of its own component, taking one vertex as the tail, and find a cycle between the remaining two.3) Check that V has at least 4 edges to the vertices of its own component and select 2 of the 4 vertices as parts of the tail and check that removing them from the component can find a path between the remaining two.Link to my solution: https://mirror.codeforces.com/contest/1818/submission/203962283
 » 7 months ago, # | ← Rev. 3 →   For C, it can be observed both polynomials have to be in the form $(ax+b)^d + C$ . The problem can then be rephrased as finding $(b_B-b_A)/a$. Taking the $d-1$ derivative gives us $n!a^dx+n!ba^{(d-1)}$ which means we can get $b/a$ or the answer by finding the differences.
 » 7 months ago, # | ← Rev. 2 →   For Div1C, does anybody know why this submission is giving WA on test 5? Staring at code with no luck :) Many thanks.Edit: I found it. sumd % mod should be sumd %= mod. Just took 4 hours.
•  » » No -Wall -Wextra moment
•  » » » I tried it and it tells me statement has no effect! Thank u.
•  » » » » Glad to help ;)
 » Can anyone give a testcase in which the following code is giving wrong answer . Problem C div 2 Submission link Thanks
 » Thanks for Div1D/Div2F.
 » Very frustrated that my div2D submission (203945910) only failed because of a stack overflow. I wrote in Python, so a possible solution to this situation is to increase the stack limit using the method sys.setrecursionlimit() which allows to set the maximum depth of the Python interpreter stack to the required limit. Thus, adding it to the code (203980915), all tests were passed successfully. Definitely worth considering this experience in the future.
 » Can someone tell me why my binary search submission for Div 2 C is wrong?Thanks!
 » Can anyone explain more the div2 C problem? I still don't understand the solution very much, thanks
•  » » for an increasing subsequence, this condition must hold: x >= y >= z, you can remove one of the elements from each triplet so this no longer holds
•  » » Let's call a Sequence Bad if it is non-increasing, a thing to be observed in such sequences is that if you wish to include elements from those sequences, the maximum number of elements you can include are 2, this is because if a sequence follows the order (a[i] >= a[i+1] >= a[i+2] >= ... >= a[i+n], no matter what subsequence you choose to hold the condition for "almost increasing subsequence" you can only include 2 elements from it. Working upon this idea for a specific range [l, r] knowing that we have (r-l+1) elements in the range, you can observe that if a sequence of the form (a[i] >= a[i+1] >= a[i+2]) lies in the range you are bound to choose only two elements from it. Hence you can count while iterating through the given array the number of bad "indices" that are included in the subsequence as a prefix array. Then to get the final answer you can simply subtract the total "bad indices" in the given range [l, r] from the total length of the range. Since you have already precalculated the value of "bad indices in [l, r]" the operation takes constant O(1) time for each query.
•  » » » Here I am using the same approach but getting wrong answer on test case 3. Can you tell me the counter testcase for my submission submission link
 » missing 1 rating for expert
 » For Div 1A: 1817A — Almost Increasing Subsequence,"A sequence is almost-increasing if it does not contain three consecutive elements x,y,z such that x≥y≥z"May I know how to solve it if instead of 3 consecutive elements, we do k consecutive elements?If k is big (lets say n / 2) would it still be possible to preprocess in an efficient manner to run our prefix sum / binary search?
•  » » As explained in the tutorial, we took at most 2 numbers from a group if 3 consecutive non-increasing were not allowed.We will take at most k-1 numbers from every group if k consecutive non-increasing are not allowed.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   I am not entirely sure how to take at most k-1 numbers from every group, for groups of 3 we can just take the inner elements using prefix sum, however for groups of k how do we take and count it properly?
•  » » » » Let's say the subarrays formed by cutting at a[i] < a[i+1] be of sizes:x1, x2, x3, ... x(k)Now find which subarray contains index L and R using binary search and prefix sum. How?Let y(i) = sum from x1 to x(i) You can apply binary search on "y" array to find exactly which subarray contains indices L and R.All the subarrays in between would contain min(k-1, |x(j)|) numbers. You can easily precompute this using prefix sums.andThose containing indices L and R would contain min(k-1, |y(l')|-L+1) and min(k-1, R+1-|y(r'-1)|) where l' and r' denote which subarrays contain L and R.
•  » » » » » Oh I understand now, thank you!
 » 7 months ago, # | ← Rev. 2 →   For Div1A, my approach was slightly different. It is as follows:Hypothesis: If a[i] >= a[i+1] >= a[i+2], then it does not make any sense to keep a[i+1] in a subsequence.Proof:=> We must not keep all 3 in any subsequence, as it won't be almost increasing. So Let's remove 1 out of the 3.=> a[i-1] >= a[i+1] is more probable than a[i-1] >= a[i], so removing a[i+1] is preferred over removing a[i]=> a[i+1] < a[i+3] is less probable than a[i+2] < a[i+3], so removing a[i+1] is preferred over removing a[i+2]Algorithm: Let b[i] = 1 if b[i-1] >= b[i] >= b[i+1], else 0.For query [L, R], result = no. of elements in [L,R] — sum(b[i]) where L < i < R. We do not include b[L] and b[R] because they cannot lie in the middle of a triplet a[i] >= a[i+1] >= a[i+2]
 » Div2 A: You have to follow the boss to not get kicked out of the meeting! Follow the boss, keep the opinion same as your boss's opinion. Couldn't solve the problem in contest time. But it's a fun problem. I enjoyed it.
 » can someone explain why my div 2 C code does not work? https://mirror.codeforces.com/contest/1818/submission/203953371
•  » » i found out why
 » 7 months ago, # | ← Rev. 2 →   Div2-D/1-B Fish Graph is a great problem. It took me about 6.5 hours to learn this well and get accepted.(submitted for 15 times) I learned a lot from this. Thanks for preparing the contest.
•  » » Can you list some important observations you made during the process?
•  » » » Almost the same as the editorial. However, I had trouble implementing that code. So I implemented it in an easier way. Here's my code.
 » Pupil
 » Really sad that there wasn't a sample for highest degree not equal to 1 in D1C, would have been red otherwise (on a sidenote, don't ever try to figure out a solution to a polynomial question in your head)
 » hello everyone I am curious to know if It is possible to solve div1 Aif the question was longest increasing subarray instead of subsequence(basically we need to tell the longest increasing subarray in the bounds of l to r)?any idea would be highly appreciated and if its impossible to solve in the given contrains please let me know. Thank You CF Community ^_^
•  » » you can probably do it with a segment tree to query the longest almost increasing subarry, then just handle the edge cases
•  » » » Can you tell me why my code is failed in test case 3. Here is my submission i'dsubmission
 » 7 months ago, # | ← Rev. 5 →   I have a couple of doubts regarding div1 C. The editorial treats the equivalent polynomials to be equal at all points. It doesn’t take into account that the problem mentions that they are equal mod 10^9 + 7. The problem statement applies an additional constraint. So is it necessary that if the polynomials are equal mod 10^9 + 7 then they are also equal if we remove the modulo constraint? The editorial says that k (the coefficient of x^d) is the same for both the polynomials. A proof would be nice. And while I can prove it in the general case, why would this be true modulo 10^9 + 7?
•  » » I can clarify your second doubt as why they have same coefficient. wee can write , A(x+s)-B(x) = q(x). MOD ; where for each x , q(x) is an integer. now this can be possible only when q(x) is integer for all real x. which intuitively is possible only when q(x) is constant and equal to some integer. hence , A(x+s)-B(x) is independent of x. hence the conclusion follows that their leading coefficients are same.
 » For Politics problem, why are we declaring string of size n, and not of size k ?
 » can someone explain how method of differences works for diff 1 C if the output is modulo 10^9 + 7
 » Problem F can be solved by basic substring structure. Which can be solved in $O(n)$.
 » Div1 -B or Div2- D https://mirror.codeforces.com/contest/1817/submission/204224008getting runtime error on test 8th some help please.
•  » » 7 months ago, # ^ | ← Rev. 2 →   First finding all the cycles and sorting them in increasing order of their size. Checking each cycle if it has any node with degrees >=4. If yes then taking that cycle and 2 other edges for that node which are not part of the cycle.
•  » » » i think you should check for the degree first,then check for cycles.
 » can some body give me a simpler implementation of problem D of div 2 FISH GRAPH just the code
•  » » 7 months ago, # ^ | ← Rev. 2 →   https://mirror.codeforces.com/contest/1818/submission/204263634I solved it just now and feel that this is simple to implement:So I build the path while I DFS and take the shortest cycle for nodes with >= 4 neighbours. Then I take the remaining 2 nodes from the "tail", and print out the answer. Note that shortest cycle must have length > 2, because otherwise it would be A -> B -> A which is an invalid cycle for the fish graph.
 » can somebody explain this: auto dfs = [&](auto&& self, int at) -> void
•  » » i got it,thanks vishesh
 » Hey, am I misunderstanding the tutorial for 1E? Shouldn't it be the case that $k\in [p, p + 30]\cup [q - 30, q]$, where $p$ is the first position that $a_{p + 1} - a_p > 0$, and $q$ is the last position that $a_{q + 1} - a_q > 0$?
•  » » Well I understand the tutorial. Both of them are correct.
 » How to solve Fish Graph in O(N+M)? Can anyone help?
 » 7 months ago, # | ← Rev. 2 →   How?
 » #include using namespace std; #define all(v) (v).begin(), (v).end() void solve(); int ceilIdx(int tail[], int l, int r, int x) { while (r > l) { int m = l + (r - l) / 2; if (tail[m] >= x) r = m; else l = m + 1; } return r; } vector LIS(int arr[], int x, int y) { int n = (y - x + 1); vector dp(n + 1, 0); int tail[n]; int len = 1; int c1 = 0; tail = arr[x - 1]; for (int i = 1; i < n; i++) { dp[i] = len; if (arr[i + x - 1] > tail[len - 1]) { tail[len] = arr[i + x - 1]; len++; c1 = 0; } else if (c1 == 0 && arr[i + x - 1] <= tail[len - 1]) { tail[len] = arr[i + x - 1]; len++; c1++; } else { int c = ceilIdx(tail, 0, len - 1, arr[i + x - 1]); tail[c] = arr[i]; c1 = 0; } } // for (auto it : tail) // cout << it << " "; // cout << endl; dp[n] = len; return dp; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); } void solve() { int n, q; cin >> n >> q; int arr[n]; for (int i = 0; i < n; i++) cin >> arr[i]; vector v; v = LIS(arr, 1, n); for (int i = 1; i <= q; i++) { int x, y; cin >> x >> y; cout << v[y] - v[x] + 1 << endl; } // for (auto &it : v) // cout << it << " "; // cout << endl; } can anyone please explain why this code is giving wrong answer on test case 3 . Thank you
 » 7 months ago, # | ← Rev. 2 →   I wrote one solution for problem 1817B in Python but it gives Runtime Error on Test 2.However I do not understand how to debug my code.Here is the submission: https://mirror.codeforces.com/contest/1818/submission/204716762Some insight would be helpful.UPDATE:After some debugging, I have cornered the error to a portion of my code, which gives a 'NoneType' error on test case 274 of Test 2. However, there still lies the mystery of why this test case is raising such an exception.Here is the solution with the error being caught: https://mirror.codeforces.com/contest/1818/submission/204722921
 » explaination of 1818C/1817A is so good!
 » Can we use some greedy approach in div2C? I made an array dp where dp[i] tells the length of the longest almost-increasing subsequence from index 0 to i. Afterwards I subtracted dp[l-1] from dp[r] and output it as the answer. I know this approach is not full proof so I would be grateful if someone points out the mistake in my implementation or in the approach itself.Here is the link to submission (Main code starts at line 81 at void solve(int test_case)): 206277166 Code snippetvoid solve(int test_case) { long long n, q, l, r; cin >> n >> q; vector a(n); fori(n) { cin >> a[i]; } vector dp(n + 1, 0); dp = 1; dp = 2; for (int i = 2; i < n; i++) { int j = i; while (j < n && a[i - 2] >= a[i - 1] && a[i - 1] >= a[j]) { dp[j] = dp[i - 1]; j++; } if (j == n) break; dp[j] = dp[i - 1] + 1; i = j; } while (q--) { cin >> l >> r; if (r - l + 1 < 3) { cout << r - l + 1; } else { l--, r--; cout << dp[r] - ((l == 0) ? 0 : dp[l - 1]); } cout << "\n"; }}
•  » » same thing here man , any updates ? my submission used the same approach as yours
 » I am not able to stress test for Div2 C , here's my submission I have used a dp array to store the answer at each possible r from 1 , i.e. maximum possible AIS for each r , then for each l and r in the query , the answer is dp[r]-dp[l] + 1 , but I am not able to dig into where its failing. I wish if any one is able to find out the mistake here , it would be helpful, thank you.
 » 1818B — IndivisibleI am a beginner guys and I thought that doing the question was just putting it in the formula r-1+1 and then finding the modulus of the value with the prefix sum of the array. This worked for the test case mentioned in the question but here I come to realize that my approach was totally wrong .Also am I wrong ?I mean this looks like a very high rating problem as per the editorial, Kindly advice me regarding this.
 » 6 months ago, # | ← Rev. 2 →   I am not finding any shortest cycle but instead of finding shortest cycle, my claim is that if a node x having adj[x].size() is greater than 3 and x is part of a cycle then it must form a fish subgraph.but my solution is Wrong On Test 15 Can Anyone tell, what i am doing wrong and provide me a testcase where my code fails.My_Code
 » For n=3, for sequence 1, 2, 3If l=1, r=2. then it can be our valid answer.I think I didn't understood the question properly, can anyone tell through this test case please.
 » 6 months ago, # | ← Rev. 2 →   1817A - Almost Increasing Subsequence problem can also be solved using a PBDS here is how. Let's consider an index i if it is satisfying the condition a[i] >= a[i + 1] >= a[i + 2] for all (0 <= i < n-2) as a tripletindex, we can store all those indices in our PBDS. Length of the subsequence for a particular query is (r + 1 — l) let's call it as len, if len < 3 then we already have our answer as for having at-least one triplet we need 3 length, otherwise we will only keep the indices in the range l to r such that it doesn't contain any tripletindex, which could be easily done using a PBDS. Code:#include #include #include using namespace __gnu_pbds; #define ordered_set tree, rb_tree_tag,tree_order_statistics_node_update> #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define endl "\n" using namespace std; int main() { IOS; int n, q; cin >> n >> q; vector arr(n); for(int i = 0; i < n; i++) cin >> arr[i]; ordered_set triplet; for(int i = 0; i < n - 2; i++) { if(arr[i] >= arr[i + 1] && arr[i + 1] >= arr[i + 2]) triplet.insert(i); } for(int i = 0; i < q; i++) { int l, r; cin >> l >> r; l--, r--; int len = r + 1 - l; if(len < 3) cout << len << endl; else { int left = triplet.order_of_key(l); int right = triplet.order_of_key(r - 1); len += (left - right); cout << len << endl; } } return 0; }  Time and space complexity:Since we are using an ordered set we can and we can precompute for all indices before jumping on queries on worst case it would be taking O(max(n * log(n), q * (2 * log(n)) and O(n) space for PBDS.
 » I don't understand how is the second test case given for the question D in this contest is valid because the special node here is node 3 then it is taking extra edges as 2 <-> 3 and 3<-> 5 but the edge 3 <--> 2 is problematic I think, because the node two which is a part of extra node is already connected with the node 1 which is in the cycle and hence violating the condition of the question (that is "but they should not be connected to any other node of the cycle.", 4th line). Can anyone please clarify the statement
 » 3 months ago, # | ← Rev. 7 →   please consider this case for Div1B: n = 5, m = 8, edges are: {(1 2), (2 5), (5 4), (4 1), (1 3), (3 2), (3 5), (3 4)}I don't see a Fish Graph here, although it satisfies the condition and also, it breaks the author's code
•  » » Is this a valid test? It seems to me $(4,5)$ and $(5,4)$ form parallel edges, which is not allowed.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   sorry it's a typo. the last edge was supposed to be (3 4), not (5 4) (fixed now)
 » What power do u have?How dare r u give incomplete codes?Do u have tg1= in Grade 1?U were diaodaed by me,FVV.