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.com/contest/1873/submission/224447874

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

For E first i solved in Python and got AC but time was around 1400s.So for the fear of hacking i converted that code to C++ and submitted it but still the first AC time is being taken in account.so is the first ac soln final in div 4?

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)

Great Editorial. Especially liked Problem G's illustration.

two liner solution for B.

(*min_element(v.begin(), v.end()))++; 
cout << accumulate(v.begin(), v.end(), 1LL, [&](int res, int x) { return (res * x);}) << '\n';

Could someone help me, why this code is getting wrong answer in problem H https://codeforces.com/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

For E , i used the value of high as x + sum of array.

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;
};

It was my best CF contest ever through my CP journey. I overcame my limit at last..

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.com/contest/1873/submission/224561489

One of those balanced contest that we wished for thank you

Can someone explain solution for problem G? Tutorial is unavailable((

can someone please explain why my code does't work for problem E, thanks!

https://codeforces.com/contest/1873/submission/224479403

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

Can anyone point out error in my code for Problem F. I am trying to do the O(n) approach. My code will return max_count as the answer.

sum=0, count=0, max_count=0;
for(int i=0;i<n-1;i++)
{
    if(h[i]%h[i+1]==0)
    {
        if((sum+a[i])<=k)
        {
            sum+=a[i];
            count++;
        }
        else
        {
            while(sum+a[i]>k)
            {
                sum-=a[i-count];
                count--;
            }
            sum+=a[i];
            count++;
        }
    }
    else
    {
        sum=0;
        count=0;
    }
    max_count=(max_count<count?count:max_count);
}

Problem C can be easily done by taking the nearest x distance and y distance (these are independent) from the 5-score zone [(4,4), (5,4), (4,5), (5,5)] (_0 based-index_). The answer is min(5-x, 5-y) per 'X' instead of hard-coding it:

#include <bits/stdc++.h>
#define ll long long
#define push push_back
#define fi first
#define se second
#define TC int t; cin >> t; for(int u=1; u<=t; u++)
using namespace std;


int main(){
   TC{
      int ans = 0;
      for(int i=0; i<10; i++){
         for(int j=0; j<10; j++){
            char c; cin >> c;
            if(c=='X'){
               /*
               (4, 4)
               (5, 4)
               (4, 5)
               (5, 5)
               */
               pair<int, int> point = make_pair(min(abs(4-i), abs(5-i)), min(abs(4-j), abs(5-j)));
               ans+=(min(abs(5-point.fi), abs(5-point.se)));
            }
         }
      }cout << ans << "\n";
   }
}

Submission: 224566541

Tutorial for G was so helpful!!!

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.

great editorial for problem 1873G - ABBC or BACB thank you :)

Can anyone tell me why my code is failing?

#define REP(i,a,b) for(ll i=a;i<b;++i)

void Cyan() {
    // Think Twice Code Once
    int n, k;
    cin >> n >> k;
    vi a(n), h(n);
    REP(i, 0, n) cin >> a[i];
    REP(i, 0, n) cin >> h[i];
    int j = 0, sum = a[0], prv = h[0], ans = 0;
    REP(i, 0, n) {
        sum += a[i];
        if (prv % h[i]) {
            j = i;
            sum = a[i];
            prv = h[i];
        }
        while (sum > k) {
            sum -= a[j++];
        }
        ans = max(ans, i - j + 1);
        prv = h[i];
    }
    cout << ans << endl;
}

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.

Here's my simple O(n) approach using sliding window on F — Money Trees @mesanu :

224470856

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

H was beauty I was played in B ;-;, although i observed quickly that answer is always incrementing the smallest element but i wasnt able to prove it at the moment. What is the proof tho?

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.com/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.

A is a pulchritudinous problem. I solved it with Bogosort!

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

Yesterday i submit solution of F problem. It gave me AC. I had 6 solved problems and 340 penalty. Now i view i solved 5 problems with 142 penalty. But today when I got the rating I saw that my solution to problem F gave TLE. Is it fair?

thanks for editorial,thanks for doing div 4.

I applied sliding window in F but getting wrong answer. Can anyone help

while(t--){
    ll n, k;
    cin>>n>>k;

    vector<ll> v(n), h(n);

    for(int i=0; i<n; i++) cin>>v[i];
    for(int i=0; i<n; i++) cin>>h[i]; 


    ll l=0, r=1;
    ll cnt=0, tot=v[0];
    ll ans=0;

    if(n==1){
        if(v[0]<=k) cout<<1<<endl;
        else cout<<0<<endl;
    }

    else{
    while(r<n){
        if(h[r-1]%h[r]==0){
            tot+=v[r];    
            if(tot<=k) ans=max(ans, r-l+1);
        } 
        else{
            while(l!=r){
                tot-=v[l];
                l++;
            }
            tot=v[l];
        }

        while(tot>k){
            tot-=v[l];
            l++;
        }
        ans=max(ans, r-l+1);
        r++; 
    }

    cout<<ans<<endl;
    }
}

224598998 224600540 May I ask why the first submission cannot solve the problem while the second one can? The only difference between them is:

while (l < r) {
        int mid = (l + r + 1) >> 1, flag = 0;
        for (int i = x; i + mid - 1 <= y; i++)
            if ((LL)s[i + mid - 1] - s[i - 1] <= k) {
                flag = 1;
                break;
            }
        if (flag) l = mid;
        else r = mid - 1;
    }

while (l <= r) {
        int mid = (l + r) >> 1, flag = 0;
        for (int i = x; i + mid - 1 <= y; i++)
            if ((LL)s[i + mid - 1] - s[i - 1] <= k) {
                flag = 1;
                break;
            }
        if (flag) l = mid + 1;
        else r = mid - 1;
    }

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!

for problem A, you can check if any of the letter is in the right position then you can return "Yes" else "No".

Finally I became Pupil after a one year of trying. Since i acheived my goal. I am done with these stupid contests. since anyway I feel there is no much difference anyway

why are they not rating the questions in the recent contests?

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

Could someone can take a look at my F: 224638271, thx. I look for all the continuous intervals that meet the conditions, then use binary search on the length of intervals, but got wa2.

1873F — Money Trees Sliding window approach

if current tree high is not divisible then we re-init it, also update ans, else try to reduce the window to match the condition.

void f() {
    int t, n, k; cin >> t;
    while(t--) {
        cin >> n >> k;
        vector<int> fruits(n), treeHigh(n);
        for(int &x: fruits) cin >> x;
        for(int &x: treeHigh) cin >> x;
        int totalFruits = fruits[0];
        int left = 0, ans = fruits[0] <= k;
        for(int i = 1; i < n; i++) {

            if(treeHigh[i-1] % treeHigh[i] != 0) {
                totalFruits = fruits[i];
                left = i;
                ans = max(ans, (totalFruits <= k) ? 1: 0);
            }else {
                totalFruits += fruits[i];
                while(totalFruits > k) {
                    totalFruits -= fruits[left++];
                }
                ans = max(ans, i - left + 1);
            }
        }
        cout << ans << "\n";
    }
}

My solution for G.

The logic was intuitive. Going left to right, it doesn't make sense to use operation 1 the operation 2 and then operation 1 again(try simulating it through the test cases given). Our best possible score is achieved through a series of operation 1s followed by a series of operation 2s.

how is the time complexity in the 1873C — Target Practice is O(1) when you have 2 nested for loops iterating the input?

Problem H was as easy as idea to solve was as much large implementation for me.

can anyone tell me where my code fails

https://codeforces.com/contest/1873/submission/224537788

Here I simply find the nodes which are part of cycle and run a disktra to find whether b can reach any part of cycle before a if true then return 1 else return 0.

Solved Actually my code for finding cycles nodes is not correct.

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

Awesome round. Enjoyed how the editorial was written.

F can be done in O(n) using Sliding Window. Much more intuitive too imo.

https://codeforces.com/contest/1873/submission/224490319

why is my F failing i just updated len and the sum in one execution rather than using a binary search approach??

I tried solving "ABBC or BACB" problem with this code but I can't find the reason why my code is not working for 2 test cases ???(given below is my code) signed main() {
ios::sync_with_stdio(false); cin.tie(NULL); int size; cin>>size; while(size--) { string s; cin>>s; int n = s.length(); bool check=false; if(s[0]=='B' || s[n-1]=='B') check=true;

int acount = 0;
       int mn = n;
       for(int i=0;i<n;i++)
       {
           int end = i;
           if(s[i]=='A')
           {
               acount++;
               while(end<n && s[end]!='B')
               {
                    end++;
               }
           }
           int temp = end-i;
           mn = min(mn,temp);

           if(s[i]=='B')
           {
               if(i+1<n && s[i+1]=='B')
                check=true;
           }
       }

       int fck = 0;
       if(check)
        cout<<acount<<endl;
       else
       {
          cout<<max(acount-mn,fck)<<endl;
       }
    }
    return 0;

}

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

