Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3404 |

3 | TLE | 3356 |

4 | apiadu | 3351 |

5 | mnbvmar | 3281 |

6 | LHiC | 3276 |

7 | Um_nik | 3268 |

8 | 300iq | 3267 |

9 | yosupo | 3249 |

10 | ainta | 3226 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 169 |

5 | vovuh | 167 |

5 | pikmike | 167 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 155 |

10 | McDic | 152 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Технокубок 2018 - Отборочный Раунд 3

870A - Search for Pretty Integers Idea, preparation, editorial komendart

870B - Maximum of Maximums of Minimums Idea DPR-pavlin, preparation, editorial mHuman

870C - Maximum splitting Idea, preparation, editorial komendart

870D - Something with XOR Queries Idea, preparation, editorial mHuman

870E - Points, Lines and Ready-made Titles Idea, preparation, editorial komendart

870F - Paths Idea, preparation, editorial komendart

871E - Restore the Tree Idea MikeMirzayanov, preparation fcspartakm, editorial mHuman

Also many thanks to coordinator KAN, testers ifsmirnov, gritukan, AlexFetisov and any other people who participates in preparation of contest.

Tutorial is loading...

Code (C++) 31365874

Code (Python) 31365844

Tutorial is loading...

Code 31366254

Tutorial is loading...

Code 31365909

Tutorial is loading...

Code 31366223

Tutorial is loading...

Code 31365959

Tutorial is loading...

Code 31366002

Tutorial is loading...

Code 31368704

Tutorial of Technocup 2018 - Elimination Round 2

Hi everyone!

I don't know, maybe this topis was discussed on Codeforces but google didn't help me.

It seems that standart hash function in gcc works badly (for Visual C++ all is good).

For 0 ≤ *x* ≤ 2^{32} - 1

```
std::hash<int>()(x) == x
std::hash<long long>()(x) == x
```

For any other number

```
std::hash<long long>()(x + (1LL << 32)) == std::hash<long long>()(x)
```

For example code in spoiler works more than 10 seconds on Codeforces because hashes of all numbers are equal to zero.

```
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<long long> d;
int n = 1e5;
long long t = 1LL << 32;
for (int i = 0; i < n; i++) {
d.insert(i * t);
}
cout << d.size() << endl;
}
```

What can we do without writing our own hash function?

Someday I will arrange C and D correctly :)

Firstly, in case *c* = 0 we should output YES if *a* = *b* else answer is NO.

If *b* belongs to sequence *b* = *a* + *k* * *c* where k is non-negative integer.

