### flamestorm's blog

By flamestorm, 15 months ago,

We hope you enjoyed the contest!

1829A - Love Story

Idea: SlavicG

Tutorial
Solution

1829B - Blank Space

Idea: mesanu

Tutorial
Solution

1829C - Mr. Perfectly Fine

Idea: SlavicG

Tutorial
Solution

1829D - Gold Rush

Idea: flamestorm

Tutorial
Solution

1829E - The Lakes

Idea: mesanu

Tutorial
Solution

1829F - Forever Winter

Idea: flamestorm

Tutorial
Solution

1829G - Hits Different

Idea: flamestorm

Tutorial
Solution

1829H - Don't Blame Me

Idea: SlavicG

Tutorial
Solution
• +90

| Write comment?
 » 15 months ago, # |   +10 thanks for the speedy editorial.
 » 15 months ago, # |   +10 wow what speedy editorial！
 » 15 months ago, # |   0 In F , according to the constraints , if m = 1 , then how x and y could be both greater than 1 such that x*(y+1) = m = 1 ?
•  » » 15 months ago, # ^ |   +8 It is guaranteed that this graph is a snowflake graph.So m=x+xy>2m>=1 doesn't means that m can be 1.
•  » » 15 months ago, # ^ |   0 In fact, $m=n-1$
 » 15 months ago, # |   +32 Problem H can be solved in O(k * 2^k + n) using AND Convolution, as described here: https://mirror.codeforces.com/blog/entry/115438
•  » » 15 months ago, # ^ |   +3 Wow, dude, this is really nice! Because of commutativity of AND, this is possible! I thought that I could solve it as well with convolutions, but didn't see the commutativity and ended up solved it using the standard n * 2^k dp.
•  » » 15 months ago, # ^ |   0 This is very interesting! However, I have a major doubt: How did you realize that applying the inverse SoS on the amount of subsets whose AND contain mask is the same as the amount of subsets whose AND is EXACTLY mask? In the linked blog the example is given for pairs, but I fail to realize how to connect these ideas formally. Did you prove it? Can you share your insight?Maybe I would understand it if I understood why it works for pairs, lol.
 » 15 months ago, # |   0 Wow. Loved G. Though was not able to solve it. But didn't even notice that just rotating it will make it a standard 2-D prefix sum problem. Lol struggled the whole 1hr during the contest.
•  » » 15 months ago, # ^ |   0 Can you please explain it?I am not able to get the tutorial.
•  » » » 15 months ago, # ^ |   0 Maybe it's because you don't know that technique called 2-D prefix sum. Google it and study it.The pattern was [1,3,6..][2,5,9..].Imagine this as the 2-D grid.
•  » » 15 months ago, # ^ |   0 Why I always get tle? long long f[1000010]; int main() { f[1] = 1; long long cnt = 2; for (int i = 2; i < 1420; i++) { f[cnt] = f[cnt - i + 1] + cnt * cnt; cnt++; for (int j = 2; j < i; j++) { f[cnt] = f[cnt - i] + f[cnt - i + 1] + cnt * cnt - f[cnt - i + 1 - i + 1]; cnt++; } f[cnt] = f[cnt - i] + cnt * cnt; cnt++; } int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); printf("%lld\n", f[n]); } return 0; } 
•  » » » 15 months ago, # ^ |   0 use ios:sync_with_stdio(false); command
 » 15 months ago, # |   0 Didn't get H
•  » » 15 months ago, # ^ |   0 It's a standard dp bitmask problem.
•  » » » 7 weeks ago, # ^ |   0 can u refer the classic problem where could i understand it please ?
 » 15 months ago, # |   0 G is possible by simply using sum of squares of N natural numbers for each row and is easy implementation too.https://mirror.codeforces.com/contest/1829/submission/204823035
•  » » 9 months ago, # ^ |   0 can you explain your approach a bit?
 » 15 months ago, # | ← Rev. 2 →   0 in problem F what is the output of this case : 1 2 1 1 2 
•  » » 15 months ago, # ^ | ← Rev. 2 →   +8 $m$ can't be $1$. (https://mirror.codeforces.com/blog/entry/115896?#comment-1027861)
•  » » 15 months ago, # ^ |   +13 There is an additional constraint in the inputs. It is guaranteed that this graph is a snowflake graph for some integers $x$ and $y$ both greater than $1$.
 » 15 months ago, # |   0 Tonight's problems' interesting and not typical, thank the writer and codeforces for such a great contest!
 » 15 months ago, # |   0 Have anyone solved E using BFS?
