Codeforces Round #898 (Div. 4) Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Thank you for participating!

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
string alph = "abc";
 
void solve() {
	string s;
	cin >> s;
	int cnt = 0;
	for (int i = 0; i < 3; i++) {
		cnt += (s[i] != alph[i]);
	}
	cout << (cnt <= 2 ? "YES\n" : "NO\n");
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1873B - Хороший ребенок

Idea: mesanu

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    int ans = 1;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    a[0]++;
    for(int i = 0; i < n; i++)
    {
        ans*=a[i];
    }
    cout << ans << endl;
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

1873C - Стрельба по мишени

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
int score[10][10] = {
	{1,1,1,1,1,1,1,1,1,1},
	{1,2,2,2,2,2,2,2,2,1},
	{1,2,3,3,3,3,3,3,2,1},
	{1,2,3,4,4,4,4,3,2,1},
	{1,2,3,4,5,5,4,3,2,1},
	{1,2,3,4,5,5,4,3,2,1},
	{1,2,3,4,4,4,4,3,2,1},
	{1,2,3,3,3,3,3,3,2,1},
	{1,2,2,2,2,2,2,2,2,1},
	{1,1,1,1,1,1,1,1,1,1}
};
 
void solve() {
	int ans = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			char c;
			cin >> c;
			if (c == 'X') {ans += score[i][j];}
		}
	}
	cout << ans << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1873D - 1D Ластик

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	int res = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'B') {
			res++; i += k - 1;
		}
	}
	cout << res << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1873E - Построение аквариума

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int n;
	long long x;
	cin >> n >> x;
	long long a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	long long lo = 0, hi = 2'000'000'007;
	while (lo < hi) {
		long long mid = lo + (hi - lo + 1) / 2;
		long long tot = 0;
		for (int i = 0; i < n; i++) {
			tot += max(mid - a[i], 0LL);
		}
		if (tot <= x) {lo = mid;} 
		else {hi = mid - 1;}
	}
	cout << lo << endl;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1873F - Деревья с деньгами

Idea: mesanu

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
const int N = 200'000;
 
int n, k;
int a[N+5], h[N+5], pref[N+5], length[N+5];
 
bool get(int dist)
{
    bool found = false;
    for(int i = 0; i < n-dist+1; i++)
    {
        if(length[i] < dist){continue;}
        int sum = pref[i+dist]-pref[i];
        if(sum <= k)
        {
            found = true;
            break;
        }
    }
    return found;
}
 
void solve()
{
    pref[0] = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        pref[i+1] = pref[i]+a[i];
    }
    for(int i = 0; i < n; i++)
    {
        cin >> h[i];
    }
    length[n-1] = 1;
    for(int i = n-2; i >= 0; i--)
    {
        if(h[i]%h[i+1] == 0)
        {
            length[i] = length[i+1]+1;
        }
        else
        {
            length[i] = 1;
        }
    }
    int l = 1, r = N;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(get(mid))
        {
            l = mid+1;
        }
        else
        {
            r = mid-1;
        }
    }
    cout << r << endl;
}
 
int main() {
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

1873G - ABBC или BACB

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	string s;
	cin >> s;
	int n = s.length(), cnt = 0;
	bool all = (s[0] == 'B' || s[n - 1] == 'B');
	for (int i = 0; i < n - 1; i++) {
		if (s[i] == s[i + 1] && s[i] == 'B') {all = true;}
	}
	vector<int> lens;
	int curr = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'A') {curr++;}
		else {
			if (curr != 0) {lens.push_back(curr);}
			curr = 0;
		}
	}
	if (curr != 0) {lens.push_back(curr);}
	sort(lens.begin(), lens.end());
	
	if (lens.empty()) {cout << 0 << '\n'; return;}
	
	int tot = 0;
	if (all) {tot += lens[0];}
	for (int i = 1; i < lens.size(); i++) {
		tot += lens[i];
	}
	cout << tot << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1873H - Безумный город

Idea: mesanu

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200005;
 
vector<int> adj[N];
vector<bool> vis(N);
 
int entry_node = -1;
vector<int> path;
 
bool dfs1(int u, int p)
{
    vis[u] = true;
    for(auto v : adj[u])
    {
        if(v != p && vis[v])
        {
            entry_node = v;
            return true;
        }
        else if(v != p && !vis[v])
        {
            if(dfs1(v, u))
            {
                return true;
            }
        }
    }
    return false;
}
 
