Codeforces Round #835 (Div. 4) Editorial

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

We hope you enjoyed the contest! Sorry for the late editorial.

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	cout << a[1] << '\n';	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1760B - Atilla's Favorite Problem

Idea: SlavicG

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int n; string s; cin >> n >> s;
    sort(all(s));
    cout << s.back() - 'a' + 1 << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

1760C - Advantage

Idea: Errichto

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];
        vector<int> b(a);
        sort(b.begin(), b.end());
        forn(i, n) {
            if (a[i] == b[n - 1])
                cout << a[i] - b[n - 2] << " ";
            else
                cout << a[i] - b[n - 1] << " ";
        }
        cout << endl;
   }
}

1760D - Challenging Valleys

Idea: mesanu

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<int> a;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if(i == 0 || x != a.back())
        {
            a.push_back(x);
        }
    }
    int num_valley = 0;
    for(int i = 0; i < a.size(); i++)
    {
        if((i == 0 || a[i-1] > a[i]) && (i == a.size()-1 || a[i] < a[i+1]))
        {
            num_valley++;
        }
    }
    if(num_valley == 1)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}

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

1760E - Binary Inversions

Idea: SlavicG

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

ll calc(vector<int>& a) {
    ll zeroes = 0, ans = 0;
    for(int i = sz(a) - 1; i >= 0; --i) {
        if(a[i] == 0) ++zeroes;
        else ans += zeroes;
    }
    return ans;
}
void solve() {
    int n; cin >> n;
    vector<int> a(n);
    forn(i, n) cin >> a[i];
    ll ans = calc(a);
    forn(i, n) {
        if(a[i] == 0) {
            a[i] = 1;
            ans = max(ans, calc(a));
            a[i] = 0;
            break;
        }
    }
    for(int i = n - 1; i >= 0; --i) {
        if(a[i] == 1) {
            a[i] = 0;
            ans = max(ans, calc(a));
            a[i] = 1;
            break;
        }
    }
    cout << ans << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

1760F - Quests

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n, d;
	long long c;
	cin >> n >> c >> d;
	long long a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n, greater<long long>());
	int l = 0, r = d + 2;
	while (l < r) {
		int m = l + (r - l + 1) / 2;
		long long tot = 0;
		int curr = 0;
		for (int i = 0; i < d; i++) {
			if (i % m < n) {tot += a[i % m];}
		}
		if (tot >= c) {
			l = m;
		}
		else {
			r = m - 1;
		}
	}
	if (l == d + 2) {cout << "Infinity\n"; return;}
	if (l == 0) {cout << "Impossible\n"; return;}
	cout << l - 1 << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1760G - SlavicG's Favorite Problem

Idea: SlavicG

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 1e5 + 10;
vector<pair<int, int>> adj[N];
set<int> s;
bool ok = true;
int n, a, b;
void dfs1(int u, int par, int x) {
    if(u == b) return;
    s.insert(x);
    for(auto e: adj[u]) {
        int v = e.first, w = e.second;
        if(v == par) continue;
        dfs1(v, u, x ^ w);
    }
}

bool dfs2(int u, int par, int x) {
    if(u != b && s.count(x)) return true;
    for(auto e: adj[u]) {
        int v = e.first, w = e.second;
        if(v == par) continue;
        if(dfs2(v, u, w ^ x)) return true;
    } 
    return false;
}