•  » » 15 months ago, # ^ |   0 Yes. 204779800
•  » » 15 months ago, # ^ |   0 My guess is that most people solved it using BFS
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 I solved it with DFS. However, the code was in Go, and I needed a few submissions to optimize memory usage. Strange thing...
•  » » » » 15 months ago, # ^ |   0 please help me,it is giving Runtime error in test-12
•  » » » » » 15 months ago, # ^ |   0 If you open the submission details, it says that it's "Stack overflow" error. I don't know Java, but you should either increase the stack size or rewrite it using bfs
•  » » » 15 months ago, # ^ |   +8 I solved by union find.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 For this Problem1829E - The LakesThe solution is written in O(n*m)But How it is possible if there is recursion calls inside the nested solution.Solution in tutorial is:Please someone help me understand the time complexity?Shouldn't it be O(n*m*n*m).I know we are not checking same grid twice.Please someone help me.
•  » » 15 months ago, # ^ |   0 I did
 » 15 months ago, # |   +8 Alt solution to G:From the given $n$, try to go upwards to the left block $l_n$, and to the right block $r_n$.If we can visit both ways, there some blocks will be taken twice. So we find the common blocks between $l_n$ and $r_n$ and subtract them from the answer. If the common block exists, it's either $l_{r_n}$ or $r_{l_n}$.There is a recursive relation, until the blocks exist. It can be either of: $ans_n = n*n + ans_{l_n} + ans_{r_n} - ans_{l_{r_n}}$ $ans_n = n*n + ans_{l_n} + ans_{r_n} - ans_{r_{l_n}}$Implementation: 204825154
•  » » 15 months ago, # ^ |   +8 I also coded it this way, but if you look closely, this is actually just the 2d prefix sum solution!
•  » » » 15 months ago, # ^ |   +8 It is!This is just a different way of looking at it, without all the modifications. I feel this is more intuitive.
•  » » 15 months ago, # ^ |   0 this is 2023 per test case right? originally, this solution was right on the edge of passing :( and was supposed to not pass. But setters remembered its a div4.
•  » » » 15 months ago, # ^ |   0 It's actually $10^6$ for all test cases since you can do memoization.Also you do not need all of the $2023$ rows. $x*(x+1)/2 = 10^6$ $x \approx 1414$
 » 15 months ago, # |   +8 For problem F, if you see: Wrong answer on test 2 wrong answer 65th numbers differThen it is the x == y+1 edge case mentioned in editorial.
 » 15 months ago, # | ← Rev. 2 →   0 Someone please help me spot the error in my solution to D I spent almost the entire contest trying to fix it: def solve(n, m): if n == m: return(1) elif n % 3 != 0 or m > n: return(0) elif n // 3 >= m: return(solve(n // 3, m)) else: return(solve(n-(n//3), m)) for tt in range(int(input())): n, m = map(int, input().split()) if solve(n, m): print("YES") else: print("NO") 
•  » » 15 months ago, # ^ |   0 Here is a failing test case: Input: 1 27 8 Correct Output: YES Your Output: NO Can you see why this happens?
 » 15 months ago, # | ← Rev. 2 →   0 204848665my solution for (E) The lakes is clearly an O(mn) solution, but was exceeding limit, can anyone explain where it can be optimised?
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 204858437 is logically same as my solution 204848665 , but the first solution was accepted but mine got TLE, both are written in python
•  » » » 7 months ago, # ^ |   0 Both are giving TLE now, instead I switched from using input to using readline and it worked. 240657725
•  » » 15 months ago, # ^ |   0 Currently you are adding the same squares into the queue multiple times: when adding a new square to the queue you're only checking if you've been to the square before. Importantly, you're not checking if the square has already been added to the queue. This starts actually growing exponentially and the time complexity is definitely not $O(nm)$. It can be fixed with a small modification — changing the place where some operations are done. This ensures that no square will be added to the queue more than once and the complexity is now truly $O(nm)$.204888301
•  » » » 15 months ago, # ^ |   0 understood, thanks for the explanation
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 Actually an even simpler modification gets AC:Before adding the next squares into the queue, just make sure that grid[i][j] > 0. Now no exponential growth will happen and each square will get added to the queue at most 4 times.204889157
 » 15 months ago, # |   0 I tried Solving E using Standard DFS in python Python Code. But I was continuously getting Runtime Error at TC 6. C ++ did the trick though (for the same) C++ code. Can someone tell me why I was getting Error in Python for the same Implementation ?
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 Python's default stack limit is 1000 which can be changed with sys.setrecursionlimit(big number), on cases where you are forced to recurse deeper then 1000 layers (imagine a spiral pattern of values separated by 0's) you will run time error. (Be careful python recursion is very slow so you may run into issues with time limit)Changing to c++ fixed the issue because c++ does not have this issue with low default stack limit.
•  » » » 15 months ago, # ^ |   0 Ps Update: Just tried using it. It didn't make any difference in the outcome of the submission (RE Again ;_;). But thanks again, It was Informative.
•  » » » » 15 months ago, # ^ |   0 Since the grid can be of size 1000 * 1000, you would need the stack limit to be that big as well (ie 1e6+ a bit). Though you might lead to TLE since recursion is quite slow in python. I would suggest if you do get tle (and can't switch languages) to try programming the flood fill as an iterative bfs as although the time complexity is the same the constant factor should be significantly faster.
 » 15 months ago, # |   0 204849479 Why am I getting runtime error in this code?
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 Python's default stack limit is 1000 which can be changed with sys.setrecursionlimit(big number), on cases where you are forced to recurse deeper then 1000 layers (imagine a spiral pattern of values separated by 0's) you will run time error.
 » 15 months ago, # |   0 wow. so speedy
 » 15 months ago, # |   +3 JUST CAME BACK TO VISIT A TAYLOR SWIFT ROUND. OMG!!
