solution section for problem C, E and G2 seems to be not formatted well

I think so jiangly had some different solution for G which is using DSU. If anyone could explain it that would be great.

For G1, I had the same solution in mind but why are we not ensuring the existence of $$$m$$$ in $$$(l, r]$$$? I got confused because of that and left

Fast editorial!!!

Hi, I am new to this platform, I am unable to view others submissions for some reason. In the source section it shows N/A. Not sure what is the reason for this, can anybody help me out with this?

How to solve problem D when the value of "real" is not necessarily between l and r? I spent hours on this version of the problem. One approach is dp but states are too big. Is there any other way?

Here's a testcase:

4 6
2 4 1
5 6 4
5 7 2
1 3 100

Output: 100

Alternative solution for $$$F$$$ (which I've seen quite a few times and are probably the reason for all the hacks):

Let's fix some $$$X$$$. For all vertices $$$u$$$ with $$$\mathrm{deg}(u) \le X$$$, we can just simulate the change and recalculate the answer in $$$\mathcal O(X)$$$. If $$$\mathrm{deg}(u) \gt X$$$, for all adjacent colors, we will store the sum of edges with that specific color that end in $$$u$$$. A color-update of such vertices can be performed in $$$\mathcal O(1)$$$ (add the contribution of the old color, remove the contribution of the new color).

It remains to update this "color-map". Since each vertex $$$v$$$ can be adjacent to at most $$$\frac{n}{X}$$$ such vertices, these updates can also be performed in $$$\mathcal O(n / X)$$$ time.

The total time complexity is $$$\mathcal O(n + q \cdot \max (X, n / X))$$$. The memory complexity is $$$\mathcal O \left(n + \frac{n}{X} \cdot n \right)$$$ if we remove the unused colors from the map.

If we choose $$$X = \sqrt{n}$$$, the total time complexity is $$$\mathcal O((n + q) \sqrt{n})$$$. Unfortunately, my solution with that choice of $$$X$$$ was hacked (MLE), but setting $$$X$$$ to $$$3500$$$ ($$$~5\sqrt{n}$$$) works.

Looks like there were many solutions for $$$G2$$$, here's mine using Persistent Segment Trees and maximum subarray sum queries (somewhat similar to the editorial but worse time complexity xd). (This segtree extension was also part of the solution of a recent div 3H).

The general idea is to fix the index $$$i \in [1, n]$$$ of the minimum element and find the largest possible median containing $$$i$$$. We can binary search the median with the same construction of the array $$$b(m)$$$ as in the editorial of $$$G1$$$, i.e. for some fixed $$$m$$$, $$$b_j(m) = a_j \ge m\ ?\ 1 : -1$$$. Any non-negative subarray sum would correspond to a median $$$\ge m$$$. To ensure that $$$i$$$ is included in that subarray, we add a large number to $$$b_i(m)$$$, i.e. $$$b_i(m) = X + (a_i \ge m\ ?\ 1 : -1)$$$. One option would be $$$X = 2n$$$.

We need all the possible arrays of $$$b(m)$$$, which can be stored in a persistent segment tree. Start with $$$b_j = -1$$$ and for all $$$v \in [1, n]$$$ in descending order, do the following:

• For all indices $$$i$$$ with $$$a_i = v$$$, set $$$b_i(v) = 1$$$.

After doing that for all indices with value $$$v$$$ (and values $$$ \gt v$$$), our persistent segment tree will have the values of $$$b(v)$$$.

While iterating over the $$$i$$$ and doing the binary search, we need to add $$$2n$$$ to $$$b_i$$$. This is easy, since we can simply update $$$b_i$$$ and "forget" about the update.

The total time complexity is $$$\mathcal O(n \cdot \log^2(n))$$$, where the $$$\log$$$ factors come from binary search and persistent segment tree update. The memory complexity is around $$$\mathcal O(n \cdot \log n)$$$, but this has a high constant hidden, since we need to store 4 ints in each vertex of our segment tree for the queries. It is important that we remove the persistent segment tree vertices we create while querying — otherwise, we will need quite a lot of memory ...

Submission

I am sorry if I missed something, but in the proof for the solution of problem E, I think there are times when $$$P_i=\frac{p_i}{g}$$$ and $$$x=\frac{p_{i-1}}{p_i}$$$ are not coprime: For example, if the underlying array is [49, 7, 1], then the prefix array would be [49, 7, 1] and the suffix array is [1, 1, 1]. If we let $$$i=2$$$, then $$$P_i=\frac{7}{1}=7$$$ and $$$x=\frac{49}{7}=7$$$, and they are not coprime.

Is there something I’m missing here? I’d appreciate any clarification.

my g2 sol uses a two pointer approach while using segtree to handle query and updates. you can find nlogn solution here

For E: Should it be "Key arithmetic facts: $$$S_i$$$ and $$$x$$$ are always coprime, because $$$x = \frac{P_{i-1}}{P_i}$$$ and no prime can divide both a number and its own quotient. Symmetrically, $$$P_i$$$ and $$$y$$$ are coprime." ？

doubt solved

soullless Why didn't you decide to accept $$$O(n\sqrt{n}\cdot logn)$$$ solutions in F?

Is there an issue with the solution for problem D?
For example, take this test case:
3 5
1 2 100
4 6 9
4 6 9
The reference program outputs 100, but the correct answer should be 9.

"In the solution to problem G1, I have a different opinion. I believe the correct case should be when the suffix maximum is greater than the prefix minimum."

Problem D: Why does my DSU approach gives TLE on test 28.. it must be O(n.logn) Submission: 330766212

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

2126A — Only One Digit

solution- https://youtu.be/T2g3bK6eNrM?si=d49_BqqFjlu1jTkh

Problem F: why use map instead of unordered_map? The elements don't need to be sorted and map offers worse time complexity for access

For Problem D:

1 9 20, 1 9 8, 8 8 100

the editorial solution gives answer 20 but the actual answer is 100 right?

In problem F, different heavy-light partition ways will get different verdict(TLE or AC) in spite of all of them is $$$O(\sqrt{n} \cdot logn)$$$ per query. I found a way that can AC(640ms): https://codeforces.me/contest/2126/submission/350566213

Had an alternative solution to E : https://codeforces.me/contest/2126/submission/352395496

Tried to create the original array and verify if the pref and sum gcd arrays match for the created array. An element i in the original array at a bare minimum has to have both p[i] and s[i] as factors. So generate an array v where v[i] = (p[i] * s[i]) / gcd(p[i], s[i]). This ensures that v[i] does not have any additional factors and only the bare minimum to be valid for both p[i] and s[i] values simultaneously.

Then to just verify p and s using this array. Can someone help with how to prove that this would work for all cases?

How is F rated 2000. The logic is simple. May be critical edge cases??

I am stucked in a doubt in Problem D. In editorial, it is checking only lower bound. It is not checking if curr value is greater than ri? And, It is clearly given in the question, that we can only enter in the casino, if our coin's value is between li and ri.

can someone explain this to me.

the solution of the problem E is not formatted correctly really difficult to even understand the solution

Problem B has already a neat solution, but other way to think of it in terms of sliding window is as follows.

The idea is to maintain a sliding window of size k and check two things:

1. whether all elements in the current window are 0 (good weather),
2. whether we are allowed to start a hike at this position.

To check if a window contains only zeros, maintain a variable rain which stores the number of 1s in the current window. Using a sliding window:

rain += a[i];
if(i >= k)
    rain -= a[i-k];

At any index i ≥ k-1, the window [i-k+1 ... i] is valid if rain == 0.

Next, we need to enforce the break condition. For this, maintain a variable next which represents the earliest index where the next hike can start.

When we find a valid window:

• let start = i - k + 1
• we can take the hike only if start >= next

So the condition becomes:

if(start >= next && rain == 0)

After taking a hike:

• the hike occupies days [start ... i]
• day i+1 is a mandatory break
• hence the next possible starting day is i+2

So we update:

next = i + 2;
count++;

Overall, we iterate once over the array, maintaining the sliding window and greedily taking the earliest possible valid hike.

This greedy works because taking a hike as early as possible always leaves more room for future hikes, and never reduces the total count.

Complete implementation:

void solve() {
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n);
    init(a);

    ll next = 0, count = 0;
    ll rain = 0;

    for(int i = 0; i < n; i++) {
        rain += a[i];
        if(i >= k)
            rain -= a[i-k];

        if(i >= k-1) {
            ll start = i-k+1;
            if(start >= next && rain == 0) {
                next = i + 2;
                count++;
            }
        }
    }
    cout << count << endl;
}

Don't get how test case 1 for C is 3->2->1->4->5

shouldn't it be 1->2->3->4->5? as we need to climb in a non-decreasing manner.

Is this a valid test case for C?? 3 5 4 10 9 5 6 5 6 7 6

if yes , then the number of coins won't be monotonic as said in the editorial!!!!

I did not understand the solution of problem E after reading the editorial, especially due to the "key arithmetic fact" part, which just sent me. (Maybe I am just stupid)

So I tried to derive a valid proof on my own again (first time I did it incorrectly hence I got a WA). It's as follows:

The first 3 necessary conditions are quite obvious from the editorial, so I won't go deep into that.

But for the sufficient condition..

We know the overall GCD of the hidden array a must be just one value. The overall GCD (lets call it g) can also be calculated by finding the GCD of "the prefix GCD at index i, the suffix GCD at index i + 1" for i in range [1, n — 1]. This works as the prefix of i and the suffix of (i + 1) covers the entire array.

So essentially we must check if (g == gcd(p[i], s[i + 1])) holds true in the domain of i.

We can easily prove this is a sufficient condition through contradiction.

So to check if the given arrays p and s are valid for a hidden array a, we need to check the three necessary conditions and then this last sufficient condition.

If all checks out, we print YES, else NO.