Educational Codeforces Round 58 F Trucks and Cities
https://codeforces.com/contest/1101/problem/F
The following solution is faster than mine. It is based on the fact that the prefix maximum doesn't change at most O(log N) times.
https://codeforces.com/blog/entry/64438?#comment-483640
There is an articles about this fact.
https://codeforces.com/blog/entry/62602
My solution is also used randomization, but it is not based on another fact.
If for all i we do binary search, time is not enough. So we first pick i randomly, and then find the answer only for it. Then, the answers of almost half of i s is less than this answer, so we can remove them. Repeat this thing, this action doesn't happen in O(log n) times.
But we got TLE. Sampling 10 elements instead of single element, finally I got AC.
https://codeforces.com/contest/1101/submission/48256161
Educational DP Contest Z Flog 3
https://atcoder.jp/contests/dp/tasks/dp_z
It is convex hull trick. There are two ways to understrand CHT, the one is using lines, another is using points.
We are given N points (a[i], b[i]) on the a-b plain. And then given $x$, please find the maximum value of $a_i x + b_i$ and find what point gives such a maximum. CHT is used in such a problem. Since $\mathrm{grad} (ax+b)=(x,1)$, we move toward the direction $(x,1)$, the value increases. For example $x=1$, the gradient is as follows.
Therefore, the most farthest point in direction $(x,1)$ gives the maximum. This point must be on the convex hull, so we move on the convex hull, finally find the answer. In this phase, we can use binary search.
By the way, we can generalize CHT. Given $x$ and $y$, please find the maximum of $a_i x + b_i $.
Codeforces Hello 2019 F. Alex and a TV Show
https://codeforces.com/contest/1097/problem/F
A[k] denote the number of multiples of k included in the multiset A. Then the following holds.
\[(A \cup B)[i]=A[i]+B[i]\]\[(A \times B)[i]=A[i] \times B[i]\]
Clearly, $A \cup B$. Conversely, $a$ and $b$ is both a multiple of $i$ if and only if $\gcd(a,b)$ が $i$ if a multiple of i.
Therefore, we can reduce the problem not condidering the number of k in the multiset, but considering the number of multiples of k in the multiset. After finding it, we should reduce the answer fitting the original condition. By inclusion exclusion
\[ A[k]-A[2k]-A[3k]-A[5k]+A[6k]-A[7k]+A[10k]-A[11k]-A[13k]+A[14k]+A[15k]+ \cdots \]
gives original values. Precisely,
\[ A[k] - \sum_{p}A[pk] + \sum_{p < q}A[pqk] - \sum_{p < q < r} A[pqrk] + \cdots \]
Since this problem only requires mod 2 values, we can use bitsets
Good Bye 2018 D New Year and the Permutation Concatenation
https://codeforces.com/contest/1091/problem/D
The sum is N(N+1)/2 is equivalent to the sequence is a permutation. For N=10, we have two permutations
AAAABBBBBB CCCCDDDDDD
When BBBBBBCCCC is a permutation, BBBBBB is not sorted in descending order. That's why, if BBBBBB is not descending order, since AAAABBBBBB < next(AAAABBBBBB)=CCCCDDDDDD <= AAAA + reverse_sort(BBBBBB), BBBBBBCCCC is a permutation, if it is descending order, since we cannot get larger permutation by rearranging BBBBBB, we should use the number in BBBBB to CCCC in CCCC. Therefore, BBBBBBCCCC cannot be a permutation. So we only have to find the number of permutations satisfying such a property, and this is
\begin{align}
N!+\sum_{k=1}^{N-1} \left(N! - \frac{N!}{k!}\right)
\end{align}
December Lunchtime 2018 Find Best Path
https://www.codechef.com/LTIME67A/problems/BESTPATH
The distance array D[i] is filled with zero. Then start Bellman-ford, finally D[i] stores the shortest distance between a certain vertex and vertex i. If there are no negative cycles, we can obtain the answer.
When we are repeating Bellman-ford, if a value changes after N iterations, there must be a negative cycles through vertex i. If i is on a negative cycle, the vertices reachable from i are also on a negative cycle.
Johnson's algorithm is too slow to pass all cases. If we use SPFA instead of Dijkstra, we got AC.
2N times loop is not enough for detecting negative cycles because there is a counterexample.
1 3 3 2 1 1000000 2 3 -1 3 2 -1
#include <stdio.h> int T, N, M; int U[1000], V[1000], W[1000]; long long D[1000], E[1000]; int tau0[1000]; int tau1[1000]; int neg0[1000]; int neg1[1000]; void solve() { scanf("%d %d", &N, &M); for (int i = 0; i < M; i++) { scanf("%d %d %d", &U[i], &V[i], &W[i]); U[i]--; V[i]--; } for (int i = 0; i < N; i++) { D[i] = 0; E[i] = 0; tau0[i] = 0; tau1[i] = 0; neg0[i] = 0; neg1[i] = 0; } for (int i = 1; i <= N * 2; i++) { for (int j = 0; j < M; j++) { if (D[V[j]] > D[U[j]] + W[j]) { D[V[j]] = D[U[j]] + W[j]; tau0[V[j]] = i; } if (E[U[j]] > E[V[j]] + W[j]) { E[U[j]] = E[V[j]] + W[j]; tau1[U[j]] = i; } } } for (int i = 0; i < N; i++) { if (tau0[i] >= N) neg0[i] = 1; if (tau1[i] >= N) neg1[i] = 1; } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { neg0[V[j]] |= neg0[U[j]]; neg1[U[j]] |= neg1[V[j]]; } } for (int i = 0; i < N; i++) { if (!neg0[i] && !neg1[i]) { printf("%lld\n", D[i] + E[i]); } else { puts("INF"); } } } int main() { scanf("%d", &T); while (T--) { solve(); } }