So answer is YES if (*b* - *a*) / *c* is non-negative integer else answer is NO.

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c;
cin >> a >> b >> c;
if (c == 0) {
if (a == b) cout << "YESn";
else cout << "NOn";
} else {
if ((b - a) % c == 0 && (b - a) / c >= 0) cout << "YESn";
else cout << "NOn";
}
}
```

x a y

b m c

z d w

Number in the center may be any from 1 to *n* because number in the center belongs to all subsquares 2 × 2. So, let's find answer with fixed number in the center and then multiply answer by *n*.

Let's iterate over all possible *x*. Sums of each subsquare 2 × 2 are the same so *x* + *b* + *a* + *m* = *y* + *c* + *a* + *m* and *y* = *x* + *b* - *c*.

Similarly, *z* = *x* + *a* - *d* and *w* = *a* + *y* - *d* = *z* + *b* - *c*.

This square is legal if 1 ≤ *y*, *z*, *w* ≤ *n*. We should just check it.

Also we can solve this problem in *O*(1).

```
#include <iostream>
using namespace std;
int main() {
int n, a, b, c, d;
cin >> n >> a >> b >> c >> d;
long long ans = 0;
for (int x = 1; x <= n; x++) {
int y = x + b - c;
int z = x + a - d;
int w = a + y - d;
if (1 <= y && y <= n && 1 <= z && z <= n && 1 <= w && w <= n) {
ans++;
}
}
ans *= n;
cout << ans << endl;
}
```

We have array *a*_{i} and should make all numbers in it be equal to zero with minimal number of operations. Sum of all *a*_{i} equals to zero.

We can divide array into parts of consecutive elements with zero sum. If part has length *l* we can use all pairs of neighbours in operations and make all numbers be equal to zero with *l* - 1 operations.

So, if we sum number of operations in each part we get *ans* = *n* - *k* where *k* is number of parts. We should maximize *k* to get the optimal answer.

One of the part consists of some prefix and probably some suffix. Each of other parts is subarray of *a*.

Let's calculate prefix sums. Each part has zero sum so prefix sums before each part-subarray are the same.

So we can calculate *f* — number of occurencies of the most frequent number in prefix sums and answer will be equal to *n* - *f*.

Bonus: how to hack solutions with overflow?

```
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
map<long long, int> d;
long long sum = 0;
int ans = n - 1;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
sum += t;
d[sum]++;
ans = min(ans, n - d[sum]);
}
cout << ans << endl;
}
```

We have binary search tree (BST) and should insert number in it with good time complexity.

Let we should add number *x*. Find numbers *l* < *x* < *r* which were added earlier, *l* is maximal possible, *r* is minimal possible (all will be similar if only one of this numbers exists). We can find them for example with std::set and upper_bound in C++.

We should keep sorted tree traversal (it's property of BST). So *x* must be right child of vertex with *l* or left child of vertex with *r*.

Let *l* hasn't right child and *r* hasn't left child. Hence lowest common ancestor (lca) of *l* and *r* doesn't equal to *l* or *r*. So lca is between *l* and *r* in tree traversal. But it's impossible because *l* is maximal possible and *r* is minimal possible. So *l* has right child or *r* has left child and we know exactly which of them will be parent of *x*.

That's all. Time complexity is .

```
#include <iostream>
#include <set>
#include <map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
set<int> numbers;
map<int, int> left;
map<int, int> right;
int n, v;
cin >> n >> v;
numbers.insert(v);
for (int i = 0; i < n - 1; i++) {
cin >> v;
auto it = numbers.upper_bound(v);
int result;
if (it != numbers.end() && left.count(*it) == 0) {
left[*it] = v;
result = *it;
} else {
it--;
right[*it] = v;
result = *it;
}
numbers.insert(v);
cout << result;
if (i == n - 2) cout << 'n';
else cout << ' ';
}
}
```

Let the indexation will be from zero. So we should subtract one from all *a*_{i}. Also let *a*_{n - 1} = *n* - 1.

*dp*_{i} is sum of shortests pathes from *i* to *i* + 1... *n* - 1.

*dp*_{n - 1} = 0

*dp*_{i} = *dp*_{m} - (*a*_{i} - *m*) + *n* - *i* - 1 where *m* belongs to range from *i* + 1 to *a*_{i} and *a*_{m} is maximal. We can find *m* with segment tree or binary indexed tree or sparse table.

Now answer equals to sum of all *dp*_{i}.

```
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1 << 18;
pair<int, int> tree[maxn * 2];
void build(const vector<int> &a, int n) {
for (int i = 0; i < n; i++) tree[maxn + i] = {a[i], i};
for (int i = maxn - 1; i > 0; i--)
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
int get(int l, int r) {
pair<int, int> ans{-1, -1};
for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans = max(ans, tree[l++]);
if (r & 1) ans = max(ans, tree[--r]);
}
return ans.second;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
a[n - 1] = n - 1;
for (int i = 0; i < n - 1; i++) {
cin >> a[i];
a[i]--;
}
build(a, n);
vector<long long> dp(n);
long long ans = 0;
dp[n - 1] = 0;
for (int i = n - 2; i >= 0; i--) {
int m = get(i + 1, a[i]);
dp[i] = dp[m] - (a[i] - m) + n - i - 1;
ans += dp[i];
}
cout << ans << 'n';
}
```

Tutorial of Codeforces Round #353 (Div. 2)

Hello, everyone!

Codeforces Round #353 (Div. 2) will take place tomorrow on the 16th of May at 19:35 MSK. I tried to make interesting problems, hope you enjoy them.

I'd like to thank GlebsHP for his help in preparing problems and MikeMirzayanov for Codeforces and Polygon.

Good luck!

**UPD** Scoring **500-1000-1500-2000-2500**

**UPD** Editorial

**UPD** Congratulations to winners!

Div. 2

Div. 1

Announcement of Codeforces Round #353 (Div. 2)

It's optimal to do the biggest possible step everytime. So elephant should do several steps by distance 5 and one or zero step by smaller distance. Answer equals to

Solution 15550796

We are given array which contains only ones and zeroes. We must divide it on parts with only one 1.

Tricky case: when array contains only zeroes answer equals to 0.

In general. Between two adjacent ones we must have only one separation. So, answer equals to product of values *pos*_{i} - *pos*_{i - 1} where *pos*_{i} is position of i-th one.

Bonus: what's the maximal possible answer for *n* < 100?

Solution 15550806

First radius equals to zero or distance from first fountain to some flower. Let's iterate over this numbers. Second radius equals to maximal distance from second fountain to flower which doesn't belong to circle with first radius. Now we should choose variant with minimal *r*_{1}^{2} + *r*_{2}^{2}.

Bonus: It's *O*(*n*^{2}) solution. Can you solve problem in *O*(*nlogn*)?

Solution *O*(*n*^{2}) 15550812

Solution *O*(*nlogn*) 15550822

Answer equals to one if all coordinates x or y of points are same.

When answer equals to two? Let's iterate over all pairs of points. Let first point in pair is beginning of polyline, second point is end. Only one or two such polylines with answer two exist. If third point is on the polyline it belongs to rectangle with corners in first two points. We can just check it.

Else answer equals to three. We can build vertical lines which contains the most left and the most right point and horizontal line through third point. If we erase some excess rays we will get polyline.

Solution 15550843

617E - XOR and Favorite Number

We have array *a*.

Let's calculate array *pref* (*pref*[0] = 0, ).

Xor of subarray *a*[*l*...*r*] equals to .

So query (l, r) is counting number of pairs *i*, *j* (*l* - 1 ≤ *i* < *j* ≤ *r*) .

Let we know answer for query (l, r) and know for all *v* *cnt*[*v*] — count of *v* in *a*[*l* - 1...*r*]. We can update in O(1) answer and *cnt* if we move left or right border of query on 1. So we can solve problem offline in with sqrt-decomposion (Mo's algorithm).

Solution 15550846

Tutorial of Codeforces Round #340 (Div. 2)

Hi!

Tomorrow, on 23rd of January at 18:35 MSK Codeforces Round #340 (Div. 2) will take place. It's my first round, hope you enjoy the problems.

Thanks to GlebsHP for his help in preparing the problems, Delinur for translations of statements and MikeMirzayanov for Codeforces and Polygon.

Good luck!

**UPD** Scoring **500-1000-1250-1750-2750**

**UPD** Editorial

**UPD** Congrats to winners!

Div. 2

Div. 1

Announcement of Codeforces Round #340 (Div. 2)

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/18/2020 14:11:19 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|