Awesome contest with awesome editorial !! Really had a great time solving this amazing problems

G can also be done using dp. for every 'B' we store the count of A's on its left and right and then we try every possible way of using those A's.. 225181389

Can't we do problem F in O(n)?

simplest solution of G ~~~~~

string s; cin >> s;
int mn = 1e9, cnt = 0, a = 0;

for(int i = 0; i < s.size(); i++) {
    if(s[i] == 'A') cnt++, a++;
    else {
       mn = min(mn, cnt); cnt = 0;
    }
}
mn = min(mn, cnt);
cout << a - mn;

~~~~~

I have implemented Problem H a little bit differently than the editorial if you are interested then check out my code.

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

int n, a, b;
vector<vector<int>> g;
vector<int> vis, parent, cycle;
bool is_cycle = 0;

void dfs(int node, int par) {
    vis[node] = 1;
    parent[node] = par;
    for (auto v : g[node]) {
        if (!vis[v]) {
            dfs(v, node);
        } else {
            if (par != v) {
                if (!is_cycle) {
                    int temp = node;
                    while (temp != v) {
                        cycle.push_back(temp);
                        temp = parent[temp];
                    }
                    cycle.push_back(temp);
                }
                is_cycle = 1;
            }
        }
    }
}

pair<int, int> mssp() {
    vector<int> dis(n + 1, 1e9);
    queue<int> q;
    for (auto x : cycle) {
        q.push(x);
        dis[x] = 0;
    }
    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (auto v : g[node]) {
            if (dis[v] == 1e9) {
                dis[v] = dis[node] + 1;
                q.push(v);
            }
        }
    }
    return make_pair(dis[a], dis[b]);
}

