Writing blog posts is harder than I thought it would be.
Jailbreak
Benelux Algorithm Programming Contest(BAPC) 2013 #J
In this problem, you are given the layout of a jail with walls, doors, and two prisoners. The problem is to find the minimum of number of doors necessary to open in order for a third person to escape the two prisoners
To solve this, lets add an empty layer around the jail. Then we can think of escaping the prisoners as moving them to (0,0). However, finding how the third person has to move still remains a challenge.
Lets change the problem a bit more. Rather than just the third person moving, we can instead think that all three people move, and meet at one point. We can calculate the number of doors each person has to open to reach a certain point, then calculate the total number of doors needed to open for all possible meeting points. This process can be achieved using 0-1 BFS or dijkstra’s.
One thing to remember is that if the meeting point is at a door, to reduce 2 from the total sum of doors opened, as the door at the meeting point is counted 3 time.
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
const ll dx[] = {0,0,-1,1};
const ll dy[] = {-1,1,0,0};
ll n,m,vis[110][110],dist[110][110][3];
char a[110][110];
void bfs(ll sx, ll sy, ll f){
memset(vis,0LL,sizeof(vis));
deque<pll> dq; dq.push_front({sx,sy});
vis[sx][sy] = 1; dist[sx][sy][f] = 0;
while(!dq.empty()){
ll cx = dq.front().ff, cy = dq.front().ss;
dq.pop_front();
for(int i=0;i<4;i++){
ll nx = cx+dx[i], ny = cy+dy[i];
if(nx<0||ny<0||nx>n+1||ny>m+1) continue;
if(vis[nx][ny]||a[nx][ny]=='*') continue;
vis[nx][ny] = 1;
if(a[nx][ny]=='#'){
dist[nx][ny][f] = dist[cx][cy][f] + 1;
dq.push_back({nx,ny});
}
else{
dist[nx][ny][f] = dist[cx][cy][f];
dq.push_front({nx,ny});
}
}
}
}
void solve(){
memset(a,'.',sizeof(a));
memset(dist,-1LL,sizeof(dist));
ll x1,y1,x2,y2,idx=0;
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> a[i][j];
if(a[i][j]=='$'&&!idx){
x1 = i; y1 = j;
idx++;
}
else if(a[i][j]=='$'){
x2 = i; y2 = j;
}
}
}
bfs(0,0,0); bfs(x1,y1,1); bfs(x2,y2,2);
ll ans = LLONG_MAX;
for(int i=0;i<=n+1;i++){
for(int j=0;j<=m+1;j++){
ll d = 0;
if(a[i][j]=='#') d -= 2;
for(int k=0;k<3;k++) d += dist[i][j][k];
if(d!=-3&&ans>d) ans = d;
}
}
cout << ans << "\n";
}
int main(){
fastio;
ll t = 1; cin >> t;
while(t--) solve();
}
오일러 회로
Baekjoon Online Judge(BOJ) 1199
In this problem, you are given a adjacency matrix, and must find an Euler cycle, or report the fact there is none.
It is a well-known fact that an Euler cycle only exists when the degree of all nodes are even. Therefore if there is at least one node with an odd degree we can report that there is no cycle.
To find a cycle, we can simply run a DFS search from some node. However, due to some reason, an $O(VE)$ implementation will exceed the time limit. Hence, more careful implementation is needed.
If your using an adjacency matrix, you must find the next available edge in $O(1)$ or $O(logV)$. If your using an adjacency list, you must find a way to delete edges in $O(1)$ or $O(logV)$. In my case, I implemented an adjacency list using a STL set.
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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
ll n,a[1010][1010],in[1010];
vector<ll> ans;
set<pll> g[1010];
ll tmp;
void dfs(ll i){
while(!g[i].empty()){
auto t = *(g[i].begin());
ll j = t.ff;
tmp = t.ss;
while(tmp){
//cout << g[i].size() << "\n";
g[i].erase({j,tmp}); g[j].erase({i,tmp});
if(tmp-1){
g[i].insert({j,tmp-1});
g[j].insert({i,tmp-1});
}
tmp--;
dfs(j);
}
}
ans.push_back(i);
}
void solve(){
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ll x; cin >> x;
a[i][j] = x;
in[i] += x;
if(x) g[i].insert({j,x});
}
if(in[i]%2){
cout << -1;
return;
}
}
for(int i=1;i<=n;i++){
if(in[i]){
dfs(i);
break;
}
}
for(auto i:ans) cout << i << " ";
}
int main(){
//fastio;
ll t = 1; //cin >> t;
while(t--) solve();
}
Non-boring sequences
Central European Regional Contest(CERC) 2012 #D
In this problem, you have to determine whether or not a sequence is boring. If a sequence is non-boring, all connected subsequences contain a unique element.
For a sequence to be non-boring, it must contain a unique element. Lets say it does. Then every subsequence that contains that element will all have a unique element, hence there’s no need to check them.
Therefore, if we find a unique element, we can split the sequence in two according to that elements location. Then we can continue doing the same thing in the new subsequences. In other words, we can divide and conquer.
Now we just have to think of two things, how to check if an element is unique in a certain range in $O(1)$, and an efficient way to perform the DnC part. As for the DnC part, assuming we can check if an element is unique in $O(1)$, we can perform a bidirectional search in order to reduce time.
To check if an element is unique, the method I used is to precompute the location of the nearest left($L$) and nearest right($R$) element that is the same as the current element. Then, in the range $[S,E]$, is $L < S$ and $R > E$ then we can know that the element is unique in that range in $O(1)$ time. Implementation is not too hard.
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 100010
#define MOD 1000000007
#define performance orange
ll a[200010];
ll pre[200010],suc[200010];
ll dnc(ll s, ll e){
if(s>e) return 1;
ll l = s, r = e;
while(l<=r){
if(pre[l]<s&&suc[l]>e) return dnc(s,l-1)&&dnc(l+1,e);
if(pre[r]<s&&suc[r]>e) return dnc(s,r-1)&&dnc(r+1,e);
l++; r--;
}
return 0;
}
void solve(){
ll n; cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
map<ll,ll> m;
for(int i=1;i<=n;i++){
if(m[a[i]]) pre[i] = m[a[i]];
else pre[i] = 0;
m[a[i]] = i;
}
m.clear();
for(int i=n;i>=1;i--){
if(m[a[i]]) suc[i] = m[a[i]];
else suc[i] = n+1;
m[a[i]] = i;
}
if(dnc(1,n)) cout << "non-boring\n";
else cout << "boring\n";
}
int main(){
fastio;
ll t; cin >> t;
while(t--) solve();
}
Farmer John Solves 3SUM
USA Computing Olympiad(USACO) 2020 January Contest Gold #2
In this problem you are given a sequence $A$ and $Q$ queries. For each query, you must find the number of triplets $i, j, k$ where $A_i + A_j + A_k = 0$ in a given range.
Lets define $DP_{i,j}$ as the number of elements $k$ where $A_i + A_k + A_j = 0$ ($i < k < j$). We can keep track of how often a number occurs in the range $[i,j]$, then set $DP_{i,j}$ to the number of times $- A_i - A_j$ occurs. After that, we can add $DP_{i+1,j} + DP_{i,j-1} - DP_{i+1,j-1}$ to $DP_{i,j}$ to get the total number of triplets that exist inside $[i,j]$.
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 100010
#define MOD 1000000007
#define performance orange
#define tetrio A+
const ll del = 1000001;
ll n,q,a[5010],cnt[2000010],dp[5010][5010];
void solve(){
cin >> n >> q;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=n;i>=1;i--){
for(int j=i+1;j<=n;j++){
if(abs(a[i]+a[j])<=del) dp[i][j] = cnt[del-a[i]-a[j]];
cnt[a[j]+del]++;
dp[i][j] += dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
}
for(int j=i+1;j<=n;j++) cnt[a[j]+del]--;
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout << dp[i][j] << " ";
// }
// cout << "\n";
// }
while(q--){
ll x,y; cin >> x >> y;
cout << dp[x][y] << "\n";
}
}
int main(){
fastio;
ll t = 1; //cin >> t;
while(t--) solve();
}
Making the Grade
USA Computing Olympiad(USACO) 2008 February Contest Gold #1
In this problem problem you are given a sequence $A$ of length $N$, and must create a sequence $B$ of the same length that minimizes $\sum^N_{i=1} |A_i - B_i|$. At the same time, sequence $B$ must be monotone. In other words only one of $B_i \leq B_{i+1}$ or $B_i \geq B_{i+1}$ must be true for all $i$ ($1 \leq i \leq N$).
One key observation to make here is that sequence $B$ is made up of elements in sequence $A$. Once this observation is made, we can use dynamic programming to solve this problem.
Lets define $DP_{i,j}$ as the minimum value achievable when $j$ elements of $A$ are used up until the $i$’th element of $B$. Then $DP_{i,j} = min(DP_{i-1,k}+|A_j - A_i|)$ ($1 \leq k \leq j$).
If we implement simply based on the equation above, the total time complexity is $O(N^3)$, which is not enough. To solve this, lets keep count of $min(DP_{i-1,k})$. Lets define $P_{i,j} = min(DP_{i-1,k})$ ($1 \leq k \leq j$). Then we can figure out that $P_{i,j} = min(P_{i,j-1},DP_{i-1,j})$. Using this we can calculate $P_{i,j}$ as we calculate $DP_{i,j}$. The total time complexity is $O(N^2)$.
Note that we can find $B$ assuming $B$ increases, then reverse $A$ and repeat the same thing to make $B$ decreasing.
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 100010
#define MOD 1000000007
#define performance orange
ll n,a[2010],dp[2010][2010],prv[2010][2010];
vector<ll> b;
int main(){
fastio;
cin >> n;
b.push_back(0);
for(int i=1;i<=n;i++){
cin >> a[i];
b.push_back(a[i]);
}
sort(b.begin()+1,b.end());
b.erase(unique(b.begin()+1,b.end()),b.end());
ll sz = b.size();
for(int j=1;j<sz;j++){
for(int i=1;i<=n;i++){
if(i-1==0) prv[i][j] = prv[i][j-1];
else if(j-1==0) prv[i][j] = dp[i-1][j];
else prv[i][j] = min(prv[i][j-1],dp[i-1][j]);
dp[i][j] = prv[i][j] + abs(a[i]-b[j]);
//cout << prv[i][j] << " ";
}
//cout << "\n";
}
ll ans = LLONG_MAX;
for(int i=1;i<sz;i++) ans = min(ans,dp[n][i]);
reverse(a+1,a+1+n);
for(int j=1;j<sz;j++){
for(int i=1;i<=n;i++){
if(i-1==0) prv[i][j] = prv[i][j-1];
else if(j-1==0) prv[i][j] = dp[i-1][j];
else prv[i][j] = min(prv[i][j-1],dp[i-1][j]);
dp[i][j] = prv[i][j] + abs(a[i]-b[j]);
//cout << prv[i][j] << " ";
}
//cout << "\n";
}
for(int i=1;i<sz;i++) ans = min(ans,dp[n][i]);
cout << ans;
}
보급
Korean Olympiad in Informatics(KOI) 2022 first Highschool #3
In this problem, you are given $N$ points and a range $[A_i,B_i]$ indicating when each point can be supplied. You must assign a supply date to all points that satisfies the conditions below. When the assigned date is $V_i$:
- $A_i \leq V_i \leq B_i$
- for all $i,j$, if $X_i < X_j$ and $Y_i < Y_j$, then $V_i < V_j$
- if $i \neq j$, $V_i \neq V_j$
Lets start by reordering all points in order of increasing $x$ coordinates, so we only have to worry about the $y$ coordinate.
For every $(i,j)$ that satisfies $i < j$ and $Y_i < Y_j$, $V_i < V_j$ must be true, there for we can change the range of the two points into $B_i < V_j \leq B_j$, and $A_i < V_i \leq A_j$. In other words, for all $(i,j)$ that satisfy the condition, we can perform $A_j \leftarrow min(A_j, A_i+1)$, and $B_i \leftarrow min(B_i, B_j-1)$. We can change $A$ in increasing order of $j$, and in decreasing order of $i$ when changing $B$. The change itself can be done in $O(logN)$ time per change using a segment tree.
With the new ranges in place, we just have to find a sequence of $V$ that satisfies those ranges. We can assign $V$ in the order of $B$ starting from the one with the smallest one. This can be done in $O(NlogN)$ using a priority queue.
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
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 100010
#define MOD 1000000007
#define performance orange
ll fmn(ll a, ll b){return min(a,b);}
ll fmx(ll a, ll b){return max(a,b);}
struct Segtree{
ll tree[4*250010], null = 0;
ll (*func)(ll,ll);
Segtree(){
memset(tree,0LL,sizeof(tree));
}
void init(){
fill(tree,tree+4*250010,null);
}
void update(ll n, ll l, ll r, ll x, ll v){
if(x<l||x>r) return;
if(l==r){
tree[n] = v;
return;
}
ll m = (l+r)>>1;
update(2*n,l,m,x,v);
update(2*n+1,m+1,r,x,v);
tree[n] = func(tree[2*n],tree[2*n+1]);
}
ll query(ll n, ll l, ll r, ll s, ll e){
if(e<l||s>r) return null;
if(s<=l&&r<=e) return tree[n];
ll m = (l+r)>>1;
return func(query(2*n,l,m,s,e),query(2*n+1,m+1,r,s,e));
}
};
struct Point{
ll x,y,a,b,i;
friend istream& operator >> (istream& in, Point &p){
return in >> p.x >> p.y >> p.a >> p.b;
}
bool operator > (const Point& p) const {
return b>p.b;
}
};
Segtree tmn, tmx;
ll n,ans[250010];
Point a[250010];
int main(){
fastio;
tmn.func = fmn; tmn.null = LLONG_MAX; tmn.init();
tmx.func = fmx; tmx.null = 0; tmx.init();
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
a[i].i = i;
}
sort(a+1,a+1+n,[&](Point x, Point y){
return x.x<y.x;
});
for(int i=1;i<=n;i++){
a[i].a = max(a[i].a,tmx.query(1,1,n,1,a[i].y)+1);
//cout << a[i].a << "\n";
tmx.update(1,1,n,a[i].y,a[i].a);
}
for(int i=n;i>0;i--){
a[i].b = min(a[i].b,tmn.query(1,1,n,a[i].y,n)-1);
//cout << a[i].b << "\n";
tmn.update(1,1,n,a[i].y,a[i].b);
}
sort(a+1,a+1+n,[&](Point x, Point y){
return x.a<y.a;
});
priority_queue<Point,vector<Point>,greater<Point> > pq;
for(int i=1,j=1;i<=n;i++){
while(j<=n&&a[j].a<=i) pq.push(a[j++]);
if(pq.empty()){
cout << "NO";
return 0;
}
Point p = pq.top(); pq.pop();
if(p.a<=i&&i<=p.b) ans[p.i] = i;
else{
cout << "NO";
return 0;
}
}
cout << "YES\n";
for(int i=1;i<=n;i++) cout << ans[i] << " ";
}