Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n = int(input())
print(2 ** n - 1)
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
if 3**(n-1) > 10**9:
print("NO")
else:
print("YES")
print(*[3**x for x in range(n)])
1651C - Fault-tolerant Network
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
typedef long long li;
const int INF = int(1e9);
int n;
vector<int> a, b;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
b.resize(n);
fore (i, 0, n)
cin >> b[i];
return true;
}
int bestCandidate(const vector<int> &vals, int cur) {
int bst = INF + 10, pos = -1;
fore (i, 0, n) {
if (bst > abs(cur - vals[i])) {
bst = abs(cur - vals[i]);
pos = i;
}
}
return pos;
}
inline void solve() {
li bst = 10ll * INF;
vector<int> cds1 = {0, bestCandidate(b, a[0]), n - 1};
vector<int> cds2 = {0, bestCandidate(b, a[n - 1]), n - 1};
for (int var1 : cds1) {
for (int var2 : cds2) {
li ans = (li)abs(a[0] - b[var1]) + abs(a[n - 1] - b[var2]);
if (var1 > 0 && var2 > 0)
ans += abs(b[0] - a[bestCandidate(a, b[0])]);
if (var1 < n - 1 && var2 < n - 1)
ans += abs(b[n - 1] - a[bestCandidate(a, b[n - 1])]);
bst = min(bst, ans);
}
}
cout << bst << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) {
read();
solve();
}
return 0;
}
1651D - Nearest Excluded Points
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (vovuh)
#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
scanf("%d", &n);
vector<pair<int, int>> a(n);
for (auto &[x, y] : a) scanf("%d %d", &x, &y);
set<pair<int, int>> st(a.begin(), a.end());
map<pair<int, int>, pair<int, int>> ans;
queue<pair<int, int>> q;
for (auto [x, y] : a) {
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (st.count({nx, ny})) {
continue;
}
ans[{x, y}] = {nx, ny};
q.push({x, y});
break;
}
}
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (!st.count({nx, ny}) || ans.count({nx, ny})) {
continue;
}
ans[{nx, ny}] = ans[{x, y}];
q.push({nx, ny});
}
}
for (auto [x, y] : a) {
auto it = ans[{x, y}];
printf("%d %d\n", it.first, it.second);
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 3043;
vector<int> g[2 * N];
int n;
int used[2 * N];
int choose2(int n)
{
return n * (n + 1) / 2;
}
int count_ways(int L, int R, const vector<int>& forbidden)
{
if(L > R)
{
int ml = *min_element(forbidden.begin(), forbidden.end());
int mr = *max_element(forbidden.begin(), forbidden.end());
return choose2(ml) + choose2(mr - ml - 1) + choose2(n - 1 - mr);
}
int minl = 0;
int maxl = L;
int minr = R;
int maxr = n - 1;
for(auto x : forbidden)
{
if(L <= x && x <= R)
return 0;
else if(x < L) minl = max(minl, x + 1);
else maxr = min(maxr, x - 1);
}
return (maxl - minl + 1) * (maxr - minr + 1);
}
vector<int> cur;
void dfs(int x)
{
if(used[x] == 1) return;
used[x] = 1;
cur.push_back(x);
for(auto y : g[x]) dfs(y);
}
long long calc(const vector<int>& cycle)
{
int m = cycle.size();
int k = m / 2;
long long ans = 0;
for(int i = 0; i < m; i++)
{
int z = cycle[i];
if(z >= n) z -= n;
ans += choose2(n) * 1ll * (choose2(z) + 0ll + choose2(n - z - 1));
int l = n - 1, r = 0, L = n - 1, R = 0;
int pl = i, pr = i;
for(int j = 0; j < k; j++)
{
for(auto x : vector<int>({cycle[pl], cycle[pr]}))
{
if(x < n)
{
l = min(l, x);
r = max(r, x);
}
else
{
L = min(L, x - n);
R = max(R, x - n);
}
}
vector<int> f, F;
pl--;
if(pl < 0) pl += m;
pr++;
if(pr >= m) pr -= m;
for(auto x : vector<int>({cycle[pl], cycle[pr]}))
{
if(x < n) f.push_back(x);
else F.push_back(x - n);
}
long long add = count_ways(l, r, f) * 1ll * count_ways(L, R, F);
ans += add;
}
}
return ans;
}
int main()
{
cin >> n;
for(int i = 0; i < 2 * n; i++)
{
int x, y;
cin >> x >> y;
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
long long ans = n * 1ll * choose2(n) * 1ll * choose2(n) * 2ll;
for(int i = 0; i < n; i++)
{
if(used[i]) continue;
dfs(i);
vector<int> cycle = cur;
ans -= calc(cycle);
cur = vector<int>();
}
cout << ans / 2 << endl;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
struct node{
node *l, *r;
long long sumc, sumr;
node() : l(NULL), r(NULL), sumc(0), sumr(0) {}
node(node* l, node* r, long long sumc, long long sumr) : l(l), r(r), sumc(sumc), sumr(sumr) {}
};
node* build(int l, int r, vector<int> &c){
if (l == r - 1)
return new node(NULL, NULL, c[l], 0);
int m = (l + r) / 2;
node* nw = new node();
nw->l = build(l, m, c);
nw->r = build(m, r, c);
nw->sumc = nw->l->sumc + nw->r->sumc;
return nw;
}
node* upd(node* v, int l, int r, int pos, int val){
if (l == r - 1)
return new node(NULL, NULL, 0, val);
int m = (l + r) / 2;
node* nw = new node(v->l, v->r, 0, 0);
if (pos < m)
nw->l = upd(v->l, l, m, pos, val);
else
nw->r = upd(v->r, m, r, pos, val);
nw->sumc = nw->l->sumc + nw->r->sumc;
nw->sumr = nw->l->sumr + nw->r->sumr;
return nw;
}
long long getsum(node *v, int mult){
return v->sumc + v->sumr * mult;
}
int trav(node *v, int l, int r, int L, int R, long long &lft, int mult){
if (L >= R){
return 0;
}
if (l == L && r == R && lft - getsum(v, mult) >= 0){
lft -= getsum(v, mult);
return r - l;
}
if (l == r - 1){
return 0;
}
int m = (l + r) / 2;
int cnt = trav(v->l, l, m, L, min(m, R), lft, mult);
if (cnt == max(0, min(m, R) - L))
cnt += trav(v->r, m, r, max(m, L), R, lft, mult);
return cnt;
}
struct seg{
int l, r, lst, cur;
};
int main() {
int n;
scanf("%d", &n);
vector<int> c(n), r(n);
forn(i, n) scanf("%d%d", &c[i], &r[i]);
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y){
return c[x] / r[x] > c[y] / r[y];
});
vector<int> vals;
for (int i : ord) vals.push_back(c[i] / r[i]);
vector<node*> root(1, build(0, n, c));
for (int i : ord)
root.push_back(upd(root.back(), 0, n, i, r[i]));
vector<seg> st;
for (int i = n - 1; i >= 0; --i)
st.push_back({i, i + 1, 0, c[i]});
long long ans = 0;
int q;
scanf("%d", &q);
forn(_, q){
int t;
long long h;
scanf("%d%lld", &t, &h);
while (!st.empty()){
auto it = st.back();
st.pop_back();
if (it.r - it.l == 1){
it.cur = min((long long)c[it.l], it.cur + (t - it.lst) * 1ll * r[it.l]);
if (it.cur <= h){
h -= it.cur;
}
else{
st.push_back({it.l, it.r, t, int(it.cur - h)});
h = 0;
}
}
else{
int mx = vals.rend() - lower_bound(vals.rbegin(), vals.rend(), t - it.lst);
int res = it.l + trav(root[mx], 0, n, it.l, it.r, h, t - it.lst);
assert(res <= it.r);
if (res != it.r){
if (it.r - res > 1)
st.push_back({res + 1, it.r, it.lst, 0});
int nw = min((long long)c[res], r[res] * 1ll * (t - it.lst));
assert(nw - h > 0);
st.push_back({res, res + 1, t, int(nw - h)});
h = 0;
}
}
if (h == 0){
break;
}
}
if (st.empty()){
st.push_back({0, n, t, 0});
}
else if (st.back().l != 0){
st.push_back({0, st.back().l, t, 0});
}
ans += h;
}
printf("%lld\n", ans);
return 0;
}
I am wondering Why I didn't think about BFS on D during contest
I have a strange solution using binary search instead of BFS. Maybe it can help you when you can't think about BFS.
Let us consider the answer is $$$k$$$. The set of points whose distance between $$$(x_i,y_i)$$$ equal $$$k$$$ form a diamond. It's our job to find whether it is "full" with points given in the problem. Diamonds are annoying. We can turn it with $$$45$$$ degree to make it a square. Now we can sort the points in the order $$$x_i+y_i$$$ so every points in the same oblique line, from top left to bottom right, stay together. Then we can calculate the number of consecutive points in the way from bottom left to top right. Using rmq to calculate the smallest one and check whether it is legal, or "full" anyway. Obviously, the answer has monotonicity, so we can use binary search.
The time complexity of this algorithm is also $$$O(n\log{n})$$$.
My solution 149159334
Ah, I have a similar solution. However, I didn't think of sorting and used parallel binary search. It's so stupid of me that it's $$$O(n\log ^2 n)$$$ and got FST(MLE) at last because of my shit like code. Thank you for offering me such clear binary search solution! Hope there would be no FST forever:(
I travelled every point and did binary search on distance from point[Length of diamond], helper function includes checking that all consecutives are present in diamonds or not... I used gp_hash_table which makes it fast...
Here is my submission — 271505091
I have the same approach but can not debug why this code get WA, can anyone help me please 289695395
Felt like a complete idiot the moment my eyes fell on "BFS" in the editorial
I am wondering if there is some solution for D of nroot(n) complexity ? I got tle on test 30 because of extra log factor. If anyone did it in O(nroot(n)) ,suggest me your approach?
You can see my solution above. Enumerating the answer instead of binary search, you will get a solution of $$$O(n\sqrt{n})$$$ complexity.
My $$$O(n \sqrt{n} \log n)$$$ solution https://codeforces.net/contest/1651/submission/149151251 passed the test cases. I use binary search on vectors instead of sets to reduce the constant factor.
Problem C was easy to understand but very punishing implementation.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
Note that for problem D: Nearest Excluded Points, you need to select the constraints a bit creatively. We basically want to pack as many points as possible in a single box, so you should select
co_ord_highas a small value and choosen_high = co_ord_high^2(or a smaller number). (Remember that we should have at least $$$n$$$ distinct points in the box chosen).For example,
co_ord_high = 6andn = 36works.If you just select the parameters randomly, there's a high chance that you won't find a failing testcase.
Bug in my solution of D?
Iterate over all points, if the answer for this point is yet to found then call function rec(Pi) from this point.
Description of rec(Pi) function:
Case 1: if Pi has any adjacent cell which is not in the input, set it as the answer for Pi and return.
Case 2: if all adjacent cells of Pi is present in the input, call rec function for the adjacent cells if there answers are yet to found. And then choose answer for Pi among the 4 adjacent cells answers(choose the one with shortest Manhattan distance).
code: here
Consider all points in $$$[1,7] \times [1, 7]$$$
If you want to analyze this testcase, compute the Manhattan distance of all points using the valid output, and see which points' Manhattan distance did you not minimize.
F is too similar with CF453E.
Oh, so that's how that problem is solved! I remember seeing it ages ago and not being able to come up with the solution.
Hi everyone
In problem F, I understand until the "Then it creates a segment that covers the prefix and possibly a segment of length 1" part. Because monsters take time to go from $$$i$$$ to $$$i+1$$$, surely the visited towers in the prefix won't have equal drain times? Rather the prefix drain time sequence for monster $$$j$$$ would be something like $$$t_j,t_j+1,t_j+2,..., t_j+r_j-1$$$, where $$$r_j$$$ is the farthest tower drained? If it is so, then $$$O(n)$$$ new segments would be created instead, which breaks the complexity? Can someone please explain to me how we would maintain such a thing, or if I misunderstood? Thanks in advance
Same question, can someone please explain a little bit more in detail or give some example?
Ok, yeah, I missed one transition in the editorial.
Basically, you can imagine that each monster doesn't visit towers with intervals of one second, but just arrives at each of them at the same time $$$t$$$ following the order of towers. What does that change? For tower $$$2$$$, the time is just shifted down by $$$1$$$. For tower $$$3$$$, it's by $$$2$$$. And so on. Absolute time changed, but relative time differences between monsters remained the same. And that's what matters for the solution.
Can anyone help me calculate the time complexity of problem D? I am unable to figure out how the time complexity of the BFS solution in O(n log n).
The provided solution uses a map and a set inside the BFS iteration, this is where the $$$\log n$$$ comes from.
It seems the size of the coordinate space requires either using data structures with $$$\log n$$$ access times, or you have to use sorting and/or binary search.
Ohh... missed their complexity.. thanks!!
In problem D I tried to sort of do this dp/bfs type solution, which didn't work. What I thought is let's say I want to find the answer for some point. This point has 2 types of surrounding points. Either it has a point which is not from the set, then any neighbor point not from the set one will be the answer. Or it only has neighboring points which are from the set. In that case recursively solve the problem and collect the closest points to each of the neighbors and find which one is closest to current one. It passes only the first 8 test cases :( Help is appreciated. Not sure why my logic/implementation is flawed.
https://codeforces.net/contest/1651/submission/149762286
Failing testcase : Ticket 2185
The testcase contains all but one point in $$$[1,4] \times [1,4]$$$
Oh wow this is so cool. Thanks. Edit: Unfortunately, my answer is different but still should be correct as the difference is the same as the expected. Might try to find another test case that fails.
No, it's not correct. Don't go by the highlighted difference, the backend does have a valid checker to handle multiple correct answers.
For example, the highlighted difference tells you that 6th, 8th, 12th and 14th numbers differ.
Now, if you look at the 8th point, which is $$$(3,3)$$$, the jury's answer prints $$$(3,5)$$$ which has a Manhattan distance of 2. However, your answer prints $$$(0,3)$$$ which has a Manhattan distance of 3.
Oh, my bad. I tried comparing the distance and I guess I miscalculated. Thanks a lot for your help. This tool is really cool.
Problem F can be solved simply by chunking in $$$O(n\sqrt n)$$$
My solution
D is interesting! I want to add one more thing: the time complexity of a normal BFS implementation for a graph with N vertices and M edges is O(M), but here in the graph each vertex is connected to 4 neighbors so M <= 4*N. So the time complexity is indeed O(N*log(N)).
what may i be missing in my implementation of problem C: submission: .
help is appreciated