Problem H was awesome!

You can avoid hard coding in problem C.

Value of cell $$$(i,j)$$$ is $$$\min(i,j,11-i,11-j)$$$.

problem E and F gives me some real stress but overall the contest was fun!!

Problem G's walk-through was so clear I could understand the concept in a split second!

For C, I asked chatGPT to provide me with a program to generate the matrix and then I used it. Happy to get skipped as the rating doesn't matter to me.

Can someone explain why in problem B, it's optimal to increase the smallest digit ?

$$$E$$$ can be solved in $$$O(n \log(n))$$$ and $$$F$$$ can be solved in $$$O(n)$$$.

For $$$E$$$, first sort the array $$$a$$$. The optimal value of $$$h$$$ is $$$\max_i(v_i)$$$ where $$$v_i=\min(a_{i+1}-1, \left \lfloor (x+PrefixSum([a_1:a_i]))/i \rfloor \right)$$$ if $$$v_i \geq a_i$$$ and $$$v_i=0$$$ otherwise (set $$$a_{n+1}$$$ as $$$\infty$$$ or handle the case $$$i=n$$$ separately).

$$$F$$$ can be done by sliding windows method.

Can someone explain why this code doesn't work for Problem E. I understood immediately that Binary Search would be used but my code fails on TestCase-7. TIA

https://codeforces.net/contest/1873/submission/224447874

For problem F: Given, (l≤i<r). I don't understand why l and r can be same.

Video Editorial For Problem A to H

In f, we can use two pointers instead of binary search, so it can be reduced to O(2*n)

Could someone help me, why this code is getting wrong answer in problem H https://codeforces.net/contest/1873/submission/224501501

For Problem F,

Can someone explain if I take l = 2 and r = 2 as well, then how is 2<=2<2 ?

I found an exactly same problem as problem H (Mad City)

https://github.com/all1m-algorithm-study/uospc2021/blob/main/problems/Police_Thief/statements.md

This is from an intra-college contest held by University of Seoul in 2021.

There is no English statement, but if you use a translator you'll notice there are few differences.

Even the examples given in the descriptions are the same.

Thanks for a good contest, although i joined late the experience was enjoable

Problem E can be solved in $$$\mathcal{O}(n\log n + \log n\log (a_i+x))$$$.

First, we notice that the permutation of $$$a[i]$$$ does not matter at all.

So we can sort(a,a+n) first, and then when we want to calculate how much water we use when the height is $$$h$$$, we can use idx=lower_bound(a,a+n,h)-a, and then the water we use nowuse=idx*mid-s[idx-1].

$$$s[i]$$$ is the prefix of sorted $$$a[i]$$$, i from 0 to n-1. We can use this because for $$$idx\le i\le n-1$$$, we have $$$a[i]>h$$$, so the use of $$$i$$$ is $$$0$$$.

By using this way, we can avoid calculating max(0,...) with n times.

Since sort takes $$$\mathcal{O}(n\log n)$$$ and in every check in binary search we use lower_bound which is $$$\mathcal{O}(\log n)$$$, we have $$$\mathcal{O}(n\log n + \log n\log (a_i+x))$$$ in all.

In problem c:

auto position = [](int i, int j)->int 
{
    int output;
    if((i+j)<=9){
        output = min(i, j);
    }else{
        output = (9-max(i, j));
    }
    output++;
    return output;
};

for problem G, as mentioned in the tutorial, we can see the problem as each B choose one direction(left or right) to eat the A's, so we can use dp.

dp[i][0] means if the i-th B choose to go left, the maximum A's that the 1-th, 2-th, ..., i-th B can eat. dp[i][1] is similar, it means the i-th B choose to go right.

therefore, we can get the transition equation: dp[i][0] = dp[i-1][0] + i-th B's position — (i-1)-th B's position — 1 (because if the (i-1)-th B go right and the i-th B wants to left, it will have conflict, so (i-1)-th B can only choose to go left) dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + (i+1)-th B's position — i-th B's position (if i-th B wants to go right, we don't need to care about the (i-1)-th B's choice)

and here is the implementation https://codeforces.net/contest/1873/submission/224561489

please can someone suggests similar problems to F in which you do binary search on the answer plus some other computations?

Video Editorial (A-H) LINK TO YOUTUBE EDITORIAL

Not getting how to solve F problem, can anyone explain the intuition?

I request Div4's authors to make future rounds a little more challenging. This was on the easier side.

For the last problem, I didn't notice the number of edges is n, I skipped the first line immediately assuming it just says there are n nodes. Then I thought maybe around 20 mins on this and was amazed how people can solve it while I was trying to prove it is a hard problem. It was like finding a bunch of induced cycles, which isn't an easy problem in general graphs. I can't blame that it wasn't explicit enough, since if I was reading the input format or the first line, it was clear there are n edges.

How to understand "Because we have a tree with an additional edge, our graph has exactly one cycle."? I think we are only gived a simple graph and there may be more cycle.

In hindsight my bridge-finding algorithm seems like an overkill :) 224589798

Can somebody explain Problem F using BS Please.

Can some please explain why I got wrong answer when the value assigned to 'hi' was 1e14 or 1e18?

