jeroenodb's blog

By jeroenodb, 11 months ago, In English

1818A - Politics

Problem idea: adamant
Preparation: adamant

Editorial
Solution

1818B - Indivisible

Problem idea: adamant
Preparation: adamant

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

Problem idea: adamant
Preparation: adamant

Editorial
Solution

1817D - Toy Machine

Problem idea: adamant
Preparation: jeroenodb

Editorial
Solution

1817E - Half-sum

Problem idea: adamant
Preparation: adamant

Editorial
Solution

1817F - Entangled Substrings

Problem idea: adamant
Preparation: adamant

Editorial
Solution
  • Vote: I like it
  • +54
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks for fast tutorial!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Light speed tutorial sheeeesh!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

so fast

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So fast! Noice

»
11 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Why is it impossible for a python solution to pass div1C/div2E?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    degree >= 4 won't ensure that that the tail of fish don't lie inside the cycle.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Refer to editorial, if you still think it is not enough then try to make a counterexample and prove that it is impossible

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Sorry. The editorial came so fast that I thought I was replying on announcement blog.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I guess your solution will not work if the graph is not connected because you are calling DFS only for vertex 1

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    do you mean a tarjan approach?

»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nvm, I forgot to output the number of edges, dumb mistake, thank you the board for answering my question

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Understood

    Get 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}$$$.

»
11 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Alternative solution for 1817D - Toy Machine

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

»
11 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Little note: for E, you can tighten the bound to $$$\frac{n}{2} \pm \frac{\log(MAX)}{2}$$$ (possibly with some off-by-one).

»
11 months ago, # |
  Vote: I like it -15 Vote: I do not like it

For problem Similar Polynomials

I 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?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    TLE results that were non-trivial, i.e., you had to change ur code even the slightest, they don't regrade it.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, you remind me.

      I tried the same code and got AC now, it's really a judge fault.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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 :(

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
          Rev. 3   Vote: I like it +11 Vote: I do not like it

          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++.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Using cin/cout and C++20(64 bit) brings it down to 841 ms 204067531

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      Thanks for the tips.

      It seems that it is time to embrace the new century.

»
11 months ago, # |
  Vote: I like it +74 Vote: I do not like it

Toy Machine was fun. The web page was a great addition!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really enjoyed the problems. Good work by the authors!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a constructive way to figure out B? Or was it just observation?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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<int>& a,int n){
    	for(int i=0;i<n-1;i++){
    		int sum=a[i];
    		for(int j=i+1;j<n;j++){
    			sum+=a[j];
    			if(sum%(j-i+1)==0){
    				return false;
    			}
    		}
    	}
    
    	return true;
    }
    
    void solve() {
    	int n;cin>>n;
    	cout << "n: " << n << '\n';
    	vector<int> 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 like

    2 1 4 3 6 5 ..... n-2 n-3 n n-1

    you can try the above code and check it out yourself

    The 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.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      After 1 hour of trying, this is what I did to find the pattern.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    Proof

    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.

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

F can be solved with suffix automaton in $$$\mathcal{O}(n)$$$.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Hi, could you share some details please?

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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

»
11 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

what is the point from problems like div2B ? problems that depends on a pattern/sequence is pointless

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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. .

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You can also solve in $$$O(n+m)$$$ by finding bridges and running one BFS or DFS to print the cycle.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Thank you, could you please elaborate on the bridges part? I am not really familiar with bridges and articulation points

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        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.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Yes can you please elaborate?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest! Although my B failed the system test.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wouldn't it then be the max number of strings that are the same?

»
11 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

»
11 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

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.

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Why is the leading coefficient of B(x-s) in 1C equal to 1? I think it's k.

»
11 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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)"

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for noticing! I will fix it soon.

»
11 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
11 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone give a testcase in which the following code is giving wrong answer . Problem C div 2 Submission link Thanks

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for Div1D/Div2F.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why my binary search submission for Div 2 C is wrong?

Thanks!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain more the div2 C problem? I still don't understand the solution very much, thanks

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

missing 1 rating for expert

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        and

        Those 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.

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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]

Code: https://codeforces.com/contest/1817/submission/203931292

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain why my div 2 C code does not work? https://codeforces.com/contest/1818/submission/203953371

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you list some important observations you made during the process?

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Pupil

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hello everyone

I am curious to know if It is possible to solve div1 A

if 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 ^_^

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can probably do it with a segment tree to query the longest almost increasing subarry, then just handle the edge cases

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you tell me why my code is failed in test case 3. Here is my submission i'dsubmission

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how with seg tree we can handle the longest increasing subarray

»
11 months ago, # |
Rev. 5   Vote: I like it +21 Vote: I do not like it

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?
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Politics problem, why are we declaring string of size n, and not of size k ?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain how method of differences works for diff 1 C if the output is modulo 10^9 + 7

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F can be solved by basic substring structure. Which can be solved in $$$O(n)$$$.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div1 -B or Div2- D https://codeforces.com/contest/1817/submission/204224008

getting runtime error on test 8th some help please.

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can some body give me a simpler implementation of problem D of div 2 FISH GRAPH just the code

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    https://codeforces.com/contest/1818/submission/204263634

    I 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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody explain this: auto dfs = [&](auto&& self, int at) -> void

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well I understand the tutorial. Both of them are correct.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Fish Graph in O(N+M)? Can anyone help?

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it
#include <bits/stdc++.h>
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<int> LIS(int arr[], int x, int y)
{
    int n = (y - x + 1);
    vector<int> 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<int> 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

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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/204716762

Some 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

»
10 months ago, # |
  Vote: I like it +10 Vote: I do not like it

explaination of 1818C/1817A is so good!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 snippet
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same thing here man , any updates ? my submission used the same approach as yours

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1818B — Indivisible

I 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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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:)

»
10 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in 1818B — Indivisible

For n=3, for sequence 1, 2, 3

If 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.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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:
Time and space complexity:
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is this a valid test? It seems to me $$$(4,5)$$$ and $$$(5,4)$$$ form parallel edges, which is not allowed.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      sorry it's a typo. the last edge was supposed to be (3 4), not (5 4) (fixed now)

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

What power do u have?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Because
    PS

    I don't think the codes are incomplete they gave you the core part that was needed.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

who can tell me in the tutorial of the problem D(div2),why to resize the vector p? Isn't p's size clearly?