https://atcoder.jp/contests/abc143/tasks/abc143_eBecause I hear that O((n + m) log n) Dijkstra is slow, I tried it. Indeed, it is slow. I hear that fibonacci heap is faster than binary heap, so I tried it. Indeed, it is fast. But does this…

Official Editorial https://discuss.codechef.com/t/cnnct2-editorial/40191Please consider this problem: Please construct two trees on each graph so that the number of edges which appears in both trees as many as possible. This problem is the…

Official Editorial : https://discuss.codechef.com/t/jiit-editorial/39300My solution is really complicated. As far as viewing other people's solutions, more simple solution exists.We can consider the row and the col independently, so it is …

https://judge.yosupo.jp/problem/exp_of_formal_power_seriesI implemented the algorithm to compute exp(f(x)) by divide and conquer described in https://arxiv.org/abs/1807.11597. To improve performance, I did the following. Precalculate the F…

https://codeforces.com/contest/1228/problem/EI used inclusion-exclusion principle. Let R_i be the event that the minimum of i-th row is not 1, and C_i is similarly defined. Then the answer is can be written as\begin{align} | \overline{R_1}…

https://codeforces.com/contest/1229/problem/CStraight forward solution runs in O(Q sqrt(N)). Let's prove this fact by potential analysis. We define the potential of this problem as the sum of the degrees of the vertices whose in-degree is …

https://codeforces.com/contest/1229/problem/DConsider this problem : How many permutations can be represented by the product of P[L] ... P[R]? In other words, please find the order of the group generated by P[L] ... P[R]. Then, this answer…

https://atcoder.jp/contests/agc038/tasks/agc038_bRolling hash is useful in this problem. For example, we are given 2013754689 and K=4, then suppose that we are now looking at 20[1375]4689. In this case, we write "1", "3", "5", "7" on the s…

https://atcoder.jp/contests/agc038/tasks/agc038_cBefore solving this task, solve this problem.\begin{align} f_k = \sum_{\mathrm{gcd}(i, j)=k} a_i b_j. \end{align}We can find this from the following by inclusion-exclusion principle.\begin{a…

https://atcoder.jp/contests/agc038/tasks/agc038_dType 0 has transitivity, that is for all a, b, c, if there is exactly one path between a and b and there is exactly one path between b and c, then there is exactly one path between a and c. …

https://codeforces.com/contest/1221/standingsFirst, if there is a segment whose length x is B Second, if there are two or more segments whose length x is 2B, the second player always wins. The optimal movement of the second player is to ma…

https://atcoder.jp/contests/abc141/tasks/abc141_eThere exists the way to find LCS (longest common prefix) using DP. LCS, LCP and edit distance are typical problems of string DP. Since the ant book describes only LCS, LCS may be not well kn…

https://atcoder.jp/contests/abc141/tasks/abc141_fIf the number of ones on i-th bit is odd, 2^i is always added to the answer no matter how we classified them. Therefore, we can use an usual approach for finding lexicographically maximum. W…

https://codeforces.com/contest/1209/problem/FSuppose that we already understand the official editorial. Official solution is really simple but I didn't come up with this algorithm without reading it. Instead, I will explain another way to …

https://yukicoder.me/problems/no/879Struct generator is available on Github now. github.com The lazy information on LZ segtree usually has linearity. So, it can be expressed by a matrix. This time, we prepare a vector having (value, odd or…

https://codeforces.com/contest/1217/problem/FIt didn't take long to come up with a solution, but I couldn't remove bugs during a contest.I always make mistakes due to index variables name and loop range. To avoid them, I wrote a code which…

https://codeforces.com/contest/1214/problem/FIf we have to solve sequence version instead of a circular sequence, greedy solution will work. Specifically, we first sort both sequences according to its coordinate, then match elements having…

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_l?lang=jaSince $(x \bmod 10^K) = 0 \iff (x \bmod 2^K) = 0 \land (x \bmod 5^K) = 0$, we can use brute-force. I got TLE when using non-constexpr mod. #include <bits/stdc++.h> #define rep(i, n) for (int i </bits/stdc++.h>…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_f Before explaining the solution, we first explain the four typical problems. These often appears in various counting problems. Problem 1 How many are there N non-negative integer…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_eWe should calculate not the maximum spanning forest but the maximum pseudo forest. K - 種類数 β uses similar property. We know we can swap edges in any tree, and we can also swap…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_cLooking at elements from left to right, we'll decide to open or close an interval. We can determine which operation we should do by the parity of the number of intervals currentl…

https://codeforces.com/contest/1207/problem/GI'm not good at string problems, but I have solved it luckily. First we construct the Aho-Corasick of the query strings. If N strings is produced by type 2 except the first string, we can direct…

https://codeforces.com/contest/1204/problem/EI just wanted to draw figures. #include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) using namespace std; using ll = long long; constexp</bits/stdc++.h>…

https://atcoder.jp/contests/abc138/taskshttps://drive.google.com/file/d/15FST30n57Kb4yDPkUfNV4E4XR8qL8XLN/viewProblem C We should use items in ascending order because the first item thrown into the bin is finally multiplied by 1/2**(N-1). …

Problem - F2 - CodeforcesI wonder why my solutions passes. My solution is quite different from the official solution. We assume that the optimal solution forms like this. In the following figure, elements are sorted in descending order acc…

https://codeforces.com/contest/1200/problem/EThe array used in KMP algorithm is useful to compute the length of common string. Someone may think this algorithm is squared time, but we don't have to treat whole string, so it works in linear…

F - Polynomial Constructiondrive.google.comProblem C: I forget a hashtable whenever I use C++. C++'s hashtable is really dangerous because it doesn't use randomness.Problem D: Considering reversed time, the items we can choose increases. T…

https://atcoder.jp/contests/abc136/tasks/abc136_fI solved problems with F# because I don't want to use C++. Although I prefer to OCaml, I gave up it due to 64bit integers. I use verbose F# because in off-side rule we can't restore indents …

F - Permutation OddnessAny permutation can be represented as a permutation. For example, [0,8,3,6,9,7,2,5,1,4] can be drawn as the following graph.The oddness is the sum of the number of edges across over the lines. Let us consider doing D…

The answer is \[ [x^M] \frac{1}{{}_N \mathrm{H}_M}\prod_{i=1}^{N} \left( C_i + (C_i+1)x + (C_i+2)x^2 + \cdots \right). \]We already know\[ 1+x+x^2+\cdots = \frac{1}{1-x}. \]\begin{align} x+2x^2 + 3x^3 + \cdots &= x \frac{d}{dx} (1+x+x^2+\c…