Get your f*cking AI slop out of here.

This is a really fun contest, I highly recommend to participate in the mirror tomorrow!

I am not sure I have the right idea, but it seems like you are doing HLD?

The average distance between two random nodes in a random tree is asymptotically approximately $$$\sqrt{\frac{n\pi}{2}}-1$$$. Therefore, in random trees there is not much improvement, as $$$\log\left(\sqrt{\frac{n\pi}{2}}-1\right) \approx \frac{1}{2}\log(n)$$$.

I think it would be really bad. Part of the fun of ICPC is strategizing what tasks to do first, and partial points would completely eliminate that.

Check out my submission for G: https://mirror.codeforces.com/contest/2205/submission/364629640

It is quite a bit shorter than the editorial code. I also did inclusion-exclusion in a bit of a weird way: we only want to subtract $$$d$$$ such that $$$d$$$ does not divide $$$n$$$. Hence we can skip $$$d$$$ such that there is a $$$p | n$$$ such that $$$p^e$$$ divides $$$d$$$ but $$$p^e$$$ does not divide $$$n$$$ for some $$$e \gt 1$$$. (you can figure this out without factoring $$$n$$$!). Then we multiply by $$$\mu\left(\frac{d}{\gcd(d,n)}\right)$$$. So you can get away with not computing some $$$f(T)$$$, where either T fails the above checks, or $$$\mu\left(\frac{T}{\gcd(T,n)}\right) = 0$$$, although this is only a constant optimization.

Just explain why you make a new solution for C1, after you solved C2 already.

I am like 99% sure something is up with your submissions (cheating?!)

Why would you submit C1 10 minutes after solving C2, when C1 is an intermediate step of solving C2. I find this very weird. Mind explaining why? Why would you write a completely new solution when you already solved the problem?

6 7

why do you cheat bro?

do div 3 and div 4 instead

The queue was kinda bad. At this rate, we might as well remove pretests altogether and only have systests.

If you want a hint, you can also look at the editorial. My advice: don't. You learn much more if you do it without hints. You certainly don't and shouldn't need AI.

Rohit_suiii My dude... you are not fooling anyone. Just one look at your recent submissions, and what do we see: No way a human would ever write this. Just stop lying, and find an actual hobby, that you are willing to spend time on to get better.

Getting a GF is easier than getting CM. Getting CM actually takes time and effort, getting GF just takes confidence.

LMAO. I didn't know this, but that is just hilarious.

Not only that, but this account obviously either used AI, or had multiple people participating on the same account, since their submissions have different templates. Quite sad.

Contrary to the popular opinion, I think problem C is good.

...

However, the queue was very slow. It took like 20 minutes for me to find out that my first submit was WA.

A good thing to do after you get WA, is to stresstest: - make a (python) script that generates very small testcases - make the dumbest possible brute force - make a script that generates the test cases, runs the brute force and your code, and then compares the outputs

the 3rd point you can already do before the contest. This saves a lot of time usually, although it is a bit tricky to find a good testcase for problem C. Once you have a small testcase where your solution does not work, it is easy to see why it does not work. That way, you don't get more than 1 WA on a problem

Silence, AI clown!

Signature of the AI.

Hey mr. Arnab Manna. Why don't you participate in ICPC? Given your impressive problem solving skills on Codeforces, you should do quite well!

If you do 4d mo, just write a quadratic solution with good constant factor, and it will be faster

Iron_china ballast666

Think about it as a 2d plot, where you draw a cross in the middle of the plot. Then you choose (left top + right bottom) and (left bottom + right top)

Hint: try to solve it in exactly 2 operations.

This does not work, the polynomials you get in the recursion are (much) larger than $$$O\left(\frac{n}{2}\right)$$$. This would be at least $$$O(n^2)$$$, with extra log factor from FFT.

There is a trick to do this in $$$O(k log(k))$$$, where $$$k$$$ is the largest value in the queries ($$$\leq 10^5$$$). It goes as follows:

