### jeroenodb's blog

By jeroenodb, 6 weeks 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
• +54

 » 6 weeks ago, # |   +10 Thanks for fast tutorial!
 » 6 weeks ago, # |   0 Light speed tutorial sheeeesh!
 » 6 weeks ago, # |   0 so fast
 » 6 weeks ago, # |   0 So fast! Noice
 » 6 weeks ago, # |   +20 Why is it impossible for a python solution to pass div1C/div2E?
 » 6 weeks ago, # |   0 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?
•  » » 6 weeks ago, # ^ |   0 degree >= 4 won't ensure that that the tail of fish don't lie inside the cycle.
•  » » » 6 weeks ago, # ^ |   +4 Refer to editorial, if you still think it is not enough then try to make a counterexample and prove that it is impossible
•  » » » » 6 weeks ago, # ^ |   +3 Sorry. The editorial came so fast that I thought I was replying on announcement blog.
•  » » » 6 weeks ago, # ^ |   +6 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.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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://codeforces.com/contest/1818/submission/203991640
•  » » » » 6 weeks ago, # ^ |   +1 I guess your solution will not work if the graph is not connected because you are calling DFS only for vertex 1
•  » » » » » 6 weeks ago, # ^ |   0 Ohh, i missed it! thanks a lot!!
•  » » 6 weeks ago, # ^ |   0 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).
•  » » » 5 weeks ago, # ^ |   0 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).
•  » » » » 5 weeks ago, # ^ |   0 Cool
•  » » 5 weeks ago, # ^ |   0 do you mean a tarjan approach?
 » 6 weeks ago, # |   +6 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
•  » » 6 weeks ago, # ^ |   0 Nvm, I forgot to output the number of edges, dumb mistake, thank you the board for answering my question
 » 6 weeks ago, # |   0 1818B - Indivisible seems to be repeated question
•  » » 6 weeks ago, # ^ |   0 i felt the same.
•  » » 6 weeks ago, # ^ |   +19 what is the original problem?
 » 6 weeks ago, # |   0 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?
•  » » 6 weeks ago, # ^ |   +15 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}$.
 » 6 weeks ago, # | ← Rev. 2 →   +8 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
 » 6 weeks ago, # |   +18 Little note: for E, you can tighten the bound to $\frac{n}{2} \pm \frac{\log(MAX)}{2}$ (possibly with some off-by-one).
 » 6 weeks ago, # |   -15 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?
•  » » 6 weeks ago, # ^ |   +11 TLE results that were non-trivial, i.e., you had to change ur code even the slightest, they don't regrade it.
•  » » » 6 weeks ago, # ^ |   0 Well, you remind me.I tried the same code and got AC now, it's really a judge fault.
•  » » » » 6 weeks ago, # ^ |   +11 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 :(
•  » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +11 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++.
•  » » 5 weeks ago, # ^ |   0 Using cin/cout and C++20(64 bit) brings it down to 841 ms 204067531
•  » » » 5 weeks ago, # ^ |   +23 Thanks for the tips.It seems that it is time to embrace the new century.
 » 6 weeks ago, # |   +74 Toy Machine was fun. The web page was a great addition!
 » 6 weeks ago, # |   0 Really enjoyed the problems. Good work by the authors!
 » 6 weeks ago, # |   0 Is there a constructive way to figure out B? Or was it just observation?
•  » » 6 weeks ago, # ^ |   0 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.
•  » » » 6 weeks ago, # ^ |   0 After 1 hour of trying, this is what I did to find the pattern.
•  » » 5 weeks ago, # ^ |   +3 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.
 » 6 weeks ago, # |   +3 F can be solved with suffix automaton in $\mathcal{O}(n)$.
•  » » 6 weeks ago, # ^ |   +8 Hi, could you share some details please?
•  » » » 5 weeks ago, # ^ |   +8 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://codeforces.com/contest/1817/submission/203993098
 » 6 weeks ago, # | ← Rev. 2 →   +9 what is the point from problems like div2B ? problems that depends on a pattern/sequence is pointless
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   +5 that seems like chat gpt answer
 » 6 weeks ago, # |   +10 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. .
•  » » 6 weeks ago, # ^ |   +4 You can also solve in $O(n+m)$ by finding bridges and running one BFS or DFS to print the cycle.
•  » » » 6 weeks ago, # ^ |   +10 Thank you, could you please elaborate on the bridges part? I am not really familiar with bridges and articulation points
•  » » » » 5 weeks ago, # ^ |   +13 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.
•  » » » » » 5 weeks ago, # ^ |   +13 Amazing, thank you so much!
•  » » » 5 weeks ago, # ^ |   +10 Yes can you please elaborate?
 » 6 weeks ago, # |   0 Nice contest! Although my B failed the system test.
 » 6 weeks ago, # |   0 I used the same approach you mentioned in problem d fish graph , but it shows wrong answer. Here's my solution https://codeforces.com/contest/1818/submission/203940101 , I can't find wats wrong
 » 6 weeks ago, # | ← Rev. 2 →   0 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?
