Inspired by ivan100sic's [problem list blog](https://codeforces.me/blog/entry/98630), 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](https://szkopul.edu.pl/problemset/problem/v2Y2_UW56ENMcbwP22tkTb7a/site/?key=statement)). ↵
↵
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:↵
↵
1. [Multidrink 2013](https://szkopul.edu.pl/problemset/problem/GyDCbdIgFY5FsMa9iIsBl3hf/site/?key=statement) [Solved Jan 15]↵
↵
<spoiler summary="Fun-ness:">↵
5/10↵
↵
<spoiler summary="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. ↵
↵
<spoiler summary="my ugly code (if ppl not doing the challenge want to take a peek?)">↵
↵
```c↵
#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;↵
↵
}↵
↵
```↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
2. [Snake 2014](https://szkopul.edu.pl/problemset/problem/3zwfwt3ZGc2f6NndNgzS3Dfu/site/?key=statement)↵
3. [Arkanoid 2016](https://szkopul.edu.pl/problemset/problem/O730xgZEVynTWBmscBinhMbD/site/?key=statement) [Solved Jan 16]↵
↵
<spoiler summary="Fun-ness:">↵
4/10↵
↵
<spoiler summary="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...↵
↵
<spoiler summary="more ugly code">↵
↵
```c↵
#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);↵
↵
}↵
```↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
↵
↵
4. [Strikes 2017](https://szkopul.edu.pl/problemset/problem/lR_LabSUC2n7EMmDHpw-wk_b/site/?key=statement) [Solved Jan 16]↵
↵
<spoiler summary="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↵
↵
<spoiler summary="code :/">↵
```c↵
#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;↵
}↵
↵
}↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
5. [Rally 2014](https://szkopul.edu.pl/problemset/problem/BnzEADCfeJFjjev1Y9iHQANg/site/?key=statement)↵
6. [Trips 2015](https://szkopul.edu.pl/problemset/problem/zKf5Ua8okcS0jngsrTgKVM9L/site/?key=statement) [Solvd Jan 18]↵
↵
<spoiler summary="Fun-ness:">↵
3/10↵
↵
<spoiler summary="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.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="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 ↵
↵
```c↵
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.......↵
</spoiler>↵
↵
7. [Panini 2017](https://szkopul.edu.pl/problemset/problem/w-dbshXVyRol4LIT9jeP-bNn/site/?key=statement)↵
8. [Crossroads of Parity 2017](https://szkopul.edu.pl/problemset/problem/-7cqC3RrH4e-Ar7DWy4GKzLv/site/?key=statement)↵
9. [Hydrocontest 2016](https://szkopul.edu.pl/problemset/problem/y9HM1ctDU8V8xLMRUYACDIRs/site/?key=statement)↵
10. [Sorcerers 2015](https://szkopul.edu.pl/problemset/problem/fuTBSUcQ2U9sVPYJUDI4JwIe/site/?key=statement)↵
11. [Direction Signs 2015](https://szkopul.edu.pl/problemset/problem/4roJ2TqCXhLN6ftK2jiWKlO9/site/?key=statement)↵
↵
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 :)
↵
It seems to me that POI is better suited for this format as their editorials are quite difficult to find (if possible [at all](https://szkopul.edu.pl/problemset/problem/v2Y2_UW56ENMcbwP22tkTb7a/site/?key=statement)). ↵
↵
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:↵
↵
1. [Multidrink 2013](https://szkopul.edu.pl/problemset/problem/GyDCbdIgFY5FsMa9iIsBl3hf/site/?key=statement) [Solved Jan 15]↵
↵
<spoiler summary="Fun-ness:">↵
5/10↵
↵
<spoiler summary="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. ↵
↵
<spoiler summary="my ugly code (if ppl not doing the challenge want to take a peek?)">↵
↵
```c↵
#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;↵
↵
}↵
↵
```↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
2. [Snake 2014](https://szkopul.edu.pl/problemset/problem/3zwfwt3ZGc2f6NndNgzS3Dfu/site/?key=statement)↵
3. [Arkanoid 2016](https://szkopul.edu.pl/problemset/problem/O730xgZEVynTWBmscBinhMbD/site/?key=statement) [Solved Jan 16]↵
↵
<spoiler summary="Fun-ness:">↵
4/10↵
↵
<spoiler summary="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...↵
↵
<spoiler summary="more ugly code">↵
↵
```c↵
#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);↵
↵
}↵
```↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
↵
↵
4. [Strikes 2017](https://szkopul.edu.pl/problemset/problem/lR_LabSUC2n7EMmDHpw-wk_b/site/?key=statement) [Solved Jan 16]↵
↵
<spoiler summary="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↵
↵
<spoiler summary="code :/">↵
```c↵
#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;↵
}↵
↵
}↵
↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
5. [Rally 2014](https://szkopul.edu.pl/problemset/problem/BnzEADCfeJFjjev1Y9iHQANg/site/?key=statement)↵
6. [Trips 2015](https://szkopul.edu.pl/problemset/problem/zKf5Ua8okcS0jngsrTgKVM9L/site/?key=statement) [Solvd Jan 18]↵
↵
<spoiler summary="Fun-ness:">↵
3/10↵
↵
<spoiler summary="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.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="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 ↵
↵
```c↵
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.......↵
</spoiler>↵
↵
7. [Panini 2017](https://szkopul.edu.pl/problemset/problem/w-dbshXVyRol4LIT9jeP-bNn/site/?key=statement)↵
8. [Crossroads of Parity 2017](https://szkopul.edu.pl/problemset/problem/-7cqC3RrH4e-Ar7DWy4GKzLv/site/?key=statement)↵
9. [Hydrocontest 2016](https://szkopul.edu.pl/problemset/problem/y9HM1ctDU8V8xLMRUYACDIRs/site/?key=statement)↵
10. [Sorcerers 2015](https://szkopul.edu.pl/problemset/problem/fuTBSUcQ2U9sVPYJUDI4JwIe/site/?key=statement)↵
11. [Direction Signs 2015](https://szkopul.edu.pl/problemset/problem/4roJ2TqCXhLN6ftK2jiWKlO9/site/?key=statement)↵
↵
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 :)