Now we use that $$$\log(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \frac{x^4}{4} + \ldots$$$. To get $$$\log(1+x^i)$$$, we replace $$$x$$$ in this formula by $$$x^i$$$. Since we are only interested in the first $$$k \leq 10^5$$$ coefficients, the number of nonzero coefficients of $$$\log(1+x^i)$$$ that we care about is $$$O\left(\frac{k}{i}\right)$$$. Therefore, we can calculate the first $$$k$$$ coefficients of $$$2\sum_{i=1}^{n}\log\left(1+x^i\right)$$$ in $$$O\left(\sum_{i=1}^{n} \frac{k}{i}\right) = O(k \log(n))$$$. Lastly, once we calculated $$$p(x) = 2\sum_{i=1}^{n}\log\left(1+x^i\right)$$$, we need to calculate the generating function $$$e^p(x)$$$. This can be done in $$$O(k \log(k))$$$ using FFT (link).

Since any terms $$$(1+x^i)$$$ with $$$i \gt k$$$ are irrelevant for the answer, we can assume that the complexity is therefore $$$O(k\log(k))$$$, where $$$k$$$ is the largest index we care about. The only annoying thing is that $$$10^9+7$$$ is not suited for NTT, but you can still do it, only with a ever so slightly worse constant factor.

Real men use the $$$O(n^{1+\varepsilon})$$$ flow algorithm.

Very cool! I hope others follow and upload lessons.

Require govt id to sign up

For E, you can also just compute $$$a_i := lcm(p_i,s_i)$$$, and then verify that $$$a$$$ produces $$$p$$$ and $$$s$$$.

cost is $$$\sum_{i=1}^{n}p_i$$$ plus some additional cost. So we want to minimize the additional cost. Sort everything by height. if we are at $$$h_i$$$, and want to go to $$$h_j$$$, the cost is 0 if $$$h_j \lt h_i + p_i$$$ and $$$h_j-h_i-p_i$$$ otherwise. Note that going down is always free. We do dp to get the minimum extra cost to be at height $$$h_i$$$. Either this value depends linearly on some previous value (as in $$$C + h_j$$$ for some C), or it is constant (if it is close enough to some previous height). We of course take the minimum of these 2 options. Maintain a data structure to update the minimum (C) in some interval, and query at a point (segment tree). Complexity is $$$O(n\log(n))$$$ with coordinate compression.

I would really check your previous implementation. I implemented it without any tricks, and max test runs in < 2 seconds. It should not be as slow as your code is

yes. Then the actual runtime is O(B), and the code size is ~300 m / B, where B is the blocksize. B = 3e6 should do the trick.

min25 is really overkill. If it is still too slow, notice that you only care about the count of $$$e_i$$$'s. That is, how many $$$e_i$$$'s are 1, how many are 2, etc. This gives us some classes. For example, $$$12=2^2\times 3$$$ is in the class $$$1,1,0,0,0,...$$$, since it has one prime once and one prime twice. There are only very few possible such classes. Instead of directly computing the answer, use your segmented sieve to count how many times each class appears in each segment, and store the results in a table (i mean compute locally on your own computer, where there is no 5s timelimit). This way, you only need to compute the last segment from scratch.

Also, segmented sieve should really not be that slow.

Look up segmented sieve. You can do it with sqrt(m) memory :) If you want faster time, you can use min25 sieve, and then it is $$$\tilde{O}(m^{\frac{2}{3}})$$$ time aswell, but given the constraints this is not even needed. If you want an even faster solution, you can precompute classes.

If the last value is $$$a = \prod_{i} p_i^{e_i}$$$ for some primes $$$p_i$$$, Then for each prime factor separately, the number of occurrences among the $$$n$$$ positions can only increase. Therefore, for $$$p_i$$$, there are $$$\binom{n-1+e_i}{e_i}$$$ possible ways of distributing. Since $$$e_i$$$ is at most $$$\log_2(m)$$$, we just precompute all possible values. Now the total number of sequences for last element $$$a$$$ is the product of $$$\binom{n-1+e_i}{e_i}$$$ for all primes. We can now do this for all possible last numbers with sieve of eratosthenes in $$$O(m \log\log(m))$$$, which is sufficient given the bounds.

Read the question again. It is about the line graph of the original graph, which is much larger.

Yes it can. Then its just an empty graph.

"Certain regions" LOL

Does anyone have a "nice" formula? I ran a DP for $$$1\leq n \leq 7$$$, and the answers are

1. 1
2. 1
3. 2
4. 228
5. 1575480
6. 743368208920
7. 37926888480957490332

