Блог пользователя flamestorm

Автор flamestorm, 11 месяцев назад, По-английски

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
Разбор задач Codeforces Round 871 (Div. 4)
  • Проголосовать: нравится
  • +90
  • Проголосовать: не нравится

»
11 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

thanks for the speedy editorial.

»
11 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

wow what speedy editorial!

»
11 месяцев назад, # |
  Проголосовать: нравится 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 ?

»
11 месяцев назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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

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

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 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.

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the round!!
I liked problem G(only problem which I couldn't AC :sadge:) and the intended solution idea.

»
11 месяцев назад, # |
  Проголосовать: нравится 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.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please explain it?

    I am not able to get the tutorial.

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 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.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    G was a really good problem, it reminded me of http://www.usaco.org/index.php?page=viewproblem2&cpid=416.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 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;
    }
    
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Didn't get H

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

G is possible by simply using sum of squares of N natural numbers for each row and is easy implementation too.

https://codeforces.com/contest/1829/submission/204823035

»
11 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.com/contest/1829/submission/205007790

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yup, I noticed that too.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain more about your approach?

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      think like that any number a can be divided to the form a/3 , 2a/3 which further divide into a/9 ,2a/9 and 4a/9 and so on so the number m should be of latter form . so find how much is the differences of maximum power of 3 say y and divide the first number by that . and then try checking for all powers of 2 if u can get to number m before finishing the tries u have which is y

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

in problem F what is the output of this case :

1
2 1
1 2
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Have anyone solved E using BFS?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i solved 5/8. Great contest everyone!!

»
11 месяцев назад, # |
  Проголосовать: нравится +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

G

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do you mean to say like this: My Submission I guess it's easier this way.Not sure!

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I also coded it this way, but if you look closely, this is actually just the 2d prefix sum solution!

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      It is!

      This is just a different way of looking at it, without all the modifications. I feel this is more intuitive.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 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$$$
  • »
    »
    10 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    My Submission my logic is to go upwards in the form of an inverted tree until the base of the inverted tree is greater than the number of cans in that level, after which all the cans above this level will fall, and if the can lies on the left or right boundary then only the boundary cans fall, but it seems to fail for large testcases can you please explain why?

»
11 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
11 месяцев назад, # |
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")



  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Here is a failing test case:

    Input:
    1
    27 8
    
    Correct Output:
    YES
    
    Your Output:
    NO
    

    Can you see why this happens?

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ohhhhhhhhh, thank you so much.

      Yeah I see now.

      27 // 3 is 9 -> 9 > 8, so my solution tries to split up 9 to get 8 -> outputs NO.

      And a fix be to use return (solve(n//3, m) or solve(n-n//3, m)) right?

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Yeah, this should fix the problem.

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        did u solved it?

        • »
          »
          »
          »
          »
          11 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          yup, here is final submission:

          def solve(n, m):
              if n == m:
                  return(1)
          
              if n % 3 != 0 or m > n:
                  return(0)
          
              return solve(n//3, m) or 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")
          
          
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There is a no brainer dp solution to C.
DP
basically if we have S as a set of skills we took then xor(s)=3 ATP.
we have to find a set such that cost is minimum

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    11 месяцев назад, # ^ |
    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

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 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

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      understood, thanks for the explanation

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
        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

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Use visited array

»
11 месяцев назад, # |
  Проголосовать: нравится 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 ?

  • »
    »
    11 месяцев назад, # ^ |
    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.

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks a lot. That solve a lot of my problems with python. Been getting these kinda errors frequently.

    • »
      »
      »
      11 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      for beginners, how large can the "big number" can be in-case of O(N) required space complexity ? Will 10^4 do?

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится 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.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

204849479
Why am I getting runtime error in this code?

  • »
    »
    11 месяцев назад, # ^ |
    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.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
WoW Fast Editorial
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wow. so speedy

»
11 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    come back...be here (another Taylor's song)

    • »
      »
      »
      11 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
      message in a bottle
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Or you can go with that whenever there is a level greater than 2 then that is surely not our central node of snowflake.204843315

»
11 месяцев назад, # |
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

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you!

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится 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.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
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$$$).

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

task E is the best

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wow, fast editorial <3

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

that was a good contest, thanks :)

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Amazing

»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

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)

»
11 месяцев назад, # |
  Проголосовать: нравится 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:

  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

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

question E was interesting. loved solving it.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain in problem c why did we use >1e6 for the -1 case.

  • »
    »
    10 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Doesn't really matter you just have to take a number which is larger than any input number which are given less than or equal to 10^5 so any number greater than 10^5 will work.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

One interesting Observation in F is that all leaf nodes have degree 1 so count all degree 1 lets say total and then other are degree >1 which means they would be x+1 as one node with degree >1 would be central vertex so answer would be x and total/x.

»
11 месяцев назад, # |
  Проголосовать: нравится 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?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится 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!

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I submitted the question (C) 2 min before the contest end , last time it was showing it green now its showing it red ?? WHY?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Some of the hacks are very... strange looking.

First

Second

»
11 месяцев назад, # |
  Проголосовать: нравится 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)}$$$

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I approached F the following: let be the number of outermost nodes l.

