pekempey's blog

998244853

AtCoder Beginner Contest 143 E Travel by Car

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…

October Challenge 2019: Faulty System

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…

October Challenge 2019 Queries on Matrix

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 …

Yosupo Judge : Exp of Formal Power Series

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…

Codeforces #589 E. Another Filling the Grid

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}…

CF 588 C. Konrad and Company Evaluation

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 …

CF #588 D. Wojtek and Card Tricks

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…

AGC038 B - Sorting a Segment

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…

AGC 038 C - LCMs

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…

AGC 038 D - Unique Path

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. …

Educational Codeforces 73 E. Game With String

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…

ABC141 E. Who Says a Pun?

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…

ABC141 F Xor Sum 3

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…

Codeforces Round #584 F. Koala and Notebook

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 …

yukicoder No.879 Range Mod 2 Query

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…

Educational Codeforce #72 F. Forced Online Queries Problem

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…

Codeforces #583 F - Employment

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…

TTPC 2019 L. 多項式の零点の個数

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>…

Japanese Student Championship 2019 Qualification F - Candy Retribution

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…

Japanese Student Championship 2019 Qualification E - Card Collector

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…

Japanese Student Championship 2019 Qualification C - Cell Inversion

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…

Educational Codeforces Round 71 (Rated for Div. 2) G. Indie Album

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…

CF 581 Div2. E. Natasha, Sasha and the Prefix Sums

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>…

ABC 138 screencast

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). …

CF 579 Div. 3 F Complete the Projects

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…

CF 578 Div 2 E. Compress Words

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…

ABC 137 screencast

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…

ABC 136 F. Enclosed Points

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 …

ABC134 F. Permutation Oddness

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…

SRM763 1000pts ProductAndProduct

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…