Today I virtual’ed ioi 2025 day 1. tl;dr: would be 40th day 1, which is like high silver.
my log:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
[13:08]jay_jayjay. AIternet : 00:00 read A
[13:29]jay_jayjay. AIternet : 39 mindsolve on A
[13:59]jay_jayjay. AIternet : im ngl i have no progress at all
[13:59]jay_jayjay. AIternet : on A
[14:13]jay_jayjay. AIternet : i might have full A but hella sketch
[14:20]jay_jayjay. AIternet : gna impl A
[14:21]jay_jayjay. AIternet : mfw i trigger sl
[14:51]jay_jayjay. AIternet : ac A
[14:52]jay_jayjay. AIternet : ugh i got wa cuz i was printing debug stuff :skull: i thought that didnt matter on interactive but whatever
[14:52]jay_jayjay. AIternet : ok imma read B
[14:52]jay_jayjay. AIternet : technically i have lb signal that B is cursed ish but imma ignore it
[14:52]jay_jayjay. AIternet : what the fuck
[14:53]jay_jayjay. AIternet : i dont need lb signal to know that this is cursed
[15:04]jay_jayjay. AIternet : i have 24 on B but lowk thats kinda silly
[15:30]jay_jayjay. AIternet : ok i have like
[15:30]jay_jayjay. AIternet : 35
[15:31]jay_jayjay. AIternet : but still not great
[15:51]jay_jayjay. AIternet : i think i 70
[15:51]jay_jayjay. AIternet : gnna impl
[16:33]jay_jayjay. AIternet : nvm fakesolve
[16:33]jay_jayjay. AIternet : 42.6
[16:33]jay_jayjay. AIternet : huh
[16:35]jay_jayjay. AIternet : 53.6
[16:35]jay_jayjay. AIternet : huhh
[16:35]jay_jayjay. AIternet : howd i get subtask 5
[16:35]jay_jayjay. AIternet : how
[16:58]jay_jayjay. AIternet : wtf is C
[16:58]jay_jayjay. AIternet : actually wtf
[16:59]jay_jayjay. AIternet : i have like
[16:59]jay_jayjay. AIternet : 70 ish maybe
[16:59]jay_jayjay. AIternet : on C
[16:59]jay_jayjay. AIternet : but like i would never code it :skull:
[17:15]jay_jayjay. AIternet : famous last words
[17:15]jay_jayjay. AIternet : chat imma code it
[18:04]jay_jayjay. AIternet : lowk 4 mins left i give up
[18:04]jay_jayjay. AIternet : ts problem too cancer
[18:04]jay_jayjay. AIternet : anyway [screenshot of distro: 100/53.97/72]
my solve process for A:
It was kinda like, notice you must guess $P_0-1$ at the start, and then you either get like a single or multiple, and you know the sum of it. and that’s like all the information you get. After inspecting $n=3$ case (you either get one, and that’s ez, or you get two, and the only solution which is forced is to take floor midpoint as next guess). In an attempt to generalize, guessing floor average seems like good idea. at this point I’m playing around and i realize you just ignore the missing info about the prefix etc and keep guessing deeper until you get to the end, and then refactor in the info you get from the end. it kinda works out. code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include "souvenirs.h"
[template]
#define bs bitset<100>
struct eq {
mutable bs b;
mutable ll s;
friend bool operator<(const eq& a, const eq& b) {
return a.b._Find_first() > b.b._Find_first();
}
};
void buy_souvenirs(int n, ll p0) {
vector<ll> ans(n,-1);
set<eq> eqs;
eqs.insert({bs(1),p0});
vector<int> used(n);
set<int> idk;for(int i=0;i<n;i++)idk.insert(i);
while(eqs.size()) {
auto& e = *min_element(all(eqs));
ll guess=0;
if(e.b.count()==1) {
// we know this bit now yay
int i = e.b._Find_first();
ans[i]=e.s;
//printf("we know %d: %lld\n",i,e.s);
eqs.erase(e);
idk.erase(i);
for(auto&f:eqs) {
if(f.b[i]) {
f.b[i]=0;
f.s-=e.s;
}
}
if(!idk.count(i+1)) continue;
guess=e.s-1;
}
else {
guess=e.s/e.b.count();
}
//printf("guess: %lld\n",guess);
pair<vector<int>,ll> res = transaction(guess);
eq f;
f.s=guess - res.second;
for(auto x:res.first) {
used[x]++;
if(ans[x]==-1)
f.b[x]=1;
else f.s-=ans[x];
}
//cout<<f.b<<' '<<f.s<<endl;
eqs.insert(f);
}
for(int i=0;i<n;i++) {
while(used[i]<i)
transaction(ans[i]),used[i]++;
}
};
Anyway this was nice to solve, maybe two hours is a bit too much tho since this seems perhaps easier.
My approach to B was to casework through the matchings of the heights and distances. 5 of the cases turn out to be doable in O(n) but I couldn’t figure out the last case :skull:. Anyway if you just do that you end up with like 50ish points. Plus for part B i just did rng(5) and i got $\eps$ points so great.
I actually don’t know why I get subtask 5, but i got it, so free points ig?
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#pragma GCC optimize("Ofast")
[template]
#include "triples.h"
//long long count_triples(std::vector<int> H) {
//return 0ll;
//}
ll count_triples(vector<int> h) {
int n=size(h);
auto ok=[&](int x) { return 0<=x&&x<n; };
vector<array<int,3>> tri;
int cnt=0;
auto found = [&](int i, int j, int k) {
//printf("found %d %d %d\n",i,j,k);
//tri.push_back({i,j,k});
cnt++;
};
// C on right
//printf("type 1\n");
for(int i=0;i<n;i++) {
int j=i+h[i];
if(!ok(j)) continue;
int k=j+h[j];
if(!ok(k)) continue;
if(h[k]!=k-i) continue;
found(i,j,k);
}
//printf("type 2\n");
for(int i=0;i<n;i++) {
int j=i-h[i];
if(!ok(j)) continue;
int k=i+h[j];
if(!ok(k)) continue;
if(h[i]==h[j])continue;
if(h[k]!=k-j) continue;
found(j,i,k);
}
//printf("type 3\n");
// C on left
for(int i=0;i<n;i++) {
int j=i-h[i];
if(!ok(j)) continue;
int k=j-h[j];
if(!ok(k)) continue;
if(h[k]!=i-k) continue;
found(k,j,i);
}
//printf("type 4\n");
for(int i=0;i<n;i++) {
int j=i+h[i];
if(!ok(j)) continue;
int k=i-h[j];
if(!ok(k)) continue;
//printf("%d %d %d\n",i,j,k);
if(h[i]==h[j])continue;
if(h[k]!=j-k) continue;
found(k,i,j);
}
//printf("type 5\n");
// C in middle, easy case
for(int i=0;i<n;i++) {
int j=i+h[i];
if(!ok(j)) continue;
int k=i+h[j];
if(!ok(k)) continue;
if(h[k]!=k-j) continue;
if(h[i]==h[k]) continue;
found(i,j,k);
}
//printf("type 6\n");
// C in middle, hard case
// ahhh this is gonna be so much pain...
// [commented out wrong code cuz im stupid]
for(int i=0;i<n;i++) {
//int l = max(lef[i]+1,i+1-h[i]);
//int r = min(i-1+h[i],rgt[i]-1);
int l = max(0,i+1-h[i]);
int r = min(i-1+h[i],n-1-h[i]);
for(int j=l;j<=r;j++) {
int k=j+h[i];
if(h[j]-j==h[i]-i && h[k]+k==h[i]+i) {
found(j,i,k);
}
}
}
//for(auto&x:tri)sort(all(x));
//sort(all(tri));
//tri.resize(unique(all(tri))-tri.begin());
//printf("tri sz = %d\ncnt=%d\n",size(tri),cnt);
return cnt;
}
vector<int> construct_range(int n, int k) {
srand(time(0));
//vector<int> a(n);for(int i=0;i<n;i++)a[i]=1+(i&1);
vector<int> a(n);for(int i=0;i<n;i++)a[i]=rand()%5+1;
return a;
}
C was lowk kinda cancer to write IMO and also cancer to solve. Also I was at like 1hr mark so i wrote the first thing i thought of.
It’s like take some arbitrary spanning tree and do like small squares in big squares like those venn diagram thingies. Then add down-edges arbitrarily somewhere. Impl is a bit pain tho.
Honestly did not like this problem rly…
sorry for the messy code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
[template]
#include "worldmap.h"
int n,k;
vector<vector<int>> adj;
vector<int> vis;
vector<int> wi,ht,tin,dep;
vector<int> flag;
vector<vector<int>> a;
int ti=0;
array<int,2> work(int v, int p=-1) {
vis[v]=1;
tin[v]=ti++;
int wid=1, hgt=1, nc=0;
for(auto x:adj[v]) if(x!=p) {
if(vis[x]) {
if(tin[x]>tin[v])nc++;
}
else {
dep[x]=dep[v]+1;
auto [w,h]=work(x,v);
wid+=w+1;
hgt=max(hgt,1+h);
}
}
if(nc) {
wid+=2,hgt=max(hgt,2*nc);
}
if(tin[v]==dep[v]&&wid>1)wid--,flag[v]|=1;
wi[v]=wid;ht[v]=hgt;
//printf("%d; %d %d\n",v,wid,hgt);
return {wid,hgt};
}
void solve(int v, int x, int y, int p=-1) {
vis[v]=1;
tin[v]=ti++;
// paint [x,y] to [x+wid,mx]
for(int i=x;i<x+wi[v];i++)for(int j=y;j<y+ht[v];j++)a[i][j]=v;
//if(tin[v]==dep[v])x--;
//if(tin[v]==dep[v]&&wi[v]>1)x--;
if(flag[v]&1)x--;
int j=1;
vector<int> nc;
for(auto u:adj[v]) if(u!=p) {
if(vis[u]) {
if(tin[u]>tin[v])
nc.push_back(u);
}
else {
solve(u,x+1,y+1,v);
x+=wi[u]+1;
}
}
for(auto k:nc) {
a[x+1][y+j]=k;
j+=2;
}
}
vector<vector<int>> create_map(int n_, int m, vector<int> eda, vector<int> edb) {
vis.clear();adj.clear();wi.clear();ht.clear();tin.clear();
flag.clear();
dep.clear();
n=n_;
flag.resize(n);
vis.resize(n);
dep.resize(n);
adj.resize(n);
wi.resize(n);
ht.resize(n);
tin.resize(n);
for(int i=0;i<m;i++) {
eda[i]--;edb[i]--;
adj[eda[i]].push_back(edb[i]);
adj[edb[i]].push_back(eda[i]);
}
auto [h,w] = work(0);
printf("w h %d %d\n",h,w);
k=max(h,w);
//vector<vector<int>> a(k,vector<int>(k));
a.clear();
ti=0;
vis.assign(n,0);
a.resize(k);for(auto&x:a)x.resize(k);
solve(0,0,0);
for(auto&x:a)for(auto&y:x)y++;
printf("ratio = %lf\n",1.*k/n);
return a;
}
OK it appears I’ve been a bit lucky in not getting stuck in impl pitfalls today. but also my solve speed is not up to date (or my impl speed, or my solve skill really). but the perf was ok and that’s all that matters trust.
lowk i do feel bad for all the ioi competitors who were thrown off by being at like 2000m elevation that must be rough.
p.s. (probably) one of my classmates changed my handle to AIternet when I wasn’t looking……… (btw speaking of ai i think i did worse than ai)
