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

I think problem D amounts to checking whether the equation 2^a * n == 3^b * m has a solution where b >= a. I used two-pointers to search for a and b.

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

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 ?

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

my strat for F was to take a node with degree 1, and go to the next node. the degree of this node is y + 1. then go to a node which degree is greater than one from this node, and the degree of this node is x.

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 submitted the question (C) 2 min before the contest end , last time it was showing it green now its showing it red ?? WHY?

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

author is a huge ts fan i guess :)

In problem H

What should be the answer to this tc

1 4 1 64 64 64 64

The editorial code is giving 0 but I think the answer should be 15

G has a complex formula. But for anyone who wondered, here I deducted the formula.

Suppose we have l numbers and r numbers when counted to left and right(as the picture shows, in that example, $$$n=25$$$, $$$l=4$$$ and $$$r=4$$$), we can directly compute the result: $$$\dfrac{1}{120}lr(6l^4+15l^3(r+1)+10l^2(2r^2+r+2)+5l(3r^3-2r^2+5)+(6r^4-15r^3+20r^2-25r+18))$$$.

If you are bored you can try to obtain that formula by observing the pattern.

356063457