Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution (MikeMirzayanov)**

```
#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 a[3];
cin >> a[0] >> a[1] >> a[2];
sort(a, a + 3);
if (a[2] <= a[0] + a[1])
cout << (a[0] + a[1] + a[2]) / 2 << endl;
else
cout << a[0] + a[1] << endl;
}
}
```

Idea: Stepavly

**Tutorial**

Tutorial is loading...

**Solution (Stepavly)**

```
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<char> calced(n);
vector<string> a(n);
set<string> have;
int res = 0;
for (string &pin : a) {
cin >> pin;
have.insert(pin);
}
for (int i = 0; i < n; i++) {
if (calced[i]) {
continue;
}
vector<int> sameIds;
for (int j = i + 1; j < n; j++) {
if (a[i] == a[j]) {
sameIds.push_back(j);
calced[j] = 1;
res++;
for (int k = 0; k < 4 && a[i] == a[j]; k++) {
for (char c = '0'; c <= '9'; c++) {
string t = a[j];
t[k] = c;
if (!have.count(t)) {
have.insert(t);
a[j] = t;
break;
}
}
}
}
}
}
cout << res << "\n";
for (string& s : a) {
cout << s << "\n";
}
}
int main() {
int test;
cin >> test;
while (test--) {
solve();
}
}
```

Idea: unreal.eugene

**Tutorial**

Tutorial is loading...

**Solution (unreal.eugene)**

```
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define ALL(s) (s).begin(), (s).end()
#define rALL(s) (s).rbegin(), (s).rend()
#define sz(s) (int)(s).size()
#define mkp make_pair
#define pb push_back
#define sqr(s) ((s) * (s))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;
#ifdef EUGENE
mt19937 rng(1337);
#else
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
void solve() {
int n;
cin >> n;
vector<int> ans;
int s = (int)sqrtl(n);
for (int i = 0; i <= s; i++)
ans.pb(i);
for (int i = 1; i <= s; i++)
ans.pb(n / i);
sort(ALL(ans));
ans.resize(unique(ALL(ans)) - ans.begin());
cout << sz(ans) << endl;
for (int &x : ans)
cout << x << " ";
cout << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
#ifdef EUGENE
freopen("input.txt", "r", stdin);
// freopen("output.txt", "r", stdout);
#endif
int t;
cin >> t;
while (t--)
solve();
}
```

Idea: Stepavly

**Tutorial**

Tutorial is loading...