•  » » 15 months ago, # ^ |   0 come back...be here (another Taylor's song)
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +8 message in a bottleDear Reader, This is me trying to come back be here at this holy ground. and i almost do, but everything has changed and story of us looks like a tragedy now, so long live, had a marvellous time ruining everything. People in cf are the lucky one and they should stay stay stay.It's time to go - Yours slayor twift
 » 15 months ago, # |   0 Can anybody hack this solution for TLE ?? https://mirror.codeforces.com/contest/1829/submission/204874235
 » 15 months ago, # |   0 Problem F: Observe that the starting vertex is the ONLY vertex that is not a leaf AND also has no leaf neighbours. 204824064
 » 15 months ago, # | ← Rev. 2 →   0 for problem D, why we used this formula for master theorem: T(n) = 2T(n/3) + O(1) , but it's really T(n/3)+T((2*n)/3)+O(1) why we can Ignore that coeff (2*) ? thank you
•  » » 15 months ago, # ^ |   0 Usually for time complexity we don't consider coefficients so we just say it is 2 * T(n/3), since the order is the same.
•  » » » 15 months ago, # ^ |   0 Thank you!
•  » » » » 15 months ago, # ^ |   0 I thik this is wrong. Recurrence T(n)=T(n/3)+T(2n/3) +c has an O(n) solution for T(n). In fact, T(n) is Omega(n). This can be proved by induction easily. That is, you can prove that T(n) >= kn for some k and for every n sufficiently large.
•  » » » » » 5 months ago, # ^ |   0 I agree with juanxo_gu the solution using the master theorem given in solution list lower bound of T(n).
 » 15 months ago, # |   0 Another approach to solve E (https://mirror.codeforces.com/contest/1829/submission/204823633)
 » 15 months ago, # |   0 Have anybody solved problem E without using bfs and DFS???
•  » » 15 months ago, # ^ |   0 Here you can find another approach -> (https://mirror.codeforces.com/contest/1829/submission/204823633)
•  » » 15 months ago, # ^ |   0 I just used dsu
•  » » » 8 months ago, # ^ | ← Rev. 3 →   0 how do you solve it using dsu?
 » 15 months ago, # | ← Rev. 2 →   +3 $H$ can be solved in $(maxa_i^2 * t + ∑n)$ where you can just keep track of how many ways each number between $0-63$ inclusive can be constructed. Submission: 204886301 (binpower is not needed, we can just pre-calculate powers of $2$).
 » 15 months ago, # | ← Rev. 3 →   +9 There is a much faster solution to DEach time you either multiply by 1/3 or 2/3, so the final multiplier must be 2^a / 3^b where a <= b.Then just check whether the ratio m/n can be expressed in that form.Code (gets AC): t=int(input()) import math def ispow(a, b): if a==1: return True else: return a%b==0 and ispow(a//b, b) for i in range(t): line = [int(a) for a in input().split()] n = line[0] m = line[1] s = m // (math.gcd(n,m)) r = n // (math.gcd(n,m)) if ispow(s,2) and ispow(r,3) and math.log2(s) <= math.log(r,3): print('YES') else: print('NO') 204904968There is an even more cheesy solution, where once you realize the 2^a / 3^b and a<=b part, you precompute a list of all such fractions of that form within 10^7, and for each test case, just check whether m/n is equal to some fraction in that list: t=int(input()) def equal(a,b,c,d): return a*d==b*c fractions = [] for b in range(15): for a in range(b+1): fractions.append([2**a, 3**b]) for i in range(t): line = [int(a) for a in input().split()] n = line[0] m = line[1] ans = False for frac in fractions: if equal(m, n, frac[0], frac[1]): ans = True if ans: print('YES') else: print('NO') (also AC)
 » 15 months ago, # |   0 One thing I noticed on F: Each node is in the 2nd layer of nodes if and only if its degree is $1$. That means we can perform the following: Find a node with degree $1$. (Second layer) Get its neighbor, which will have $y + 1$ edges. (First layer) Since $x*y=m$, we can divide $m$ by $y$ to get $x$. my submission
 » 15 months ago, # |   0 For E, my dfs solution gives TLE which has the same logic as the solution given. When I changed the visited array and input array to global variables, it got accepted. Why is that so?
