vovuh's blog

By vovuh, history, 3 years ago, translation,

976A - Minimum Binary Number

Editorial
Solution (Vovuh)
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int n;
string s;
cin >> n >> s;
if (n == 1) {
cout << s << endl;
} else {
int cnt0 = 0;
for (int i = 0; i < n; ++i)
cnt0 += s[i] == '0';
cout << 1;
for (int i = 0; i < cnt0; ++i)
cout << 0;
cout << endl;
}

return 0;
}


976B - Lara Croft and the New Game

Editorial
Solution (PikMike)
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int n, m;
long long k;

int main() {
scanf("%d%d%lld", &n, &m, &k);
if (k < n){
printf("%lld 1\n", k + 1);
return 0;
}
k -= n;
long long row = k / (m - 1);
printf("%lld ", n - row);
if (row & 1)
printf("%lld\n", m - k % (m - 1));
else
printf("%lld\n", k % (m - 1) + 2);
return 0;
}


976C - Nested Segments

Editorial
Solution (PikMike)
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second

using namespace std;

typedef pair<int, int> pt;

const int N = 300 * 1000 + 13;

int n;
pair<pt, int> a[N];

int main() {
scanf("%d", &n);
forn(i, n){
scanf("%d%d", &a[i].x.x, &a[i].x.y);
a[i].y = i + 1;
}

sort(a, a + n, [&](pair<pt, int> a, pair<pt, int> b){if (a.x.x != b.x.x) return a.x.x < b.x.x; return a.x.y > b.x.y;});

set<pt> cur;
forn(i, n){
while (!cur.empty() && cur.begin()->x < a[i].x.x)
cur.erase(cur.begin());
if (!cur.empty() && (--cur.end())->x >= a[i].x.y){
printf("%d %d\n", a[i].y, (--cur.end())->y);
return 0;
}
cur.insert({a[i].x.y, a[i].y});
}

puts("-1 -1");
return 0;
}


976D - Degree Set

Editorial
Solution (PikMike)
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

typedef pair<int, int> pt;

const int N = 100 * 1000 + 13;

int n;
vector<int> d;
vector<int> g[N];

vector<pt> construct(int st, vector<int> d){
if (d.empty())
return vector<pt>();

vector<pt> res;
forn(i, d[0])
for (int j = st + i + 1; j <= st + d.back(); ++j)
res.push_back({st + i, j});

int nxt = st + d[0];
for (int i = 1; i < int(d.size()); ++i)
d[i] -= d[0];
d.erase(d.begin());
if (!d.empty())
d.pop_back();

auto tmp = construct(nxt, d);
for (auto it : tmp)
res.push_back(it);

return res;
}

int main() {
scanf("%d", &n);
d.resize(n);
forn(i, n)
scanf("%d", &d[i]);
auto res = construct(0, d);
printf("%d\n", int(res.size()));
for (auto it : res)
printf("%d %d\n", it.first + 1, it.second + 1);
return 0;
}


976E - Well played!

Editorial
Solution (Ajosteen)
#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 9;

int n, a, b;
int hp[N], dmg[N];

bool cmp(int i, int j){
if(hp[i] - dmg[i] != hp[j] - dmg[j])
return hp[i] - dmg[i] > hp[j] - dmg[j];
return i < j;
}

int get(int id){
return  hp[id] > dmg[id]? hp[id] : dmg[id];
}

int main(){
scanf("%d %d %d", &n, &a, &b);
for(int i = 0; i < n; ++i)
scanf("%d %d", hp + i, dmg + i);

b = min(b, n);
vector <int> p(n);
for(int i = 0; i < n; ++i) p[i] = i;
sort(p.begin(), p.end(), cmp);
long long res = 0, sum = 0;
for(int i = 0; i < n; ++i){
int id = p[i];
if(i < b) sum += get(id);
else sum += dmg[id];
}
res = sum;

if(b == 0){
printf("%lld\n", res);
return 0;
}

long long x = (1LL << a);
for(int i = 0; i < n; ++i){
int id = p[i];
long long nres = sum;
if(i < b){
nres -= get(id);
nres += hp[id] * x;
res = max(res, nres);
}
else{
nres -= dmg[id];
nres += hp[id] * x;
int id2 = p[b - 1];
nres -= get(id2);
nres += dmg[id2];
res = max(res, nres);

}
}

printf("%lld\n", res);
return 0;
}


