KEP Contest #10 - Codeforces

Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

KEP Contest #10

Автор KEPuzOfficial, 22 месяца назад, По-русски

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

physics0523 — 11
ywwuyi — 11
hocln — 11
JahonaliX — 11
Haksell — 11
wltt — 10
Timosh — 10

kepuz

KEPuzOfficial
22 месяца назад
20

Комментарии (18)

Показать архивные | Написать комментарий?

conqueror_of_timosh

22 месяца назад, скрыть # |

KEP!

→ Ответить

tempturing

22 месяца назад, скрыть # |

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.

→ Ответить

Haksell

22 месяца назад, скрыть # |

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?

→ Ответить

MDSPro

22 месяца назад, скрыть # ^ |

solution (as russian yt channel video)

→ Ответить

tempturing

22 месяца назад, скрыть # ^ |

← Rev. 2 →

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.

→ Ответить

Haksell

22 месяца назад, скрыть # ^ |

← Rev. 4 →

My code looked like this:

G. Most Popular Problem #28

def iterative():
    G = 9.81
    DT = 3e-5

    x = 1.0
    t = v = 0.0
    while x > 0.0:
        dy = 2.0 * x
        slope = sqrt(1 + dy**2)
        a = G * dy / slope
        v += a * DT
        x -= v * DT / slope
        t += DT
    return t

→ Ответить

tempturing

22 месяца назад, скрыть # ^ |

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

→ Ответить

Haksell

21 месяц назад, скрыть # ^ |

← Rev. 2 →

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

def conservation_dx(x, steps):
    e = x**2 * G
    dx = x / steps
    t = 0.0
    for _ in range(steps):
        mx = x - dx / 2
        s = sqrt(2 * (e - G * mx**2))
        sx = s / hypot(1, 2 * mx)
        dt = dx / sx
        x -= dx
        t += dt
    return t

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

def conservation_ds(x, steps):
    e = x**2 * G
    fs = sqrt(2 * e)
    ds = fs / steps
    s = t = 0.0
    for _ in range(steps):
        y0 = (e - 1 / 2 * s**2) / G
        y1 = max(0, (e - 1 / 2 * (s + ds) ** 2) / G)
        x0 = sqrt(y0)
        x1 = sqrt(y1)
        ms = s + ds / 2
        dt = hypot(x0 - x1, y0 - y1) / ms
        s += ds
        t += dt
    return t

→ Ответить

tempturing

22 месяца назад, скрыть # |

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

→ Ответить

KEPuzOfficial

22 месяца назад, скрыть # ^ |

Solution (Lucina)

#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
const int N = 25001;
vector <int> queries[N];

int r[N];

void solve() {
    int q, n1, k1;
    cin >> q >> n1 >> k1 >> MOD;
    r[0] = 1;

    while (q --) {
        queries[n1].push_back(k1);
        n1 = (n1 * 943 + 17) % 25000 + 1;
        k1 = (k1 * 1999 + 24) % 25000 + 1;
    }
    int ans = 0;
    for (int i = 1 ; i < N ; ++ i) {
        for (int j = i ; j >= 1 ; -- j) {
            r[j] += r[j - 1];
            if (r[j] >= MOD) r[j] -= MOD;
        }
        for (int v : queries[i]) {
            ans += r[v];
            if (ans >= MOD) ans -= MOD;
        }
    }
    cout << ans << '\n';

}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int T = 1;
    for (; T -- ; ) {
        solve();
    }
}

→ Ответить

wltt

22 месяца назад, скрыть # ^ |

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

→ Ответить

KEPuzOfficial

22 месяца назад, скрыть # ^ |

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

→ Ответить

Haksell

22 месяца назад, скрыть # ^ |

← Rev. 2 →

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

from itertools import count
from math import comb

q, n1, k1, m = map(int, input().split())
n, k = n1, k1
xs = []
for i in count(1):
    x = comb(n, k) % m
    xs.append(x)
    n = (943 * n + 17) % 25000 + 1
    k = (1999 * k + 24) % 25000 + 1
    if n == n1 and k == k1:
        chunks, remaining = divmod(q, i)
        print((sum(xs) % m * chunks % m + sum(xs[:remaining])) % m)
        break

→ Ответить