Heres PS journal 2. It’s a little late because I had exams.
Also I decided not to translate titles due to laziness. However, I will briefly explain the problem in the description.
삼색 그래프
Baekjoon Online Judge(BOJ) 24024
In this problem, you are given a simple undirected weighted graph, where each edge has one of the colors black, blue or red. With the graph, you can either increase the weight of every blue edge by one, or every red edge by one. Then, by increasing the weight as explained at most $X$ times, your task is to find the maximum length of the shortest distance between two nodes.
When solving this problem, one thing you can easily figure out is the fact that it is always optimal to increase the weight $X$ times. This is because increasing the weight of any edge can only increase the shortest distance(or it stays the same), and never decrease it.
Lets say we increase the weight of $t$ blue vertices and $X-t$ red vertices. Then, for the path $(w,r,b)$ the distance would be $f(t) = w + rX + (b-r)t$.
For every possible (w,r,b), if you plot out f(t) and take the minimum of all the lines, the result will be a convex shape. This means that the function will keep increasing, reach the maximum, and then keep decreasing. With such a funtion, we can use ternary search to find the maximum.
If we use dijkstra’s algorithm to find the shortest distance, it will take $O((V+E)logV)$ time to find the shortest distance. Since the ternary search will take $O(logX)$ time, the total time complexity of the solution would be $O((V+E)logElogX)$.
As a sidenote, this problem can also be solved using binary search.
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
#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 path{
ll e,w;
ll col;
bool operator < (path&O) const{
return w<O.w;
}
};
ll n,m,k;
vector<path> g[200010];
ll dist[200010];
ll dijkstra(ll st, ll en, ll t){
for(int i=1;i<=n;i++) dist[i] = 1e15;
dist[st] = 0;
priority_queue<pll> pq;
pq.push({0,st});
while(!pq.empty()){
ll cur = pq.top().ss, w = -pq.top().ff;
pq.pop();
if(w>dist[cur]) continue;
for(auto i:g[cur]){
ll nxt = i.e, nc = w+i.w;
ll col = i.col;
if(col==1) nc += t;
else if(col==2) nc += k-t;
if(nc<dist[nxt]){
dist[nxt] = nc;
pq.push({-nc,nxt});
}
}
}
return dist[en];
}
int main(){
fastio;
cin >> n >> m >> k;
for(int i=0;i<m;i++){
ll a,b,c,d;
cin >> a >> b >> c >> d;
g[a].push_back({b,c,d});
g[b].push_back({a,c,d});
}
ll s=0,h=k,ans=0;
while(s+5<h){
ll l = (2*s+h)/3;
ll r = (s+2*h)/3;
ll d1 = dijkstra(1,n,l), d2 = dijkstra(1,n,r);
if(d1>d2){
h = r;
ans = max(ans,d1);
}
else{
s = l;
ans = max(ans,d2);
}
}
for(int i=s;i<=h;i++){
ll d = dijkstra(1,n,i);
ans = max(ans,d);
}
cout << ans;
}
외판원 순회 3
Baekjoon Online Judge(BOJ) 16991
This problem is the infamous traveling salesman problem, where you have to find a tour that visits every point, and returns to the starting point that has the minimum distance of travel. In this problem, the maximum number of cities is 16, therefore a naive solution won’t work, and we must use dynamic programming.
Let’s define $dp_{ij}$ as the minimum distance where $i$ is the current point and $j$ is a bitmask where the bits with the index of the visited points are on. Then, we can find the value of $dp_{ij}$ using a top down approach. Remember that after all points have been visited(all the bits in $j$ are on), the current point must be equal to the starting point.
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
#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
pii a[20];
double cost[20][20];
double dp[16][1<<16];
int n;
double solve(int s, int v){
if(v==(1<<n)-1){
if(cost[s][0]==0) return 1e30;
else return cost[s][0];
}
double& res = dp[s][v];
if(res) return res;
double l = 1e30;
for(int i=1;i<n;i++){
if(cost[s][i]!=0&&(v&(1<<i))==0){
l = min(l,cost[s][i]+solve(i,v|(1<<i)));
}
}
res = l;
return res;
}
int main(){
fastio;
cin >> n;
for(int i=0;i<n;i++) cin >> a[i].ff >> a[i].ss;
for(int i=0;i<n;i++){
int x = a[i].ff, y = a[i].ss;
for(int j=i+1;j<n;j++){
int xx = a[j].ff, yy = a[j].ss;
cost[i][j] = sqrt(pow(x-xx,2)+pow(y-yy,2));
cost[j][i] = cost[i][j];
}
}
cout.precision(10);
cout << fixed << solve(0,1);
}
PLAĆE
Crotian Open Competition in Informatics(COCI) 2011/2012 constest #3 #5
In this problem, every person has a superior, and the superior can raise all of its subordinates wages. When given the relation between people, you need to perform the following two queries:
- Increase the wage of the subordinates of some person
- Print the wage of a certain employee
If this were a problem where the queries are performed on a sequence, it would be easily solvable using segment trees and lazy propagation. So lets change the problem to work like this.
Every person has only one superior, except for one person, who is everybody’s superior. There for, the relation between the employees would have a shape of a tree, where an edge connects an employee and its superior.
We can perform a dfs starting from the root of that tree and assign an index to each employee based on when we search it. Also, we can keep track of which index the superior of an employee has, as well as which index the subordinate of an employee ends.
This way, increasing the wage would be adding a value on a certain range, and thus we can use segment trees with lazy propagation 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
#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 500010
int n,m,c;
int s[MAX],e[MAX],a[MAX],lazy[4*MAX],tree[4*MAX];
vector<int> g[MAX];
void dfs(int x){
s[x] = ++c;
for(auto i:g[x]){
if(!s[i]) dfs(i);
}
e[x] = c;
}
void ulazy(int node, int s, int e){
if(!lazy[node]) return;
tree[node] += lazy[node]*(e-s+1);
if(s!=e){
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
int update(int node, int s, int e, int l, int r, int val){
ulazy(node,s,e);
if(l>e||r<s) return tree[node];
if(l<=s&&e<=r){
lazy[node] += val;
ulazy(node,s,e);
return tree[node];
}
int mid = (s+e)/2;
return tree[node] = update(node*2,s,mid,l,r,val)+update(node*2+1,mid+1,e,l,r,val);
}
int query(int node, int s, int e, int l, int r){
ulazy(node,s,e);
if(l>e||r<s) return 0;
if(l<=s&&e<=r) return tree[node];
int mid = (s+e)/2;
return query(node*2,s,mid,l,r)+query(node*2+1,mid+1,e,l,r);
}
int main(){
fastio;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
if(i!=1){
int x; cin >> x;
g[x].push_back(i);
}
}
dfs(1);
for(int i=1;i<=n;i++) update(1,1,n,s[i],s[i],a[i]);
while(m--){
char c; cin >> c;
if(c=='p'){
int x,y; cin >> x >> y;
if(s[x]==e[x]) continue;
update(1,1,n,s[x]+1,e[x],y);
}
else{
int x; cin >> x;
cout << query(1,1,n,s[x],s[x]) << "\n";
}
}
}
같은 탑
Baekjoon Online Judge(BOJ) 1126
In this problem, we are given the height of a few blocks, where the sum of the heights are at most $500,000$. Then, we must determine the maximum possible height that two towers both have using the given blocks, or determine that it is impossible.
This problem can be solved using dynamic programming. Let $dp_{i,j}$ be the maximum height when we used $i$ blocks and the height difference between the two towers are $j$. Then, there are 5 possible scenario’s.
Lets say were on our $i$’th block, and the current difference between height is $j$. Also, let $a_i$ be the height of the $i$’th block. Then:
- If $dp_{i-1,j} = -1$($-1$ meaning impossible), there is no tower available to stack on in the first place, so we continue.
- If we choose not to stack the $i$’th block, then $dp_{i,j} = max(dp_{i,j}, dp_{i-1,j})$.
- If we choose to stack it on the higher tower, the height difference will become $j + a_i$, therefore $dp_{i,j+a_i} = max(dp_{i,j+a_i}, dp_{i-1,j} + a_i)$.
- If we choose to stack in on the lower tower, there are two possibilities:
- If $j < a_i$ then the total height increases, therfore $dp_{i,a_i-j} = max(dp_{i,a_i-j}, dp_{i-1,j}+a_i-j)$.
- If $j \geq a_i$ then the total height stays the same, therefore $dp_{i,j-a_i} = max(dp_{i,j-a_i}, dp_{i-1,j})$.
If we fill in the dp table based on the above scenarios, the answer will be $dp_{n,0}$, where $n$ is the number of blocks.
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
#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 500010
int n,a[100],dp[51][500001],sz=0;
int main(){
fastio;
cin >> n;
for(int i=0;i<n;i++){
cin >> a[i];
sz += a[i];
}
memset(dp,-1,sizeof(dp));
dp[0][0] = 0;
dp[0][a[0]] = a[0];
for(int i=1;i<n;i++){
for(int j=0;j<=sz;j++){
if(dp[i-1][j]==-1) continue;
dp[i][j] = max(dp[i][j],dp[i-1][j]);
dp[i][j+a[i]] = max(dp[i][j+a[i]],dp[i-1][j]+a[i]);
if(j<a[i]) dp[i][a[i]-j] = max(dp[i][a[i]-j],dp[i-1][j]+a[i]-j);
if(j>=a[i]) dp[i][j-a[i]] = max(dp[i][j-a[i]],dp[i-1][j]);
}
}
if(dp[n-1][0]==-1||dp[n-1][0]==0) cout << -1;
else cout << dp[n-1][0];
}
JuQueen
German Collegiate Programming Contest(GCPC) 2014 #H
In this problem, we must perform three types of queries on a sequence:
- Change the value at some index
- Change the value of the indices in a given range
- Return the value of a certain index
In addition to the queries, there is a maximum minimum value each index can have(minimum being 0), and if changing the value goes over or under it, we just increase or decrease until we reach the limit. Plus, we have to return how much we increased or decreased for queries 1 and 2.
The queries themselves can be solved by using a segment tree with lazy propagation. However, since we have to know whether we go over the maximum or minimum value, we should also use two segment trees to keep track of the maximum and minimum values in a certain range.
Then, for each query, we can check if the maximum value in the range goes over the given limit, or if the minimum value goes below zero. If so, we can calculate how much we need to change, output that, and change the values.
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
127
128
#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 5000010
int c, n, o, minseg[4*MAX], maxseg[4*MAX], minlazy[4*MAX], maxlazy[4*MAX], x, y, z;
void xlazy(int node, int x, int y) {
if (!maxlazy[node])
return;
maxseg[node] += maxlazy[node];
if (x!=y) {
maxlazy[node * 2] += maxlazy[node];
maxlazy[node * 2 + 1] += maxlazy[node];
}
maxlazy[node] = 0;
}
void nlazy(int node, int x, int y) {
if (!minlazy[node])
return;
minseg[node] += minlazy[node];
if (x != y) {
minlazy[node * 2] += minlazy[node];
minlazy[node * 2 + 1] += minlazy[node];
}
minlazy[node] = 0;
}
void xupdate(int lo, int hi, int val, int node, int x, int y) {
xlazy(node, x, y);
if (y < lo || hi < x)
return;
if (lo <= x&&y <= hi) {
maxlazy[node] += val;
xlazy(node, x, y);
return;
}
int mid = (x + y) >> 1;
xupdate(lo, hi, val, node * 2, x, mid);
xupdate(lo, hi, val, node * 2 + 1, mid + 1, y);
maxseg[node] = max(maxseg[node * 2], maxseg[node * 2 + 1]);
}
void nupdate(int lo, int hi, int val, int node, int x, int y) {
nlazy(node, x, y);
if (y < lo || hi < x)
return;
if (lo <= x&&y <= hi) {
minlazy[node] += val;
nlazy(node, x, y);
return;
}
int mid = (x + y) >> 1;
nupdate(lo, hi, val, node * 2, x, mid);
nupdate(lo, hi, val, node * 2 + 1, mid + 1, y);
minseg[node] = min(minseg[node * 2], minseg[node * 2 + 1]);
}
int maxquery(int lo, int hi, int node, int x, int y) {
xlazy(node, x, y);
if (y < lo || hi < x)
return 0;
if (lo <= x&&y <= hi)
return maxseg[node];
int mid = (x + y) >> 1;
return max(maxquery(lo, hi, node * 2, x, mid), maxquery(lo, hi, node * 2 + 1, mid + 1, y));
}
int minquery(int lo, int hi, int node, int x, int y) {
nlazy(node, x, y);
if (y < lo || hi < x)
return 500001;
if (lo <= x&&y <= hi)
return minseg[node];
int mid = (x + y) >> 1;
return min(minquery(lo, hi, node * 2, x, mid), minquery(lo, hi, node * 2 + 1, mid + 1, y));
}
int main() {
fastio;
cin >> c >> n >> o;
while(o--){
string a;
cin >> a;
int res;
if (a == "state") {
cin >> x;
res = maxquery(x, x, 1, 0, c - 1);
}
else if (a == "change") {
cin >> x >> y;
int v = maxquery(x, x, 1, 0, c - 1), val;
if (v + y > n) val = n-v;
else if (v + y < 0) val = -v;
else val = y;
xupdate(x, x, val, 1, 0, c - 1);
nupdate(x, x, val, 1, 0, c - 1);
res = val;
}
else {
cin >> x >> y >> z;
int val;
if (z > 0) {
int v = maxquery(x, y, 1, 0, c - 1);
if (v + z > n) val = n-v;
else val = z;
}
else {
int v = minquery(x, y, 1, 0, c - 1);
if (v + z < 0) val = -v;
else val = z;
}
xupdate(x, y, val, 1, 0, c - 1);
nupdate(x, y, val, 1, 0, c - 1);
res = val;
}
cout << res << "\n";
}
}
New Years Party
USA Computing Olympiad(USACO) Winter 2022 Contest Green #2
In this problem on person can bring $K$ dishes, and each dish can have one distinct food for each person. Also, there is a limit to how much each food can be brought. Then, you must figure out the maximum number of dishes that can be brought.
This is a flow problem. We can connect the source with each person, where the weight is the number of dishes $K$. Then, we connect each person with the food that they can bring, the weight being one, since one person can’t bring two of the same food. Finaly, we connect the food with the sink, with the weight being the maximum number each food can be brought.
Once we create the graph, the maximum flow is the answer to the 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
#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 1000010
const int START = 300+1, END = 300+2;
int ret;
int cap[401][401],flo[401][401],from[401];
vector<int> node[401];
void nflow(){
while(1){
fill(from,from+401,-1);
queue<int> q;
q.push(START);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto& next:node[cur]){
if(cap[cur][next]-flo[cur][next]>0&&from[next]==-1){
from[next]=cur;
q.push(next);
if(next==END) break;
}
}
}
if(from[END]==-1) break;
int flow = 2e9;
for(int i=END;i!=START;i=from[i]) flow = min(flow,cap[from[i]][i]-flo[from[i]][i]);
for(int i=END;i!=START;i=from[i]){
flo[from[i]][i] += flow;
flo[i][from[i]] -= flow;
}
ret += flow;
}
}
int main(){
fastio;
int n,k,d; cin >> n >> k >> d;
for(int i=1;i<=n;i++){
node[START].push_back(i);
node[i].push_back(START);
cap[START][i] = k;
}
for(int i=200+1;i<=200+d;i++){
int x; cin >> x;
node[i].push_back(END);
node[END].push_back(i);
cap[i][END] = x;
}
for(int i=1;i<=n;i++){
int t; cin >> t;
for(int j=0;j<t;j++){
int f; cin >> f;
f += 200;
node[i].push_back(f);
node[f].push_back(i);
cap[i][f] = 1;
}
}
nflow();
cout << ret;
}
당근과 채찍
Baekjoon Online Judge(BOJ) 26527
In this problem, for multiple test cases, you are given two values $a$ and $b$. Each time you feed the horse a carrot, its ‘feeling’ increase by $b$, and if you hit it, it decreases by $a$. If the horses feeling goes below $0$, it will abandon you. Then, you must find the number of ways to feed the horse $a$ carrots and hit it $b$ time without it abandoning you(with modulo $10^9+7$.
If we plot the feeling for a sequence, we will get a graph that starts and ends at $0$. It is easy to know that only when the lowest point of the graph is at the beginning, will all the other points be positive.
Therefore, for every $(a+b)$ sequences there will be one possible answer. In other words, the answer will be ${a+b \choose a} \frac{1}{a+b}$.
Now we just have to calculate that quickly. The given formula can changed into the following: $\frac{(a + b - 1)!}{a!b!} = (a + b - 1)! \times (a!)^{-1} \times (b!)^{-1}$.
We can calculate all of the factorials in $O(a+b)$ time. In addition, since $(a+1)!^{-1} \times (a+1) = a!^{-1}$, we can calculate the inverse of all the factorials in $O(a+b)$ time as well.
Once all the precomputation has been done, each test case can be solved in $O(1)$ 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
#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 1000010
const ll mod = 1000000007LL;
ll fac[2000010],inv[2000010];
int main(){
fastio;
fac[1] = 1LL; fac[0] = 1LL;
for(int i=2;i<=2000000;i++){
fac[i] = (fac[i-1]*i)%mod;
}
inv[2000000] = 407182070LL;
for(int i=1999999;i>=1;i--){
inv[i] = (inv[i+1]*(i+1))%mod;
}
int t; cin >> t;
while(t--){
ll a,b; cin >> a >> b;
cout << (((fac[a+b-1]*inv[a])%mod)*inv[b])%mod << "\n";
}
}