Ever since I made this blog, I was too lazy to write anything frequently. Therefore, I’m going to start this PS journal type post where I write about problems I solved during a certain time period(probably a week).
I’ll leave a link to a place where you can read the problems, though some might be in korean while others will have english translations. I’ll also write a translation to the problem title if it’s not in english. Finally, I’ll write where the problem is from if I know it.
I probably won’t write detailed descriptions of the solution, more like a brief overview. I’ll try to leave the code if necessary, although it will be very messy without any comments. On that note, lets get started.
DVDs
2013 ACM-ICPC Thailand National Programming Contest #G
In this problem, you have a sequence that consists of numbers 1 to $n$, and must perform 2 queries.
- Swap two numbers with the indices $A$ and $B$
- When given two indices $A$ and $B$($A \leq B$), check if all numbers from $A$ to $B$ exist between indices $A$ and $B$.
It is easy to notice that this problem is solved using segment trees. The first query can be done by simply changing the value at a certain index twice.
The second query is a bit more complex. However, if you think about it, if the maximum value between indices $A$ and $B$ is $B$, and the minimum is $A$, then the rest should all be between $A$ and $B$, therefore satisfying the query. Therfore, for the second query, all we have to do is find the maximum and minimum value within the range, which can be done easily with a segment tree.
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
#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;
#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
#define INF 0x7f7f7f7f
ll a[100010];
ll xtree[4*100010],ntree[4*100010];
int n,m;
int minu(int node, int s, int e, int idx, int x){
if(idx<s||idx>e) return ntree[node];
if(s==e) return ntree[node] = x;
int mid = (s+e)/2;
return ntree[node] = min(minu(node*2,s,mid,idx,x),minu(node*2+1,mid+1,e,idx,x));
}
int maxu(int node, int s, int e, int idx, int x){
if(idx<s||idx>e) return xtree[node];
if(s==e) return xtree[node] = x;
int mid = (s+e)/2;
return xtree[node] = max(maxu(node*2,s,mid,idx,x),maxu(node*2+1,mid+1,e,idx,x));
}
int fmin(int node, int s, int e, int l, int r){
if(r<s||l>e) return INT_MAX;
if(l<=s&&e<=r) return ntree[node];
int mid = (s+e)/2;
return min(fmin(node*2,s,mid,l,r),fmin(node*2+1,mid+1,e,l,r));
}
int fmax(int node, int s, int e, int l, int r){
if(r<s||l>e) return 0;
if(l<=s&&e<=r) return xtree[node];
int mid = (s+e)/2;
return max(fmax(node*2,s,mid,l,r),fmax(node*2+1,mid+1,e,l,r));
}
int main(){
int t; scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
a[i] = i;
maxu(1,0,n-1,i,i);
minu(1,0,n-1,i,i);
}
for(int i=0;i<m;i++){
int x,y,z; scanf("%d%d%d",&x,&y,&z);
if(x==0){
minu(1,0,n-1,y,a[z]);
maxu(1,0,n-1,y,a[z]);
minu(1,0,n-1,z,a[y]);
maxu(1,0,n-1,z,a[y]);
swap(a[z],a[y]);
}
else{
int t1 = fmin(1,0,n-1,y,z);
int t2 = fmax(1,0,n-1,y,z);
//cout << t1 << " " << t2 << "\n";
if(t1==y&&t2==z) printf("YES\n");
else printf("NO\n");
}
}
}
}
트리와 쿼리 1(Trees and Queries 1)
Baekjoon Online Judge(BOJ) 13510
In this problem, you are given a tree with weighted edges and must perform two queries.
- Change the $i$’th edges weight to $c$
- Find the maximum weight of an edge on the path from node $u$ to $v$
This problem is an introduction problem to heavy-light decomposition. Each nodes weight can be defined as the weight of the edge that connects itself and its parent node. Then heavy-light decomposition can be used to perform the queries.
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#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;
#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
#define INF 0x7f7f7f7f
#define MAX 100010
struct segtree{
int tree[4*100010];
void update(int x, int v, int node, int s, int e){
if(x<s||x>e) return;
if(s==e) tree[node] = v;
else{
int m = (s+e)/2;
update(x,v,node*2,s,m);
update(x,v,node*2+1,m+1,e);
tree[node] = max(tree[node*2],tree[node*2+1]);
}
}
int query(int l, int r, int node, int s, int e){
if(r<s||l>e) return 0;
if(l<=s&&e<=r) return tree[node];
int m = (s+e)/2;
return max(query(l,r,node*2,s,m),query(l,r,node*2+1,m+1,e));
}
}seg;
int n;
int sz[MAX], dep[MAX], par[MAX], top[MAX], in[MAX], out[MAX], w[MAX];
vector<pii> g[MAX];
vector<pii> inp[MAX];
vector<pair<pii,int> > edg;
int vis[MAX];
void dfs(int v=1){
vis[v] = 1;
for(auto i:inp[v]){
if(vis[i.ff]) continue;
vis[i.ff] = 1;
g[v].push_back({i.ff,i.ss});
dfs(i.ff);
}
}
void dfs1(int v=1){
sz[v] = 1;
for(auto &i:g[v]){
dep[i.ff] = dep[v]+1; par[i.ff] = v;
dfs1(i.ff); sz[v] += sz[i.ff];
if(sz[i.ff] > sz[g[v][0].ff]) swap(i.ff,g[v][0].ff);
}
}
int pv;
void dfs2(int v=1){
in[v] = ++pv;
for(auto i:g[v]){
top[i.ff] = i.ff==g[v][0].ff?top[v]:i.ff;
dfs2(i.ff);
}
out[v] = pv;
}
void update(int v, int w){
seg.update(in[v],w,1,1,n);
}
int query(int a, int b){
int ret = 0;
while(top[a]^top[b]){
if(dep[top[a]]<dep[top[b]]) swap(a,b);
ret = max(ret,seg.query(in[top[a]],in[a],1,1,n));
a = par[top[a]];
}
if(dep[a]>dep[b]) swap(a,b);
ret = max(ret,seg.query(in[a]+1,in[b],1,1,n));
return ret;
}
void init(int v=1){
for(auto &i:g[v]){
update(i.ff,i.ss);
init(i.ff);
}
}
int main(){
fastio;
cin >> n;
for(int i=1;i<n;i++){
int a,b,c; cin >> a >> b >> c;
inp[a].push_back({b,c});
inp[b].push_back({a,c});
edg.push_back({ {a,b},c});
}
dfs(); dfs1(); dfs2();
for(int i=0;i<n-1;i++){
if(edg[i].ff.ff==par[edg[i].ff.ss]){
swap(edg[i].ff.ff,edg[i].ff.ss);
}
update(edg[i].ff.ff,edg[i].ss);
}
int m; cin >> m;
while(m--){
int x,y,z; cin >> x >> y >> z;
if(x==2){
if(y==z){
cout << 0 << "\n";
continue;
}
if(y>z) swap(y,z);
cout << query(y,z) << "\n";
}
else{
update(edg[y-1].ff.ff,z);
}
}
}
트리(Tree)
Korean Olympiad in Informatics(KOI) 2016 highschool #3
In this problem you are given an unweighted tree, and must perform several queries. Basically, you must figure out if a path from node $u$ ti $v$ exists, and depending on the query must remove an edge.
To solve this problem, we can think of edges that exist an edge that has weight 1, and an edge that doesn’t an edge with weight 0. Then we can do the boolean AND operation(&&) on all the weights on the path from two nodes. If the result is 1, then a path exists, else it doesn’t.
Then, removing an edge would become changing an edges weight to 0. This and the AND operation can be both performed using heavy-light decomposition.
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
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#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
#define INF 0x7f7f7f7f
#define MAX 200010
struct segtree{
int tree[4*MAX];
void update(int x, int v, int node, int s, int e){
if(x<s||x>e) return;
if(s==e){
tree[node] = v;
}
else{
int m = (s+e)/2;
update(x,v,node*2,s,m);
update(x,v,node*2+1,m+1,e);
tree[node] = tree[node*2]&&tree[node*2+1];
}
}
int query(int l, int r, int node, int s, int e){
if(r<s||l>e) return 1;
if(l<=s&&e<=r) return tree[node];
int m = (s+e)/2;
return query(l,r,node*2,s,m)&&query(l,r,node*2+1,m+1,e);
}
}seg;
int n,m;
int sz[MAX], dep[MAX], par[MAX], top[MAX], in[MAX], out[MAX];
vector<int> g[MAX];
void dfs1(int v=1){
sz[v] = 1;
for(auto &i:g[v]){
dep[i] = dep[v]+1; par[i] = v;
dfs1(i); sz[v] += sz[i];
if(sz[i] > sz[g[v][0]]) swap(i,g[v][0]);
}
}
int pv;
void dfs2(int v=1){
in[v] = ++pv;
for(auto i:g[v]){
top[i] = i==g[v][0]?top[v]:i;
dfs2(i);
}
out[v] = pv;
}
void update(int v, int w){
seg.update(in[v],w,1,1,n);
}
int query(int a, int b){
int ret = 1;
while(top[a]^top[b]){
if(dep[top[a]]<dep[top[b]]) swap(a,b);
ret = ret&&seg.query(in[top[a]],in[a],1,1,n);
a = par[top[a]];
}
if(dep[a]>dep[b]) swap(a,b);
ret = ret&&seg.query(in[a]+1,in[b],1,1,n);
return ret;
}
int main(){
fastio;
cin >> n >> m;
for(int i=1;i<n;i++){
int a; cin >> a;
g[a].push_back(i+1);
}
dfs1(); dfs2();
for(int i=1;i<=n;i++){
update(i,1);
}
while(m--){
int x,y,z; cin >> x >> y >> z;
if(z==0){
if(query(x,y)){
cout << "YES\n";
}
else{
cout << "NO\n";
}
}
else{
if(query(x,y)){
cout << "YES\n";
update(x,0);
}
else{
cout << "NO\n";
update(y,0);
}
}
}
}
TV Show Game
ICPC Asia Regional - Seoul 2018 #K
In this problem you need to find a sequence of either blue or red that satisfies a few conditions stated in the problem.
When three indices $x$, $y$, and $z$ are given along with 3 colors, at least two of them must be the given colors. If we think of blue as true and red as false, we can change this problem into a set of boolean operations.
For example if the three indices are $x$, $y$, and $z$, and the colors are red, red and blue, the following must be true:
$(\neg x \lor \neg y) \land (\neg y \lor z) \land (z \lor \neg x)$
As a result, the problem can be changed into a 2-SAT problem, which is a well known problem.
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
#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;
#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
vector<vector<int> > g,rg;
vector<int> scc;
stack<int> s;
bool vis[10005];
void dfs(int x){
vis[x] = 1;
for(auto next:g[x]){
if(!vis[next]) dfs(next);
}
s.push(x);
}
void rdfs(int x, int y){
vis[x] = 1;
scc[x] = y;
for(int next:rg[x]){
if(!vis[next]) rdfs(next,y);
}
}
int re(int x, int n){
return x>n?x-n:x+n;
}
int main(){
fastio;
int n,m; cin >> n >> m;
g.resize(2*n+5);
rg.resize(2*n+5);
scc.resize(2*n+5);
for(int i=0;i<m;i++){
int a[3]={};
char x[3]={};
for(int j=0;j<3;j++){
cin >> a[j] >> x[j];
if(x[j]=='R') a[j] += n;
}
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
if(j==k) continue;
g[re(a[j],n)].push_back(a[k]);
rg[a[k]].push_back(re(a[j],n));
}
}
}
for(int i=1;i<2*n+1;i++){
if(!vis[i]) dfs(i);
}
memset(vis,0,sizeof(vis));
int idx = 1;
while(!s.empty()){
int x = s.top();
s.pop();
if(!vis[x]) rdfs(x,idx++);
}
for(int i=1;i<=n;i++){
if(scc[i]==scc[i+n]){
cout << -1;
return 0;
}
}
for(int i=1;i<=n;i++){
cout << (scc[i]>scc[n+i]?'B':'R');
}
}
Land Acquisition
USA Computing Olympiad(USACO) March 2007 Contest Gold #1
In this problem, you’re given several rectangles, that can be bought in a special way stated in the problem. Your goal is to find the least amount of money to buy all the land.
Lets first start with sorting the lands based on the width. Then, if there is a land with width $w_i$ and height $h_i$ that are both larger than another land with width $w_j$ and height $h_j$, it is always better to buy these two together. We can search through all lands in $O(n)$ time and remove these kinds of lands. As a result, both the width and height will be sorted.
Now lets use dynamic programming. Lets define $dp_i$ the least amount of money needed to buy all the land form 1 to $i$. Then, we can make the following equation:
$dp_i = min(dp_{j-1} + w_jh_i) \quad (j \leq i)$
This will usually take $O(n^2)$ time to compute, but this case has a special equation that makes it possible to use the convex hull trick to optimize it, therefore resulting in $O(n)$ 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
#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;
#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
struct CHT{
ll sz = 0, p = 0;
ll la[1000001],lb[1000001];
double cross(ll x, ll y){
return 1.0*(lb[y]-lb[x])/(la[x]-la[y]);
}
void insert(ll p, ll q){
la[sz] = p;
lb[sz] = q;
while(sz>1&&cross(sz-1,sz-2)>cross(sz-1,sz)){
la[sz-1] = la[sz];
lb[sz-1] = lb[sz];
sz--;
}
sz++;
}
ll query(ll x){
while(p+1<sz&&cross(p,p+1)<=x) p++;
return lb[p]+la[p]*x;
}
};
CHT cht;
ll n;
pll a[50010];
int main(){
fastio;
cin >> n;
for(int i=0;i<n;i++){
cin >> a[i].ff >> a[i].ss;
}
sort(a,a+n);
reverse(a,a+n);
ll now = -1, prv = 0;
for(int i=0;i<n;i++){
if(now>=a[i].ss) continue;
now = a[i].ss;
cht.insert(a[i].ff,prv);
prv = cht.query(a[i].ss);
}
cout << prv;
}