void solve() {
    s.clear();
    cin >> n >> a >> b; --a, --b;
    forn(i, n) adj[i].clear();
    for(int i = 0; i < n - 1; ++i) {
        int u, v, w; cin >> u >> v >> w; --u, --v;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    dfs1(a, -1, 0);
    if(dfs2(b, -1, 0)) cout << "YES\n";
    else cout << "NO\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h> using namespace std; #define int long long #define uint unsigned long long #define endl '\n' #define vi vector < int > #define pb push_back; #define all(a) a.begin(), a.end() const int INF = 1e9 + 10; signed main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t; cin >> t; for(int i = 0; i < t; i++){ int n; cin >> n; vi otv(n); int maxi = 0; int predmaxi = 0; int ind_max = 0; for(int j = 0; j < n; j++){ int s; cin >> s; if(j != 0) { if (s >= predmaxi) { if (s >= maxi) { predmaxi = maxi; maxi = s; ind_max = j; } else { predmaxi = s; } } otv[j] = s; }else{ maxi = s; otv[0] = s; } } for(int h = 0; h < n; h++){ if (h != ind_max){ cout << otv[h] - maxi << ' '; }else{ cout << otv[h] - predmaxi << ' '; } } cout << endl; } return 0; }

#include <bits/stdc++.h> using namespace std; int t; int n, a, b; void dfs(int u, int now, int father, vector<vector<pair<int, int>>>& g, unordered_set<int>& st) { if (father != -1) { st.insert(now); } for (auto [nxt, w]: g[u]) { if (nxt != father) { dfs(nxt, now ^ w, u, g, st); } } } bool dfs2(int u, int now, int father, vector<vector<pair<int, int>>>& g, unordered_set<int>& st) { if (st.count(now)) { return true; } for (auto [nxt, w]: g[u]) { if (nxt != father && nxt != b and dfs2(nxt, now ^ w, u, g, st)) { return true; } } return false; } int main() { ios::sync_with_stdio(false); cin >> t; while (t--) { cin >> n >> a >> b; vector<vector<pair<int, int>>> g(n + 1); unordered_set<int> st; for (int i = 0; i < n - 1; i++) { int u, v, e; cin >> u >> v >> e; g[u].push_back({v, e}); g[v].push_back({u, e}); } dfs(b, 0, -1, g, st); if (dfs2(a, 0, -1, g, st)) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0; }

// This is a easiest way to solve this problem // Time complexity O(N) Space complexity O(1) #include<bits/stdc++.h> using namespace std; int main() { int test, a,b,c, mx, mn; cin >> test; while(test --)//Time complexity O(N) and space complexity O(1) { cin >> a >> b >> c; mx = max(a, max(b,c)); mn = min(a, min(b, c)); if(a != mx && a != mn) cout << a << endl; else if(b != mx && b != mn) cout<< b <<endl; else cout<< c <<endl; } return 0; }

Комментарии (52)

Показать архивные | Написать комментарий?

mercury.16

17 месяцев назад, # |

Such a elegant implementation of problem G

→ Ответить

samdavydov

← Rev. 2 →

I believe C can be done in O(n).

Read everything into array a
Find two maximum values — max and pre_max
Do a run:

for (i in a) 
if (i == max) print(i - pre_max) else print(i - max)

Lolka555

17 месяцев назад, # ^ |

Yes, this one is work. You can check my solution that use idea of remember max and pre_max: 181961801

ciopphit

15 месяцев назад, # ^ |

can you post it cause it says I'm not allowed to view it

azizbeksheripboev07

6 месяцев назад, # ^ |

thank you

mnkp

I had the exact same idea for G as the tutorial, But I screwed up the implementation in so many ways

yash1402_

I find 'screwing up in so many ways' very relatable and funny, maybe this should be my spiritual quote!!

white_harmony

Why is this code for problem C, getting TLE? Code

ssvb

"Arrays.sort" has a bad worst case time complexity in Java and can be hacked. See https://codeforces.com/blog/entry/102175 and maybe some other blogs on this topic.

strokeme

Damn the problem ratings are so inflated

AlphaMale06

I think only G and F are inflated, G should be 1500/1600, but then again, for some 1500s and 1600s I think trees are a new topic, so it is normally going to be inflated, while F is just a binary search with a few more steps, so I think it should be 1300/1400.

tibinyte

cap, SlavicG problems are proven to be $$$3500$$$

It's actually a really nice problem, I just don't think it's that hard

TrendBattles

In problem F, I also sort the array in descending order and then I made a prefix sum of n elements. (Let's call it p) We have 3 situations:

1.If (c + p[1] - 1) / p[1] > d then there's no way that we can get c coins in d days.

2.If there is p[i] (i <= d) such that p[i] >= c then any value k satisfies.

3. Brute-force k from d to 0 as k >= d + 1 in this situation is not possible anymore.

Time complexity is O(n log n + d)

sarafsanskar468

Hi, @TrendBattles, If the sum of the entire array is greater than the c coins needed, will that not result in infinity? In case 2: you wrote only for a particular element, why so.?? What if a particular element is not greater than c but the entire array sum is greater?

Well, I made a prefix sum of n elements and p[i] is the sum of the first i elements.

l1l1l1l1

For problem G，unordered_map will give you TLE

zbl

why does my code get TLE for problem G.

haiender288

I changed from unordered_set to set and it got accepted

182220698

why unordered_set slower than set......

While it's true that unordered_set is faster than set on average, the worst case time complexity of unordered_set can get to O(n^2) instead of O(log n) in a normal set (specifically on big prime numbers). It's likely that the test you got TLE on was deliberately constructed for solutions like yours

ok thx～

Bryce3D

Must be beethoven97 again

vantaablackk

How does G solution take care of 2 things?

1.) We may never need to teleport and just reach end node with value 0. In that case inside dfs2, we need to have a condition for that.

2.) I don't see where is the condition to not go beyond end node in dfs2 when we don't get true before reaching end node.

gaspar.kristijan

1.) We may teleport from a to a. Consider the following graph Let's say we start at node 1 and need to end at node 3.

