I tried searching for this on codeforces but couldn't find it, so here it is in case it's news for someone.
# | 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 |
I tried searching for this on codeforces but couldn't find it, so here it is in case it's news for someone.
Most people here are aware of the book "Looking for a Challenge", a collection of the best problems from contests organized or co-organized by the University of Warasw. I think it would be a nice idea for Codeforces to write a similar book including its best problems with high quality tutorials, Codeforces can make money by selling it and users will be happy with the problems.
I think the main benefit of such a book would be highlighting good old and not very popular problems, and offering an educational tutorial that can help users deeply understand them.
The same suggestion goes for other platforms with a big archive of problems like Topcoder and Opencup, and maybe non English platforms that have a collection of good problems.
I would be interested in hearing your opinions.
Hello,
The problem set is basically divided into 2 parts, very easy problems that were created for teams completely new to ICPC contests, and harder problems for experienced teams. I believe that all the problems were suitable for a div.3 contest except for problems G and L.
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a >= b);
}
#include <bits/stdc++.h>
using namespace std;
bool isp(int x){
if (x < 2)return false;
for (int i = 2; i * i <= x; ++i)if (x % i == 0)return false;
return true;
}
int main(){
int x;
scanf("%d", &x);
if (isp(x - 2))printf("%d %d\n", 2, x - 2);
else printf("-1\n");
}
Hello,
The problem set of The 2019 University of Jordan Collegiate Programming Contest will be available at the gym Jul/04/2019 17:00 (Moscow time).
The problem set consists mostly of div. 3 problems with the exception of few problems, as the majority of teams were new to ICPC contests with the exception of few div. 1 and div. 2 teams, we recommend this contest mostly for div. 3 participants, but div. 2 participants might find some problems interesting.
The problem set was prepared by Jester, Dark, Onflow and Motarack.
Thanks to MikeMirzayanov for the usual stuff, and Kilani for help with judging.
Good luck.
UPD1: Editorial link.
UPD2: Forgot to thank Namco Tales Studio for one of the ideas of the problems.
UPD3: There was a flow in the solution of problem L, it's now fixed, all AC practice solutions were rejudged, sorry for the inconvenience.
Some problems don't have a tutorial yet, those should be added later.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 1000000;
int dpfr[2][N + 1], dp[N + 1], n, gr[N + 1];
vector<int> tr[N + 1];
vector<int> cn;
int getcn(int v = 1, int p = 0){
bool ok = true;
int s = 1;
f(i, 0, tr[v].size()){
int u = tr[v][i];
if (u == p)continue;
int t = getcn(u, v);
if (t > n >> 1)ok = false;
s += t;
}
if (n - s > n >> 1)ok = false;
if (ok)cn.push_back(v);
return s;
}
int G;
void pl(int v, int p = 0){
dp[v] = dp[p] + 1;
gr[v] = G;
f(i, 0, tr[v].size()){
int u = tr[v][i];
if (u == p)continue;
pl(u, v);
}
}
ll P(int x) { return (ll)x * (x - 1) >> 1; }
void solve(){
scanf("%d", &n);
f(i, 1, n + 1)tr[i].clear();
f(j, 0, 2)f(i, 1, n + 1)dpfr[j][i] = 0;
f(i, 2, n + 1){
int t;
scanf("%d", &t);
tr[i].push_back(t);
tr[t].push_back(i);
}
cn.clear();
getcn();
ll an = P(n);
if ((int)cn.size() == 1){
pl(cn[0]);
f(i, 1, n + 1)++dpfr[0][dp[i]];
f(i, 1, n + 1)an += P(dpfr[0][i]);
}else {
G = 0;
dp[cn[1]] = 0;
pl(cn[0], cn[1]);
G = 1;
dp[cn[0]] = 0;
pl(cn[1], cn[0]);
dp[cn[0]] = 1;
f(i, 1, n + 1)++dpfr[gr[i]][dp[i]];
f(i, 1, n + 1){
an += P(dpfr[0][i]);
an += P(dpfr[1][i]);
an -= (ll)dpfr[0][i] * dpfr[1][i];
}
}
printf("%lld\n", an);
}
int main(){
int t;
scanf("%d", &t);
while (t--)solve();
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 200000, md = 1e9 + 7;
int x[N], y[N], fc[N + 1], xt[N + 1], yt[N + 1];
void solve(){
int n;
scanf("%d", &n);
n <<= 1;
f(i, 0, n)scanf("%d%d", x + i, y + i);
f(i, 0, n)xt[i] = x[i];
sort(xt, xt + n);
f(i, 0, n)yt[i] = y[i];
sort(yt, yt + n);
n >>= 1;
if (xt[n - 1] == xt[n]) { printf("0\n"); return; }
if (yt[n - 1] == yt[n]) { printf("0\n"); return; }
n <<= 1;
int a = 0, b = 0;
f(i, 0, n)if (x[i] < xt[n >> 1])y[i] < yt[n >> 1] ? ++a : ++b;
int an = (ll)fc[a] * fc[b] % md;
printf("%d\n", an);
}
int main(){
fc[0] = 1;
f(i, 1, N + 1)fc[i] = (ll)fc[i - 1] * i % md;
int t;
scanf("%d", &t);
while (t--)solve();
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 1000000, md = 1e9 + 7;
int fc[N + 1], inv[N + 1], fcin[N + 1];
void ad(int &x, int y) { if ((x += y) >= md)x -= md; }
void sb(int &x, int y) { if ((x -= y) < 0)x += md; }
int ch(int n, int r) { return (ll)fc[n] * fcin[r] % md * fcin[n - r] % md; }
void solve(){
int n;
scanf("%d", &n);
int s = 0, an = 0;
f(i, 0, n){
ad(s, ch(n, i + 1));
int t;
scanf("%d", &t);
ad(an, (ll)t * s % md);
sb(s, ch(n, i));
}
printf("%d\n", an);
}
int main(){
fc[0] = 1;
f(i, 1, N + 1)fc[i] = (ll)fc[i - 1] * i % md;
inv[1] = 1;
f(i, 2, N + 1)inv[i] = md - md / i * (ll)inv[md % i] % md;
fcin[0] = 1;
f(i, 1, N + 1)fcin[i] = (ll)fcin[i - 1] * inv[i] % md;
int t;
scanf("%d", &t);
while (t--)solve();
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const int oo = 1000000000;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define pb push_back
#define all(c) (c).begin(),(c).end()
int T,n,k;
multiset<int> A,B;
int main(){
cin>>T;
while(T--){
A.clear();
B.clear();
cin>>n>>k;
for(int x,i=0; i<n; ++i){
scanf("%d",&x);
A.insert(x);
}
for(int x,i=0; i<n; ++i){
scanf("%d",&x);
if(A.find(x)!=A.end())
A.erase(A.find(x));
else
B.insert(x);
}
if(A.empty())
puts("YES");
else if(A.size()==1 && B.size()==1 && abs(*A.begin()-*B.begin())<=k)
puts("YES");
else
puts("NO");
}
return 0;
}
Short and precise explanation by TooDumbToWin can be found here.
//#pragma comment(linker, "/STACK:16777216")
#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100000;
int n, res;
vector<vector<int> > g, o, v;
vector<vector<vector<int> > > cyc;
set<pair<int, int> > br;
int low[N], idx[N], dfs;
bool vis[N];
void DFS(int u, int p) {
low[u] = idx[u] = ++dfs;
for (auto v : g[u])
if (!idx[v]) {
DFS(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > idx[u])
br.insert({ min(u,v),max(u,v) });
}
else if (v != p)
low[u] = min(low[u], idx[v]);
}
void DFS(int u) {
if (vis[u])
return;
v.back().push_back(u);
vis[u] = true;
for (auto &w : g[u])
DFS(w);
}
vector<vector<int> > options;
void findOptions(int u, int p) {
if (g[u].size() > 3 && vis[u]) {
if (options.back()[0] == options.back().back())
options.back().pop_back();
return;
}
if (p != -1 && g[u].size() == 3)
return;
vis[u] = true;
for (auto v : g[u])
if (v != p) {
if (p == -1) {
if (vis[v])
continue;
options.push_back(vector<int>());
options.back().push_back(u);
}
options.back().push_back(v);
findOptions(v, u);
}
}
void findCycles(vector<int> &comp, vector<vector<int> > &cyc) {
for (int i = 0; i < n; ++i)
vis[i] = 0;
for (auto u : comp) {
if (vis[u])
continue;
cyc.push_back(vector<int>());
queue<int> q;
q.push(u);
vis[u] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cyc.back().push_back(u);
for (auto v : g[u])
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
if (cyc.back().size() == 1)
cyc.pop_back();
}
if (cyc.size() == 1) {
int at = -1;
for (auto x : cyc[0])
if (g[x].size() == 4) {
at = x;
break;
}
if (at != -1) {
for (int i = 0; i < n; ++i)
vis[i] = 0;
options.clear();
findOptions(at, -1);
assert(options.size() == 2);
cyc = options;
}
}
assert(cyc.size() <= 2);
}
int findClosest(const vector<int> &v, int x) {
int idx = lower_bound(v.begin(), v.end(), x) - v.begin();
int cur = 1e9;
if (idx != v.size())
cur = v[idx] - x;
if (idx != 0)
cur = min(cur, x - v[idx - 1]);
return cur;
}
int calc(int u, int p) {
int ret = findClosest(cyc[0][0], u);
for (auto v : g[u])
if (v != p && br.find({ min(u,v),max(u,v) }) != br.end())
ret = min(ret, calc(v, u));
res = min(res, ret + findClosest(v[1], u));
return ret;
}
int main()
{
int t;
scanf("%d", &t);
int totalN=0;
while (t--) {
scanf("%d", &n);
totalN+=n;
g.clear();
g.resize(n);
if (n < 1 || n>100000) {
puts("invalid n");
exit(1);
}
set<pair<int, int> > e;
for (int i = 1, a, b; i < n; ++i) {
scanf("%d%d", &a, &b);
if (a<1 || a>n || b<1 || b>n) {
puts("Invalid (a, b)");
exit(2);
}
if (a > b)
swap(a, b);
if (e.insert({ a,b }).second == false) {
puts("Multiple edges");
exit(3);
}
--a; --b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 0; i < n; ++i)
vis[i] = 0;
for (int i = 0; i < n; ++i)
idx[i] = 0;
dfs = 0;
v.clear();
cyc.clear();
for (int i = 0; i < n; ++i)
if (!vis[i]) {
v.push_back(vector<int>());
if (v.size() == 4)
break;
DFS(i);
}
if (v.size() == 4) {
puts("-1");
continue;
}
if (v.size() == 1) {
puts("0");
continue;
}
br.clear();
for (int i = 0; i < n; ++i)
if (!idx[i])
DFS(i, -1);
o = g;
for (int i = 0; i < n; ++i)
for (int j = 0; j < g[i].size(); ++j)
if (br.find({ min(i,g[i][j]),max(i,g[i][j]) }) != br.end()) {
g[i][j] = g[i].back();
g[i].pop_back();
--j;
}
cyc.resize(v.size());
for (int i = 0; i < v.size(); ++i)
findCycles(v[i], cyc[i]);
for (auto &cycles : cyc)
for (auto &x : cycles) {
sort(x.begin(), x.end());
assert(x.size() >= 3);
}
res = 1e9;
if (v.size() == 2) {
if (cyc[0].empty()) {
v[0].swap(v[1]);
cyc[0].swap(cyc[1]);
}
sort(v[1].begin(), v[1].end());
g = o;
for (auto x : cyc[0][0])
calc(x, -1);
printf("%d\n", res);
continue;
}
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
if (cyc[j].size() < cyc[j + 1].size()) {
v[j].swap(v[j + 1]);
cyc[j].swap(cyc[j + 1]);
}
if (cyc[0].size() == 2) {
pair<int, int> A(1e9, 1e9), B(1e9, 1e9);
for (int it = 1; it <= 2; ++it) {
for (int i = 0; i < v[it].size(); ++i) {
A.first = min(A.first, findClosest(cyc[0][0], v[it][i]));
A.second = min(A.second, findClosest(cyc[0][1], v[it][i]));
}
swap(A, B);
}
res = min(A.first + B.second, A.second + B.first);
printf("%d\n", res);
continue;
}
if (!cyc[1].empty()) {
for (int i = 0; i < 2; ++i) {
int curA = 1e9;
for (auto x : v[2])
curA = min(curA, findClosest(cyc[i][0], x));
int curB = 1e9;
for (auto x : v[2])
curB = min(curB, findClosest(cyc[!i][0], x));
for (auto x : v[i])
curB = min(curB, findClosest(cyc[!i][0], x));
res = min(res, curA + curB);
}
printf("%d\n", res);
continue;
}
options.clear();
for (int i = 0; i < n; ++i)
vis[i] = 0;
for (auto u : cyc[0][0])
if (g[u].size() > 2) {
findOptions(u, -1);
break;
}
assert(options.size() == 3);
for (auto &x : options)
sort(x.begin(), x.end());
int cur[2][3] = {};
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 3; ++j) {
cur[i][j] = 1e9;
for (auto x : v[i + 1])
cur[i][j] = min(cur[i][j], findClosest(options[j], x));
}
for (int i = 0; i < 3; ++i) {
res = min(res, cur[0][i] + min(cur[1][!i], cur[1][3 - i - !i]));
res = min(res, cur[1][i] + min(cur[0][!i], cur[0][3 - i - !i]));
}
printf("%d\n", res);
}
cerr<<totalN<<endl;
assert(totalN<=5000000);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
typedef vector<pair<int, int> > vp;
int const N = 100000, inf = 1e9;
vp g[N + 1];
vector<int> cy[N];
int vis[N + 1], vs = 1, n;
struct CM{
vector<set<int> > v;
set<int> all;
CM(){}
bool operator <(CM const &o)const { return v.size() > o.v.size(); }
bool in(int x) { return all.find(x) != all.end(); }
};
bool in(int x, set<int> const &st) { return st.find(x) != st.end(); }
int getCost(int x, set<int> const &st){
set<int>::iterator it = st.lower_bound(x);
int an = it == st.end() ? inf : *it - x;
if (it == st.begin())return an;
--it;
return min(an, x - *it);
}
int getCost(set<int> const &a, set<int> const &b){
int an = inf;
set<int>::iterator ita = a.begin(), itb = b.begin();
while (ita != a.end() && itb != b.end()){
an = min(an, abs(*ita - *itb));
if (*ita < *itb)++ita; else ++itb;
}
return an;
}
vector<CM> cm;
map<vector<int>, int> mp;
int getId(vector<int> const &v){
map<vector<int>, int>::iterator it = mp.find(v);
if (it == mp.end()){
int an = mp.size();
cm.back().v.push_back(set<int>());
return mp[v] = an;
}
return it->second;
}
int C;
vp build(int v, int p = 0){
vp c;
vis[v] = 0;
f(i, 0, g[v].size()){
int u = g[v][i].first;
if (u == p)continue;
if (vis[u] == 0)c.push_back(make_pair(C, u)), cy[g[v][i].second].push_back(C++);
else {
vp t = build(u, v);
while (t.size())c.push_back(t.back()), cy[g[v][i].second].push_back(t.back().first), t.pop_back();
}
}
f(i, 0, c.size())if (c[i].second == v)c.erase(c.begin() + i), --i;
vis[v] = 1;
return c;
}
void geted(int v){
vis[v] = 0;
cm.back().all.insert(v);
f(i, 0, g[v].size()){
int u = g[v][i].first;
int id = g[v][i].second;
if (!cy[id].empty()){
sort(cy[id].begin(), cy[id].end());
int cid = getId(cy[id]);
cm.back().v[cid].insert(v);
cm.back().v[cid].insert(u);
cy[id].clear();
}
if (vis[u] == 0)continue;
geted(u);
}
}
void visi(int v){
if (vis[v] == vs)return;
vis[v] = vs;
f(i, 0, g[v].size())visi(g[v][i].first);
}
int go(int v, int p, int mn = inf){
int an = mn + getCost(v, cm[0].v[0]);
mn = min(mn, getCost(v, cm[1].all));
f(i, 0, g[v].size()){
int u = g[v][i].first;
if (u == p)continue;
an = min(an, go(u, v, mn));
}
return an;
}
int solve(){
scanf("%d", &n);
f(i, 1, n + 1)g[i].clear();
f(i, 1, n)cy[i].clear();
f(i, 1, n){
int a, b;
scanf("%d%d", &a, &b);
g[a].push_back(make_pair(b, i));
g[b].push_back(make_pair(a, i));
}
int cmp = 0;
f(i, 1, n + 1)vis[i] = inf;
f(i, 1, n + 1)if (vis[i] > vs)++vs, visi(i), ++cmp;
if (cmp == 1)return 0;
if (cmp > 3)return -1;
cm.clear();
f(i, 1, n + 1)if (vis[i] > 1){
cm.push_back(CM());
mp.clear();
build(i);
geted(i);
}
sort(cm.begin(), cm.end());
int an = inf;
if (cmp == 2){
an = getCost(cm[0].v[0], cm[1].all);
f(i, 1, n + 1)if (in(i, cm[0].v[0]))f(j, 0, g[i].size())if (!in(g[i][j].first, cm[0].v[0]))an = min(an, go(g[i][j].first, i));
return an;
}
if (cm[0].v.size() > 1){
f(i, 0, cm[0].v.size())f(j, 0, cm[0].v.size())if (i != j)an = min(an, getCost(cm[0].v[i], cm[1].all) + getCost(cm[0].v[j], cm[2].all));
return an;
}
int a = getCost(cm[0].v[0], cm[1].all);
int b = getCost(cm[0].v[0], cm[2].all);
int c = getCost(cm[1].v[0], cm[0].all);
int d = getCost(cm[1].v[0], cm[2].all);
return min(b + min(c, d), d + min(a, b));
}
int main(){
int t;
scanf("%d", &t);
while (t--)printf("%d\n", solve());
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
int const N = 200000;
double const eps = 1e-7;
int n, a, q;
long double an[N];
bool eq(double a, double b) { return abs(a - b) <= eps; }
struct V{
double x, y;
V(double a = 0.0, double b = 0.0):x(a), y(b) {}
void sc() { scanf("%lf%lf", &x, &y); }
double operator |(V const &o)const {
return x * o.y - o.x * y;
}
bool operator <(V const &o)const {
if (eq(x, o.x))return y < o.y;
return x < o.x;
}
V operator -(V const &o)const { return V(x - o.x, y - o.y); }
void pr() { printf("%lf %lf\n", x, y); }
}st[N];
pair<V, int> qu[N];
bool cmpr(V const &a, V const &b){
V v1 = a - st[0], v2 = b - st[0];
return (v1 | v2) < -eps;
}
vector<V> ch;
void getCh(){
sort(st + 1, st + n, cmpr);
ch.push_back(st[0]);
f(i, 1, n){
while ((int)ch.size() > 1 && (st[i] - ch.back() | ch.back() - ch[ch.size() - 2]) < eps)ch.pop_back();
ch.push_back(st[i]);
}
}
double getx(double xs, double z, double xq){
return xs + z / (z + a) * (xq - xs);
}
int left(int x) { return x ? x - 1 : ch.size() - 1; }
int right(int x) { return x + 1 == (int)ch.size() ? 0 : x + 1; }
void solve(){
scanf("%d%d", &n, &a);
f(i, 0, n)st[i].sc();
double mnz = st[0].y, mxz = st[0].y;
f(i, 1, n){
mnz = min(mnz, st[i].y);
mxz = max(mxz, st[i].y);
}
f(i, 0, n)st[i].y = a - st[i].y;
sort(st, st + n);
ch.clear();
getCh();
scanf("%d", &q);
f(i, 0, q){
qu[i].first.sc();
qu[i].second = i;
}
sort(qu, qu + q);
int lp = 0, rp = 0;
f(i, 0, ch.size())ch[i].y = a - ch[i].y;
while (ch[right(rp)].y < ch[rp].y)rp = right(rp);
while (ch[left(lp)].y > ch[lp].y)lp = left(lp);
f(i, 0, q){
while (true){
int ni = right(lp);
if (getx(ch[ni].x, ch[ni].y, qu[i].first.x) < getx(ch[lp].x, ch[lp].y, qu[i].first.x))lp = ni;
else break;
}
while (true){
int ni = right(rp);
if (getx(ch[ni].x, ch[ni].y, qu[i].first.x) > getx(ch[rp].x, ch[rp].y, qu[i].first.x))rp = ni;
else break;
}
double x = abs(getx(ch[rp].x, ch[rp].y, qu[i].first.x) - getx(ch[lp].x, ch[lp].y, qu[i].first.x));
double y = getx(0, mxz, qu[i].first.y) - getx(0, mnz, qu[i].first.y);
an[qu[i].second] = (long double) x * y;;
}
f(i, 0, q)printf("%.10lf\n", (double)an[i]);
}
int main(){
int t;
scanf("%d", &t);
while (t--)solve();
}
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef pair<int,int> pii;
typedef long long ll;
const int N = 10000+1;
int n , q,T;
vector<pii> g[N];
ll ans = 0,in[N],out[N];
void dfs(int u , int p, int w){
for(auto v : g[u]){
if(v.first==p)continue;
dfs(v.first,u,v.second);
in[u] += in[v.first];
out[u] += out[v.first];
}
ans += 1ll*abs(in[u]-out[u])*w;
}
int main(){
cin >> T;
while(T--){
cin >> n;
ans = 0;
for (int i = 1; i <= n; ++i){
g[i].clear();
in[i] = out[i] = 0;
}
for (int u , v,w , i = 0 ; i < n-1 ; ++i){
scanf("%d%d%d",&u,&v,&w);
g[u].pb(mp(v,w));
g[v].pb(mp(u,w));
}
cin >> q;
for(int u , v , i = 0 ; i < q ; ++i){
scanf("%d%d",&u,&v);
out[u]++;
in[v]++;
}
dfs(1,-1,0);
cout << ans << endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1001;
int n , l , dp[N][N],T;
pii a[N];
int calc(int idx , int time){
if(idx > n || time > l+1)return -N;
if(idx == n && time == l+1)return 0;
int &ret = dp[idx][time];
if(ret != -1)return ret;
ret = max(calc(idx,time+1),calc(idx+1,time));
if(time >= a[idx].first)
ret = max(ret,1+calc(idx+1,time+a[idx].second));
return ret;
}
int main(){
cin >> T;
while(T--){
memset(dp,-1,sizeof dp);
cin >> n >> l;
for (int i = 0; i < n; ++i)scanf("%d%d",&a[i].first,&a[i].second);
printf("%d\n",calc(0,1));
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n , m , r,T;
vector< vector<int> > g;
multiset< pii > hv[100002];
multiset<pii> cur;
int
ALL_PEOPLE = 0;
bool check(int md){
cur.clear();
for(int i = 0 ; i < m ; ++i)hv[i].clear();
for(int j = 0 ; j < md ; ++j)cur.insert(make_pair(-2,m));
for(int j = 0 ; j < n ; ++j){
for (int i = 0; i < m; ++i){
int rem = g[i][j];
vector<int> nw;
while(rem > 0){
assert(cur.size() == md);
if(hv[i].size()){
pii fr = *--hv[i].end();
hv[i].erase(--hv[i].end());
cur.erase(cur.find(fr));
cur.insert(make_pair(j,i));
nw.push_back(j);
}else{
pii em = *cur.begin();
if(em.first >= j-1)return false;
cur.erase(cur.begin());
if(em.second != m)
hv[em.second].erase(hv[em.second].find(em));
cur.insert(make_pair(j,i));
nw.push_back(j);
}
rem -= r;
}
for(int k = 0 ; k < nw.size();++k){
hv[i].insert(make_pair(nw[k],i));
}
}
}
return 1;
}
int main(){
// freopen("2.in","r",stdin);
// freopen("2.out","w",stdout);
cin >> T;
while(T--){
scanf("%d%d%d",&m,&n,&r);
g.clear();
g.resize(m);
int total = 0;
for (int i = 0; i < m; ++i){
g[i].resize(n);
for(int j = 0 ; j < n ; ++j){
scanf("%d",&g[i][j]);
total += g[i][j];
}
}
ALL_PEOPLE += total;
int lo = 1, hi = total,best = -1;
while(lo <= hi){
int md = (lo + hi)/2;
if(check(md)){
best = md;
hi = md-1;
}else{
lo=md+1;
}
}
cout << best << endl;
}
//cout << "ALL PEOPLE = " << ALL_PEOPLE << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const int oo = 1000000000;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define pb push_back
#define all(c) (c).begin(),(c).end()
int n,m,cmp[2*N],t;
vi g[2*N],rg[2*N];
bool vis[2*N];
int Not(int x){
return x>=n?x-n:x+n;
}
void addEdge(int a, int b){
g[Not(b)].pb(a);
g[Not(a)].pb(b);
rg[a].pb(Not(b));
rg[b].pb(Not(a));
}
stack<int> st;
void dfs(int u, vi g[N], int cc=-1){
vis[u]=1;
for(int i=0; i<g[u].size(); ++i)
if(!vis[g[u][i]])
dfs(g[u][i], g, cc);
if(cc==-1){
st.push(u);
}else{
cmp[u]=cc;
}
}
void get(int &x, int l, int r){
assert(scanf("%d",&x)==1);
assert(x>=l && x<=r);
}
int main(){
get(t,1,1000);
while(t--){
get(n, 1, 100000);
get(m, 0, 100000);
for(int a,b,c,i=0; i<m; ++i){
get(a,1,n);
get(b,1,n);
assert(a!=b);
get(c,0,1);
--a;--b;
if(c)
addEdge(Not(a), Not(b));
addEdge(a, b);
}
for(int i=0; i<2*n; ++i)
vis[i]=0;
for(int i=0; i<2*n; ++i)
if(!vis[i])
dfs(i,g);
for(int i=0; i<2*n; ++i)
vis[i]=0;
int cc=0;
while(!st.empty()){
int u=st.top();
st.pop();
if(vis[u])continue;
dfs(u, rg, cc++);
}
bool win=1;
for(int i=0; i<n && win; ++i){
if(cmp[i]==cmp[Not(i)])
win=0;
}
if(win)
puts("YES");
else
puts("NO");
for(int i=0; i<2*n; ++i){
g[i].clear();
rg[i].clear();
}
}
return 0;
}
Hello Everyone!
The problem set of AICCSA, which was held last Saturday, will be available in Codeforces Gym tomorrow, Oct/30/2018 19:00 (Moscow time)
The problems were prepared by Hasan0540, Hiasat, Dark and Motarack. We would like to thank MikeMirzayanov for Codeforces and Polygon, and ifsmirnov for Jngen.
The contest duration is 5 hours, and it is intended for teams of three. We believe the difficulty is suitable for people with rating in the range [1600, 2600].
We hope that you enjoy the problems, and we welcome any feedback.
UPD: Tutorial link
Name |
---|