Notice that the 7-th value does not fit in a long long anymore :)

In python the seed is random, in c++ you need to do that yourself. See this blog: BLOG

GGs. Does anyone know solution for problem C? I was thinking of some solutions with aliens trick to make sure you use the free stuff, but no idea if that would have even worked.

Edit: also, it was not clear to me whether you already paid for the p,q operations, or those are the max amounts you can pay for.

I am starting to think the authors like arrays. Literally all problems were like "you have an array and an operation on this array, what happens?"

$$$\gcd(7,14 + 7*2^{50}) = 7$$$. However $$$7 \oplus (14 + 7*2^{50}) = 9 + 7*2^{50}$$$, and $$$\gcd(7, 9 + 7*2^{50}) = \gcd(7,9)=1$$$.

Those do not matter, you can have k or k + 2^50*a[i]. Both have same result. Fix your problem please.

$$$2^n-1$$$ does not even work. Take $$$\gcd(7,14) \neq \gcd(7,7\^14 = 9)$$$ for example. only $$$2^n$$$ or $$$0$$$ work.

Very nice construction!

To get a very large number with as little edges as possible, the Fibonacci construction is indeed optimal: Order all nodes by the number of paths to that node. Suppose some node has indegree d > 2, then we can replace those edges by d-2 intermediate nodes with indegree 2. Therefore, each indegree is at most 2. It is clearly optimal to have the edges going into each node to be from the largest nodes before that node. Therefore, we only care about the number of paths to the largest 2 nodes, lets say a < b. We have two options: either the next node has degree 2, in which case it is a+b. Or it has degree 1, in which case it is b. Since having more than 2 nodes of the same size is useless (since all nodes have indegree at most 2), we know that the node after that must be b+b. Hence, if we want to grow as quickly as possible, we have 2 possible transitions:

$$$(a,b) - \gt (b, a+b)$$$ with 2 edges

$$$(a,b) - \gt (b, b) - \gt (b, 2b)$$$ with 3 edges.

Note that after both the second largest element is identical, even though the first uses less edges. Moreover, if $$$a \geq (\sqrt[3]{4}-1)b$$$, then the largest element grows quicker on a log scale as well. Therefore, when $$$a \geq (\sqrt[3]{4}-1)b$$$, the first operation is optimal. Now, note that in the fibonacci sequence, 1, 2, 3, 5, ..., from 2/3 onwards, all ratios are larger than $$$\sqrt[3]{4}-1$$$. This means that after some of the second operations, if we do the first operation a single time, it is optimal to only do the first operation from that point onwards. Therefore, the optimal growth rate is achieved by doing O(1) of the second operations (in fact only 1!), then only do the first operation.

This argument for the (asymtotically) fastest growth is not sufficient for the question, since we need to add extra edges to the last node (as in binary/fibonacci expansion). However, we can easily see that the fibonacci construction is more efficient in this than the binary construction as well. Suppose we used F_i as well as F_{i+1}, then we might as well have used $$$F_{i+2}$$$ instead. Hence we need to use at most $$$\frac{\log_{~1.61}(n)}{2}$$$ extra edges, instead of the $$$\log_2(n)$$$ extra edges in the binary construction.

If someone has an easier approach, please share. I think we can do d&c. Suppose we split a segment in the middle, and the "optimal" segment lies over this split. Then it consists of a suffix of the left segment, and a prefix of the right segment. We have 2 cases:

• One of the endpoints (left or right) is neither the smallest nor the largest element of the corresponding half.

• The endpoints are the largest (but not smallest) and the smallest (but not largest) in their halfs.

For the first case, we iterate over the other side, and we only need to check the furthest prefix/suffix on the other side that satisfies the first case.

For the second case, we can do 2 pointers approach over the suffixes/prefixes that satisfy this case, and keep track of the furthest suffix/prefix that is still (maybe) possible. For example, if right endpoint is minimum in its half, and left endpoint is maximum, and H is the largest value in the right half, then from the suffix maxima on the left side, we point to the largest one that is strictly less than H. Then we need to check whether the minimum on the left side is less than the right endpoint.

This is O(n log(n)). I feel like there might be a way easier solution, so please tell me if so.

I am curious how your O(n) solution works. Can you maybe share it? You can do O(n log(n)) with d&c, but if there is an easier way please tell me.

