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

Idea: flamestorm

**Tutorial**

Tutorial is loading...

**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**

Tutorial is loading...

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

Idea: Errichto

**Tutorial**

Tutorial is loading...

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

Idea: mesanu

**Tutorial**

Tutorial is loading...

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

Idea: SlavicG

**Tutorial**

Tutorial is loading...

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

Idea: flamestorm

**Tutorial**

Tutorial is loading...

**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**

Tutorial is loading...

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

Such a elegant implementation of problem G

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

`a`

`max`

and`pre_max`

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

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

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

I find

'screwing up in so many ways'very relatable and funny, maybe this should be my spiritual quote!!Why is this code for problem C, getting TLE? Code

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

Damn the problem ratings are so inflated

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.

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

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

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

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.

https://ideone.com/3eEgf3 whats the problem in this code. wa on test 2... problem D

For problem G，unordered_map will give you TLE

why does my code get TLE for problem G.

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～

Must be beethoven97 again

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.

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

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

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.

In problem C, I guess you do not need to sort the entire array. What you need is just to find out the largest and 2nd-largest element from the array.

(2nd-largest element might be identical to the largest element if the largest value appears 2 or more times in the array)

Awesome round.

any idea why I'm getting wa2 in e?

submissionhttps://codeforces.com/contest/1760/submission/182235832

It getting

WAbecause of two things:-You need to handle the case in which you

will notdo any operations.Function

`cal()`

needs to returnlong long, because in the worst caseans = (10^10), this will cause overflow of course.I didn't notice that we can not use the operation thank you <3

"The minimum value of k is 0, and the** maximum value is n** (for larger k, we won't be able to do the same quest multiple times anyways, so it's useless to consider them). "

Why the maximum value for k is n? Isn't it

d? Then for larger k than d we won't be able to do the same quest multiple times anyways because there are only d days right? So the complexity should be O(n log(n) + d log(d)) ? Am i missing something or?maximum value of k depends on d and the entries supplied, it may also exceed d

ex: A=[3,2,1], d=1,c=3 k can increase infinitely, look, i have a single day to make profit and if i complete the first quest i get the sum>=c, i dont need to use that quest again or any other quest so you can increase k as much as you like

ofc if K can increase infinitly then you return Infinite, you dont infinite loop xd. What i mean is computationally, to find k, you work with order of d not n (or at least in my solution i do that)

can anyone tell me my mistake in problem D 181949662

yes. you are right. The code shown is same as what you are saying

Take a look at Ticket 16544 from

CF Stressfor a counter example.can someone kindly point out error in my solution here for problem G? https://codeforces.com/contest/1760/submission/182250273

test1

11 2 7

2 11 6

4 6 12

9 4 8

9 10 2

6 3 5

8 1 6

5 2 10

7 3 7

8 2 11

7 1 4

OutputNO

answerYES

..

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

okay:) Thank You

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

Take a look at Ticket 16545 from

CF Stressfor a counter example.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]`

, 182365763Can somebody help me with my problem G code. I am getting runtime error in testcase 20.

https://codeforces.com/contest/1760/submission/182632177

I have submitted this problem like 20 times, but I keep getting wrong answer on token 162 on test 1. I've literally tried debugging every nuance of the code and compared it with the solution, but I don't know what I'm doing wrong. Here's my code: https://codeforces.com/contest/1760/submission/182718256

You never know, 21st time's the charm.

Take a look at Ticket 16543 from

CF Stressfor a counter example.In the tutorial of problem D it says:

`i=0 or bi−1<bi and i=n−1 or bi>bi+1`

But shouldn't it be like:

`i=0 or bi−1>bi and i=n−1 or bi<bi+1`

or am I missing something?did anyone solve G with bfs ? i got stuck in test 40 . any idea why i'm getting wrong answer ? 183283417

Take a look at Ticket 16546 from

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

Take a look at Ticket 16551 from

CF Stressfor a counter example.why does this code fails 185000763 for G.

Take a look at Ticket 16564 from

CF Stressfor a counter example.Solved F in O(n) using prefix sum — Code

you sorted at the beginning tho --> O(nlogn)

Could anybody please tell me what might be the problem in this code for problem E. Its failing on second test case for 2653rd iteration. Link to submission

Take a look at Ticket 16572 from

CF Stressfor a counter example.Thanks man finally figured it out. That site is a lifesaver.

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

Take a look at Ticket 16617 from

CF Stressfor a counter example.Can someone help me? The example case of problem F in my local works but in Codeforces it does not. 188250142

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 ?

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

Take a look at Ticket 16694 from

CF Stressfor a counter example.very easy solution all you have to do is iterate and find letter with greatest ascii value and take away 96

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

Thanks a lot in advance!

Take a look at Ticket 16731 from

CF Stressfor a counter example.can someone plz tell me whats wrong with my code it says wtong answer of test 2000 sthng : 201593881

Take a look at Ticket 16823 from

CF Stressfor a counter example.202246684 Can anyone tell me why this submission for problem G fails for test 53?

Take a look at Ticket 16833 from

CF Stressfor a counter example.why the Problem G can't solve with at most once dfs ?