•  » » 15 months ago, # ^ |   0 because you define a new 2d vector after each test, and that consumes much time
 » 15 months ago, # |   0 Can someone tell me why my H problem is giving TLE with $dp[n][64]$ 204872960 but accepted with space optimization 204874966?
 » 15 months ago, # |   0 Hi, I wonder is this round rated for all who has a rating < 1400? If so, why my ratings didn't change? I'm new to codeforces so please forgive me for asking these questions. Thanks!
•  » » 15 months ago, # ^ |   0 System testing is going on, after some time ratings will change.
 » 15 months ago, # |   0 I solved G in a similar way. Let $dp_i$ be the answer for $i$ and $x_i$ be the row for $i$. Now we know that $dp_1 = 1$ , and $dp_0 = 0$, and for each $1 \leq i \leq N$ we have two cases:$i - x_i$ only lies on the previous row $x_i - 1$ , then $dp_i = i^2 + dp_{i-x_i}$$i - x_i + 1$ only lies on the previous row $x_i - 1$ , then $dp_i = i^2 + dp_{i-x_i+1}$ both $i - x_i$ and $i - x_i + 1$ lie on the previous row $x_i - 1$. Here we can't simply do $dp_i = i^2 + dp_{i-x_i} + dp_{i-x_i+1}$ because $dp_{i-x_i}$ and $dp_{i-x_i+1}$ have common numbers that were added to both of them. We can see that they have different answers except the one they took from $dp_{i-2(x+1)}$ so it becomes $dp_i = i^2 + dp_{i-x_i} + dp_{i-x_i+1} - dp_{i-2(x+1)}$
 » 15 months ago, # |   0 alt for D, we can just check wether we can get from m to n if we can do the operations belowm := 3*mm := 3*m/2 (if m mod 2 = 0)So we need to check if there exist integer pair x and y (x >= y and m mod 2^y = 0) s.t. m * 3^x / 2^y = nwe can do it in O(log2(n))
 » 15 months ago, # |   0 How could H be solved with larger values? for example (a[i] <= 1e6 or 1e9) and of course a corresponding K.
 » 15 months ago, # | ← Rev. 3 →   +11 I am Expert now thanks to this round, SpeedForces forever xD
•  » » 15 months ago, # ^ |   0 That's a huge jump orz
 » 15 months ago, # |   0 I dont know why my submission 204795848 in the contest using C++ 17 giving the TLE but it's Accepted if I submit it with C++20 204978167
 » 15 months ago, # |   0 /* this question is basically of precomputation + dp in this question we will first precompute the matrix then make a loop from 1 to 1e6 and calculate the answer for all the elements and then for each query we will give answer in O(1) / / dp of current element will be the x^2 (dp[k]=(vec[i][j]*vec[i][j])) + dp of the two elements above it if exists i.e. { if(i-1>=0 && j-1>=0) dp[k]+=dp[vec[i-1][j-1]]; if(i-1>=0 && j=0 && j-1>=0 && j-1 inclusion / exclusion principle as in given example for calculating the answer for 9 dp[9] = 9*9 + dp[6] + dp[5] - dp[3]*/ // do a dry run you will get by yourself/* <--------------------------------- THANK YOU -----------------------------> */