https://codeforces.net/contest/1873/submission/224393419

This resulted in wrong answer in test case 4 but was accepted when I updated the value of 'hi' to 1e10.

Thanks.

Why in problem H, in test 2, in test case 3, the answer is NO? Test case: 1 18 7 15 14 6 14 8 6 18 4 13 3 12 11 9 14 2 14 17 14 11 11 5 1 7 16 11 15 11 14 18 1 13 10 8 13 14 12 6 UPD: Sorry I missed one test case, the answer for test case above was YES

⠀

You can also watch the video editorials I made on the problems E , F, G and H

Enjoy watching and let me know what you think about them!

H problem Clearing the array vis[N] is the most important !

Problem H Idea is simple but implementation bit complex.

Problem F can also be solved using Binary Search ... My code

Can someone explain the second last sample test case for problem H?

8 5 3

8 3 5 1 2 6 6 8 1 2 4 8 5 7 6 7

I think Valeriu can always escape Marcel by choosing node 3 or 4, whichever one Marcel doesn't choose.

G is the hardest problem I think, but solving it was gratifying

for H,what if there are 2 entrances of the circle?

I absolutely loved the editorial for problem G! Wow! It was so fun to read, and so easy to understand! It would be amazing if all editorials were like this: being longer is not necessarily bad if a longer editorial is better at explaining the solution than a shorter one.

What exactly I am doing wrong here in Problem E. I solved this on a pen and paper, and seems to me that the calculations are correct. I am first sorting the heights and then start filling up from the leftmost side of the tank. My submission My solution

why the answer of test case "ABAAB" in problem G is 2

Hey, Can anyone help me with this runtime error? I have tried debugging and wasted a lot of time. Any help is appreciated.

https://codeforces.net/contest/1873/submission/226134316

227178473 my dp with memoisation solution,store every preceding and proceeding B's and then use dp to choose the best possible combinations(note that:once u eat all the A's from right,u cant eat any left A's for all the B's proceeding that B).

Problem F can also be solved in O(n) using sliding window approach. It is the modified version of the problem of Longest subarray having sum of elements atmost K. My submission — https://codeforces.net/contest/1873/submission/233766852

What does the phrase "Notice the order of operations doesn't matter." precisely means for the problem D

The tutorial of problem G is beautiful, it was very informative for me to learn how to approach a problem :)

243211598 i dont understand why counting sum is giving overflow on problem E.

Overall Good contest, No offense but I don't think problem G was kind of an Ad hoc problem. I solved it using DP. Later came to see your approach and the explanation is amazing.

Problem C can be solved using a triple for loop: since every "square" has a delta with the outer one of 1, that is constant, we can iterate trough the whole sub-square adding 1 to the final answer each time we find a 'X'. In this way, we will find an 'X' as many time as it worths.

int ans = 0;
for (int x=0; x<5; ++x)
    for (int i = x; i < 10-x; ++i)
        for (int j = x; j < 10-x; ++j)
            if (grid[i][j] == 'X') ++ans;

My sumbission as reference: 247543890

ik I'm late but in E, instead of computing value of 'tot' for every height(mid), why not just check if the height is greater than the height of longest coral, if it is, then instead of looping through all coral heights to calculate 'tot' we can calculate it by subtracting total volume of coral from total volume of aquarium. Total volume can be precomputed while taking input of coral heights.

1873C — Target Practice (alternative way to it may be a bit convenient if we don't want to write that number matrix)

// By: TESFAMICHAEL TAFERE

include <bits/stdc++.h>

using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int t; cin >> t; while (t--) { char s[10][10];

int count = 0;
for (int i = 0; i < 10; i++)
{
     for (int j = 0; j < 10; j++)
    {
        cin >> s[i][j];
      if (s[i][j] == 'X')
      { 
        if (i == 0 || 10 - 1 == i || j == 0 || 10 - 1 == j)
             count++;
        else if (i == 1 || 10 - 2 == i || j == 1 || 10 - 2 == j)
             count+=2;
         else if ((i == 2 || 10 - 3 == i) || j == 2 || 10 - 3 == j)
             count+=3;
         else if (i == 3 || 10 - 4 == i || j == 3 || 10 - 4 == j)
             count+=4;
         else 
             count+=5;
      } 
   }
}
cout << count << "\n";

}

return 0;

}

Problem G becomes way easy you just have to find smallest consecutive A substring . The ans = Number of A(s) — Length of smallest consecutive A(s) substring . Submission = https://codeforces.net/contest/1873/submission/264596469

Problem G was very good for the beginners and thanks for the lovely Editorial .

But the given implementation part (code) is bit complex and not easy to understand. I think I have written a code which is very easy to understand code out of all the solutions I've watched till now

Here's my submission link for those who are struggling in the implementation part : https://codeforces.net/contest/1873/submission/265911111

Approach is simple :

1. If the string start with 'B' or ends with 'B' or if it has any two consecutive 'B' in it , then the answer is simply the sum of all A's in the string.

2. Otherwise we have to eat the A's where it occurs more in a chunk , hence the chunk with minimum no. of A's would be ignore , so in this case we can simply print, Sum of all A's — (minimum number of A's in any chunk/group);