976F - Minimal k-covering

Editorial
#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

#define sz(a) int((a).size())
#define x first
#define y second

const int INF = int(1e9);
const int N = 4221;

struct edge {
int to, c, f, id;

edge(int to = 0, int c = 0, int f = 0, int id = -1) : to(to), c(c), f(f), id(id) {}
};

vector<edge> es;
vector<int> g[N];

void add_edge(int fr, int to, int cap, int id) {
g[fr].push_back(sz(es));
es.emplace_back(to, cap, 0, id);
g[to].push_back(sz(es));
es.emplace_back(fr, 0, 0, id);
}

int pw[N];
int n1, n2, m;

if(!(cin >> n1 >> n2 >> m))
return false;

fore(id, 0, m) {
int u, v;
assert(cin >> u >> v);
u--, v--;

pw[u]++;
pw[n1 + v]++;

add_edge(u, n1 + v, 1, id);
}
return true;
}

int d[N], q[N], hd, tl;
inline bool bfs(int s, int t, int n) {
fore(i, 0, n)
d[i] = INF;
hd = tl = 0;

d[s] = 0;
q[tl++] = s;
while(hd != tl) {
int v = q[hd++];
if(v == t)
break;

for(int id : g[v]) {
if(es[id].c - es[id].f == 0)
continue;

int to = es[id].to;
if(d[to] > d[v] + 1) {
d[to] = d[v] + 1;
q[tl++] = to;
}
}
}
return d[t] < INF;
}

int nxt[N];

int dfs(int v, int t, int mx) {
if(v == t) return mx;
if(mx == 0) return 0;

int sum = 0;
for(; nxt[v] < sz(g[v]); nxt[v]++) {
int id = g[v][nxt[v]];
int rem = es[id].c - es[id].f;
int to = es[id].to;

if(rem == 0 || d[to] != d[v] + 1)
continue;

int cur = 0;
if((cur = dfs(to, t, min(mx - sum, rem))) > 0) {
es[id].f += cur;
es[id ^ 1].f -= cur;
sum += cur;
}

if(sum == mx)
break;
}
return sum;
}

inline int dinic(int s, int t, int n) {
int mf = 0;
while(bfs(s, t, n)) {
fore(i, 0, n)
nxt[i] = 0;

int cf = 0;
while((cf = dfs(s, t, INF)) > 0)
mf += cf;
}
return mf;
}

vector<int> res[N];

inline void getCert(int k) {
fore(v, 0, n1) {
for(int id : g[v]) {
if(es[id].to < n1 || es[id].to >= n1 + n2)
continue;
assert(es[id].c > 0);
if(es[id].f > 0)
continue;

res[k].push_back(es[id].id);
}
}
}

void solve() {
int cnt = *min_element(pw, pw + n1 + n2);

int s = n1 + n2; int t = s + 1;
fore(i, 0, n1)
add_edge(s, i, pw[i] - cnt, -1);
fore(i, n1, n1 + n2)
add_edge(i, t, pw[i] - cnt, -1);

int mf = 0, mn = cnt;
while(mn >= 0) {
mf += dinic(s, t, n1 + n2 + 2);
getCert(mn);

if(mn > 0) {
for (int id : g[s]) {
assert(es[id].id < 0);
assert((id & 1) == 0);
es[id].c++;
}
for (int id : g[t]) {
assert(es[id].id < 0);
assert(es[id].c == 0);
es[id ^ 1].c++;
}
}
mn--;
}

fore(i, 0, cnt + 1) {
printf("%d ", sz(res[i]));
for(int id : res[i])
printf("%d ", id + 1);
puts("");
}
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif

solve();
}
return 0;
}


• +27

 » 3 years ago, # |   0 An nlogn solution itself gave tle for me in C.nested segments question using c++ default sort function, is there any one like this.http://codeforces.com/contest/976/submission/37770261
