Codeforces functionality may be limited from June 18, 19:00 (UTC) to June 19, 3:00 AM (UTC) due to technical maintenance. Polygon will work as usual. ×

### jeroenodb's blog

By jeroenodb, 14 months ago,

1818A - Политика

Editorial
Solution

1818B - Неделимые отрезки

Editorial
Solution

1817A - Почти возрастающая подпоследовательность

Problem idea: dario2994
Preparation: jeroenodb

Editorial
Solution

1817B - Граф-рыба

Problem idea: jeroenodb
Preparation: jeroenodb

Hint 1
Hint 2
Hint 3
Editorial
Solution

1817C - Подобные многочлены

Editorial
Solution

1817D - Автомат с игрушками

Preparation: jeroenodb

Editorial
Solution

1817E - Полусумма

Editorial
Solution

1817F - Запутанные строки

Editorial
Solution
• +54

| Write comment?
 » 14 months ago, # |   +10 Thanks for fast tutorial!
 » 14 months ago, # |   0 Light speed tutorial sheeeesh!
 » 14 months ago, # |   0 so fast
 » 14 months ago, # |   +20 Why is it impossible for a python solution to pass div1C/div2E?
 » 14 months 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?
•  » » 14 months ago, # ^ |   0 degree >= 4 won't ensure that that the tail of fish don't lie inside the cycle.
•  » » » 14 months 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
•  » » » » 14 months ago, # ^ |   +3 Sorry. The editorial came so fast that I thought I was replying on announcement blog.
•  » » » 14 months 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.
•  » » » 14 months 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://mirror.codeforces.com/contest/1818/submission/203991640
•  » » » » 14 months ago, # ^ |   +1 I guess your solution will not work if the graph is not connected because you are calling DFS only for vertex 1
•  » » » » » 14 months ago, # ^ |   0 Ohh, i missed it! thanks a lot!!
•  » » 14 months 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).
•  » » » 14 months 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).
•  » » 14 months ago, # ^ |   0 do you mean a tarjan approach?
 » 14 months 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
•  » » 14 months ago, # ^ |   0 Nvm, I forgot to output the number of edges, dumb mistake, thank you the board for answering my question
 » 14 months ago, # | ← Rev. 2 →   0 .
•  » » 14 months ago, # ^ |   +19 what is the original problem?
 » 14 months 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?
•  » » 14 months 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}$.
 » 14 months ago, # | ← Rev. 2 →   +8 Alternative solution for 1817D - Автомат с игрушкамиIf 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
 » 14 months 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).
 » 14 months 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?
•  » » 14 months ago, # ^ |   +11 TLE results that were non-trivial, i.e., you had to change ur code even the slightest, they don't regrade it.
•  » » » 14 months ago, # ^ |   0 Well, you remind me.I tried the same code and got AC now, it's really a judge fault.
•  » » » » 14 months 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 :(
•  » » » » » 14 months 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++.
•  » » 14 months ago, # ^ |   0 Using cin/cout and C++20(64 bit) brings it down to 841 ms 204067531
•  » » » 14 months ago, # ^ |   +23 Thanks for the tips.It seems that it is time to embrace the new century.
 » 14 months ago, # |   +74 Toy Machine was fun. The web page was a great addition!
 » 14 months ago, # |   0 Is there a constructive way to figure out B? Or was it just observation?
•  » » 14 months 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.
•  » » » 14 months ago, # ^ |   0 After 1 hour of trying, this is what I did to find the pattern.
•  » » 14 months 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.
 » 14 months ago, # |   +3 F can be solved with suffix automaton in $\mathcal{O}(n)$.
•  » » 14 months ago, # ^ |   +8 Hi, could you share some details please?
•  » » » 14 months 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://mirror.codeforces.com/contest/1817/submission/203993098
 » 14 months ago, # | ← Rev. 2 →   +9 what is the point from problems like div2B ? problems that depends on a pattern/sequence is pointless
•  » » 14 months 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.
•  » » » 14 months ago, # ^ |   +5 that seems like chat gpt answer
 » 14 months 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. .
•  » » 14 months ago, # ^ |   +4 You can also solve in $O(n+m)$ by finding bridges and running one BFS or DFS to print the cycle.
•  » » » 14 months ago, # ^ |   +10 Thank you, could you please elaborate on the bridges part? I am not really familiar with bridges and articulation points
•  » » » » 14 months 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.
•  » » » » » 14 months ago, # ^ |   +13 Amazing, thank you so much!
•  » » » 14 months ago, # ^ |   +10 Yes can you please elaborate?
 » 14 months ago, # |   0 Nice contest! Although my B failed the system test.
 » 14 months ago, # |   0 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
 » 14 months 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?
•  » » 14 months ago, # ^ |   0 Wouldn't it then be the max number of strings that are the same?
•  » » » 14 months ago, # ^ |   0 I see, that seems to work. Thanks!
 » 14 months 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.
 » 14 months 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.
 » 14 months ago, # |   +10 Why is the leading coefficient of B(x-s) in 1C equal to 1? I think it's k.
•  » » 14 months ago, # ^ |   0 On the third line of the editorial.
 » 14 months 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)"