#include <bits/stdc++.h>
#include <algorithm>
#include <limits>
#include <cstring>

using namespace std;

#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(NULL);
#define chaki cout.tie(NULL);

#define ll long long
#define int ll
#define ld long double
#define ull unsigned long long
const ld pi = 3.141592653589793238;
const ll INF = LONG_LONG_MAX;
const ll MIN = LONG_LONG_MIN;
const ll mod = 1e9 + 7;

typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef unordered_map<ll, ll> umll;
typedef map<ll, ll> mll;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define vv(T) vector<vector<T>>
#define maxhp(T) priority_queue<T>
#define minhp(T) priority_queue<T, vector<T>, greater<T>>
#define mem(n, i) memset(n, i, sizeof n)
#define p(A, B) pair<A, B>

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return (a / gcd(a, b) * b); }
ll moduloMultiplication(ll a, ll b, ll mod)
{
    ll res = 0;
    a %= mod;
    while (b)
    {
        if (b & 1)
            res = (res + a) % mod;
        b >>= 1;
    }
    return res;
}
ll powermod(ll x, ll y, ll p)
{
    ll res = 1;
    x = x % p;
    if (x == 0)
        return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

bool sorta(const pair<int, int> &a, const pair<int, int> &b) { return (a.second < b.second); }
bool sortd(const pair<int, int> &a, const pair<int, int> &b) { return (a.second > b.second); }

bool isPrime(ll n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}
bool isPowerOfTwo(int n)
{
    if (n == 0)
        return false;
    return (ceil(log2(n)) == floor(log2(n)));
}
bool isPerfectSquare(ll x)
{
    if (x >= 0)
    {
        ll sr = sqrt(x);
        return (sr * sr == x);
    }
    return false;
}

#define ff first
#define ss second
#define mp make_pair
#define pb push_back

#define ps(x, y) fixed << setprecision(y) << x;

#define vi vector<int>
#define vs vector<string>
#define vvi vector<vector<int>>
#define vvs vector<vector<string>>
#define vpi vector<pair<int, int>>

#define i1(A, a) \
    A a;         \
    cin >> a;
#define i2(A, a, b) \
    A a, b;         \
    cin >> a >> b;
#define i3(A, a, b, c) \
    A a, b, c;         \
    cin >> a >> b >> c;
#define i4(A, a, b, c, d) \
    A a, b, c, d;         \
    cin >> a >> b >> c >> d;
#define i5(A, a, b, c, d, e) \
    A a, b, c, d, e;         \
    cin >> a >> b >> c >> d >> e;
#define i6(A, a, b, c, d, e, f) \
    A a, b, c, d, e, f;         \
    cin >> a >> b >> c >> d >> e >> f;

// #define Fl(i, n) for (ll i = 0; i < n; i++)
// #define Bl(i, n) for (ll i = n; i >= 0; i--)
#define fl(i, k, n) for (ll i = k; i < n; i++)
#define bl(i, k, n) for (ll i = n; i >= k; i--)
#define yes cout << "yes" << "\n";
#define minus1 cout << "-1" << endl;
#define no cout << "no" << "\n";
#define it(v) v.begin(), v.end()
#define itr(v) v.rbegin(), v.rend()
#define rit(v) v.end(), v.begin()

#define o(x) cout << (x) << " ";
#define o2(x, y) cout << (x) << " " << (y) << " ";
#define o3(x, y, z) cout << (x) << " " << (y) << " " << (z) << " ";

#define oe(x) cout << (x) << endl;
#define oe2(x, y) cout << (x) << " " << (y) << endl;
#define oe3(x, y, z) cout << (x) << " " << (y) << " " << (z) << endl;
bool check(vector<int> &a, vector<int> &h, int key, int k)
{
    int left = 0;
    int right = 0;
    int temp = k;
    while (right < h.size())
    {
        if (right - left >= key && k >= 0)
        {
            return true;
        }
        if (right == h.size() - 1)
        {
            k -= a[right];
            right++;
            // oe(k);
            if (right - left >= key && k >= 0)
            {
                return true;
            }
            else
                break;
        }
        else if (k < 0)
        {
            k += a[left];
            left++;
        }
        else if (h[right] % h[right + 1] == 0)
        {
            k -= a[right];
            right++;
        }
        else if (k - a[right] >= 0)
        {
            k -= a[right];
            right++;
            if (right - left >= key && k >= 0)
            {
                return true;
            }
            else
            {
                k = temp;
                left = right;
            }
        }
        else
        {
            k = temp;
            right++;
            left = right;
        }
        // oe(k);
    }
    return false;
}
void solve()
{
    i2(int, n, k);
    vi a(n);
    vi h(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
    }

    int l = 0;
    int r = n;
    int ans = 0;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
        // cout<<"mid: "<<mid<<endl;
        if (check(a, h, mid, k))
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    oe(ans);
}

signed main()
{

    Code By chaki

        ll tt;
    cin >> tt;
    while (tt--)
    {
        solve();
    }
}

Problem E : Can anyone help to find an error?!

dp soultion for G :

284204976