**Solution (Stepavly)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = (int)2e5 + 100;
vector<int> g[N];
char used[N];
void addEdge(int v, int u) {
g[v].push_back(u);
g[u].push_back(v);
}
void dfs(int v) {
used[v] = 1;
for (int to : g[v]) {
if (!used[to]) {
dfs(to);
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (char c : s) {
addEdge(i, n + c - 'a');
}
}
int res = 0;
for (int i = n; i < n + 26; i++) {
if (!g[i].empty() && !used[i]) {
dfs(i);
res++;
}
}
cout << res;
return 0;
}
```

Idea: Supermagzzz

**Tutorial**

Tutorial is loading...

**Solution (Supermagzzz)**

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
struct MyStack {
int cnt = 0;
int allOpens = 0;
stack<int> s;
stack<int> minValue;
stack<int> maxValue;
void push(int x) {
s.push(x);
cnt += x;
if (x == 1) {
allOpens += 1;
}
minValue.push((minValue.size() ? min(minValue.top(), cnt) : cnt));
maxValue.push((maxValue.size() ? max(maxValue.top(), cnt) : cnt));
}
void pop() {
if (s.size() == 0) {
return;
}
cnt -= s.top();
if (s.top() == 1) {
allOpens -= 1;
}
s.pop();
minValue.pop();
maxValue.pop();
}
int top() {
return s.top();
}
bool isCorrect() {
return (minValue.size() == 0 || minValue.top() >= 0);
}
int depth() {
return (maxValue.size() ? maxValue.top() : 0);
}
};
int main() {
int n;
cin >> n;
string s;
cin >> s;
MyStack left, right;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
right.push(0);
}
left.push(0);
int pos = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'L') {
if (pos != 0) {
pos--;
right.push(-left.top());
left.pop();
}
} else if (s[i] == 'R') {
pos++;
left.push(-right.top());
right.pop();
} else if (s[i] == '(') {
left.pop();
left.push(1);
} else if (s[i] == ')') {
left.pop();
left.push(-1);
} else {
left.pop();
left.push(0);
}
if (left.isCorrect() && right.isCorrect() && left.cnt == right.cnt) {
cout << max({left.depth(), right.depth(), left.cnt}) << " ";
} else {
cout << "-1 ";
}
}
}
```

Idea: AdvancerMan

**Tutorial**

Tutorial is loading...

**Solution (Rox)**

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#ifdef LOCAL
#define eprint(x) cerr << #x << " = " << (x) << endl
#define eprintf(args...) fprintf(stderr, args), fflush(stderr)
#else
#define eprint(x)
#define eprintf(...)
#endif
vector<vector<int>> precalc(int n, vector<int> p, vector<int> id) {
vector<vector<int>> res(n, vector<int>(n));
for (int l = 0; l < n; l++) {
vector<int> deg(sz(p));
for (int i = 1; i < sz(p); i++)
deg[p[i]]++;
int val = 0;
for (int r = l; r < n; r++) {
int v = id[r];
while (v != 0 && deg[v] == 0) {
deg[p[v]]--;
v = p[v];
val++;
}
res[l][r] = val;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> p(2);
vector<vector<int>> id(2);
for (int i = 0; i < 2; i++) {
int vn;
cin >> vn;
p[i].resize(vn);
for (int v = 1; v < vn; v++) {
cin >> p[i][v];
p[i][v]--;
}
id[i].resize(n);
for (int j = 0; j < n; j++) {
cin >> id[i][j];
id[i][j]--;
}
}
vector<vector<vector<int>>> cost(2);
for (int i = 0; i < 2; i++)
cost[i] = precalc(n, p[i], id[i]);
vector<int> dp(n + 1);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
dp[j] = max(dp[j], dp[i] + max(
cost[0][i][j - 1],
cost[1][i][j - 1]
));
}
}
cout << dp[n] << endl;
}
```

Problem C can be done in O(√n) , I think. I just have a for loop 1->sqrt(n) and add 2 numbers to the list and got accepted :D

I think I have the same idea with you

Edit: There was no need to use set or sort the vector. I was wrong.

You need to either use a set, or if you used a vector then you need to sort them. So the factor of log(N) comes from there.

For each $$$i \leq \sqrt{n}$$$, I calculate $$$h= \lfloor \dfrac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$$$. If $$$i=h$$$, I push back $$$i$$$ into a vector. If $$$t=\lfloor \frac{n}{i} \rfloor \neq i$$$, I also push back $$$t$$$ into another vector.

Rearrange the order of printing elements from both vectors and you are good to go.

You add numbers to a set. Adding to the set is log(n). So your solution has O(sqrt(n)log(n))

We can add i to vector1 and n / i to vector2. Then, we write vector1 and reversed vector2. Is it O(sqrt(n))? https://codeforces.com/contest/1263/submission/65979113

Yes, you are right. I came to the same solution in the shower btw https://codeforces.com/contest/1263/submission/66073816

For Problem B a similar solution would be to consider a map for storing all the found pins while iterating through the list. Once it finds a pin that already exists in the map, randomly choose any position in the pin to replace it randomly with another digit. This repeats until we get a new 4 digit number. And this counts as a step.

Finally, print the step count and the new pins.

https://codeforces.com/contest/1263/submission/66044121

This question looks easy-medium but it's just cakewalk. During contest, it screwed me up but here is the simplest solution with array and simple logic https://codeforces.com/contest/1263/submission/66003837

Yes, I agree with you. I think problem A was harder than B.

Indeed A harder than B, C and D

I gave up after failing to solve A... I wish I had started from B

C can also be solved using the fact that $$$j = \left\lfloor \dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor }\right\rfloor$$$ is the largest $$$j$$$ such that $$$\left\lfloor\dfrac{n}{i}\right\rfloor = \left\lfloor\dfrac{n}{j}\right\rfloor$$$.

65967376

Can anybody explain me logic of problem E. How it is done using segment tree?

Suppose that '(' is 1 and ')' is -1, and others are 0. If the string is a correct text, these conditions will be satisfied:

- The sum of any prefix should not less than 0 because that means the number of ')' is greater than '(' in this prefix.

- The sum of the whole string should be 0 because the number of '(' and ')' should be equal.

If the two conditions are not satisfied, the answer is -1.

Otherwise, the answer is equal to the maximum depth of these brackets. It is equal to the maximum sum prefix because the sum of a prefix means how much '(' do not match with a ')' in the prefix.

So we can use a segment tree to keep the sum of all prefixes and get the maximum and minimum sum prefix.

My code: 66065668

Thanks got it.

Can you explain your solution a little bit. What is the use of tag.

I use a segment tree to keep

prefix sum array, so when I modify the $$$i$$$-th element in the original array, I need to update sums of prefixes that contain the $$$i$$$-th element. They are a continuous range $$$[i, n-1]$$$ in the prefix sum array, so we need to use lazy tag to do range updates. If the tag of a node is $$$t$$$, that means every element in the range should plus $$$t$$$, and the maximum and minimum value of the node should plus $$$t$$$, too.What's the time complexity? Is it n^2*log(n) ?

No, the time complexity is $$$O(n \log n)$$$.

The time complexity of doing a range update or range minimum/maximum query is $$$O(\log n)$$$. In my code, when I process a command, I do range update at most twice and range minimum/maximum query at most 3 times, so the time complexity of processing a command is $$$O(\log n)$$$. There is $$$n$$$ commands, so the time complexity is $$$O(n \log n)$$$.

How to solve problem E using lazy segment tree? :)

is trivial with segment tree

https://codeforces.com/blog/entry/71844?#comment-561697 This comment is exactly lazy segment tree

My solution lazy segment tree, maintaining max and min interval. Every time we update the range from x to n(the end of the line) code

Stepavly How can I solve D using std::set ?

A different O(n) approach for E:

Maintain a prefix sum and store maximum and minimun in it.

Be lazy when the operation is L\R or when #( != #) (number of brackets).

when #( = #), update the prefix sum just in the range the cursor touched, amortize time is O(1) since L,R operations paid for each update in this range.

To maintain maximum and minimum store an histogram of prefixes.

solution: 66080615

i was thinking in this way, but then i've remembered that i'm dummy and came with obvious segment tree solution

Sweet candies problem If we are given 8 2 8 candies, there is no possible way that we can eat it for 9 days. Can you tell me what is wrong in my approach?

It is possible that we can eat candies for 9 days. One scenario for example would be that we eat 7 candies from biggest and medium piles i.e. 8 and 8 here. This can be done for 7 days. Then we are left (1 2 1) candies. Then eat such that the pile is (0 1 1) on the 8th day and on 9th day, it would be (0 0 0).

Thank you very much!

In Problem A, how is the answer if r < g +b is (r + b +g)/2, what is the maths behind? Or is it purely observational?

When the maximum number is less than the sum of the other two numbers, you can try to simulate this process. Use a priority queue to select the maximum two numbers from each time and subtract one. When this operation is completed, the maximum number is always less than the sum of the other two numbers until it becomes 0.00 or 0.01. The answer (B + G + R) / 2 mathematical induction can prove that my English expression is not very good I hope my answer will help you When the maximum number is larger than the sum of the other two numbers, answer is obviously the sum of two less numbers.

Would please show the proof for the mathematical induction of (r+b+g)/2

Suppose B>=G>=R, and B is less than or equal to G + R, When (B + G + R) <= 2, (when B G R is 1 1 0 or 0 0 0 respectively), the answer is (B + G + R) / 2 When (B + G + R) > 2, when we reduce B G by one, the maximum number of the answer plus one or three numbers is still less than or equal to the sum of the other two numbers, so we prove that. Above all.

Can anybody explain the Segment tree solution of E problem a little elaborately, I have read solutions of many people but couldn't decipher the logic of what they are trying to do. I know these things that the minimum sum prefix has to be greater than -1, total sum has to be 0 and maximum sum prefix would the answer, but how exactly are we computing this using a segment tree?

Suppose you know that the total length of everything is n. Let each '(' to be a +1, each ')' to be a -1, and each regular character to be a 0.

So for example if I have string (((a))), we get [1, 2, 3, 3, 2, 1, 0]. Notice that if we drop below 0 then we have an invalid string since there are too many ')'. The maximum amount of nesting is what we want to query, and that's just the maximum value on the segment.

When we make changes we can just perform updates on segment. For example if I change from 'a' -> '(' at index i, then I just add 1 for all elements from [i...n], if I change from ')' to '(', then I have to add 2 for all elements [i...n]. Really we have range sum updates and range max/min queries which a straightforward use of segment tree

Thank you so much, this explanation is crystal clear. But I wanted to ask you this that changing a a to ( is a point update so can't we do that point update and calculate the max prefix and min prefix sum using some other way? I thought of a way that we store totalSum, MaxPrefixSum and MinPrefixSum for each node, now for every parent thw updation would be something like parent.MaxPrefixSum = max(Left.MaxPrefixSum, Left.TotalSum+Right.MaxPrefixSum) And similarly for MinPrefixSum TotalSum would be updated directly.

Can someone explain Problem C, I am not able to understand the math

The idea is that, given n, you need to iterate through all numbers i where (0<=i<=n) and see the result of dividing n/i and store it in a set.

The optimization trick is to only iterate through i where (0<=i<=√n) and store both i and n/i in the set. So the time complexity is O(t√n). Here is my code: 65966154

Challenge Problem F completed:

The complexity of my code is linear. I only use algorithms like dfs, counting sort, monotonic stack.

My solution

please explain about B problem. I not getting What is logic.thanks.

(In the editorial of problem A)Is the line correct? "Then we make equal the piles g, b by eating g−b from the piles r and b".

I think it would be-"Then we make equal the piles g, b by eating g−b from the piles r and g".

You are right, thanks for pointing it out! The tutorial for A will be updated soon.

How to solve problem E with segment tree??? plz explain for me. thanks..

Lets assume '(' = 1 and ')' = -1 and any other character is equal to 0. For each segment store the following things:-

`1. Number of opening brackets.`

`2. Number of closing brackets.`

`3. Maximum prefix sum and minimum prefix sum.`

For each iteration update the tree. The string is balanced if minimum prefix sum is positive or zero and number of opening brackets == number of closing brackets. Number of different colors (final answer) is maximum prefix sum. You can have a look on my submission.66222540

Tutorial for problem has a typo I guess: Then we make equal the piles g, b by eating g−b from the piles r and b.

Here it should be piles r and g I think. Correct me if I am wrong.

Can someone explain how to solve Div2-F. I am not able to understand the editorial. P.S- What is " the segment [l,r]", I am not able to understand it. Thanks in advance.

How to solve F by lowest common ancestor approach?

Can anyone please tell me where my approach of Problem B is wrong .

https://codeforces.com/contest/1263/submission/66242150

It's even showing the wrong answer on test case 1, which i can't seems to understand.

EDIT: Found my mistake !!Can you tell me why for the input 8 9 10

output is 13, it should be 16.

Tanya can't eat for $$$16$$$ days straight because the sum of piles' sizes is reducing by $$$2$$$ every day so she can't eat for more than $$$\left\lfloor \frac{8 + 9 + 10}{2} \right\rfloor = 13$$$ days.

For problem A, how can I prove this that if g+b>r, then the best possible approach would be to make the stacks equal?

66304111 I am unable to see due to which part my code is exceeding the time limit for Question D, used simple DFS in my approach. Above is the submission link. Thanks in Advance :)

How to solve D?

My submission is 66433037 and it's completely linear but it's giving me TLE for problem E?? Can anyone help me fix this? I've used a Stack of an object which is 4 generics, and all of my actions are push and pop and writing to an array; not really sure where I could clean this up; is there some Java structure I'm using which is particularly slow?

For D, 4 l k al ak Answer is 1. Can someone tell me how l and k are equivalent?

"for (string &pin : a)" what does this mean?