fft | brain

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967E1 - Again Counting Arrays (Easy Version)

CF 1967E1 - Again Counting Arrays (Easy Version) Rating: 3100 Tags: combinatorics, dp, fft, math Solve time: 1m 13s Verified: no Solution Problem Understanding We are given a fixed starting height $b_0$ and we imagine building an integer path $b_0, b_1, \ldots, b_n$ where each step moves by exactly $+1$ or $-1$, but the path is never allowed to go below zero. This is a standard “walk on the non-negative...

Practice › Codeforces Solutions › Codeforces Round 947 (Div. 1 + Div. 2) ›

CF 1975G - Zimpha Fan Club

CF 1975G - Zimpha Fan Club Rating: 3000 Tags: fft, greedy, math, strings Solve time: 5m 19s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472G - Design Tutorial: Increase the Constraints

CF 472G - Design Tutorial: Increase the Constraints Rating: 2800 Tags: bitmasks, data structures, fft Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given two long binary strings, a and b . Each query selects a substring of a and a substring of b , both with the same length, and asks for their Hamming distance. The Hamming distance between two binary strings is simply the number...

Practice › Codeforces Solutions ›

Codeforces Round 181 (Div. 2)

Codeforces Round 181 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 2/3 | Rating range: 1500-2300 | Time: 5m 24s Problem Name Rating Tags Solve Time Verified B Coach 1500 brute-force, dfs-and-similar, graphs 2m 18s ✓ D Painting Square 2300 dp, fft 1m 49s ✗ E Empire Strikes Back 2300 binary-search, math, number-theory 1m 17s ✓

Practice › Codeforces Solutions › Codeforces Round 176 (Div. 1) ›

CF 286E - Ladies' Shop

CF 286E - Ladies' Shop Rating: 2800 Tags: constructive algorithms, fft, math Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given a collection of “bag capacities” $a_1 < a_2 < \dots < a_n$, each capacity describing a special requirement: the bag can exactly accommodate some multiset of item weights whose sum is exactly that capacity, but it is forbidden to use a configuration whose total weight is...

Practice › Codeforces Solutions ›

Codeforces Round 176 (Div. 1)

Codeforces Round 176 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 2/2 | Rating range: 2200-2800 | Time: 2m 31s Problem Name Rating Tags Solve Time Verified B Shifting 2200 implementation 1m 1s ✓ E Ladies' Shop 2800 constructive-algorithms, fft, math 1m 30s ✓

Practice › Codeforces Solutions › Codeforces Round 181 (Div. 2) ›

CF 300D - Painting Square

CF 300D - Painting Square Rating: 2300 Tags: dp, fft Solve time: 1m 49s Verified: no Solution Problem Understanding We are asked to count the number of distinct ways to perform exactly k painting moves on an n × n table with a black border. Each move consists of selecting a square region (minimum size 2×2) entirely white inside the table, and painting a chosen row and column inside that...