int dfs2(int u)
{
    vis[u] = true;
    int distbruh = N;
    for(auto v : adj[u])
    {
        if(v == entry_node)
        {
            return 1;
        }
        if(!vis[v])
        {
            int dist = dfs2(v)+1;
            distbruh = min(dist, distbruh);
        }
    }
    return distbruh;
}
 
void solve()
{
    int n, a, b;
    cin >> n >> a >> b;
    for(int i = 0; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(b, -1);
    vis.assign(n+1, false);
    int distMarcel = N, distValeriu = 0;
    if(entry_node == a)
    {
        distMarcel = 0;
    }
    else
    {
        distMarcel = dfs2(a);
    }
    vis.assign(n+1, false);
    if(entry_node == b)
    {
        distValeriu = 0;
    }
    else
    {
        distValeriu = dfs2(b);
    }
    if(distValeriu < distMarcel)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    for(int i = 1; i <= n; i++)
    {
        adj[i].clear();
        vis[i] = false;
    }
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

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;

}

#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(); } }

Comments (121)

Show archived | Write comment?

VMaksimoski008

15 months ago, # |

Problem H was awesome!

→ Reply

AksLolCoding

15 months ago, # ^ |

its nice but pretty easy for an H

pmaddineedi

4 months ago, # ^ |

I am very late, but after all: it is Div. 4 (everything is meant to be slightly easier)

vikram_8009

11 months ago, # ^ |

When both Valeriu and Marcel would be in a cycle what would be needed to check the reaching time to the entry node? if Valeriu were in a cycle answer should be "NO". but here we are checking the reaching time to the entry node.

priy1712

if they were both in a cycle i think the answer would be yes since V would always have 2 options to choose from , its the node out of the cycle where he could be caught.

abaxes_004

7 months ago, # ^ |

← Rev. 4 →

This Case is considered in the first test case itself. Previously I just read the question, so I thought they might have missed it.

satyam343

+64

You can avoid hard coding in problem C.

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

amanrao

← Rev. 2 →

-42

dislike me >_<

ibrm

are you serious ?

Karilli

+11

Another approach is to take min Chebyshev distance from (i, j) to the 4 middle squares.

SeaSeal

Thank you for the formula. Could you please provide a more general formula that works for concentric matrices where the values decrease from the outermost layer to the inner layers? ("Do you think this formula consistently works for matrices where the values increase from the outermost layer to the inner layer min(i,j,n+1−i,n+1−j)) and thanks.

CedeaT0

yes

Zeez0

6 months ago, # ^ |

I want to know how do you come up with solutions like this??

DracoVault

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

BlackHole

Similar problem like E https://mirror.codeforces.com/contest/1840/problem/D.

_Spongey

"For more stress"

K_StA

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

ninja_ankit

totally agreed Want more this kind of tutorial in future #flamestrom

tautology

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.

using chatGPT is legal tho

avighnakc

That is smart, wish I'd have thought of that

619

13 months ago, # ^ |

hello can you explain why direction of approach doesn't matter in B question like any proof if possible?

What do you mean?

B mei jaise greedy approach laga rhe hai na left to right jaate hue, so I'm asking right to left jaane pe same answer aayega and Better answer nahi aayega iski kya guarentee hai. I would love a proof of why Direction of approach does not matter.

Are you talking about this contest’s B? My solution was just brute force where I tried everything. I reset the variable after each iteration.

oh i'm really sorry i meant D (1d eraser)

Well if you’re convinced that it works backward you can think of reversing the string and doing it backwards as the same thing as doing it forwards

no i am not convinced that it works forward

according to me the ans should be min(forward approach, back approach)

greedy gives me the idea to approach from one single direction but how can you say that both directions will give same answer

here your reversing logic doesn't apply as say i claim forward approach takes 3 operation and backward approach takes 2 operations then on reversing also answer will be same i agree(2) but this time it will be from forward approach

how can you claim that only by checking from one direction you will get a answer same as backward approach

Oh, I see.

Well, let's try to 'prove' that the forward approach always gives an optimal answer.

What my code is doing is it's going from 0 to n and checking if each character needs to be converted or not. If it does, start a window, otherwise move on to the next index. Notice that when we move on to the next index, we'll never come back to the previous one.

So why is this important? That means that when we see an element that needs to be converted, we have to start a window. You might say that there are multiple ways to start a window (for example if we want to convert i+1, we could start a window of size k>=2 at index i) so that an index is converted, but the most optimal way will always be when it's started at the index that needs to be converted, since that way more indices ahead can be affected.

If you're convinced that the forward approach is correct, you can see why the backward approach will also be correct from my above reply, thus showing that both approaches will give the same answer.

OmkarC

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

Devilzone_12

yes because if we notice that the ratio change of x+1/x (x is smallest digit) is large as compare to bigger digits so thats why it always gives ans..

CP_Sucks

if you add 1 to smaller number then you gain original product + (original — small). But if you add 1 to any other than smaller you gain -> Original product + (original — some other which is not smallest) . So first case will always be bigger

nicio9

Say you have (3,3,2,3):

Let's pretend you need to find the largest possible product with all these elements except one.

This is obviously (3*3*3), as 2 is smaller than 3, and (3*3*2)<(3*3*3). Now we know that the excluded value is 2.

Now that we've got (3*3*3) as the largest product excluding the smallest value, we can add 1 to the excluded value, and now we've increased the product by (3*3*3).

We went from (3*3*3)*2 to (3*3*3)*3.

dzhi

Based on AM-GM Inequality, a set of numbers with specific sum will have largest product if all the numbers are equal. Increasing the smallest digit will make these digits be closers to their average. It is not a solid proof but rather an intuitive way to quickly realize it.

chayleaf

assume x=a*b*c*d

then (a+1)*b*c*d-x = b*c*d

basically, increasing a single number by one increases the answer by the product of all other numbers, so it's best if b,c,d are the largest possible, which means a is the smallest possible

Non-origination

← Rev. 5 →

$$$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.

don't you use sort in E?, which is already O(n log(n))

Orifkhon

You can use binary search for finding solution. l = 0, r = 1e9

Ehsan

but r = 1e9 get wrong answer. must use r = 2^31 -1 or r = 2e9 + 7. i used 1e14, 1e15 and 1e18 then i got wrong answer. it was so boring :>

MjdMSalloum

Why ?

Its work fine for me , No need for this values .

My submission 224465049

And I think Binary Search is more simple than the formula and easier to work with for beginners.

I don't know. maybe the problem was from another thing. however this is my code who got wrong answer : 224488235

Mid is Overflow

1e18 / 2 = 5e17 which cann't stored in an int

oh really? you are kidding! I knew that. i used define for contest who i don't forget using long long

#define int long long

rajnishism

9 months ago, # ^ |

F Can be done in O(N)

using two pointer one on the current node and other at the first element of contigous part (which satisfy the condition).

254795451

Lamentis

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

whopassby

i got the same problem.i even doubt that this problem cant be solved by binary search

pppzz

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

Author's right answer is 1 in this test: 2 15 9 6 1 3 .

However, for 1<=i<r we can't find h[i] is divisible h[i + 1]. So I think this answer is 0.

flamestorm

Please read the blog https://mirror.codeforces.com/blog/entry/120638.

SystemTesting

Didn't get the idea quite right, still cant figure it out how l and r can be equal, had to go through such a pain for this :)

Read the problem carefully, it says h[i] must be divisible by h[i+1] for each l<=i<r. Note how if l=r, no i's are checked.

manitianajay45

Video Editorial For Problem A to H

tanishq2507

please make vedio editorials for atcoder regular contest.There are no english vedio editorial for that.

meliodasssf

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

AmrAhmed110

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

coderdhanraj

It fails for the below input

Aakash19971

For Problem F,

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

1xx55

pick l=2 and r=2 , you will find that no such i satistied l<=i< r . That means you don't need to check any h[i]. So you can collect fruit from a[l] to a[r] (that's a[2] actually) . The same thing works when you want to collect fruit from only one tree.

martin0327

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.

a1abay

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

CanderFlower

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.

Quark0.5

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

I use this equation : point = min(min(i,9-i),min(j,9-j)) + 1 it's the minimum distance to the edge + 1.

Njaso

← Rev. 3 →

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

javiergm06

Overkilled

dope

No.

_doomboo_

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

KINGZIE

In problem F i have first searched for a segment of divisible no.s and then i have applied sliding window technique . The time complexicity was 2.n which is actually O(n). Try this approach.

bruce_x001

Video Editorial (A-H) LINK TO YOUTUBE EDITORIAL

flat-planet

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

You can refer to : YT LINK

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

nayeem2021

That's why it's DIV4. To get more challenge you can always participate in other divisions.

saeedam

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.

Gassa

I've also read the problem like this.

In such version, we can solve it at least as follows (or maybe easier):

for each vertex, determine whether it lies on any cycle
for each vertex, find distance from Valeriu
for each vertex, find distance from Marcel
Valeriu wins if there is a vertex on a cycle that is closer to Valeriu than to Marcel

I think you are right. I thought too deep about it: I thought the winning strategy is to walk along an induced cycle, otherwise, marcel can at some point go along a chord of a cycle and catch Valeriu. Finding a winning strategy is difficult I believe, the question didn't ask for the winning strategy, though. I think the reason I've thought too much about it is that, I overlooked that every vertex that lies on a cycle, also lies on an induced cycle, so I didn't need to check if a vertex is on induced cycle, if it is on a cycle, certainly there is an induced cycle the vertex is on it. So, yes it was easier to decide if he wins but not easy to find a winning strategy.

Also one last and less important point: the approach you mentioned in general graphs could be quadratic to #vertices, so if the number of the vertices is big (like in this case), it could fail if it has too many edges (well this case didn't have that).

The first item (for each vertex, determine whether it lies on any cycle) can be performed with a single depth-first search, similar to finding articulation points or biconnected components.

Finding distances is two breadth-first searches, one from Marcel and the other from Valeriu.

So the solution is O(E) in total.

That’s correct, and O(|E|) in dense graphs could lead to O(|V|^2) and if |V| is big, like 1e5, then it will be TL. But, of course for this particular question it doesn’t happen.

When the graph is given explicitly, which is true in the majority of the problems, $$$O(|E|)$$$ is quite distinct from $$$O(|V|^2)$$$.

If we can read it, which takes $$$O(|E|)$$$ already, we can certainly work with it in $$$O(|E|)$$$ as well.

Kanna_STELLA

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.

robostac

It follows from the statement "The roads are given that it is possible to get from any building to any other building going along the roads.". This means the graph is a connected graph. A connected graph with n nodes and n-1 edges can be proven to be a tree. There is edge left over after making the tree and adding it must create a single cycle (as every node is already connected).

shikanoko_noko

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

karandh

Could you explain the idea?

If you don't understand anything just read the offical solution :))) It's much faster, simpler and more elegant.

With the given conditions, every bridge in the graph does not belong to the cycle, and thus every non-bridge belongs to the cycle. After we traverse on the graph we will find the full set of vertices that belong to the cycle. Start traversing from Valeriu's positon until you reach one that is in the cycle (possibly Valeriu's original position itself) and calculate the distance between the vertices. As the tutorial above indicates, this is Valeriu's entry to the cycle. We then calculate the distance between that entry vertice and Marcel's. The answer is No if the former distance is not smaller that the latter, or both Valeriu and Marcel share the same starting position.

