# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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, vintage_Vlad_Makeev, AlexFetisov and any other people who participates in preparation of contest.
Code (C++) 31365874
Code (Python) 31365844
Code 31366254
Code 31365909
Code 31366223
Code 31365959
Code 31366002
Code 31368704
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 ≤ 232 - 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 ai and should make all numbers in it be equal to zero with minimal number of operations. Sum of all ai 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 ai. Also let an - 1 = n - 1.
dpi is sum of shortests pathes from i to i + 1... n - 1.
dpn - 1 = 0
dpi = dpm - (ai - m) + n - i - 1 where m belongs to range from i + 1 to ai and am is maximal. We can find m with segment tree or binary indexed tree or sparse table.
Now answer equals to sum of all dpi.
#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';
}
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
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 posi - posi - 1 where posi 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 r12 + r22.
Bonus: It's O(n2) solution. Can you solve problem in O(nlogn)?
Solution O(n2) 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
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
Name |
---|