even though he is cheating, using lambda functions for sort() is not strange. I do it aswell

long long is 8 bytes, int only 4. If you use 2^26 long longs, you get MLE.

Technically, if you want a ""faster"" solution, you can use https://en.wikipedia.org/wiki/Van_Emde_Boas_tree . Then it is O(n loglog(n)) :)

You also need to delete numbers, I am not sure how DSU can handle that. Can you maybe implement it?

that does not work if the elements a_1,...,a_n are not unique, i.e. a_i=a_j for i,j <= n.

that sounds significantly more annoying to implement, and is slower (O(n log(n)^2) instead of O(n log(n))

aight, calm down:

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
typedef long long ll;
typedef vector<int> vi;

void solve(){
    int n,q; cin >> n >> q;
    vi a(n), cnt(n+1), perm(n+1);
    for(auto& c : a) cin >> c;
    set<int> missing;
    rep(i,0,n) if (a[i]<=n) cnt[a[i]]++;
    rep(i,0,n+1) if (cnt[i]<1) missing.insert(i);
    rep(i,0,n+1){
        perm[i] = *begin(missing);
        missing.erase(perm[i]);
        cnt[perm[i]]++;
        if (i<n) {
            cnt[a[i]]--;
            if (cnt[a[i]]<1) missing.insert(a[i]);
        }
    }
    while(q--){
        ll x; cin >> x; --x;
        if (x<n) cout << a[x] << '\n';
        else cout << perm[(x-n)%(n+1)] << '\n';
    }
}

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int t; cin >> t;
    while(t--) solve();
}

How does your "easy" formula work, and how do you brute force efficiently (n=1e5)?

My solution is as follows: First observe that s_{i+1},...,s_{i+n} cannot be equal to s_{i}, and furthermore for i>n, we have s_{i} <= n, since it is the mex of n numbers. Hence for i>n, the sequence is periodic with period n+1, and s_{n+1},...,s_{2n+2} are a permutation of 0,...,n.

To find this permutation, we can use an std::set that stores the numbers from 0,...,n that do not occur in our 'current' window of n elements. we can find the MEX by doing *set.begin(), and update the set by adding numbers s_{i-n} to it if it is the last occurrence of s_{i-n} in the interval, and removing s_{i} from the set, since after the interval moves one place to the right it will contain s_{i}.

I am not sure if there is an easier way? what is your solution?

I never really did codeforces, but over the past 5 years I've done a lot of ICPC style contests, with (reasonably) good results. My ICPC teammate convinced me to do more CF, and I enjoy it a lot : )

Why do you think that?

wdym?

That rating graph is proof enough lol

If you use Miller-Rabin, you might as well implement pollard rho in a few additional lines. Then you have n^1/4 solution.

Solve more problems :-) Good luck!

In Mo's algorithm, we either increase one of the ends, or decrease one of the ends. Both ways, we are interested in counting how many intervals there are in the L-R range with xor sum equal to k. If we take prefix xor sums, we can write this as pref[R+1] ^ pref[i] == k ==> pref[i] == k ^ pref[R+1]. Therefore, we need to maintain counts of all possible values of pref[i] in the interval, so that we can update the answer. Since each time L or R changes, one value of pref[i] gets inserted or removed, we can do this in O(1).

aliens trick

I do think it's cheating. Debugging and writing stress tests is part of solving a problem, and writing a generator that generates random numbers in a specific format is part of that. Unless the input is only a single number, google rng will not be of much use.

Try to do tasks completely without AI. That way, you'll actually learn something from them!

Dekubopdomdem dekubopdomdem

@dummy16661 on CF using chatgpt in contests is not allowed. Dont do it next contest please

That is a lot easier than what I've done, thanks!

You cannot insert elements in arbitrary positions. only at the beginning of some row

Does anyone have a "nice" solution for B? Apart from my horrible implementation, in retrospect it still feels harder than problem D. Maybe I'm just missing something.

I will save this post somewhere, and hold you to it. Good luck!

Beautiful art by chromate00!

AAAAAAAAHHHHHHH Why o why is problem F so much easier than E? I didnt look at the scoreboard, and hence spent 3/4 of the contest implementing E instead of F :(. Anyway, nice problems (especially A,B,C)