One can easily find this "l" from the input. It turns out that l = x*y, also, the total number of nodes is n = 1 + x + x*y. So we have due independent equations which yields to x and y values

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What about this?

»
11 месяцев назад, # |
  Проголосовать: нравится 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

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I set the recursion limit and I still get Runtime Error: 204981121 Can anyone help?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for a great round! I solved 5/8 problems, which is the highest ever (usually no more than 3). I solved the first 4 problems in 30 minutes, and then an hour later I solved F, which seemed to me easier than E, the idea of which I did not understand.

»
11 месяцев назад, # |
  Проголосовать: нравится 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<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 -----------------------------> */

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My Python implementation of the editorial solution passes only first 5 tests, then gets Runtime Error on test 6. https://codeforces.com/contest/1829/submission/205011680

Can someone help find the problem?

  • »
    »
    11 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I got the same problem. After some trials (to me) it seems impossible to pass the problem in python with recursion. I used bfs to solve this. (dfs is also not ok for it will cause MLE)

    Here's my submission: 204988219

    Tip: check each cell if it is visited or is 0 before bfs to optimize the time

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C hack has been evil U_U

»
11 месяцев назад, # |
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
»
11 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Nice problems ,i have got +156 points (:

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I had different idea for G. Keep start and end positions of cups in a line then go up and use math formula for the sum of n squares: 205064632 O(1) space and O(n) run

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone post DP solution of G?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is my solution, I just calculate how many numbers appear once. Then i subtract that number from number of nodes and i subtract -1 to get rid of the first node and from there i get x.

void solve() { int n,m; cin >> n >> m; map<int,int> mp;

for(int i = 0; i < m; i++)
{
    int prvi,drugi;cin >> prvi >>drugi;
    mp[prvi]++;
    mp[drugi]++;
}
int ans = 0;
for(auto x : mp)
    if(x.second == 1)
        ans++;
cout << n-ans-1 << ' ' << ans/(n-ans-1) << endl;

}

int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int tt;cin >> tt;
while(tt--)solve();

}

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please explain the tutorial for F (Forever Winter)? I am unable to understand the logic behind it. I only coded a TLE solution which was accepted at the time of the contest, then it changed to TLE.

EDIT:- Nevermind. I understood with the help of other's submissions.

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

UPD : solved

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Nice tutoriel

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

include

include

include

using namespace std; typedef long long ll;

bool solve1(ll n, ll x, vector& dp) { if (n == x) { return true; } if (x > n || n % 3 != 0) { return false; } if (dp[n] != -1) { return dp[n]; } bool ans = solve1(n / 3, x, dp) || solve1(2 * n / 3, x, dp); dp[n] = ans ? 1 : 0; return dp[n]; }

void solve() { ll n, m; cin >> n >> m; vector dp(n + 1, -1); if (solve1(n, m, dp)) { cout << "YES" << endl; } else { cout << "NO" << endl; } }

int main() { cin.tie(0); cin.sync_with_stdio(0); cout.tie(0); cout.sync_with_stdio(0);

int t;
cin >> t;
while (t--) {
    solve();
}

return 0;

} Why this code is giving Time complexity in Problem D, ;Gold Rush?

»
10 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Editor seems to be fan of Taylor Swift

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem G, I was using bfs for solution but it didnt seem to give any answer for the last test of test case 1. Can anyone tell why.

include<bits/stdc++.h>

include <ext/pb_ds/assoc_container.hpp>

include <ext/pb_ds/tree_policy.hpp>

using namespace std; using namespace __gnu_pbds;

define ll long long

define pb push_back

define msort(v) sort(v.begin(),v.end())

define loop(ii,n) for(long long ii = 0; ii < n; ++ ii)

define pii pair<int,int>

define ff first

define ss second

// #define ordered_set tree<int, null_type,less, rb_tree_tag,tree_order_statistics_node_update>

define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>

define o_key order_of_key

define o_set ordered_set

bool cmp(pair<int,int>& i1, pair<int,int>& i2) { return (i1.first < i2.first); } bool prime[1000005]; void sieve() { memset(prime, true, sizeof(prime));

for (int p = 2; p * p < 1000005; p++) {

    if (prime[p] == true) {

        for (int i = p * p; i < 1000005; i += p)
            prime[i] = false;
    }
}

} ll len(ll a) { int ans=0; while(a>0){a/=10; ans++;} return ans; } map<int,int> mprime; void pf(int n) {

while (n % 2 == 0)
{
    mprime[2]++;
    n = n/2;
}
for (int i = 3; i <= sqrt(n); i = i + 2)
{

    while (n % i == 0)
    {
        mprime[i]++;
        n = n/i;
    }
}
if (n > 2) mprime[n]++;

} long long binpow(long long a, long long b) { long long res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; } ll cnt(ll i) { ll ans=0; while(i>0) { ans+=(i%10); i/=10; } return ans; } /////////////////////////////////////////////////////////////////////////// //////////////////// DO NOT TOUCH BEFORE THIS LINE //////////////////////// ///////////////////////////////////////////////////////////////////////////

