same to you...looking for quick editorials

No, it is me after solving ABCDE

Though it seems F was not particularly difficult this time

post qns only after contest is over.

i used fenwick tree to optimize it, note that k <= 10, your solution fails because ranges can be very big, so your solution is n^2

you can try it in O(n*k). Refer to below link for reference.

https://www.geeksforgeeks.org/constant-time-range-add-operation-array/

My Submission

your code runs in O(K*N) where K is the number of possible jumps, theoretically in worst case it would reach O(n^2) time complexity which could defenitely get TLE. In this problem i used dynamic programming with fenwick tree, you can look at my code here

For d, you have to combine the dp you are talking about, with the range covering problem (it is easier than segment tree I leave you this video in which that guy explains that problem https://youtu.be/Zze-O2oxoEo?t=219 ) and then you just have to be careful about modulo operations (you might be doing them with negatives)

I hope this was useful

My code is similar with yours and I wonder how to optimize it too. [submission:#17148205]

For d instead of segment tree + dp you can use prefix array + dp.

You don't really need a segment tree for D
I just used prefix sums

D and E should have been swapped ,I didn't even attempt E after continuous TLE's in D .

You don't need segment tree for F either.

#include<bits/stdc++.h>
using namespace std;

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, q; cin >> n >> q;
	set<pair<int, int>> se[2];
	se[0].insert({n, n});
	se[1].insert({n, n});
	long long ans = 1LL * (n - 2) * (n - 2);
	while (q--) {
		int ty, i; cin >> ty >> i;
		ty--;
		auto it = se[ty].lower_bound({i, -1});
		int k = (*it).second;
		ans -= k - 2;
		se[ty ^ 1].insert({(k - 1), i});
	}
	cout << ans << '\n';
    return 0;
}

F: you can use std::map for the same query (lower_bound to find closest) Submission

D: you can use only partial sums of your dp and fill dp[i] with sum of previous values Submission

I also thought of using segtree with lazy prop on F, but I had no segment tree template with lazy propagation :P and I had only 35mins left. So I quit. Missed my chance of solving all problems in ABC for the first time.

I'm taking your template now XD.

I got tle in this, could you plz tell me why?

int ans = 0;
for(int i = 1 ; i <n; i++){
	int x = n-i;
	for(int j = 1; j*j<=x; j++){
		if(x%j == 0){
			ans++;
		if(x/j != j){
			ans++;
		}
		}
	}
}
// ans += ans;
cout << ans ;

Me too for the first time solved set in any contest lol

Can you please further explain how did segment tree help with this problem? I know segment tree but I cannot utilize it to solve this problem.

correct me if I am wrong, the time complexity of your D solution is N*k*log(n) and not N*log(n) which the editorial says is the optimum

In problem E , How can I know that the series will repeat itself ?

I solved it without segment tree

I used difference array. Time complexity of $$$O(N*K)$$$

basically let dp[i] be no of ways to each i.

Then you increment, $$$i$$$+$$$L_j$$$ to $$$i$$$+$$$R_j$$$ with dp[i], increment using difference array method, and keep summing as you move toward right.

The answer would be dp[n]

Submission

I solved it maintaining a prefix sum array and using dp.

dp[i] = sum of dp[j] for all j, i is reachable. As the range was contiguous it was easy to get the sum of dp[j] using prefix sum.

My Sumbission

they want you to union the segments [Li,Ri] i mean {Li,1+Li,2+Li,3+Li,....,Ri} not only values {Li,Ri}

D can be done in O(n*k).

Use range update operation on array, it will take O(n) for each range.

My submission

Thats' so because the time complexity of your solution is O(n*n).

nvm, fixed it, was not solving correctly for when the cycle would end without it ever repeating. fixed code

You can use this dp: dp[i] means how many ways do you have to go to the i-th cell.

Let's get an array of long long dp[2n]. First we fill it with zeros. Denote the sums[2n] as prefix sums array of dp.

1. dp[n] = 1, sums[n] = 1

2. for each cell from n+1 to 2*n and each segment (l[j], r[j]) we calculate: dp[i] = (mod + dp[i] + sums[i - l[j]] - sums[i - r[j] - 1]) % mod

You can understand that part as: to get how many ways I have to go to the i-th cell, I should sum the ways from all dp[the previous one, from which you can get into this].

The value sums[i - l[j]] - sums[i - r[j] - 1] gets us sum: dp[i - r] + dp[i - r + 1] + ... + dp[i - l]

$$$O(N^2)$$$ is too large for $$$N=10^6$$$.

can somebody please explain the logic for c.

n = int(input())
cnt = 0
for i in range(1, n):
    cnt += (n - 1) // i
print(cnt)

In the explanation for C : Could you please explain how the number of ways of choosing is N/A ?

I have tried to do it on paper but couldnot come up with the intution.

[ignore this, too much complex]

let $$$J$$$ be the set of possible jump lengths, now $$$ J = \cup[l_i,r_i] $$$

Now we can use generating function $$$ G $$$ to define that set.
$$$G = \sum_{i=0}^N c_i x^i $$$ where $$$ c_i = 1$$$ if $$${i \in J}$$$ else $$$c_i = 0$$$.

Now, number of ways to reach from $$$1$$$ to $$$N$$$ using exactly $$$k$$$ jumps = $$$[x^{N-1}] G^k$$$.

As there is no restriction of jumps,so we sum it over all possible $$$k$$$.
so, finally what we need is $$$[x^{N-1}]\sum_{k>=0} G^k = [x^{N-1}]\frac{1}{1-G}$$$

now coefficient of $$$ x^{N-1} $$$ in the polynomial $$$\frac{1}{1-G}$$$ can be easily calculated by calculating inverse of polynomial $$$ 1 - G $$$ restricted to max degree $$$N$$$.

Overall complexity is $$$O(N\log{}N)$$$

For calculating inverse of polynomial you can refer Operations on polynomials and series

Pigeon hole principle