For an implementation of the bridge-finding algorithm, see https://cp-algorithms.com/graph/bridge-searching.html#implementation.

shashank_008_

Can somebody explain Problem F using BS Please.

stefdasca

My video solution for F uses Binary Search and Prefix Sums.

lunaloona1111

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

https://mirror.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.

Arnur2937

Because when 1e14 or 1e18 is multiplied by 2*10^5 (maximum size of array) an overflow will occur (long long maximum value is approximately 9*1e18)

← Rev. 6 →

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

nik4o

⠀

System testing, nothing much you can do about it

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!

Sakuya_maid

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

d_sqaure

Problem H Idea is simple but implementation bit complex.

NegativeElo

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

BlueJade

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.

Akshat_Ajmera

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

At the end, you're adding x/n.. instead, you need to add x/(i+1) where i is the index of the largest coral that gets submerged. Also, you need to use a larger data type.. I modified your code.

muffin1998

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

ignored this comment

anu-

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

https://mirror.codeforces.com/contest/1873/submission/226134316

case3

In function dfs() last else block you are popping from the set without checking if it is possible to pop from the set Here is your AC code

You can always you assert to figure out the mistake in your code.

EDIT -> The word set in the first para is actually the stack you are using. I called it set as I was thinking about memory and pointers. In the last statement, "use assert"

aryxn5

14 months ago, # |

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).

copyPasteCoder

13 months ago, # |

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://mirror.codeforces.com/contest/1873/submission/233766852

pranshu_2004

12 months ago, # |

In Problem F. Money Trees can anyone tell me why my this code is not passing test case 46 of test case 2 . https://mirror.codeforces.com/contest/1873/submission/238364394

Penguin1729

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

TheEgoist

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

ln1

11 months ago, # |

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

Shailendra_Singh

10 months ago, # |

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.

whiitex

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

YogeshZT

7 months ago, # |

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.

RED_Falcon

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

ayuxh

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://mirror.codeforces.com/contest/1873/submission/264596469

VikalpShakya

6 months ago, # |

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://mirror.codeforces.com/contest/1873/submission/265911111

Approach is simple :

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.
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);

kp_s33

3 months ago, # |

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

Ahmad_Hajjouz

dp soultion for G :

284204976

mesanu's blog

include <bits/stdc++.h>