•  » » 15 months ago, # ^ |   +1
 » 15 months ago, # | ← Rev. 4 →   0 Just an implementation detail about the tutorial solution for problem 1829H - Don't Blame Me: if you are using GNU C++20 compiler, then you do not have to use the built-in function __builtin_popcount. You can use the standard library function std::popcount instead. Also, as the next-state at any index $i$ depends only on the previous state at index $i-1$, it is sufficient to compute the answer using two vectors only instead of using a matrix of $n+1$ vectors. Accepted Solution#include using namespace std; int main() { const int M = 64, mod = 1e9+7; const auto add = [&](unsigned& x, unsigned y) { if (x += y, x >= mod) x -= mod; }; int k, n, t; cin.tie(nullptr)->sync_with_stdio(false), cin >> t; for (unsigned ans; t--; cout << ans << '\n') { unsigned a, b, pres[M] = {}, next[M] = {}; for (cin >> n >> k; n--; memcpy(pres,next,sizeof next)) for (cin >> a, add(next[a],1), b = 0; b < M; ++b) add(next[a&b],pres[b]); for (ans = a = 0; a < M; ++a) if (popcount(a) == k) add(ans,pres[a]); } } 
 » 15 months ago, # |   +4 Nice problems ,i have got +156 points (:
 » 15 months ago, # |   0 Hello! Does anyone know how to solve H using combinatorics?
 » 15 months ago, # |   0 Can someone post DP solution of G?
•  » » 15 months ago, # ^ |   0
 » 15 months ago, # | ← Rev. 2 →   0 Nice tutoriel
 » 15 months ago, # |   +5 Editor seems to be fan of Taylor Swift
 » 11 months ago, # |   0 I solved problem D using the same recursive method as the problem solution, but I saw dp in the problem label. I want to know how to solve it with dp? Can you help me? Thank you very much
 » 10 months ago, # |   0 Can anyone explain how the time complexity of solution D(Gold Rush).
 » 7 months ago, # |   0 I used topological sorting in F and passed :)
 » 7 months ago, # |   0 wow!强大！
 » 5 months ago, # |   0 I used dfs to solve the G, just search the (i — 1, j) and (i — 1, j — 1)!
•  » » 2 months ago, # ^ |   0 I am trying to do the same thing , I am getting TLE
 » 4 months ago, # |   0 In problem G. How do you come up with the number of rows and columns as 1500. Isn't is supposed to be 2024?
•  » » 2 months ago, # ^ |   0 summation of first 1500 natural numbers is greater than 1e6.
 » 4 months ago, # |   0 I think flamestorm is huge fan of taylor swift..
 » 3 months ago, # |   0 Can someone help me make my code pass? I did problem H with recursive python DP and I'm getting TLE even after memoization and bootstrapping Please Help me get an AC
 » 3 months ago, # | ← Rev. 2 →   0 could someone enlighten me on my TLE for E? thank you in advance :) codefrom collections import defaultdict, deque import math from bisect import bisect_left, bisect_right def bfs(grid, i, j, directions): frontier = deque() frontier.append((i, j)) vol = 0 while frontier: x, y = frontier.popleft() vol += grid[x][y] grid[x][y] = 0 for d in directions: nx = x + d[0] ny = y + d[1] if nx < 0 or nx >= len(grid): continue if ny < 0 or ny >= len(grid[0]): continue if grid[nx][ny] == 0: continue frontier.append((nx, ny)) return vol def solve(): n, m = map(int, input().split()) grid = [] for _ in range(n): row = [int(x) for x in input().split()] grid.append(row) directions = ((1, 0), (0, 1), (-1, 0), (0, -1)) answer = 0 for i in range(n): for j in range(m): if grid[i][j] != 0: answer = max(answer, bfs(grid, i, j, directions)) print(answer) num_of_tests = int(input()) for _ in range(num_of_tests): solve() update : the issue seems to be the out of bounds check, although im not sure why AC if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny]: vol += grid[nx][ny] grid[nx][ny] = 0  TLE if nx < 0 or nx >= len(grid): continue if ny < 0 or ny >= len(grid[0]): continue if grid[nx][ny] == 0: continue 
 » 3 months ago, # |   0 author is a huge ts fan i guess :)
 » 3 months ago, # |   0 In editorial's solution of 1829H - Don't Blame Me, Why is there a need to add this transition dp[i][a[i]]=dp[i][a[i]]+1 `Shouldnt this be counted in the two previous transitions.Someone please explain
 » 3 months ago, # |   0 There's another approach for problem F with same complexity but with no constant factors , exactly $\mathcal{O}(n+m)$ 258238660
 » 2 months ago, # | ← Rev. 2 →   0 Can somebody explain why am I getting TLE, even though my time complexity should not be that bad since I am only traversing each number at most once.submission : 266642608