Inspired by ivan100sic's [problem list blog](https://codeforces.net/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)↵
4. [Strikes 2017](https://szkopul.edu.pl/problemset/problem/lR_LabSUC2n7EMmDHpw-wk_b/site/?key=statement)↵
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)↵
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)↵
↵
↵
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)↵
4. [Strikes 2017](https://szkopul.edu.pl/problemset/problem/lR_LabSUC2n7EMmDHpw-wk_b/site/?key=statement)↵
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)↵
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)↵
↵
↵
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 :)