•  » » 3 years ago, # ^ |   +6 It is your cmpr function.
•  » » » 3 years ago, # ^ |   0 but exactly why it created problem??
•  » » » » 3 years ago, # ^ |   0 it can't make rgt in increasing order
•  » » 3 years ago, # ^ |   0 I am confused too.. what's the problem here? :/ I have submitted very much the same solution as yours and I have got Correct Answer!http://codeforces.com/contest/976/submission/37790630
•  » » » 3 years ago, # ^ |   0 See this
•  » » 3 years ago, # ^ |   +8 Never use equal sign in compare function
•  » » 3 years ago, # ^ | ← Rev. 2 →   +13 you must use <,> operator with compare function,not <=,>=. because it can occur cycle in stl sorting.
•  » » 3 years ago, # ^ |   0 When in doubt, read language specifications.Here is the documentation for sort. You can see that the 3rd argument needs to define a strict weak ordering. You can read about the mathematical concept, or you can go directly to the cpprefence of Compare.
 » 3 years ago, # |   0 976D — Degree Set ,Graph for some (d1, d2, ..., dk) need to be sorted?
•  » » 3 years ago, # ^ |   +17 What do you mean by "sorted"? My checker takes the list of edges you output and calculates the degree set to compare it with the given one.
•  » » » 3 years ago, # ^ |   0 problem Bcan You please explain why we don't consider the case, when we do -1 to k, by decreasing height of our final answer?
•  » » » » 3 years ago, # ^ |   0 We transition from the number of steps Lara made to the number of cells she visited. You can see that she visits (m - 1) cells of the bottom row, then (m - 1) cells of the row above it and so on. And the formula tells you which one of these cells was the (k - n)-th.
 » 3 years ago, # |   0 Alternative solution for F: For a fixed degree d connect a new source vertex s with each vertex of U with capacity ∞ and demand d, and connect every vertex of V with capacity ∞ and demand d to a new sink vertex t. And then find the minimal flow as described in the e-maxx-eng article Flow with demands (add two more vertices to get rid of the demands, and do a binary search on the minimal flow value).This has a worse complexity than the editorial solution (due to the binary search and a slightly bigger network), but my implementation 37840246 still runs in under 1 second using Edmond-Karp.
 » 3 years ago, # |   +1 Is anyone getting WA on test case 10 of E well played :| http://codeforces.com/contest/976/submission/37842203 here is my submission
•  » » 3 years ago, # ^ |   0
•  » » 3 years ago, # ^ |   0 I getted too, you are wrong because you are trying to maximize hp[i] * 2^a — dmg[i], but its not correct. For example you have got hp[i] * 2^a — dmg[i] > hp[j] * 2^a — dmg[j], but dmg[i] + hp[j] * 2^a — dmg[j] can be larger then dmg[j] + hp[i] * 2^a — dmg[i] and you should use your a spells on j but not i.
•  » » » 3 years ago, # ^ |   0 yeah so that is why I sorted (passed compare function sorted by first increasing hp[i] * 2^a the dec dmg[i] ?
 » 3 years ago, # |   0 How is solution for E nlogn? If we precalc powers of two it is O(n) isnt it?
•  » » 3 years ago, # ^ |   +8 You need to sort your array complexity of sorting — nlogn.
•  » » » 3 years ago, # ^ |   0 Wow...wrote same solution after contest but now I forgot you need to sort hahaha
 » 3 years ago, # |   0 Changed >= to > om sort, and from Runtime error in test 84 got accepted.. Can someone explain why?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1
 » 3 years ago, # |   0 Can you please add a link to this editorial that is accessible from the contest? I cannot access the editorial from here.
•  » » 3 years ago, # ^ |   0 Done
 » 3 years ago, # |   0 first time implemented IdentityHashMap.
 » 3 years ago, # | ← Rev. 8 →   0 Why is this wrong for question no. D? Input 3 2 3 4 Participant's output 6 1 2 1 3 1 4 1 5 2 3 2 4 
•  » » 3 years ago, # ^ |   0 Degree of vertex 5 in your graph is 1 whereas the given degree set is {2, 3, 4}
 » 2 years ago, # |   0 In problem F, why is the complexity O((n + m)2) ?
 » 20 months ago, # |   0 how to calculate dinic's complexity in problem F?why not n*n*m?
 » 18 months ago, # |   0 ME:making 100 of test cases for B problem codeforces: a single formula for all the cases ME: pikachu face INNER ME: crying
 » 15 months ago, # | ← Rev. 2 →   0 I do not understand the correctness of proof of problem D. How do we know that there is a solution for the sub-problem $(d_2 - d_1, d_3 - d_1, \cdots, d_{k - 1} - d_1)$. awoo Could you please help me with it?