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
- Trips 2015 [Solvd 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.
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.......
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 :)
