Inspired by ivan100sic's problem list blog, I'll pick 10 nontrivial-seeming recent POI (Polish Olympiad in Informatics) problems that I haven't solved and track my progress here.
It seems to me that POI is better suited for this format as their editorials are quite difficult to find (if possible at all).
While Ivan's original challenge was supposed to last an entire year, I'm not nearly as patient, so I won't look for editorials only until February 1st (in just over 2 weeks). Hopefully I'll have completed at least 80% by that time. Until then, GLHF!!!
The List:
- Multidrink 2013 [Solved Jan 15]
Fun-ness:
5/10
Comments
My thought process on this problem went like "ew this is disgusting implementation" => "oh actually it's not so bad" => "oh no it's actually disgusting implementation"
But I actually enjoyed this one more than most heavy casework/implementation problems because, while you have to be very careful about the dp transitions and especially their order, it's not too hard to prove once you have it written out.
my ugly code (if ppl not doing the challenge want to take a peek?)
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"BRAK\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 1e6+5;
vector<int> pth; // path from s to t!
int dp1[maxn], dp2[maxn]; // maximum number of free steps after {1: stomping here, 2: being here but not stomping}
vector<pii> run1[maxn], run2[maxn]; // for restoring answer
bool onpth[maxn];
vector<pii> g[maxn]; // {to, edge id}
bool findpth(int v, int T, int p) {
if (v == T) {
pth.pb(T); return 1;
}
for (pii u : g[v]) {
if (u.f != p && findpth(u.f,T,v)) {
pth.pb(v); onpth[u.s] = 1; return 1;
}
}
return 0;
}
#define piii pair<pii,int>
void dfs(int v, int par) {
dp2[v] = 3; // i'm so free i haven't even stomped yet
dp1[v] = 2; // yarrr i'm freshly stomped mmm
run1[v].pb({v, -1});
vector<piii > us;
for (pii p : g[v]) {
int u = p.f;
if (!onpth[p.s] && p.f != par) {
// tree edge!
dfs(u,v);
us.pb({{dp1[u],dp2[u]}, u});
}
}
sort(ALL(us), [&](piii a, piii b) {
if (a.f.f == 2 || b.f.f == 2) return a.f.f > b.f.f; // i want to work with walking the leaf nodes first
if (a.f.f != b.f.f) return a.f.f > b.f.f;
if (a.f.f == 1) {
return a.f.s < b.f.s; // waste a bad dp
}
return a.f.s < b.f.s; // doesn't matter at this point ig
} );
for (auto rr : us) {
int u = rr.s;
if (dp2[v] == 3){ // work with node free, this time we haven't stomped yet
if (dp1[u] == 2) {
// it's a leaf or something, anyways we can ignore it after stomping and come back
run2[v].pb({u,1});
goto dp2done;
}else{
if (dp1[u]==1) { // i stomp it and come back?
run2[v].pb({u,1});
run2[v].pb({v,-1});
dp2[v] = 2;
goto dp2done;
}else { // all hopeless, i have to stomp myself first
run2[v].pb({v,-1});
dp2[v] = 2;
}
}
}
if (dp2[v] == 2) {
// im forced to have stomped here now
// this will be equivalent to a later one
if (dp2[u] == 2) {
run2[v].pb({u,2});
dp2[v] = 1;
goto dp2done;
}else{
dp2[v] = 0;
goto dp2done;
}
}
if (dp2[v] == 1) {
if (dp1[u] == 2) {
run2[v].pb({u,1});
dp2[v] = 1;
goto dp2done;
}else{
dp2[v] = 0;
goto dp2done;
}
}
dp2done:;
}
sort(ALL(us), [&](piii a, piii b) {
return a.f.f < b.f.f; // you want to waste a bad dp1 early on
} );
for (auto rr : us) {
int u = rr.s;
if (dp1[v] == 2) {
if (dp2[u] == 2) {
run1[v].pb({u,2});
dp1[v] = 1;
goto dp1done;
}else{
dp1[v] = 0;
goto dp1done;
}
}
if (dp1[v] == 1) {
if (dp1[u] == 2) {
run1[v].pb({u,1});
dp1[v] = 1;
goto dp1done;
}else{
dp1[v] = 0;
goto dp1done;
}
}
dp1done:;
}
if (dp2[v] == 3) {
run2[v].pb({v, -1});
dp2[v] = 2;
} // no point in being super free now, 2 is good enough
assert(dp2[v] >= dp1[v]);
}
vector<int> re;
void prt(int v, int tp) {
if (tp == -1) {
re.pb(v); return;
}
for (pii p : tp==1?run1[v]:run2[v]) {
prt(p.f, p.s);
}
}
signed main(){
IOS();
int n; cin>>n;
REP(i,n-1) {
int a,b; cin>>a>>b;
g[a].pb({b,i});
g[b].pb({a,i});
}
findpth(1, n, -1);
reverse(ALL(pth));
for (int x : pth) bug(x);
int can = 1;
vector<int> tp(SZ(pth));
REP(i, SZ(pth)) {
tp[i] = can;
int v = pth[i];
dfs(v, -1);
bug(v, can);
if (can == 0) GG();
if (i == SZ(pth)-1 && can == 1 && dp1[v] != 2) GG(); // can't stomp the last one first
bug(v, dp1[v], dp2[v]);
if (can == 2) {
can = dp2[v];
}else{
can = dp1[v];
}
}
bug(can);
if (can == 0 || can == 1) GG();
REP(i, SZ(pth)) {
prt(pth[i], tp[i]);
}
for (int x : re) cout<<x<<endl;
}
- Snake 2014
- Arkanoid 2016 [Solved Jan 16]
Fun-ness:
4/10
Comments
Another heavy implementation problem. Actually, the implementation isn't terrible (if you split the grid into 2N x 2M nodes), but I spent a long time debugging because I didn't realize that most exGCD implementations can't handle negative numbers well...
more ugly code
#include <bits/stdc++.h>
//#undef BALBIT
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b) % mo;
}
const int maxn = 1e5+5;
int n,m,npts;
pii flip(pii pt, pii dir) {
if (dir.f == -1 && pt.f) {
pt.f = 4*m-pt.f;
}
if (dir.s == -1 && pt.s) {
pt.s = 4*n-pt.s;
}
return pt;
}
struct point{
};
vector<pair<pii, pii> > from[maxn]; // x=1 or 3, a-value
ll euclid(ll a, ll b, ll &x, ll &y) {
if (b) { ll d = euclid(b, a % b, y, x);
return y -= a/b * x, d; }
return x = 1, y = 0, a;
}
pii get(pii p) {
int piff = p.f - p.s; bug(piff);
int x = 0;
if ((piff-1) % 4 == 0) x = 1;
else x = 3;
pii k;
euclid(-m,n,k.f,k.s);
if (k.f * -m + k.s * n < 0) {
k.f *= -1; k.s *= -1;
}
int RHS = (piff - x) / 4; assert((piff-x)%4==0);
k.f *= RHS; k.s *= RHS;
ll a = p.s + k.s * 4 * n; a %= (4*n*m);
if (a < 0) a += 4*n*m;
bug(p.f, p.s, x, a);
return {x, a};
}
ll smat(vector<pii> var){
array<set<pair<pii, pii> >, 4> s; // for the two values of x shift
REP(i,npts) {
int x,y; tie(x,y) = var[i]; x*=2; y*=2; --x; --y;
vector<pii> v;
vector<pii> vf;
if (x-1!=0){
// left edge
v.pb(flip({x-1,y}, {1,-1}));
v.pb(flip({x-1,y}, {1,+1}));
vf.pb(flip({x-1,y}, {-1,-1}));
vf.pb(flip({x-1,y}, {-1,+1}));
}
if (x+1!=m*2){
// right edge
v.pb(flip({x+1,y}, {-1,-1}));
v.pb(flip({x+1,y}, {-1,+1}));
vf.pb(flip({x+1,y}, {1,-1}));
vf.pb(flip({x+1,y}, {1,+1}));
}
if (y+1!=n*2){
// top edge
v.pb(flip({x,y+1}, {1,-1}));
v.pb(flip({x,y+1}, {-1,-1}));
vf.pb(flip({x,y+1}, {1,1}));
vf.pb(flip({x,y+1}, {-1,1}));
}
if (y-1!=0){
// bottom edge
v.pb(flip({x,y-1}, { 1,+1}));
v.pb(flip({x,y-1}, {-1,+1}));
vf.pb(flip({x,y-1}, { 1,-1}));
vf.pb(flip({x,y-1}, {-1,-1}));
}
REP(j, SZ(v)) {
pii p = v[j];
pii pa = get(p);
int x = pa.f, a = pa.s;
pii fop = get(vf[j]);
from[i].pb({{a, x}, fop});
s[x].insert({{a, i}, fop});
}
}
pii nowdir = {-1,1};
pii nowpt = flip({m,0}, nowdir);
pii A = get(nowpt);
bug(A.f, A.s);
pii tmp = get(flip({m-1,1}, nowdir));
bug(tmp.f, tmp.s);
ll ret = 0;
while (SZ(s[1])) {
auto nxt = s[A.f].lower_bound({{A.s, -1},{-1,-1}});
if (nxt == s[A.f].end()) nxt = s[A.f].begin();
ll df = (*nxt).f.f - A.s;
assert(df != 0);
if (df < 0) df += 4*n*m; // not sure, maybe 2nm??
ret += df;
bug(df, ret);
A = (*nxt).s;
// A = get(nowpt);
int bye = (*nxt).f.s;
bug(bye);
for (auto p : from[bye]) {
int X = p.f.s;
p.f.s = bye;
s[X].erase(p);
}
}
return ret;
}
int yo[500][500];
ll dumb(vector<pii> var) {
int i =0;
for (pii p : var) {
int x = p.f, y = p.s; x = x*2-1; y = y*2-1;
yo[x+1][y]++;
yo[x][y+1]++;
yo[x-1][y]++;
yo[x][y-1]++;
yo[x][y]=1;
++i;
}
int x = m, y = 0;
int dx = -1, dy = 1;
int bar = 0;
int re = 0;
while (bar < npts) {
x += dx; y += dy; ++re;
pii tmp = get(flip({x,y}, {dx, dy}));
bug(x,y,re,tmp.f, tmp.s);
if (yo[x][y]) {
// bump!
REP(ss, 4){
int tx = (ss-1)%2; // -1 0 1 0
int ty = (2-ss)%2; // 0 1 0 -1
if (yo[tx+x][ty+y]) {
int X = tx+x, Y = ty+y;
if (tx) dx *= -1;
else dy *= -1;
for (int sx:{-1,1}) for (int sy:{-1,1}) {
--yo[X+sx][Y+sy];
}
yo[X][Y] = 0;
goto yar;
}
}
yar:;
++bar;
}else{
if (x == 0 || x == 2*m) dx *= -1;
if (y == 0 || y == 2*n) dy *= -1;
}
}
return re;
}
signed main(){
IOS();
cin>>m>>n>>npts; // m is for X, n is for Y
vector<pii> var;
REP(i,npts) {
int x,y; cin>>x>>y; var.pb({x,y});
}
cout<< smat(var)<<endl;
// ll poo = dumb(var);
// bug(ss, poo);
}
- Strikes 2017 [Solved Jan 16]
Oops
Oops, I accidentally slipped a trivial one in this list X_X
I thought it was ~80 solves in the first round but it turned out to be ~80 solves in the second round haha
I'll add direction signs to the list to compensate for this one
code :/
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 5e5+5;
vector<int> g[maxn];
int par[maxn];
int ch[maxn]; // number of white children
bool black[maxn];
void dfs(int v, int p) {
par[v] = p;
for (int u : g[v]) {
if (u != p) {
dfs(u,v);
++ch[v];
}
}
}
signed main(){
IOS();
int n; cin>>n;
REP(i,n-1) {
int a,b; cin>>a>>b;
g[a].pb(b); g[b].pb(a);
}
dfs(1,-1);
int V = n; int E = n-1;
int q; cin>>q;
REP(i,q) {
int v; cin>>v;
bool toblack = v>0;
v = abs(v);
int p = par[v];
if (toblack) {
--V;
int fr = ch[v] + (p != -1 && !black[p]);
E -= fr;
if (p != -1) {
--ch[p];
}
}else{
++V;
int fr = ch[v] + (p != -1 && !black[p]);
E += fr;
if (p != -1) {
++ch[p];
}
}
black[v] ^= 1;
cout<<V-E<<endl;
}
}
- Rally 2014 [By the way, I've been stuck on this one for super long. Currently getting wrong answer on one test case (89 pts) for unknown reason.] [UPD: I ACed this problem, but my solution is wrong. It's just very hard to block with a random generator. I'll try to think of & write a proper solution when I have some more time.]
Current Spaghetti Code (with brute force checker and generator...)
#include <bits/stdc++.h>
//#define int ll
//#undef BALBIT
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
//#define MN(a,b) a = min(a,(__typeof__(a))(b))
//#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 5e5+5;
// 1. Find longest chain
// 2. For each node, find minimum (chain position - max dist), and update all indeg
// 3. Do the same for the outdeg
// 3.1. Also update the case where there there's just a hanging thread
// 4. Use seg tree or smth to update ans
// 5. Check for longest chain not connected to original
// by the way this is wrong
vector<int> g[maxn], gt[maxn];
int mxd[maxn], frm[maxn]; // for building original chain
bool onP[maxn]; // P is the biggest chain
int Pid[maxn];
vector<int> ord;
vector<int> P;
int indeg[maxn];
int n,m;
int getlen(int ban){
REP(i,n) {
indeg[i] = SZ(gt[i]); mxd[i] = 0;
}
for( int u : g[ban]) {
--indeg[u];
}
queue<int> q;
REP(i,n) {
if (indeg[i] == 0 && i!=ban) q.push(i);
}
int bg = 0, bgv = -1;
while (!q.empty()) {
int v=q.front(); q.pop();
assert(v != ban);
if (mxd[v] == 0) {
mxd[v] = 1;
}
if (mxd[v] > bg) {
bg = mxd[v]; bgv = v;
}
for (int u : g[v]) {
if (u == ban) continue;
if (mxd[u] < mxd[v] + 1) {
mxd[u] = mxd[v] + 1;
}
if (--indeg[u] == 0) {
q.push(u);
}
}
}
// bug(ban, bg);
return bg;
}
void buildP(){
// also build topo order
REP(i,n) {
indeg[i] = SZ(gt[i]);
}
queue<int> q;
REP(i,n) {
if (indeg[i] == 0) q.push(i);
}
int bg = 0, bgv = -1;
while (!q.empty()) {
int v=q.front(); q.pop(); ord.pb(v);
if (mxd[v] == 0) {
mxd[v] = 1; frm[v] = -1;
}
if (mxd[v] > bg) {
bg = mxd[v]; bgv = v;
}
for (int u : g[v]) {
if (mxd[u] < mxd[v] + 1) {
mxd[u] = mxd[v] + 1;
frm[u] = v;
}
if (--indeg[u] == 0) {
q.push(u);
}
}
}
assert(SZ(ord) == n);
for (; bgv != -1; bgv = frm[bgv]) {
P.pb(bgv); onP[bgv] = 1;
}
reverse(ALL(P));
REP(i, SZ(P)){
Pid[P[i]] = i;
bug(P[i], i);
}
}
pair<int, int> dp[maxn];
inline void MN(pii &a, pii b) {if (b.f < a.f || (b.f == a.f && b.s > a.s)) a = b;}
inline void MX(pii &a, pii b) {if (b.f > a.f || (b.f == a.f && b.s < a.s)) a = b;}
vector<pair<int, bool> > yo[maxn];
void upd(int l, int r, int v) {
if (l > r || l == -1) return;
bug(l,r,v);
yo[l].pb({v, 1});
yo[r+1].pb({v, 0});
}
pair<bool, int> bad(int M){
int ctr = 0;
REP(i,SZ(P)) {
for (pii p : yo[i]) {
if (p.f <= M) {
ctr += p.s?1:-1;
}
}
if (ctr == 0) {
return {1, P[i]};
}
}
return {0, -1};
}
void buildR(){
for (int it = SZ(ord)-1; it>=0; --it) {
int v = ord[it];
int prv = SZ(P)-1;
if (onP[v]) {
dp[v] = {Pid[v],Pid[v]};
}else{
dp[v] = {SZ(P)-1,SZ(P)};
for (int u : g[v]) {
MN(dp[v] , {dp[u].f-1, dp[u].s});
}
for (int u : g[v]) {
if (dp[u].s > dp[v].s) {
prv = min(prv, dp[u].f - 1);
}
}
}
int bg = -1;
// bug(v, dp[v].f, dp[v].s);
for(int u : gt[v]) {
if (onP[u]) {
upd(Pid[u]+1, dp[v].s-1, dp[v].f - Pid[u] - 1);
bg = max(bg, Pid[u]);
}
}
if (!onP[v]) {
if (v == 2) {
bug(dp[v].s, prv, bg);
}
upd(dp[v].s, dp[v].s, prv-bg-1);
}
upd(-1+1, dp[v].s-1, dp[v].f); // loose end
}
REP(it, SZ(ord)) {
int v = ord[it];
int prv = 0;
pair<int, int> old = dp[v];
if (onP[v]) {
dp[v] = {Pid[v],Pid[v]};
}else{
dp[v] = {0, -1};
for (int u : gt[v]) {
MX(dp[v] , {dp[u].f+1, dp[u].s});
}
for (int u : gt[v]) {
if (dp[u].s < dp[v].s) {
prv = max(prv, dp[u].f+1);
}
}
}
int smo = SZ(P);
for(int u : g[v]) {
if (onP[u]) {
smo = min(smo, Pid[u]);
upd(dp[v].s+1, Pid[u]-1, Pid[u] - dp[v].f - 1);
}
}
if (!onP[v]) {
upd(dp[v].s+1, old.s-1, old.f-dp[v].f);
if (v == 1) {
bug(old.s, dp[v].s, old.f, dp[v].f);
}
// assert(dp[v].s <= old.s);
upd(dp[v].s, dp[v].s, smo-prv-1);
}
upd(dp[v].s+1, SZ(P)-1, SZ(P) - dp[v].f - 1); // loose end
}
}
pii fast() {
buildP();
buildR();
int l = -1, r = n;
while(l!=r) {
int mid = ((l+r)/2) - (((l+r)<0) && ((l+r)%2)); // floored division
if (bad(mid).f) {
l = mid+1;
}else{
r = mid;
}
}
bug(l);
return {bad(l-1).s+1,SZ(P) - (l+1)};
// cout<<<<endl;
}
pii slow(){
int re = iinf;
int ri = -1;
REP(i,n) {
int yar = getlen(i)-1;
if (yar < re) {
re = yar; ri = i;
}
}
return {ri+1, re};
}
signed main(){
IOS();
cin>>n>>m;
int yoi = 10000;
#ifndef BALBIT
yoi = 1;
#endif // BALBIT
REP(qqq, yoi) {
#ifdef BALBIT
REP(i,n+1) {
g[i].clear(); gt[i].clear();
yo[i].clear();
mxd[i]=frm[i]=onP[i]=Pid[i]=indeg[i]=0;
}
ord.clear(); P.clear();
#endif
vector<pii> edges;
vector<int> od(n); REP(i,n) od[i] = i;
random_shuffle(ALL(od));
set<pii> hv;
REP(i,m) {
int a,b;
#ifndef BALBIT
cin>>a>>b;
--a; --b;
#else
a = rand() % n; b = rand()%n; if (od[a] > od[b]) swap(a,b);
if (a == b || hv.count({a,b})) continue;
hv.insert({a,b});
edges.pb({a,b});
#endif
g[a].pb(b); gt[b].pb(a);
}
#ifdef BALBIT
pii A = fast();
pii B = slow();
bug(A.f, A.s, B.s);
if (A.s != B.s) {
bug(A.s, B.s);
for (pii p : edges) {
bug(p.f, p.s);
}
}
assert(A.s == B.s);
#else
pii A = fast();
cout<<A.f<<' '<<getlen(A.f-1)-1<<endl;
#endif
}
}
/*
5 5
1 2
2 3
3 4
1 5
5 4
9 7
1 2
2 3
3 4
6 7
7 8
8 9
9 5
7 8
1 2
2 3
3 4
5 2
2 6
6 7
3 7
6 4
5 5
1 3
3 4
2 5
3 5
2 3
*/
- Trips 2015 [Solved Jan 18]
Fun-ness:
3/10
Comments
I got stuck on Rally for too long and decided to try this one.
Thinking of the solution and implementing it was easy; getting it to pass on szkopul was not.
Not only are time limits different for each subtask, they also vary for each test case, meaning that you'll suffer a lot if you don't implement it in the same way the author did.
Also, I didn't see that there were multiple edges for a while. That was my bad.
Code (warning: dirty, with lots of breaks and debug stuff)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
//#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 1e5+5;
typedef array<ll, 121> Vec;
typedef array<Vec, 121> Mat;
Mat M;
ll cap = (1ll<<61)-1;
int LAY = 65;
Mat Mp[65];
inline ll prod(ll a, ll b) {
if (!b || !a) return 0;
if ((a) > (cap) / b + 1) return cap;
return min(a*b, cap);
}
inline void add(ll &a, ll b) {
a = min(cap,a+b);
}
int YO, END;
void mul(Mat &c, Mat a, Mat b) {
REP(i,YO) REP(j,YO) if (i<j) swap(b[i][j], b[j][i]);
REP(i, YO) REP(j, YO) {
c[i][j] = 0;
REP(k,YO) {
add(c[i][j], prod(a[i][k], b[j][k]));
if (c[i][j] == cap) break;
}
}
}
signed main(){
IOS();
int n,m; ll k; cin>>n>>m>>k;
YO = n*3+1; END = YO-1;
k += n;
LAY = __lg(k+1)+2;
REP(i,n) {
M[i*3][i*3+1] = 1;
M[i*3+1][i*3+2] = 1;
}
REP(i,m) {
int a,b,c; cin>>a>>b>>c;
--a; --b;
M[a*3+2][b*3+3-c] += 1;
}
Vec now; fill(ALL(now), 0);
REP(i,n) {
now[i*3+2] = 1;
M[i*3+2][END] = 1;
}
M[END][END] = 1;
Mp[0] = M;
ll psig = -1;
bool yoit = 0;
REP1(i, LAY-1) {
bug(i);
mul(Mp[i], Mp[i-1], Mp[i-1]);
ll sg = 0;
REP(p,YO) {
if (p % 3 == 2)
add(sg, Mp[i][p][END]);
}
if (sg > k ) {
yoit = 1;
LAY = i+1; break;
}
psig = sg;
}
ll re = 0;
bool big = 0;ll sg= 0;
for (int mi = LAY-1; mi>=0; --mi) {
Vec tmp;
fill(ALL(tmp), 0);
ll sig = 0;
REP(i, YO) {
tmp[i] = 0;
REP(j,YO) {
add(tmp[i], prod(now[j], Mp[mi][j][i]));
}
if (i == END) {
add(sig, tmp[i]);
}
}
bug(sig, k);
if (sig < k) {
sg = sig;
re += (1ll<<mi);
now = tmp;
}else big = 1;
}
if (!big) {
assert(yoit != 1);
re = -1;
}
cout<<re<<endl;
}
Help
Is there a fast way to find min(A*B, C) where A, B, and C can be 64-bit numbers? I had to resort to doing
inline ll prod(ll a, ll b) {
if (!b || !a) return 0;
if ((a) > (cap) / b + 1) return cap;
return min(a*b, cap);
}
but it's obviously very slow. Also, szkopul doesn't support __int128.......
- Panini 2017 [Solved Jan 19]
Fun-ness
7/10
Comments
This is a great problem! It feels awesome finding observations and separating this difficult-seeming problem into a few easy-to-handle cases.
One thing that surprised me was that I forgot an entire (fairly important) case that should've been easily caught with a random testcase but was still able to get 84 points, with only 2 subtasks showing WA. I guess this goes to show the importance of multitests, however annoying they are.
code
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 3e3+5;
vector<pii> dp[maxn]; // {reaches to, cost}
ll smollest[maxn];
signed main(){
IOS();
int n,z,d; cin>>n>>z>>d;
vector<ll> a(n+1);
vector<ll> sig(n+1);
ll re = 0;
REP1(i,n) {
cin>>a[i];
if (a[i] < d) {
re += d-a[i]; a[i] = d;
}
if (i - z >= 0 && a[i] - a[i-z] < d) {
re += a[i-z] + d - a[i];
a[i] = a[i-z] + d;
}
bug(i, a[i]);
sig[i] = sig[i-1] + a[i];
}
a.pb(inf);
bug(re);
dp[0].pb({0, 0});
for (int i = 1; i<=n; ++i) {
ll cst = 0;
int ntook = 1;
int j = i;
ll base = inf;
for (; j>0 && ntook <= z && a[i]-a[j] <= d; --j, ++ntook) {
if (a[i] - a[j] == d) {
// try transition
if (dp[j][0].f <= a[j])
MN(base, dp[j][0].s + cst);
}
cst += a[i] - a[j];
}
for (pii p : dp[j]) {
if (p.f <= a[i] - d) {
MN(base, p.s + cst);
}
}
for (; j>0 && ntook <= z; --j, ++ntook) {
cst += a[i] - a[j];
MN(base, smollest[j-1] + cst);
}
bug(i, base);
int at = i;
for (int rps = 0; ; ++rps) {
dp[at].pb({a[i] + rps * d, base});
ntook = 0;
for (; a[at] <= a[i] + (rps+1)*d && ntook <= z; ++at, ++ntook) {
if (ntook) {
base += (rps+1)*d + a[i] - a[at];
}
}
if (ntook == 1) break;
--at;
}
smollest[i] = inf;
for (pii p : dp[i]) {
MN(smollest[i], p.s);
}
sort(ALL(dp[i]), [&](pii x, pii y){return x.f!=y.f?x.f < y.f : x.s < y.s;});
}
ll ret = inf;
{
ret = smollest[n];
// for (pii p : dp[n]) MN(ret, p.s);
}
cout<<ret + re<<endl;
}
/*
5 5 101
2 100 300 400 500
*/
- Crossroads of Parity 2017 [Solved Jan 19]
Fun-ness
7/10
Comments (major spoilers)
This was a pretty cute and nice problem! I found it pretty easy but still very nice.
Let $$$f(S)$$$ denote the answer after adding the set of non-MST edges $$$S$$$.
Obviously, because of MST properties, for a non-MST edge $$$e$$$ not in $$$S$$$, $$$f(S \cup {e}) > f(S)$$$, but it took me a bit of time to realize (and prove) that $$$e_1 > e_2 \implies f(S \cup {e_1}) > f(S \cup {e_2})$$$, which made the problem very nice and easy.
code
#include <bits/stdc++.h>
#define int ll
#undef BALBIT
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 5e5+5;
struct edge{
int v, u, i;
};
int bot[maxn]; // bottom node of each edge
int par[maxn]; // parent of node
int L[maxn],R[maxn];
int IT = 0;
vector<edge> g[maxn];
void dfs(int v, int p) {
par[v] = p;
L[v] = R[v] = IT++;
for (edge e : g[v]) {
if (e.u != p) {
bot[e.i] = e.u;
dfs(e.u, v);
R[v] = R[e.u];
}
}
}
vector<edge> E;
int dpar[maxn];
int find(int x) {return x == dpar[x]?x : dpar[x] = find(dpar[x]);}
void mrg(int a, int b) {
a=find(a); b = find(b);
dpar[a] = b;
}
int s[maxn];
int QU(int e) {
int re = 0;
for (++e; e>0; e-=e&-e) {
re ^= s[e];
}
return re;
}
inline bool isanc(int a, int b) {
return L[a] <= L[b] && R[a] >= R[b];
}
void MO(int e, int v) {
for (++e; e<maxn; e+=e&-e) {
s[e] ^= v;
}
}
vector<edge> lft;
bool intree[maxn];
int get(int id, ll k) { // k = 1 => find the cheapest
bug(id);
if (k > (1ll<<min(SZ(lft), 62ll))) {
return -1;
}
--k; // now change to binary rep
if (intree[id]) {
int bt = bot[id];
int re = QU(R[bt]) ^ QU(L[bt]-1);
REP(j, min(62ll, SZ(lft))) {
if (k & (1ll<<j)) {
re ^= isanc(bt, lft[j].u);
re ^= isanc(bt, lft[j].v);
}
}
return re;
}else{
REP(j, min(62ll, SZ(lft))) {
if (k & (1ll<<j)) {
if (lft[j].i == id) return 1;
}
}
return 0;
}
}
signed main(){
IOS();
int n,m; cin>>n>>m;
REP(i,n) dpar[i] = i;
bool totpar = 0;
REP(i,m) {
int a,b; cin>>a>>b; --a; --b;
E.pb({a,b,i});
if (find(a) != find(b)) {
mrg(a,b);
g[a].pb(E.back());
g[b].pb({b,a,i});
intree[i] = 1;
}else {
lft.pb(E.back());
}
}
dfs(0, -1);
REP(i,n) {
int p; cin>>p;
MO(L[i], p); // don't forget L[i]!!!
}
ll K; cin>>K;
REP(i,m) {
cout<<get(i, K)<<' ';
}
cout<<endl;
int q; cin>>q;
while (q--) {
char c; cin>>c;
if (c == 'M') {
int v; cin>>v;
--v; MO(L[v], 1);
totpar ^= 1;
}else if (c == 'K') {
cin>>K;
}else{
int i; cin>>i; --i;
if (totpar == 1) cout<<-1<<endl;
else cout<<get(i,K)<<endl;
}
}
}
- Hydrocontest 2016 [Solved Jan 30]
Fun-ness
7/10
Comments
I enjoyed this one quite a lot. Analysis was clean and the implementation was, while difficult, not as hard as I initially thought (which was that the graph was a general cactus, with some edges on no cycles).
BTW, I was gone for the past week due to a participating in a camp that took quite a bit more time than I expected.
code
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 5e5+5;
// 1. Find all faces and label each face as a node
// 2. Choose a face as the root and dfs
// 3. After finding the answer for each node (win or lose or nothing) wrt to each face except for transition nodes, dfs again for each face and push answer down
// 4. Use the answers for each face wrt to each node, answer each node
vector<int> g[maxn];
bool seen[maxn];
vector<vector<int> > face; // faces!
vector<vector<int> > type; // for each (face, point), find the node type here (-1 for lose, 1 for win, 0 for nothing)
vector<int> touchface[maxn]; // faces touching this node
vector<int> faceval[maxn]; // values of faces touching this node,
int par[maxn];
int ts[maxn]; int IT = 0;
void dfs1(int v, int p) {
par[v] = p;
seen[v] = 1;
ts[v] = IT++;
for (int u : g[v]) {
if (u == p) continue; // no double edges guaranteed
if (seen[u]) {
if (ts[u] < ts[v]) {
// u is ancestor of v
vector<int> nf;
for (int at = v; at != u; at = par[at]) {
nf.pb(at);
}
nf.pb(u);
for (int x : nf) {
touchface[x].pb(SZ(face));
}
face.pb(nf);
type.pb({});
}
}else{
dfs1(u, v);
}
}
}
void getans(int f, int w, int wval) { // get all the answers for face f, given that the dp for node w is wval
int m = SZ(face[f]);
vector<int> &T = type[f];
REP(i, m) {
if (T[i] == -5) {
T[i] = wval;
}
}
vector<int> ans(m); // answer for this node, facing this face
int nwin = 0;
REP(i,m) {
if (T[i] == 1) {
++nwin;
}
}
int lastwin = -10000000;
REP(i, 2*m) {
if (i >= m) {
if ((i-lastwin) < m && (i - lastwin) % 2 == 0) {
// win!
ans[i%m] = 1;
}
}
if (T[i%m] == 1) {
lastwin = i;
}
}
lastwin = 3*m;
for (int i = 2*m-1; i>=0; --i) {
if (i < m) {
if ((lastwin - i) < m && (lastwin-i)%2 == 0) {
ans[i] = 1;
}
}
if (T[i%m] == 1) lastwin = i;
}
REP(i,m) {
if (ans[i] == 0) {
if ((nwin == 0) || (nwin==1 && T[i] == 1)) {
// no other winning nodes left
ans[i] = m % 2 == 0? 2:3 ;
}else{
ans[i] = -1;
}
}
}
REP(i,m) {
int v = face[f][i];
if (v == w) continue;
assert(SZ(touchface[v]) == SZ(faceval[v]));
int nwin = 0; int nflip = 0;
REP(j, SZ(touchface[v])) {
int f2 = touchface[v][j];
if (f2 == f) {
faceval[v][j] = ans[i];
}else{
assert(faceval[v][j] != -5);
}
if (faceval[v][j] == 1) ++nwin;
else if (faceval[v][j] == 3) ++nflip;
}
REP(j, SZ(touchface[v])) {
int f2 = touchface[v][j];
if (f2 == f) {
continue;
}
if (faceval[v][j] == 1) {
if (nwin == 1) {
getans(f2, v, nflip%2==1?1:2);
}else{
getans(f2, v, 1);
}
}else{
if (nwin) {
getans(f2, v, 1);
}else{
getans(f2, v, (nflip - (faceval[v][j] == 3))% 2 == 1? 1 : 2);
}
}
}
}
}
int dfs2(int f, int w) { // i'm at face F, working on point w. -1: losing node, 1: winning, 2: no flip node, 3: force flip node
int m = SZ(face[f]);
vector<int> &val = type[f];
val.resize(m,-5);
int wherew = -1;
REP(i, m) {
int v = face[f][i];
// bug(f,i,w,v);
if (v == w) {
wherew = i; continue;
}
val[i] = 2;
vector<int> tmp;
for (int f2 : touchface[v]) {
if (f2 == f) {
faceval[v].pb(-5);
}else{
int gt = dfs2(f2, v);
faceval[v].pb(gt);
tmp.pb(gt);
}
}
for (int gt : tmp){
if (gt == -1 || gt == 2) continue; // no one will walk into a losing node, and no-flips do nothing
if (gt == 1) {
val[i] = 1; break; // everyone will walk a winning node!
}
if (gt == 3) {
val[i] ^= 1;
}
}
if (val[i] == 3) {
val[i] = 1; // winnin'
}
bug(f, i, v, val[i]);
}
if (wherew == -1) {
// is the root
getans(f, -1, -1);
return -100;
}
bool anywin = 0;
REP(i,m) {
if (val[i] == 1) {
anywin = 1; break;
}
}
if (anywin == 0) {
return m % 2 == 0?2 : 3; // no flip or flip
}
REP1(i, m) {
if (val[(i+wherew) % m] == 1 ) {
// encountered a winning node!
if (i % 2 == 0) {
return 1; // winning!
}
break;
}
}
REP1(i, m) {
if (val[(wherew-i+m) % m] == 1 ) {
// encountered a winning node!
if (i % 2 == 0) {
return 1; // winning!
}
break;
}
}
return -1; // there is a winning node, but the opponent will walk it
}
signed main(){
IOS();
int n; cin>>n;
int m; cin>>m;
REP(i,m) {
int a,b;
cin>>a>>b; --a; --b;
g[a].pb(b); g[b].pb(a);
}
dfs1(0, -1);
REP(i,n) sort(ALL(touchface[i]));
dfs2(0, -1);
REP(i,n) {
bool haswin = 0;
int nflip = 0;
for (int s : faceval[i]) {
if (s == 1) haswin = 1;
else if (s == 3) {
++nflip;
}
}
if( haswin || nflip % 2 == 1) {
cout<<1<<endl;
}else{
cout<<2<<endl;
}
}
}
/*
7 9
1 2
2 3
3 1
3 4
4 5
5 3
5 7
5 6
6 7
*/
}
- Sorcerers 2015 [Solved Jan 31]
Fun-ness
3/10
Comments (major spoilers)
I procrastinated for a long time on implementing this problem. Thinking of a linear-time solution was easy, but all the ideas I had had something like 48*n states, with 24 transitions each, which I wasn't sure would pass even with pruning.
But after running a brute-force and recording the possible number of states and transitions, I realized that there are only 17 states and 24 transitions total (!), making for a clean 24*N solution. After using the brute-force program to print a list of all the possible transitions, the problem was much much easier to implement.
... or so I thought. If that were the end of the story, I would've given this problem a fun-ness of 4 because the technique of using brute force to find all dp transitions instead of deriving them by hand is honestly a pretty nice.
BUT the author had to put p<=3 instead of p=3 in the statement, essentially adding lots of annoying and pointless base cases. In addition, the time limits were crazy, with 0.10s strewn between 6.00 test cases.
So after I submitted and got TLE on 1 test case, I thought that it was because my program ran at a fixed 24*N without much pruning, and I started doing all sorts of constant optimizations.
In the end, it turned out that the TLE was due to me not noticing that p can be equal to zero.... At least my now quite-optimized program runs in 0.5s even for 6.0s test cases :D
Note: the solve date would've been Jan 30 had p=0 not existed :(
code
#include <bits/stdc++.h>
//#define int ll
#pragma GCC optimize("Ofast", "unroll-loops")
//#undef BALBIT
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const int mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 1e6+5;
vector<int> nope[maxn];
inline bool ok(int a, int b) {
if (a < 0) return 0;
for (int x : nope[a]) if (x == b) return 0;
return 1;
}
const int YO = 8;
int dp[8][17];
int invorder[17];
struct trans{
int oldid, newid, AP, BP, bgdf;
bool operator < (const trans & b) const {
return make_tuple(oldid, newid, AP, BP, bgdf) <
make_tuple(b.oldid, b.newid, b.AP, b.BP, b.bgdf);
}
void upd(){
if (oldid != -1) oldid = invorder[oldid];
if (newid != -1) newid = invorder[newid];
}
};
vector<trans> th[17];
vector<int> G[17];
int indeg[17];
vector<trans> tlist = {
{0, 6, -4, -1, 0},
{2, 5, -3, -2, 0},
{2, 8, -3, -1, 0},
{3, 14, -2, 1, 1},
{4, 0, -2, -4, 0},
{5, 6, -2, -1, 0},
{5, 16, -2, 1, 1},
{6, 13, -1, 2, 2},
{6, 14, -1, 1, 1},
{7, 1, -1, -3, 0},
{8, 3, -1, -2, 0},
{8, 12, -1, 2, 2},
{8, 15, -1, 1, 1},
{9, 14, -1, -4, 0},
{11, 6, 1, -2, 1},
{12, 9, -4, -2, 0},
{13, 8, 1, -2, 1},
{13, 14, -1, -2, 0},
{14, 5, 2, -1, 2},
{14, 6, 1, -1, 1},
{15, 10, -3, -1, 0},
{16, 4, 2, -1, 2},
{16, 7, 1, -1, 1},
{16, 11, -2, -1, 0}
};
vector<trans> initlist = {
{-1, 2, 3, 0, 3},
{-1, 5, 2, 0, 2},
{-1, 6, 1, 0, 1},
};
vector<trans> finlist = {
{1, -1, -3, 0, 0},
{3, -1, -2, 0, 0},
{6, -1, -1, 0, 0},
{10, -1, 0, -3, 0},
{11, -1, 0, -2, 0},
{14, -1, 0, -1, 0}
};
vector<int> doorder;
void UPD(vector<trans> & v) {
for (trans &s : v) s.upd();
}
void build(){
for (trans t : tlist) {
if (t.bgdf == 0) {
G[t.oldid].pb(t.newid);
++indeg[t.newid];
}
}
queue<int> qq;
REP(i, 17) {
if (indeg[i] == 0) {
qq.push(i);
}
}
while (!qq.empty()) {
int v = qq.front(); qq.pop();
doorder.pb(v);
for (int u : G[v]) {
if (--indeg[u] == 0) {
qq.push(u);
}
}
}
bug(SZ(doorder));
REP(i, 17) {
invorder[doorder[i]] = i;
}
REP(i,17)
bug(i, invorder[i]);
UPD(tlist); UPD(initlist); UPD(finlist);
sort(ALL(tlist));
for (trans t : tlist) {
th[t.oldid].pb(t);
}
}
inline void ADD(int &a, int b) {
a += b; if(a >= mod) a -= mod;
}
bool test(vector<int> &v, int p=3) {
REP(i, SZ(v)) {
if (!ok(v[i],v[(i+1)%SZ(v)]) || abs(v[i] - v[(i+1)%SZ(v)]) > p) return 0;
}
return 1;
}
signed main(){
IOS();
build();
bug(tlist[0].oldid);
int n,k,p; cin>>n>>k>>p;
if (p == 0) {
if (n == 1) cout<<1<<endl;
else cout<<0<<endl;
return 0;
}
if (p == 1 && n > 2) {
cout<<0<<endl; return 0;
}
if (p == 1 && k > 0) {
cout<<0<<endl; return 0;
}
REP(i,k) {
int a,b; cin>>a>>b;
if (abs(a-b) <= 3) {
nope[a].pb(b);
}
}
clock_t t = clock();
if (n <= 3) {
vector<int> d;
REP1(i,n) d.pb(i);
int re = 0;
do{
re += test(d,p);
}while (next_permutation(ALL(d)));
cout<<re/n<<endl; return 0;
}
if (p == 1) {
if (n > 2) {
cout<<0<<endl; return 0;
}
assert(0);
}
if (p == 2) {
vector<int> dq(n);
for (int i = 0; ; ++i) {
if (n-i*2 > 0) dq[i] = n-i*2;
else break;
}
for (int i = 0; ; ++i) {
if (n-i*2-1 > 0) dq[n-i-1] = n-i*2-1;
else break;
}
int re = test(dq);
reverse(ALL(dq));
re += test(dq,p);
cout<<re<<endl;
return 0;
}
for (trans t : initlist) {
if (ok(1 + t.AP, 1+t.BP)) {
dp[1 + t.bgdf][t.newid] += 1;
}
}
for (int i = 1; i<=n; ++i) {
for (auto & t : tlist) {
if (ok(i + t.AP, i + t.BP)) {
ADD(dp[(i + t.bgdf)&7][t.newid], dp[i&7][t.oldid]);
}
}
if (i != n) memset(dp[i&7], 0, sizeof dp[i&7]);
}
ll re = 0;
for (trans t : finlist) {
if (dp[n&7][t.oldid]) if (ok(n + t.AP, n + t.BP)) {
re += dp[n&7][t.oldid];
}
}
cout<<re%mod<<endl;
bug((clock()-t)/(double)CLOCKS_PER_SEC);
}
- Direction Signs 2015 [Solved Jan 20]
Fun-ness
7/10
Comments (major spoilers)
I thought this was a nice problem, although not a very hard one (?) Maybe I've seen too many of these "The answer contains at least X% of the set" :P
At first I wasn't sure if O(N^2 * M / 64) * 20 reps would pass, but with a couple of /2s it runs really comfortably in around 0.5s.
code
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 1e5+5;
int d[1005][202];
bitset<200> so[1005];
int R[1005];
int from[1005], dp[1005];
signed main(){
IOS();
mt19937 rnd(time(0));
int n,m; cin>>n>>m;
--m;
REP(i,n) {
int r; cin>>r; R[i] = r;
REP(j,m) {
cin>>d[i][j]; d[i][j] -= r;
}
}
const int MAGIC = 20;
int bst = 0;
vector<int>re;
REP(qqq, MAGIC) {
int T = rnd()%n;
vector<int> same;
vector<pii> gv, lv;
REP(i,n) {
if (i == T) {
same.pb(i); continue;
}
int gr = 0;
int cnt = 0;
REP(j,m) {
so[i][j] = 0;
if (d[i][j] == d[T][j]) continue;
if (abs(d[i][j] - d[T][j]) >= 2) goto die;
so[i][j] = 1; ++cnt;
if (d[i][j] > d[T][j]) {
if (gr == -1) goto die;
gr = 1;
}else{
if (gr == 1) goto die;
gr = -1;
}
}
if (gr == 0) {
same.pb(i);
}else if (gr > 0) {
gv.pb({cnt,i});
}else{
lv.pb({cnt,i});
}
die:;
}
if (SZ(gv) + SZ(lv) + SZ(same) < bst) continue;
bug(T, bst, SZ(gv), SZ(lv), SZ(same));
sort(ALL(gv)); sort(ALL(lv));
memset(from, -1, sizeof from);
REP(i, SZ(gv)) {
int it = gv[i].s;
dp[it] = 1;
REP(j, i) {
if (dp[gv[j].s] + 1 > dp[it] && (so[it] | so[gv[j].s]) == so[it]) {
dp[it] = dp[gv[j].s] + 1;
from[it] = gv[j].s;
}
}
}
REP(i, SZ(lv)) {
int it = lv[i].s;
dp[it] = 1;
REP(j, i) {
if (dp[lv[j].s] + 1 > dp[it] && (so[it] | so[lv[j].s]) == so[it]) {
dp[it] = dp[lv[j].s] + 1;
from[it] = lv[j].s;
}
}
}
int btog = 0;
int bg = -1, bl = -1;
for (pii G : gv) {
if (dp[G.s] > btog) {
btog = dp[G.s]; bg = G.s; bl = -1;
}
}
for (pii L : lv) {
if (dp[L.s] > btog) {
btog = dp[L.s]; bl = L.s; bg = -1;
}
}
for (pii G : gv) for (pii L : lv) {
if (dp[G.s] + dp[L.s] > btog && ((so[G.s] & so[L.s]).count() == 0)) {
btog = dp[G.s] + dp[L.s];
bg = G.s; bl = L.s;
}
}
if (btog + SZ(same) > bst) {
vector<pair<pii, int> > rat;
int stp = 100000;
for (int at = bg; at != -1; at = from[at]) {
rat.pb({{R[at], stp}, at});
--stp;
}
stp = -100000;
for (int at = bl; at != -1; at = from[at]) {
rat.pb({{R[at], stp},at});
++stp;
}
for (int t : same) {
rat.pb({{R[t], 0},t});
}
sort(ALL(rat)); reverse(ALL(rat));
assert(SZ(rat) == btog + SZ(same));
bst = SZ(rat); re.clear();
for (auto e : rat) {
re.pb(e.s+1);
}
}
}
cout<<SZ(re)<<endl;
for (int x : re) cout<<x<<' ';
cout<<endl;
}
/*
4 4
3 3 3 4
3 4 4 4
3 3 4 4
4 4 4 4
*/
Note: I'll also leave comments/hints here in case I manage to solve them or (unfortunately) have to dig around CSDN for their solutions :)
