KEPuzOfficial's blog

KEP Contest #10
By KEPuzOfficial, 6 weeks ago, translation, In English

I invite everyone to the contest, which will take place on November 16, 2024 at 14:35UTC. Interesting problems await you in the contest.

Contest info:

  • Number of problems: 12

  • Difficulty of problems: < 2400

  • Duration: 4 hours

  • Contest type: ACM20M

  • Languages: C++, Python, C, Kotlin, Haskell, R, Nodejs, PHP, C#, Java, Rust

Link to the platform: https://kep.uz/competitions/contests/

P.S. Registration on the platform only via Gmail/Github.

UPD

Thank you for participating. I hope you liked these "strange" problems.

Results

  1. physics0523 — 11
  2. vtb — 11
  3. hocln — 11
  4. JahonaliX — 11
  5. Haksell — 11
  6. wltt — 10
  7. Timosh — 10
  8. alexwice — 9
  9. Husanboy — 9
  • Vote: I like it
  • +30
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I am new to the platform. Can we see other people's submissions after the contest or do you publish an editorial? I don't want to land in a situation where I was unable to solve a problem and don't even get a closure.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest as always. I ended solving problem G but not sure whether my physics was right or I just got lucky thanks to the 2 digits of precision. Can someone share their solution?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    solution (as russian yt channel video)

    → Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    My integral was something like this, which resulted in a wrong solution though :(

    $$$T = \frac{1}{\sqrt{2g}} \int_0^1 \frac{\sqrt{1 + 4x^2}}{x} dx$$$

    Let me know if it looks familiar.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 4   Vote: I like it +1 Vote: I do not like it

      My code looked like this:

      G. Most Popular Problem #28
      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Okay that is an innovative approach. Many of us were busy with integrals rather than thinking like you :P

        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I revisited the problem with Schmoov. He got the idea to use conservation of energy.

          The total energy of the system is $$$\frac{1}{2} m v^2 + m g h$$$. We can calculate the average speed in each interval $$$[x, x+\Delta x]$$$, find $$$\Delta t$$$ from that, and take the sum.

          conservation_dx

          This works but takes 5 million steps to converge to 4 digits of accuracy. The problem comes from the first few steps, where the average speed can be far from the mean of the start and end speed. And since the speed is slow, $$$\Delta t$$$ and its error are quite big.

          Instead of taking steps in $$$x$$$ or $$$y$$$, we can take steps in speed. The final speed can be calculated from conservation of energy as $$$f_s = \sqrt{2 G}$$$.

          This takes 70 steps to converge to 4 digits of accuracy.

          conservation_ds
          → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share their approach to Problem I where we have to calculate binomial co-efficients

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    Solution (Lucina)
    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I'm curious or dumb. The time complexity is then $$$O({N^{2}})$$$ which is about $$$3e8$$$ and not cool.

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Actually, nowadays 1e9 operations in 2 seconds is considered normal)

        → Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can detect cycles in the calculations of n and k. For reasons I don't really understand the cycle length is always 100 or a divisor, like 20. So you just need to compute the first 100 results. There are much more efficient methods to compute combinations with a modulo but this was fast enough:

    I. Binomial Coefficients
    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      mind-blowing solution

      → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Then, you hacked the problem. It was not the problem's mind, I think.

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there going to be editorials?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For what problem do you need an editorial?

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Editorial is required for K (Tetris Game) and L (Events). No one was able to solve L so it will be helpful for all. Even code is fine.

      → Reply