Fast editorial, also very few people gave the contest, maybe because of mid-sems ;)

I think today less people gave the contest

Loved the problem Div2D / Div1B

I dont really have a thing to complain about this contest LMAO XD

I think problem B in this contest is more difficult than other div2 contests

How do you guys solve the questions so fast? Every question from every contest seems so different from each other. How Do i improve?? :(

Am I the only one who found the DP approach for C2 way easier than the stack one? I saw a ton of people doing stack solutions, but DP just felt so much lighter and more intuitive to me. I just let dp[i] store the total sum of f(a[j...i]) for all points j (where 1 <= j <= i).

If you need x minimum numbers to satisfy the condition upto [1...i], you just look back at the previous state. If the prefix up to i-1 also needed those exact same x minimum numbers, your current state just smoothly extends from it having dp[i]+i-p basically where p is the first index where you could get a[i] as a[i]-1 basically, and if you need x+1 numbers than the previous one then its just dp[i] + i+1 as you would need +1 for all of the subarrays computed previously and including the current value as a[i] can be an independent value too. You basically just carry over the state from dp[i-1] without having to overcomplicate things. The transition is extremely clean.

[submission:https://mirror.codeforces.com/contest/2202/submission/364102671]

Nice Div2B. I just love those problems that make me again and again realize all of my time and efforts put into CP is just completely meaningless and useless as well as the whole existence of myself as long as I am dong this. Really, really looking forward to the end of my miserable and painful and tragic CP life when I will finally become a normal and happy and healthy human being.

DIV 2B was tricky

for me difficulty of problems are: C1<C2<B<A (div2)

My solution for Div2 C1 and C2 / Div1 A1 and A2. I didn't use a stack for implementation, so I thought this might be an alternate solution.

Solution for C1

We maintain two variables l and r. Let v denote the input vector Initially set l and r both to INT_MAX. Let the variable ans=0. Then we can run the following algorithm:-

Start Loop

For i=0,1,2, ... N-1

If v[i]-1 does not lie between l and r, update l to v[i]

Update r to v[i]

End loop

Return ans

Proof of correctness:- Let us try to understand in a layman sense what l and r actually represent. For any given 0<=i<n, for v[i] not to be an original element, v[i]-1 must have appeared before. This is a necessary condition, but it's not sufficient. Consider the test case, n=5, v=[1,2,3,2,4]. In this case, although 3 has appeared before 4, the presence of the 2 in between forces 4 to be an original element. So now, we can understand the significance of l and r. We will define an element x, to be usable if and only if it can be used to generate x+1. So all elements from l to r(both inclusive) represent the usable elements. If v[i]-1 does not belong to the set of usable elements i.e between l and r, then v[i] is an an original element. In that case, we have to increment the answer, and set l to v[i]. r will be set to v[i] regardless. This clearly solves our earlier problem( when 3 was not actually an usable element), and is also sufficient.

Solution for C2

Initialize variable ans=0 Let us make an observation. Consider each element v[i] for i=0,1,..n-1. Consider all subarrays v[l,l+1,..r], such that l<=i<=r. We want to count the number of subarrays for which v[i] has to be an original element in the subarray. Summing over all i will give us the desired answer.

Now we will try to reuse the original algorithm we had for C1. Notice that whether v[i] is an original element or not depends on only the elements before it. This means that contribution of v[i] as an original element will be the same for every subarray a[i,...m], where i<=m<=n.

Suppose we are in the if block of the algorithm, it means that v[i] is an original element of the subarray a[0,..i]. In that case, v[i] will contribute 1 to the ans for every subarray a[k,..i] for 0<=k<=i. Therefore we have i+1 contributions for every subarray a[i,...m] for i<=m<=n. So total contribution be be (i+1)*(n-i). We add this to the ans.

Otherwise, there exists an usable element for v[i], which is v[i]-1. We find the nearest occurrence of v[i]-1 to v[i]. Let it be j. We can easily find j if we story the last location of all elements using a map. Therefore, for every 1<=k<=j, v[i] is not an original element for v[k,..i]. So it will contribute 0 for all such subarrays. But for each j+1<=k<=i, v[i] does not have an usable element, so it will contribute 1 to the ans for each such subarray. So we have i-j contributions for every subarray a[i,..m]. So total contribution would be (i-j)*(n-i). We add this to the ans.

We return the final ans.

Proof of correctness is apparent from the explanation.

Hope this helps!

Me: just let me die. Problem B: solve me then.

a simpler approach to div1B / div2D

    int n, k; cin >> n >> k;
    if (k < n || k >= 2 * n) {
        cout << "no" nl;
        return;
    }
    cout << "yes" nl;
    for (int i = 2; i <= k - n + 1; i++) {
        cout << i << ' ' << i - 1 << ' ';
    }
    cout << 1 << ' ' << (k - n + 1) << ' ';
    for (int i = k - n + 2; i <= n; i++) {
        cout << i << ' ' << i << ' ';
    }
    cout nl;

Thank you for this very nice contest!

For problem A, my solution did not use the observation from the editorial. Call the amount of moves of the first kind a, the amount of the second kind b, and for the third kind c. Then, it is possible to go from (0,0) to (x,y) iff there exists a solution in which a, b, c are non-negative integers for the following:

a * (2,1) + b*(3,0) + c*(4,-1) = (x,y)

Solving this system proves the exercise left for the reader.

PS: does anyone know when is the next rollback? I can't shake off the felling that there is a lot of cheating in the recent DIV2s.

in div2D/div1B, can someone explain why does a pair flips in at most 2 ops, like there can be a case where say first 1 was seen (ops=1), then next 1 is seen when 3, 1 happens(ops=2), now finally in the 3rd op, we flip the 2 1s,

for div2: Easy C1 but to hard B.

Can someone explain me the editorial for div 2 A. its written that all are ending on same spot (6,0). but how. like

(0,0)→(2,1) -> (4,2)→(6,3)

(0,0)→(4,-1) -> (8,-2)→(12,-3).

Or i misunderstood the question or the editorial.

My solution of Div2 A (that's essentially equivalent to the second solution in the editorial).

Proposition. Let $$$S_i$$$ be the set of coordinates where Steve can reach after $$$i$$$ moves. Then,

It's not too hard to find this, if you enumerate first 2 or 3 steps by hand. Proof is easy (by induction, starting from $$$S_0 = \left\{ (0, 0) \right\}$$$).

Then, it's very clear that $$$x + y$$$ must be a positive multiple of $$$3$$$ for $$$(x, y)$$$ to be a member of $$$S_i$$$, because $$$(2i + t) + (i - t) = 3i$$$. Then you have $$$i = (x + y) / 3$$$. The answer is YES if $$$2i \le x \le 4i$$$ (if $$$x$$$ is within this range, you have a valid $$$t$$$).

I still don't understand the editorial for Div2B.

What do you mean by "you can't use the same letter twice in a row because the first and last letters of T will be the same on the next iteration"?

If we assume T is even, we already can't use the same letter twice, no? What's the point of re-stating it with additional reason? I feel like I'm missing something here... It's like as if we had a choice of picking same letter twice.

Am I the only one who solved Div2/B with DP ?

Can anyone tell me for the Question C why code 1 got WA but code2 passed?

code 1: ~~~~~~ void Puzzle_Out() { int n; cin >> n; std::vector a(n); for(int &i : a) cin >> i;

multiset<int> ml;
int ans =  0;
for(int i =0; i < n;i++){
    int val  = a[i] - 1;
    if(ml.find(val) == ml.end()){
       ans++;
       ml.clear();
    }
    ml.insert(a[i]);
}
cout << ans;
cout << nl;

} ~~~~~~

code 2: ~~~~~~~~~ void Puzzle_Out() { int n; cin >> n; std::vector a(n); for(int &i : a) cin >> i; vector s;

int ans =  0;
for(int i =0; i < n;i++){

    while(!s.empty() && s.back() != a[i] - 1){
       s.pop_back();
    }
    if(s.empty()){
       ans++;
       s.push_back(a[i]);
    }else{
       s.push_back(a[i]);
    }
}
cout << ans;
cout << nl;

} ~~~~~~~~~~

I did the B in a brute-force manner. I basically went through each letter and checked if it's possible to have and used recursion when encountered '?', and we can put both a and b...

Here's my code...

bool possible(string &s, int pos, int l, int r)
{
    int n = s.length();
    for (int i = pos; i < n; i++)
    {
        // cout << l << ' ' << r << ' ' << s[i] << nl;
        if (s[i] == 'a')
        {
            if (l % 2 == 0 && r % 2 == 0)
            {
                return false;
            }
            else if (l % 2 == 1)
            {
                l++;
            }
            else
            {
                r--;
            }
        }
        else if (s[i] == 'b')
        {
            if (l % 2 == 1 && r % 2 == 1)
            {
                return false;
            }
            else if (l % 2 == 0)
            {
                l++;
            }
            else
            {
                r--;
            }
        }
        else
        {
            if (l % 2 == r % 2)
            {
                l++;
            }
            else
            {
                return possible(s, i + 1, l + 1, r) || possible(s, i + 1, l, r - 1);
            }
        }
    }

    return true;
}

void solve()
{
    int n;
    cin >> n;

    int ap = (n + 1) / 2, bp = n / 2;
    string s;
    cin >> s;
    int a = 0, b = 0, q = 0;
    for (int i = 0; i < n; i++)
    {
        switch (s[i])
        {
        case 'a':
            a++;
            break;
        case 'b':
            b++;
            break;
        default:
            q++;
            break;
        }
    }

    if (a > ap || b > bp)
    {
        NO;
        return;
    }

    if (q == n)
    {
        YES;
        return;
    }

    if (possible(s, 0, 1, n))
    {
        YES;
    }
    else
    {
        NO;
    }
}

So sad that there was no graph/tree problem in div 2=((((( Stuck on A and B last night, somehow still managed to solve 5 problems(solve C1 before B and D before C2 lol), and still got negative delta. Can someone give me some advice on how to become CM?

for a, x = 2a+3b+4c, y = a-c, x+y = 3a+3b+3c, so x+y≡0(mod3)，

x＞=2a，a<=x/2，y<=x/2，x＞=4c，c<=x/4，-c＞=-x/4，so y＞=-x/4

so cant A2 use prefix solution?

any alternate ways of thinking about the ')' dp in Div2E/Div1C

for b , odd: aab or aba, both x[2] != x[3],expand on it, odd: x[2i] != x[2i+1]

even: ab or ba , expand on it, x[2i-1] != x[2i]

For (Div2C1==Div1A1) conclusion that element $$$a_i$$$ can be merged if $$$x \le a_i \le y+1$$$ isn't correct. $$$a_i$$$ must be bigger than $$$x$$$. In example: $$$1,2,5,6,5$$$ this solution would give $$$2$$$, but the answer is $$$3$$$ because of the last element.

For (Div2C1==Div1A1) I wrote a stress test using Solution 2 to verify Solution 1, but I haven’t been able to find any failing test cases. Could someone help me check what’s wrong with my greedy approach? :)

364147493

Give me some hint for Div2A i am unable to think and intute about A , how do i came up from (x,y) ----> (0,0) ??

loved the contest , thanks alot chromate chromate00

My solution for div1E :364151963

For conflict/overlap over all shifts: for small d: brute shifts, for sparse forced residues: count shifts via (r-s mod d),for dense: bitset rotation + popcount

Can anyone please explain to me the dp solution for C2? My approach was to store sum of f(i...j), i <= j <= n in dp[i] my submission — https://mirror.codeforces.com/contest/2202/submission/364103957

I completely neglected the fact that when I increase l then there will be some changes in the elements needed in the shortest sequence. Is there some way to account for that in the dp?

I’m a Div.2 user, but I became interested in the last problem of Div.1, so during the contest I focused only on Div.1G and solved it. Therefore, I’d like to present my approach, which I believe is more intuitive than the editorial’s method. Also, while the official solution has efficiency $$$0.4 - o(1)$$$, my method achieves efficiency $$$0.444\cdots - o(1)$$$, so it is more efficient.

Using this method, I used about $$$410,000+$$$ vertices, and my implementation is here: 364106211

i think the first solution of div2C1/ div1A1 has some problems or maybe i just misunderstood it, going by the explantion of C1,the answer of example 1 2 4 5 3 7 8 should be 3 ， not 4. but the answer is 4

For Div2 C2, it is essentially an optimization of brute-force traversal of all substrings and summing up the results, using the monotonic stack data structure. As for how to optimize, it depends on what we are actually trying to calculate — we aim to find the number of all subsegments covering the i-th position. For example:

1 2 3 6 5 6

1 2 3 4 5 6

When processing 3 (the 3rd element, 0-based), how to calculate its contribution? We just need to compute the number of all subsegments covering the i-th position within the range from the valid left interval to the valid right interval. This can be easily derived using the inclusion-exclusion principle:save = total number of subsegments — number of left subsegments — number of right subsegmentsHere, left part: [1,2], right part: [6,5,6]This is equivalent to save = (3-2)(6-3), which generalizes to (i-pre)(n-i). Here, pre stores the end of the previous mergeable subsegment. As for why pre is set to -1 when the stack (st) is empty — this is a virtual node based on 0-based indexing, which is straightforward. I have written this kind of monotonic stack optimization before, but unfortunately, I lacked this intuition during the contest. Below is my implementation:

364164769

A similar problem is Codeforces 1072 Div3 Problem E, my implementation:

364169560

for the Div2B prob , i keep 2 pointers, le and re. i have a move variable which keeps the count of latest consecutive '?'. if i encounter 'a' i see if le or le+ move or re or re — move can help to put 'a' into og array. then update the pointers accoridngly. this approach is failing idk y can someone help https://mirror.codeforces.com/contest/2202/submission/364169367

thank u :)

Newbie here. Trying to solve 2202A — Parkour Design and figured out this is plain old maths.

The possible steps to reach (x,y) are some usages of (2,1),(3,0) and (4,-1).

Let's assume we use a,b,c times of the steps respectiely. I can write this as:

a * (2,1) + b * (3,0) + c * (4,-1) = (x,y) where a,b,c are non-negative integers (a,b,c >= 0)

Comparing each coordinate individually, we get:

2a + 3b + 4c = x  -- Equation no 1
a - c = y  -- Equation no 2

If you add equation 1 and 2, you can prove that x + y is a multiple of 3. (First deduction)

From equation 2, I get a = y + c

Using this value of a in equation 1, we get:

2 * (y + c) + 3b + 4c = x -- equation 3

Isolating b from equation 3:

b = (x - 6c - 2y)/3

Now, we know that b >= 0, Implies

x - 6c - 2y >= 0
x - 2y >= 6c

We know that c >= 0, implies x - 2y >= 0 => x >= 2y => **x/2 => y (Second deduction)**

Now, using equation 3, I can get

x - 2y = 3b + 6c

(x - 2y)/3 = b + 2c

Since b >=0 => 2c <= (x-2y)/3 

And we know c >= 0 => 0 <= c <= (x - 2y)/3 -- We use this soon

We also know from eq 2, that y + c = a and a >= 0

=> y + c >= 0
=> y >= -c

So, there are two constraints on c:

c >= -y and 0 <= c <= (x-2y)/3

=> -y <= (x - 2y)/3

Leaving this deduction for your practice. Figure it out from here onwards

Div2B Was muchh harder than Div2C

The exam setter is taking revenge on society

caseforses

F2 has more successful solutions right now in upsolving than F1...

It's surprisingly easy and clean when you look back from a nice solution, although the time limit for F2 is somewhat tight. Just consider a Young diagram given by the counts of black cells in each row, another diagram given by columns and check if they're the same but transposed. In other words store the difference of actual column-diagram and the one that would be expected by transposing the row-diagram, check if this difference is nothing. Since a query is adding 1 block to a "corner" in each, it just needs computing the size of a diagram's column (in each of the 2 diagrams from the difference) on which this block is added and updating 4 values (in a map in my implementation). One size is known directly, the other is found as the number of larger rows in a diagram = segment tree.

《The proof is left as a practice for the reader.》

My solution to Div2C1:

Let $$$nxt[i]$$$ be the next index that hasn't been removed. Inititally, $$$nxt[i]=i+1$$$. And while $$$nxt[i] \leq n$$$ and $$$a[i] = a[nxt[i]]$$$, remove the element at index $$$nxt[i]$$$ and update $$$nxt[i] = nxt[nxt[i]]$$$.

I tried to use something like a DSU, but I simplified it to this. I don't think this is a great way to solve the problem because it makes me struggle a lot with C2 later.

// https://mirror.codeforces.com/contest/2202/problem/C1

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define el '\n'
#define FNAME ""
#define ll long long
#define int long long
#define ld long double

const int MOD = 1e9 + 7;
const ll INF = 1e18 + 7;
const double EPS = 1e-9;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if (fopen(FNAME ".inp", "r"))
    {
        freopen(FNAME ".inp", "r", stdin);
        freopen(FNAME ".out", "w", stdout);
    }

    return;
}

void solve()
{
    int n;
    cin >> n;

    vector<int> a(n + 5);

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<int> nxt(n + 5);

    for (int i = 1; i <= n; ++i)
        nxt[i] = i + 1;

    int ans = n;

    for (int i = n - 1; i >= 1; --i)
    {
        while (nxt[i] <= n && a[i] + 1 == a[nxt[i]])
            ans -= 1, nxt[i] = nxt[nxt[i]];
    }

    cout << ans << el;
    return;
}

signed main()
{
    setup();

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

Div2A of this contest is harder than normal Div2 As

I might not be the first one to see this, but this is blog 151515

I can't really understand the problem statement for C1. I really don't want to look at the editorial yet.

Dynamic programming approach to Div2 B: https://mirror.codeforces.com/contest/2202/submission/364212034

I really don't understand 2201D, how to find the $$$f(a)$$$.

What I understood so far:

• if $$$(i, j, k_\text{max}) \in S(a)$$$, then so $$$(i, i + 1, k_\text{max}), (i + 1, i + 2, k_\text{max}), \dots, (j - 1, j, k_\text{max}) \in S(a)$$$ with the same value. Proof: observe that the intersection of $$$s[i:i + k_\text{max})$$$ and $$$s[j:j + k_\text{max})$$$ is non-empty, otherwise we would have $$$\text{sort}(s[i:j)) = \text{sort}(s[i + 1:j + k_\text{max}))$$$. Now let's remove the intersecion $$$s[i + 1, j)$$$, which contributes to the both strings, now we see that $$$s[i] = s[i + k_\text{max}]$$$ (as $$$s[i]$$$ should be matched by something, and it's the first not removed element of $$$s[j:j + k_\text{max})$$$). Now remove $$$s[i], s[i + k_\text{max}]$$$, now the only canditdate $$$s[i + 1]$$$ can be matched is $$$s[i + 1 + k_\text{max}]$$$ and so on. Repeting this process we find that $$$s[i:j + k_\text{max})$$$ a periodic string with the period $$$k_\max \square$$$.

Also I undestand how to find $$$k_\text{max}$$$ for each query, I need for each unique $$$x$$$ maintain the set $$$\text{set}[x] = (i \mid b[i] = x)$$$. The largest spread of such set will give me $$$k_\text{max}$$$. I also understand that maintaining the $$$\text{set}[\cdot]$$$ and the maximum spread can be done in $$$\log(n)$$$ as each time at most one set is updated.

What I don't understand, how do I recompute the set of intervals. Changing one value can change the $$$k_\text{max}$$$, so I would need to rebuild the set of intervals from beginning, potentially each operation changes $$$k_\max$$$. Could anyone elaborate please.

Hi chromate00. In 1G, are there any examples of using "rules" to construct gadgets? I literally have no idea how to set up a "rule". And according to the editorial, I should write something like a brute force(obeying "rules") to generate a gadget, right?

how to delete this comment of mine?

I have a question: why does the greedy approach in solution C fail at the third step?

Although I didn't participate in the contest, I took some time afterward to tackle the problems. I thought about Problem B for a long time, and I finally cracked it. Here's my solution:

Consider the example where T="ababa". In this case, possible strings S include: "ababa" "aabab" "aabba" "abaab"

These can be segmented as follows: "a|ba|ba" "a|ab|ab" "a|ab|ba" "a|ba|ab" From this pattern, a clear regularity emerges.

am i the only one who felt div2 C2 (the hard version) easier than the easy version? it is just straightforward 1D DP 364802836

Why is my map code not working for C1?

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

void solve()
{
    int n, ans = 0;
    cin >> n;
    map<int, int> mp;
    for (int i = 0, x; i < n; i++)
    {
        cin >> x;
        if (mp.find(x - 1) == mp.end())
        {
            ans++;
            mp.clear();
        }
        mp[x]++;
    }
    cout << ans << endl;
}

int32_t main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}