thanks for the speedy editorial.

wow what speedy editorial！

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 ?

Problem H can be solved in O(k * 2^k + n) using AND Convolution, as described here: https://mirror.codeforces.com/blog/entry/115438

Implementation: https://mirror.codeforces.com/contest/1829/submission/204840516

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.

Didn't get H

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

in problem F what is the output of this case :

1
2 1
1 2

Tonight's problems' interesting and not typical, thank the writer and codeforces for such a great contest!

Have anyone solved E using BFS?

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:

Implementation: 204825154

For problem F, if you see: Wrong answer on test 2 wrong answer 65th numbers differ

Then it is the x == y+1 edge case mentioned in editorial.

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")

204848665

my solution for (E) The lakes is clearly an O(mn) solution, but was exceeding limit, can anyone explain where it can be optimised?

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 ?

[submission:204849479]
Why am I getting runtime error in this code?

wow. so speedy

JUST CAME BACK TO VISIT A TAYLOR SWIFT ROUND. OMG!!

Can anybody hack this solution for TLE ?? https://mirror.codeforces.com/contest/1829/submission/204874235

Problem F: Observe that the starting vertex is the ONLY vertex that is not a leaf AND also has no leaf neighbours. 204824064

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

Another approach to solve E (https://mirror.codeforces.com/contest/1829/submission/204823633)

Have anybody solved problem E without using bfs and DFS???

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

There is a much faster solution to D

Each 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')

204904968

There 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)

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:

1. Find a node with degree $$$1$$$. (Second layer)
2. Get its neighbor, which will have $$$y + 1$$$ edges. (First layer)
3. Since $$$x*y=m$$$, we can divide $$$m$$$ by $$$y$$$ to get $$$x$$$.

my submission

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?

Can someone tell me why my H problem is giving TLE with $$$dp[n][64]$$$ 204872960 but accepted with space optimization 204874966?

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!

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)}$$$

alt for D, we can just check wether we can get from m to n if we can do the operations below

m := 3*m

m := 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 = n

we can do it in O(log2(n))

How could H be solved with larger values? for example (a[i] <= 1e6 or 1e9) and of course a corresponding K.

I am Expert now thanks to this round, SpeedForces forever xD

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

/* 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<vec[i-1].size()) dp[k]+=dp[vec[i-1][j]]; }

and then subtracting the element which is at the top of those two elements
because that will be the intersection and it will be added twice so we have to minus it
if exist

i.e. if(i-2>=0 && j-1>=0 && j-1<vec[i-2].size()) dp[k]-=dp[vec[i-2][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 -----------------------------> */

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.

#include <bits/stdc++.h>
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]); } }

Nice problems ,i have got +156 points (:

Hello! Does anyone know how to solve H using combinatorics?

Can someone post DP solution of G?

Nice tutoriel

Editor seems to be fan of Taylor Swift

I used topological sorting in F and passed :)

wow!强大！

I used dfs to solve the G, just search the (i — 1, j) and (i — 1, j — 1)!

In problem G. How do you come up with the number of rows and columns as 1500. Isn't is supposed to be 2024?

I think flamestorm is huge fan of taylor swift..

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

could someone enlighten me on my TLE for E? thank you in advance :)

from 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

            if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny]:
                vol += grid[nx][ny]
                grid[nx][ny] = 0

            if nx < 0 or nx >= len(grid):
                continue
            if ny < 0 or ny >= len(grid[0]):
                continue
            if grid[nx][ny] == 0:
                continue

author is a huge ts fan i guess :)

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

There's another approach for problem F with same complexity but with no constant factors , exactly $$$\mathcal{O}(n+m)$$$

258238660

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