•  » » 6 weeks ago, # ^ |   0 Wouldn't it then be the max number of strings that are the same?
•  » » » 6 weeks ago, # ^ |   0 I see, that seems to work. Thanks!
 » 6 weeks ago, # |   +13 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.
 » 6 weeks ago, # | ← Rev. 2 →   +14 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.
 » 6 weeks ago, # |   +10 Why is the leading coefficient of B(x-s) in 1C equal to 1? I think it's k.
•  » » 6 weeks ago, # ^ |   0 On the third line of the editorial.
 » 6 weeks ago, # | ← Rev. 3 →   0 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)"
•  » » 6 weeks ago, # ^ |   0 Thanks for noticing! I will fix it soon.
 » 6 weeks ago, # | ← Rev. 2 →   +1 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://codeforces.com/contest/1818/submission/203962283
 » 6 weeks ago, # | ← Rev. 3 →   0 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.
 » 6 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 6 weeks ago, # ^ |   +9 No -Wall -Wextra moment
•  » » » 6 weeks ago, # ^ |   +1 I tried it and it tells me statement has no effect! Thank u.
•  » » » » 6 weeks ago, # ^ |   +5 Glad to help ;)
 » 6 weeks ago, # |   +1 Can anyone give a testcase in which the following code is giving wrong answer . Problem C div 2 Submission link Thanks
 » 6 weeks ago, # |   0 Thanks for Div1D/Div2F.
 » 6 weeks ago, # |   0 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.
 » 6 weeks ago, # |   0 Can someone tell me why my binary search submission for Div 2 C is wrong?Thanks!
 » 6 weeks ago, # |   0 Can anyone explain more the div2 C problem? I still don't understand the solution very much, thanks
•  » » 6 weeks ago, # ^ |   0 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
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   0 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
 » 6 weeks ago, # |   0 missing 1 rating for expert
 » 6 weeks ago, # |   0 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?
•  » » 6 weeks ago, # ^ |   0 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.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 6 weeks ago, # ^ |   0 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.
•  » » » » » 5 weeks ago, # ^ |   0 Oh I understand now, thank you!
 » 6 weeks ago, # | ← Rev. 2 →   0 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]
 » 6 weeks ago, # |   +10 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.
 » 5 weeks ago, # |   0 can someone explain why my div 2 C code does not work? https://codeforces.com/contest/1818/submission/203953371
•  » » 5 weeks ago, # ^ |   0 i found out why
 » 5 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 5 weeks ago, # ^ |   0 Can you list some important observations you made during the process?
•  » » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   0 Pupil
 » 5 weeks ago, # |   +3 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)
 » 5 weeks ago, # |   0 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 ^_^
•  » » 5 weeks ago, # ^ |   0 you can probably do it with a segment tree to query the longest almost increasing subarry, then just handle the edge cases
•  » » » 4 weeks ago, # ^ |   0 Can you tell me why my code is failed in test case 3. Here is my submission i'dsubmission
 » 5 weeks ago, # | ← Rev. 5 →   +21 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?
•  » » 3 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   0 For Politics problem, why are we declaring string of size n, and not of size k ?
 » 5 weeks ago, # |   0 can someone explain how method of differences works for diff 1 C if the output is modulo 10^9 + 7
 » 5 weeks ago, # |   0 Problem F can be solved by basic substring structure. Which can be solved in $O(n)$.
 » 5 weeks ago, # |   0 Div1 -B or Div2- D https://codeforces.com/contest/1817/submission/204224008getting runtime error on test 8th some help please.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 weeks ago, # ^ |   0 i think you should check for the degree first,then check for cycles.
 » 5 weeks ago, # |   0 can some body give me a simpler implementation of problem D of div 2 FISH GRAPH just the code
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 https://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.
 » 5 weeks ago, # |   0 can somebody explain this: auto dfs = [&](auto&& self, int at) -> void
•  » » 5 weeks ago, # ^ |   0 i got it,thanks vishesh
 » 5 weeks ago, # |   0 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$?
•  » » 5 weeks ago, # ^ |   0 Well I understand the tutorial. Both of them are correct.
 » 5 weeks ago, # |   0 How to solve Fish Graph in O(N+M)? Can anyone help?
 » 5 weeks ago, # | ← Rev. 2 →   0 How?
 » 5 weeks ago, # |   0 #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[0] = 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
 » 5 weeks ago, # | ← Rev. 2 →   0 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://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://codeforces.com/contest/1818/submission/204722921
 » 3 weeks ago, # |   +10 explaination of 1818C/1817A is so good!
 » 3 weeks ago, # |   0 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[0] = 1; dp[1] = 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"; }}
•  » » 2 weeks ago, # ^ |   0 same thing here man , any updates ? my submission used the same approach as yours
 » 2 weeks ago, # |   0 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.
 » 2 weeks ago, # |   0 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.