(n) node

-w- connection with weight w

(1) -2- (2) -2- (3)

It isn't optimal to teleport to any node however we can compare path from 1 to 2 having XOR value = 2 and path from 3 to 2 having the XOR value equal to 2. In that case we don't teleport but if we had to, we would teleport from node 2 to node 2.

Alternatively what the functions actually checks is all the possible XOR values starting from a and b. If there is a match answer is yes, else no. In our case we have 2 matches, 0 and 2.

We get 0 at the start because that's our starting value and 2 by traveling from node 1 to 2. When starting from b we get 0 by traveling from node 1 to 3 and value 2 by traveling from 3 to 2.

2.) dfs2 starts at node b

    if(dfs2(b, -1, 0)) cout << "YES\n";
    else cout << "NO\n";

It checks if it can hit any optimal values calculated in dfs1. In dfs1 all possible values are calculated where we have the limitation in place.

transfermarket

Awesome round.

OstadShifu

any idea why I'm getting wa2 in e?

submission

The_Ahmed

It getting WA because of two things:-

You need to handle the case in which you will not do any operations.
Function cal() needs to return long long, because in the worst case ans = (10^10), this will cause overflow of course.

manu.chittora

someone please explain "Also, we cannot pass b on the path from a→c." in tutorial of G.

It refers to the fact we cannot pass through the node b (end node) when starting dfs from a. Because it's impossible to enter b without our value being 0.

See the problem statement

you are allowed to enter node b if and only if after traveling to it, the value of x will become 0.

In other words, you can travel to node b only by using an edge i such that x XOR wi=0.

demonstrator

Can somebody please explain why i am getting WA 182023139 in G . I am storing xor from starting to ending node in a variable then from every node we can go to ending node . and xor will be xor of node from starting to xor of starting to end and then checking if it exists in our set or not.

Made some changes in your code and got AC.

Biggest change I did was the starting node in dfs2 and some changes in the functions themselves.

Submission: 182291486

Gisu

In 1760D - Challenging Valleys you could also insert INF at the start and at the end of the processed array (without successive equal elements) to simplify the job with edges, then check every triplet inside for a[i-1]>a[i]<a[i+1], 182365763

KFPanda

Could someone point out where my code fails? ato[i] is xor value of path from a to i. 184338941

Sreedhar3210

16 месяцев назад, # |

why does this code fails 185000763 for G.

Pro_Noob_25

why my solution is failing on test 2 iteration number 53 code

spkumar9952

Problem G unordered_set gives TLE but set solution Accepted. I also faced similar issues in other problems as well. Can anyone explain me why this is happening ?

tgp07

15 месяцев назад, # |

I have tried stress testing my solution to problem G, and I haven't yet been able to find a test case that breaks my code. Can anyone please take a look at this? 188826168

variety-jones

Take a look at Ticket 16694 from CF Stress for a counter example.

tong96

14 месяцев назад, # |

Anyone could help me look at what's the problem of my solution 193477917 for G.

Thanks a lot in advance!

vaal

12 месяцев назад, # |

202246684 Can anyone tell me why this submission for problem G fails for test 53?

12 месяцев назад, # ^ |

Take a look at Ticket 16833 from CF Stress for a counter example.

dp_Hero

why the Problem G can't solve with at most once dfs ?

arihant_j

10 месяцев назад, # |

[submission:https://codeforces.com/contest/1760/submission/211710923]

EaslyubitsS

9 месяцев назад, # |

For problem D --> why can't I use this method for taking input ? int n; cin >> n; vector a(n); for(int i=0;i<n;i++){ cin >> a[i]; } for this method it doesn't satisfy the sample i/o. exactly why I have to use this one ????--> int n; cin >> n; vector a; for(int i = 0; i < n; i++) { int x; cin >> x; if(i == 0 || x != a.back()) { a.push_back(x); } }

Morsalin_Islam

Arnur2937

7 месяцев назад, # |

G is the best problem

Siyah

7 месяцев назад, # ^ |

agree

-tsukasa-

← Rev. 3 →

I have used a dfs approach for G,but my code is not working,can someone help me with the debugging the following submission, https://codeforces.com/contest/1760/submission/226432202

deepaksuthar40128

3 месяца назад, # |

G :/

jama_atajonov

2 месяца назад, # |

t = int(input()) for _ in range(t): n = int(input()) s = input() a = "abcdefghijklmnopqrstuvwxyz" l = max(s, key=ord) print(a.index(l)+1)

Блог пользователя flamestorm