•  » » 14 months ago, # ^ |   0 Thanks for noticing! I will fix it soon.
 » 14 months 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://mirror.codeforces.com/contest/1818/submission/203962283
 » 14 months 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.
 » 14 months 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.
•  » » 14 months ago, # ^ |   +9 No -Wall -Wextra moment
•  » » » 14 months ago, # ^ |   +1 I tried it and it tells me statement has no effect! Thank u.
•  » » » » 14 months ago, # ^ |   +5 Glad to help ;)
 » 14 months ago, # |   +1 Can anyone give a testcase in which the following code is giving wrong answer . Problem C div 2 Submission link Thanks
 » 14 months ago, # |   0 Thanks for Div1D/Div2F.
 » 14 months 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.
 » 14 months ago, # |   0 Can someone tell me why my binary search submission for Div 2 C is wrong?Thanks!
 » 14 months ago, # |   0 Can anyone explain more the div2 C problem? I still don't understand the solution very much, thanks
•  » » 14 months 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
•  » » 14 months 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.
•  » » » 14 months 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
 » 14 months ago, # |   0 missing 1 rating for expert
 » 14 months 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?
•  » » 14 months 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.
•  » » » 14 months 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?
•  » » » » 14 months 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.
•  » » » » » 14 months ago, # ^ |   0 Oh I understand now, thank you!
 » 14 months 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]
 » 14 months 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.
 » 14 months ago, # |   0 can someone explain why my div 2 C code does not work? https://mirror.codeforces.com/contest/1818/submission/203953371
•  » » 14 months ago, # ^ |   0 i found out why
 » 14 months 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.
•  » » 14 months ago, # ^ |   0 Can you list some important observations you made during the process?
•  » » » 14 months 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.
 » 14 months ago, # |   0 Pupil
 » 14 months 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)
 » 14 months 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 ^_^
•  » » 14 months ago, # ^ |   0 you can probably do it with a segment tree to query the longest almost increasing subarry, then just handle the edge cases
•  » » » 3 months ago, # ^ |   0 how with seg tree we can handle the longest increasing subarray
 » 14 months 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?
•  » » 13 months 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.
 » 14 months ago, # |   0 can someone explain how method of differences works for diff 1 C if the output is modulo 10^9 + 7
 » 14 months ago, # |   0 Problem F can be solved by basic substring structure. Which can be solved in $O(n)$.
 » 14 months ago, # |   0 Div1 -B or Div2- D https://mirror.codeforces.com/contest/1817/submission/204224008getting runtime error on test 8th some help please.
•  » » 14 months 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.
 » 14 months ago, # |   0 can some body give me a simpler implementation of problem D of div 2 FISH GRAPH just the code
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 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.
 » 14 months 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$?
•  » » 14 months ago, # ^ |   0 Well I understand the tutorial. Both of them are correct.
 » 14 months ago, # |   0 How to solve Fish Graph in O(N+M)? Can anyone help?
 » 13 months ago, # |   +10 explaination of 1818C/1817A is so good!
 » 13 months 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"; }}
•  » » 13 months ago, # ^ |   0 same thing here man , any updates ? my submission used the same approach as yours
•  » » » 6 months ago, # ^ |   0 I am late, but I remember trying to find some test cases (in vain) and then accepting the given solution as final. I was preoccupied with work and hence could not be active, so I am sorry for the late response.
 » 13 months 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.
•  » » 6 months ago, # ^ |   0 Also am I wrong I mean, you yourself said I come to realize that my approach was totally wrong Okay, so I think you misunderstood the problem. We have to find a permutation for which, the given condition is true. The condition says that modulus has to be $\neq 0$ for all possible combinations i.e. $1 \leq l \lt r \leq n$ Find a permutation $a_1, a_2, \dots, a_n$ such that for any $1 \leq l \lt r \leq n$, the sum $a_l + a_{l+1} + \dots + a_r$ is not divisible by $r-l+1$ A and B (sometimes C as well) are generally solved with basic observations actually. Just like this one:)
 » 12 months ago, # | ← Rev. 2 →   +4 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
 » 11 months ago, # |   0 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
 » 10 months ago, # | ← Rev. 7 →   0 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
•  » » 10 months ago, # ^ |   0 Is this a valid test? It seems to me $(4,5)$ and $(5,4)$ form parallel edges, which is not allowed.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 sorry it's a typo. the last edge was supposed to be (3 4), not (5 4) (fixed now)
 » 8 months ago, # | ← Rev. 3 →   0 What power do u have?
•  » » 6 months ago, # ^ |   0 BecauseNever gonna give you up Never gonna let you down Never gonna run around and desert you Never gonna make you cry Never gonna say goodbye Never gonna tell a lie and hurt you PSI can understand that you don't use English as the primary language and that's fine, but why are you being rude?I don't think the codes are incomplete they gave you the core part that was needed.
 » 6 months ago, # |   0 who can tell me in the tutorial of the problem D(div2),why to resize the vector p? Isn't p's size clearly?