visho33's blog

By visho33, history, 23 months ago, In English

Hi! I found a type of problems I couldn't solve, but I read that we can solve them using FFT or generating functions. I don't know how to use these approaches here, can someone help me please? (I didn't found a tutorial, just discussions) The problems are: - Square Grid - The last problem in this note of Petr's blog - Kalel, The Jumping Frog Would be nice for me a more detailed explanation or a resource to check

  • Vote: I like it
  • +51
  • Vote: I do not like it

»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Problems are nice. +1 on that.

  • »
    »
    23 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    I tried to solve the first problem using ChatGPT, but it's struck on solving the easier version only.

    Find no of way to reach (x1,y1) from (0,0), you can only move one coordinate up in positive x direction or positive y direction.
    Now you cannot touch y=x+R line while going.
    Give me a closed mathematical formula
    This formula is also wrong. The correct formula is (x1+y1)!/x1!/y1! - (x1+y1)!/((x1+y1+R)/2)!/((y1-x1-R)/2)!
    Can you prove that second part represents no of ways this restriction is violated?

    At this point, I gave up.

    • »
      »
      »
      23 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I tried to calculate $$$\text{lcm}(1, 2, \dots, 16)$$$ using ChatGPT, but it's not as easy as it seems. Apparently ChatGPT is not so good at manipulating formulas and doing calculations.

»
23 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

For the last problem: you can simply treat the problem as usual matrix exponentiation problem but using a polynomial in every entry of the matrix to represent the energy spent, naive multiplication is enough for AC in something like O(D^3 K^2 logN). You can further optimize it using some polynomial operations down to O(KD logKD logN).

As for the others, I have no idea.

  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ohh interesting approach, it's a really cool solution. Thx!

»
23 months ago, # |
Rev. 6   Vote: I like it +8 Vote: I do not like it
Second problem