Hopefully more frequent posts from now on.
Relay
JOIG Spring Training Camp 2021/2022 #1-1
In this problem, you’re given $N$ pairs of numbers $A_i$ and $B_i$ . Then, you must find the minimum possible value of $A_i + max(B_i, B_j) + A_j + max(B_j, B_k) + A_k$ , where $i, j, k$ are distinct.
Without loss of generality, lets say $B_i \leq B_j \leq B_k$ . Then, we can change the equation above to the following: $A_i + B_j + A_j + B_k + A_k$ , and if we have chosen an $i, j, k$ , that would be the minimum value possible.
Therefore, we can order all the pairs in decreasing order of $B_i$ , put $A_i + B_i$ into a priority queue, then find the minimum value for every $A_i$.
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
#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
int main(){
fastio;
ll n; cin >> n;
pll a[200010] = {};
priority_queue<ll> pq;
for(int i=1;i<=n;i++){
cin >> a[i].ff >> a[i].ss;
}
sort(a+1,a+1+n,[&](pll x, pll y){
return x.ss>y.ss;
});
pq.push(-a[1].ff-a[1].ss);
pq.push(-a[2].ff-a[2].ss);
ll ans = LLONG_MAX;
for(int i=3;i<=n;i++){
ll k1 = pq.top(); pq.pop();
ll k2 = pq.top(); pq.pop();
ans = min(-k1-k2+a[i].ff,ans);
pq.push(k1); pq.push(k2);
pq.push(-a[i].ff-a[i].ss);
}
cout << ans;
}
Melons
JOIG Spring Training Camp 2021/2022 #2-1
In this problem, you are given the maximum capacity of a box, and the weight of $N$ melons. For a given $x$, you start putting in melons in a box, and when putting in the next melon causes the box to go over the capacity, you start putting melons in the next box. You must calculate how many boxes in total you need, and the weight of the last box for every $x$.
This problem can be solved using dynamic programming. Lets call $dp_i$ the weight of the last box, and $cnt_i$ the number of boxes needed. Using the prefix sum, we can find the index of the last melon that will go into the first box. Lets call this $idx$. If $idx \geq N$ then all the melons are going in the last box. Otherwise, $dp_i = dp_{idx+1}$ and $cnt_i = cnt_{idx+1} + 1$.
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
#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
ll n,l,a[200010],dp[200010],pfx[200010],cnt[200010];
int main(){
fastio;
cin >> n >> l;
for(int i=1;i<=n;i++){
cin >> a[i];
pfx[i] = pfx[i-1]+a[i];
}
dp[n] = a[n]; cnt[n] = 1;
for(int i=n-1;i>=1;i--){
ll idx = lower_bound(pfx+1,pfx+1+n,pfx[i-1]+l) - pfx;
if(pfx[idx]>pfx[i-1]+l) idx--;
if(idx>=n){
dp[i] = pfx[n] - pfx[i-1];
cnt[i] = 1;
}
else{
dp[i] = dp[idx+1];
cnt[i] = cnt[idx+1]+1;
}
}
for(int i=1;i<=n;i++){
cout << cnt[i] << " " << dp[i] << "\n";
}
}
평면그래프와 삼각형
Baekjoon Online Judge(BOJ) 1762
In this problem, you are given a planar graph, and must find the number of triangles(more specifically, cycles of length 3).
The solution to this problem is really simple. for every edge, we count the number of triangles including that edge, then divide the total number with 3.
When finding the number of triangles containing the edge, we loop over all the edges connected to the vertex with a lower degree, and check whether the other vertex is connected.
I’m not exactly sure why the solution works in the given time limit, but the time complexity of the solution is somewhere around $O(N\sqrt{N})$, due to the graph being planar(I think).
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
#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
ll n,m,deg[100010];
vector<ll> g[100010];
vector<pll> v;
map<pll,ll> mp;
int main(){
fastio;
cin >> n >> m;
for(int i=0;i<m;i++){
ll x,y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
v.push_back({x,y});
deg[x]++; deg[y]++;
mp[{x,y}] = mp[{y,x}] = 1;
}
ll ans = 0;
for(int i=0;i<m;i++){
ll x = v[i].ff, y = v[i].ss;
if(deg[x]>deg[y]) swap(x,y);
for(auto j:g[x]){
ans += mp[{j,y}];
}
}
cout << ans/3;
}
Earthquake
ONTAK 2010 #7-3
The problem statement is a little confusing, but your goal is to calculate the number of non-negative integers $x, y$ that satisfy the inequality $ax + by \leq c$.
I had no idea how to solve this problem when I first saw it, and when I looked up the solution, it was pretty amazing to see it.
What we are trying to calculate is:
\[\sum_{i=0}^{\lfloor c/a \rfloor} \lfloor \frac{c-ai}{b} \rfloor+1 = \sum_{i=1}^{\lfloor c/a \rfloor} \lfloor \frac{c-ai}{b} \rfloor + \lfloor \frac{c}{a} \rfloor + \lfloor \frac{c}{b} \rfloor + 1\]Lets condense the sigma part in the right hand side of the equation to $F(a,b,c)$.
The way we are going to calculate that is by doing something similar to the Euclidean algorithm. In the Euclidean algorithm, we can use the fact that $gcd(a,b) = gcd(b,r)$ to calculate the greatest common divisor in $O(loga)$ time. Similarly, we’re somehow going to change $F(a,b,c)$ into the form of $F(b,r,?)$ in order to calculate it in logarithmic time.
First, lets set $a = bq + r$. Then:
\[ax + by = (bq + r)x + by = b(qx + y) + rx = bu + rv \leq c\]Where $u \geq qv + 1$ and $v \geq 1$. Now, we somehow have to change the limit for $u$ so that it is greater or equal than 1, and we achieve our goal.
If we look at $v$ for a second, we can find that it has two bounds. $v \leq \frac{u-1}{q}$ and $v \leq \frac{c-bu}{r}$. It would be a good idea to know which one is the “stronger” bound, so if we put the right side to be equal, we can find that the stronger bound changes when $u = \lfloor \frac{cq+r}{a} \rfloor$. Lets call this value $t$.
When $u \leq t$, then $v \leq \frac{u-1}{q}$. If we change things around a bit, we can find that $qv + 1 \leq u \leq t$, thus the number of values for $u$ is equal to $t - (qv + 1) + 1$ which is equal to $t - qv$. Since we know that $1 \leq v \leq \frac{t-1}{q}$, we can calculate the number of values for $u$ in $O(1)$ time.
When $u > t$, then $v \leq \frac{c-bu}{r}$, and therefore $bu + rv \leq c$. If we subtract $bt$ on both sides it becomes $b(u-t) + rv \leq c-bt$. Since $u > t$, $u - t \geq 1$ and we know $v \geq 1$, therefore the number of values for $u, v$ is equal to $F(b,r,c-bt)$, which is the shape we were initially looking for. Similar to the Euclidean algorithm, this can be calculated in $O(loga)$ time.
I don’t know about you, but I thought this sort of solution was very interesting.
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
#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
ll solve(ll a, ll b, ll c){
if(a<b) swap(a,b);
if(c/a<100){
ll ans = 0;
for(int i=1;i<=c/a;i++){
ans += (c-a*i)/b;
}
return ans;
}
ll q = a/b, r = a%b, t = (c*q+r)/a;
ll x = (t-1)/q*(2*t-(1+(t-1)/q)*q)/2;
ll y = solve(b,r,c-b*t);
return x+y;
}
int main(){
fastio;
ll a,b,c; cin >> a >> b >> c;
cout << solve(a,b,c)+c/a+c/b+1;
}
It’s a Mod, Mod, Mod, Mod World
North American Invitational Programming Contest(NAIPC) 2019 #D
In this problem, you are given $p, q, n$ and must calculate $\Sigma_{i = 1}^{n} ((p\cdot i)mod \space q)$. The solution to this problem is extremely similar to the solution to Earthquake.
Since $x \space mod \space m = x - \lfloor \frac{x}{m} \rfloor \cdot m$, we can change the equation into the following:
\[\sum_{i = 1}^{n}((p\cdot i)mod \space q) = \sum_{i = 1}^{n}(pi - \lfloor \frac{pi}{q} \rfloor \cdot q) = \frac{n(n+1)}{2}p - q\sum_{i = 1}^{n}\lfloor \frac{pi}{q} \rfloor\]Lets put $F(p,q,n) = \Sigma_{i = 1}^{n} \lfloor \frac{pi}{q} \rfloor$. Now we must find a way to calculate this quickly.
If $p > q$ then $p = \lfloor \frac{p}{q} \rfloor q + p\%q$. If we put this in the equation, then it will become the following:
\[\sum_{i = 1}^{n}\lfloor \frac{pi}{q} \rfloor = \frac{n(n+1)}{2}\lfloor \frac{p}{q} \rfloor + \sum_{i = 1}^{n}\lfloor \frac{(p\%q)i}{q} \rfloor\]Now we can solve the problem by simply thinking that $p < q$.
If we change the problem a bit, it’s possible to notice that the sum were trying to calculate is equal to the number of lattice points under or on the line $y = \frac{p}{q}x$, ($y \geq 0, \space x \leq n$). It’s hard to calculate the number of lattice points in the triangle, so lets calculate it by subtracting from the number of lattice points in the rectangle. This can be calculated like the following:
\[\sum_{i = 1}^{n}\lfloor \frac{pi}{q} \rfloor = \lfloor \frac{pn}{q} \rfloor n - \sum_{i = 1}^{\lfloor pn/q \rfloor} \lfloor \frac{qi}{p} \rfloor + \lfloor \frac{n}{q} \rfloor\]The equation is basically taking the number of lattice points in the rectangle, subtracting the number of points in the upper triangle, and adding the number of points on the line. It’s easier to understand if you draw it on paper.
The sum on the right side of the equation is equal to $F(q,p,\lfloor pn/q \rfloor)$, and thus the total sum can be calculated in logarithmic time.
One final thing to note is that the calculations were done under the premise that $p$ and $q$ are coprime, so we must divide them by their greatest common divisor before solving.
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
#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
ll solve(ll p, ll q, ll n){
if(!p) return 0;
if(p>=q) return n*(n+1)/2*(p/q) + solve(p%q,q,n);
if(p<q) return p*n/q*n-solve(q,p,p*n/q)+n/q;
return 0;
}
int main(){
fastio;
ll t; cin >> t;
while(t--){
ll p,q,n; cin >> p >> q >> n;
ll g = __gcd(p,q);
cout << n*(n+1)/2*p-q*solve(p/g,q/g,n) << "\n";
}
}