int sssp() {
    vector<int> dis(n + 1, 1e9);
    queue<int> q;
    q.push(a);
    dis[a] = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (auto v : g[node]) {
            if (dis[v] == 1e9) {
                dis[v] = dis[node] + 1;
                q.push(v);
            }
        }
    }
    return dis[b];
}

void solution() {
    cin >> n >> a >> b;
    g.clear(); cycle.clear(); is_cycle = 0;
    g.resize(n + 1);
    vis.assign(n + 1, 0);
    parent.assign(n + 1, 0);
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if (a == b) {
        cout << "No" << endl;
        return;
    }
    dfs(1, 0);
    auto [adis, bdis] = mssp();
    if (bdis == 0 || adis > bdis) {
        cout << "Yes" << endl;
    } else {
        int d1 = bdis;
        int d2 = sssp() - d1;
        if (d1 < d2) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int __; cin >> __;
    while (__--) {
        solution();
    }
    return 0;
}

for F this solution is somewhat dp if you prefer. My submission: 225711679 The idea is to first find each maximal segment. then check maximum size we can get starting from any i in that seg. in order to pass TL remember sum and where it ended for previous starting point and start from there and not from i.

Can someone help me understand why my solution for F gives WA judgement: https://codeforces.com/contest/1873/submission/225741996

For money trees problem my solution is giving TLE only if I use sort else without sort it gets accepted can anyone explain why sort here is giving TLE FOR INFO: if i remove sort and optimization part the solution gets accepted include <bits/stdc++.h> using namespace std; int mm=0; define ll long long void solving(void); int main() {

ll t;
cin >> t;
while (t--)
{
    solving();
}

} void solving(void) {

ll n, k;
cin >> n >> k;
ll a[n], h[n];
ll l = -1, e = -1;

vector<pair<ll, pair<ll, ll>>> v; // this will store <length of subarray satisfying the divisibility rule<e means starting,l means ending of subarray >> elements

for (ll i = 0; i < n; i++)
{
    cin >> a[i];
}

for (ll i = 0; i < n; i++)
{
    cin >> h[i];
}

for (ll i = n - 1; i >= 0; i--)     //this for loop makes vector v declared above
{
    //  cout<<e<<l<<endl;
    if (e == -1 && l == -1)
    {
        e = i; // first true
        l = e;
        continue;
    }
    if (h[i] % h[i + 1] == 0)        
    {

        e = i;
    }
    else
    {
        v.push_back({(l - e + 1), {e, l}});
        e = i;
        l = e;
    }
}

v.push_back({(l - e + 1), {e, l}}); // e means starting and l means ending

ll sum = 0;
ll lenght = 0;




sort(v.begin(), v.end(), [](auto &a, auto &b)
  { if(a.first >= b.first) return true; else return false; });   // sorting according to subarray length


ll maxi = 0;
ll ans = 0, mid = 0;
mm=0;
for (auto &i : v)    //for each subarray
{

if (maxi >= abs((i.second.second — i.second.first) + 1)) // optimization only if vector is sorted in decreasing order of subarray length break;

ll start = i.second.first;   
    ll end = i.second.second;    
    ans = 0;
    ll sum=0;
    int t=start;

    for (int h = start; h <=end ; h++)   // h means head and t tail of sliding window
    {  

       sum+=a[h];

       while(sum>k){

        sum-=a[t];
        t++;


       }


       ans=h-t+1;

      maxi=max(maxi,ans);
    }


    maxi = max(maxi, ans);
}

    cout << maxi<<endl;

}

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.com/contest/1873/submission/226134316

226968842

Can someone help me debug this code for problem F . I can't seem to find on which test case it fails.

Thanks in Advance :)