int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll t;
cin>>t;
while(t--)
{
    // cout<<"ds";
    ll n;
    cin>>n;

    vector<vector<ll>> adj(1000005);
    ll k=1;
    for(int i=1;i<=n;i+=(k-1))
    {
        for(int j=0;j<k;j++)
        {
            adj[j+i+k].pb(i+j);
            adj[j+i+k+1].pb(i+j);
        }
        k++;
    }
    vector<ll> vis(n+5,0);
    ll ans=0;
    queue<ll> q;
    q.push(n);
    // ans+=q.front();
    // cout<<"Ds";
    while(!q.empty())
    {
        // cout<<n<<endl;
        ll tmp=q.front();
         q.pop();
         ans+=tmp*tmp;
         vis[tmp]=1;
         for(auto i:adj[tmp])
         {
             if(vis[i]==0)
             {
                 vis[i]=1;
                 q.push(i);
             }
         }
    }
    cout<<ans<<endl;
}

return 0;

}

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Alternate approach for G: https://codeforces.com/contest/1829/submission/207013133

Basically whenever we move up the tower, we make the left top and right top fall down. But the sum of a single element is not simply the sum of its parents and itself, this solution deals with that by choosing the right upper part only for the right parent, hence minimizing any overlap.

Examples: If we were to calculate for n=13, it would go the following way-


1 / 2 3 / / 4 5 6 \/ / 7 8 9 10 \/ 11 12 13 14 15 --
»
10 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Problem G is just wow, it couldn't be dissected more beautifully, could someone clear out what i and j mean in the solution mentioned in the editorial. i is the row number and j is the diagonal number?

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone explain what did I did wrong for the fourth question. When I submitted by recursive code it gets accepted, but when I memoized the code, I am getting TLE. Thanks for explanation in advance. Below is the code, RECURSIVE

bool solve(int n, int m) {
	if(n == m) return true;
	if(m > n || n % 3 != 0) return false;
	
	int ind = n / 3;
	bool left = solve(ind, m);
	bool right = solve(n - ind, m);
	return left || right;
}
// Invoking function
bool res = solve(n, m);

MEMOIZED CODE

bool solve(int n, int m, vector<int> &dp) {
	if(n == m) return true;
	if(m > n || n % 3 != 0) return false;
	if(dp[n] != -1) return dp[n];
	
	int ind = n / 3;
	bool left = solve(ind, m, dp);
	bool right = solve(n - ind, m, dp);
	return dp[n] = (left || right);
}

//Invoking function
vector<int> dp(n + 1, -1);
bool res = solve(n, m, dp);
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone tell that in question G how to decide what should be size of 2D matrix....

»
9 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

C. Mr. Perfectly Fine

//Solution without using map....

#include<bits/stdc++.h>

using namespace std;

int main(){

int t;
cin >> t;

while(t-- > 0){
    int n;
    cin >> n;
    int min0 = INT_MAX;
    int min1 = INT_MAX;
    int min2 = INT_MAX;

    for(int i=0;i<n;i++){
        int m;
        cin >> m;
        string s;
        cin >> s;

        if(s[0] == '1' && s[1] == '1' && m < min2){
            min2 = m;
        }
        if(s[0] == '1' && m < min0){
            min0 = m;
        }
        if(s[1] == '1' && m < min1){
            min1 = m;
        }
    }
    if(min0 == INT_MAX || min1 == INT_MAX){
        cout << -1 << endl;
    }else{
        cout << min(min2,(min0 + min1)) << endl;
    }
}

}

»
9 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I did the exact same solution with python and somehow exceeded the time limit on test 8

here is my solution :

def is_possible(n, m):
    if n == m:
        return True
    elif n % 3 != 0:
        return False
    else:
        return is_possible(n/3, m) or is_possible(2*n/3, m)

t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    if is_possible(n, m):
        print("yes")
    else:
        print("No")
»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

still unclear why for problem D, why we used T(n) = 2T(n/3) + O(1) , but it's really T(n/3)+T((2*n)/3)+O(1). you could say the 2/3 will dominate so b should be 1.5 but then time complexity is n^(log1.5(1)) which is O(n).

»
6 месяцев назад, # |
  Проголосовать: нравится 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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain how the time complexity of solution D(Gold Rush).

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I used topological sorting in F and passed :)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wow!强大!

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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