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 :)
Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
You'll probably be able to solve all from here if you are sufficiently motivated, I have looked at all of them in the past and none of them is ultra hard.
Consider Klubowicze (aka Club players? ) from POI 23 final 2nd day, Tablice Kierunkowe (road signs?) from POI 22 day1 final and Dlugie Podróże (long routes?) from POI 26 day2 final, they should be plenty of fun!
The fact that nobody has solved Dlugie Podroze is some misunderstanding, it had difficulty level 1/5 in an internal document (I would give it higher note, but that's what it got there) and I am positive I would solve it within 10 minutes on a contest xd
True!!! As an author of that problem I was completely astonished to see it had like 5 solves overall. I would understand it in a contest with ranking available (nobody is solving because nobody else is solving), but in POI?
Perhaps it's a standard trick for ICPC but not so common among higj schoolers
Oh, I must have misremembered. I thought it was solved by absolutely nobody, but it was actually solved by 8 people, which makes more sense. Now I remember the original thing I noted was that "nobody from Polish IOI team has solved it" instead of "nobody has solved it". A cool problem anyway, I was advocating for its inclusion at the time
Yeah I've solved Dlugie Podoze before and remember it being pretty easy :)
n/10 just looks too sus for normal algorithms
Happy to see Crossroads of Parity here cause that's mine problem :D. I actually got very good feedback from competitors about it, they all seemed to have loved it. However my personal favourites out of ones by me are Direction signs and Interplanetaty communication (But I am not sure if we want to use this set for some international team competition? So I won't link it here and please don't investigate yet :P). Funnily enough, both got quite terrible feedback from contestants xD (for direction signs it was more of an issue of weak tests allowing for heuristic solutions, not the problem itself). Amusing journeys is quite decent as well
And have fun with Snake, that's the biggest shit I have ever seen (it got accepted by two contestants during the first stage and code of one of them got over 3 thousand lines xD)
Some of the most fun one that are not on your list also include Cook and Triinformathlon
If I have to subjectively rate funness of my own problems then it would be:
10/10: Direction signs
9/10: Interplanetary communication
8/10: Crossroads of Parity
7/10: Amusing journeys, Solar lamps
6/10: Bank, Messenger
5/10: Dilligent John, Integrated circuit, Visits
4/10: Metro
Thanks for the recommendations!
I've solved cook and triinformathlon before and liked both of them a lot (I think triinformathlon appeared again in a recent opencup).
I've been analyzing the structure of the snake for a few hours and... it looks super scary :P Maybe I'll save it for last?
I'll make sure to check out direction signs later too :)
Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
I'm looking forward to this challenge! Although unfortunately I have a bit less free time for this one.
Good problem, I liked it. The funniest part was when I realized that we have to go from 1 to $$$n$$$ and not between two arbitrary vertices. Instead of fixing a decent chunk of code I added 14 additional vertices and it was a pretty fun little trick.
Well there goes my day... Really glad to be done with it. I think there might be an easier solution that uses the fact that the snake always exists, it would be nice to hear it. I didn't use it and just did a full $$$n^2$$$ dp, which I think had around 40 transitions. It was bearable during the first half when I implemented everything but in the second half I was fixing TLE on 1 single test case with .10s time limit for 3 or 4 hours straight and this part was incredibly frustrating. I already had a similar problem on Trips, but this one was much worse. This is what I really don't like about this platform. I'm almost confident they had a testcase with large $$$n$$$ and a small time limit just because it probably had a lot of solutions or a simple snake structure and I don't like not knowing the limits before I submit. Tried everything to optimize it but in the end I couldn't fit the full dp in tl for this testcase and had to run dp in dfs order and stop once I reach the end successfully.
Pretty good implementation problem. Feels nice "being forced" to do it and then somewhat enjoy doing it cleanly.
Yeah probably shouldn't be on the list :) For some reason I did $$$O(n \sqrt n)$$$ without thinking instead of linear but I was pretty sure it would pass anyway.
Another easy problem, but a very good one.
I don't know if solved is the correct word but I AC'ed it. I REALLY struggled with this problem, it's actually the first problem out of the list I started implementing, spent 3 days and 30 submissions. I quickly got rid of all exponential cases and then spent a lot of time trying to force it with berlekamp-massey and/or polynomial interpolation on proper subsequences or by vertex. Then I finally realized how to do proper matrix multiplication to count all paths of length $$$<=l$$$ instead of just length $$$l$$$, but after that I was still frustratingly struggling with TLE on several small testcases. I finally made it work but I wouldn't have solved it yet on codeforces with the same time limits.
Really cool dp with interesting greedy transitions and very short code.
Very nice problem. The solution feels good to implement and the formula for answering queries is very satisfying (unlike most problems with $$$k$$$-th lowest something).
It was a very interesting problem for me. It seemed pretty easy and standard in theory — just do 2 dfs: one to determine who wins when we go down in some tree made of vertices and cycles, and one to determine who wins when we go up. But for some reasons the concepts and implementation details in this problem felt very alien and hard to keep in mind and I had to focus a lot to understand what's going on. Don't know if it's just my personal feeling or it's an objectively unusual problem, but I enjoyed this peculiar experience :)
Didn't like it. It's pretty obvious what you have to do, just a very unpleasant implementation. I guess that's some useful practice on the other hand :)
Just wrote a simple $$$O(n^3/6)$$$ solution and it works with less than a half running time. In case it didn't work I could have also improved it to $$$O(n^2\cdot m + n^3/128)$$$ with bitset and this should be not even close to tl. The reduction to finding a maximum clique in a directed acyclic graph with a special property is not hard but pretty interesting. And the second part I don't know the faster way for now but bitset should be really fast with these constraints. I also haven't used the 20% constraint at all so it's probably not the intended way. Maybe Swistakk can tell if this solution was supposed to be cut :)
Hmmm... The intended solution was $$$O(50 \cdot (nm + n^2 + \frac{n^2m}{64}))$$$. I reckon was unaware of solutions in complexities that you mention.
But now that I think about this problem from a bit different angle than I did these years ago... I see how $$$O(n^3/6)$$$ could be achieved. Not sure about /128 though.
I think that I was fixated on an idea where I choose one particular sign that I hope belongs to the solution and I transform the whole instance to the equivalent one where it has all zeroes and other relevant signs have only 0 or 1. If the solution is big enough then I can guess such sign randomly (hence 50 in the initial complexity from the 50 guesses), but now I see it could be done in a smarter way, where at the very beginning I transform each sign so that it has 0 at the first coordinate and for each pair I record min and max difference after subtracting one from the another. If all such coordinates differences are between 0 and 1 then I put an edge from the smaller one to the larger one and I never have to examine that pair carefully again (i.e. I don't have to loop over these m coordinate).
I guess situations like these can happen when an author suggests a problem with some specific constraints and everyone involved in its preparation is skewed because of them and is satisfied after getting a solution that meets them and another better approach may slip by unnoticed.
Yeah the statement obviously heavily suggested the randomized solution but I just couldn't see how it can improve the complexity. And you got pretty much everything right. Just a small note, probably more of a personal preference: Instead of making the first coordinate 0 we can subtract the minimum coordinate from each sign. I think it is just a bit nicer because now, when we sort the signs by the sum of coordinates, we can only consider edges from left to right (condition for the edge is the same) and now we just have to find the longest path with start and end connected by a direct edge. That's what I actually really liked about the problem — how magically it turned from a scary and messy input data to a very clean and concise task.
Also you made me think more carefully about /128 optimizations and the idea I had in mind was indeed wrong. I still think there is a chance it might be possible but at least it's not that simple.
Regarding Snake and your struggle. I feel you, we had examples in the past, where contestants got lower points because some moron decided to set TLs to Constant*(model solution) where sometimes model solution was unusually fast because of structural properties of tests with big size, what basically forces you to get exactly the same solution as the model one instead of any with right complexity. Fortunately these were not historically often. And respect for getting at ACed xd
Done with the challenge! This set was significantly more implementation heavy than the last one (which is expected because of the different type of source competitions) but it also had a lot of beautiful problems I really enjoyed. And as for the implementation part of the set — this is exactly the type of problems I usually lack the motivation to practice or upsolve so I feel like I've actually improved on that side for quite a bit.
Thanks balbit for great problem selection and I will keep following this post to read your feedback on the remaining problems :)
Whoa, congratulations!
I hope I can complete the challenge in time as well :)
Unfortunately szkopul seems to be down right now... hopefully it won't take too long :-|
Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
Regarding Panini, you must have gotten a pretty serious bug if it costed you 16 points ;p. This was sadly probably the worst prepared problem ever on POI, where literally nobody has solved it during contest, but tons of people got 92pts with some shitty super simple greedy.
Btw you don't need multitests to remedy this. Tests are usually partitioned into packages and you get points for a particular package only if all your answers on this package were correct
Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
Auto comment: topic has been updated by balbit (previous revision, new revision, compare).
Auto comment: topic has been updated by balbit (previous revision, new revision, compare).