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

Автор kostia244, 4 года назад, По-английски

Hello Codeforces! I got some interesting tricks to share with you.

1. a_i := (a_i + x)%mod Range Updates, Max Range Queries

Apply usual range addition, but after each update run the following code:

void normalize(int l, int r) {
    while(getmax(l, r).max >= mod) {
        set(getmax(l, r).pos, getmax(l, r).max%mod);
    }
}

What is the complexity of this code? We all know that each time we %%=mod$ number which is $$$\geqslant mod$$$ it halves, that means each number will be updated $$$O(log)$$$ times, we will perform $$$O(n\cdot\log{n}\cdot\log{a})$$$ operations in total. So each update will be $$$O(\log{n}\cdot\log{a})$$$ amortized!

2. $$$O(\log^2{\log{n}})$$$ Segment Tree

Segment tree queries are queries on path. Instead of doing them in the usual brute force-ish way we can use HLD! Since maximum path length is $$$2\cdot\log{n}$$$, thus operations are now operations are $$$O(\log^2{\log{n}})$$$, which is better than $$$O(\log{n})$$$.

3. Faster Dinic's

We know that after $$$i$$$ operations Dinic's algo finds flow which is at least $$$\frac{i}{i+1}\cdot{maxflow}$$$. In some problems we just want to check whether flow is at least $$$x$$$. Using the fact above we can run one iteration of the algorigthm which will get us $$$\frac{1}{2}$$$ of maxflow and multiply that by two. Now just compare $$$x$$$ and maxflow.

4. Linear FFT

Usually, we use roots of unity ($$$e^{\frac{\tau\cdot t}{n} \cdot i}$$$) or primitive roots (for ntt). But why would we limit ourselves to those?

Instead of roots of unity, we can choose roots of something else, that looks complex enough. This, for example:

$$${e^{\sqrt[x]{6 \cdot \pi ^ 2 \cdot \prod_{1 \leqslant i \leqslant 10} {(x - i \cdot x^{\frac{1}{i}})}} + i\cdot\frac{\pi}{2}}} = i$$$

Let's choose a few roots of this thing which we'll use for FFT. We can notice that $$$(-1)^{\frac{i}{2\cdot i - 2}}, 1 \leqslant i \leqslant 10$$$ work. So using them we have $$$O(10\cdot n) = O(n)$$$ FFT!

5. Linear Interpolation(Actually Point Evaluation Without Finding The Polynomial)

We can interpolate in linear time if given x coordinates of given points are n consequential integers (check out 622F editorial for details). We can use this approach to perform general interpolation in $$$O(n)$$$. Let $$$f$$$ be the polynomial interpolated, n be the number of points given, $$$v$$$ be the x value in which we want to evaluate $$$f$$$, $$$x$$$ be x coordinates, and $$$y$$$ be y coordinates of given points. Let's introduce a new polynomial $$$g$$$, such that $$$g(i) = x_i, 0 \leqslant i \lt n$$$. We can solve $$$g(x) = v$$$ easily using HS math in $$$O(n)$$$ time. Now, let's interpolate $$$h(x) = f(g(x))$$$ instead of $$$f(x)$$$. We just evaluate $$$h(g^{-1}(x))$$$ since input of $$$h$$$ is n consequential integers we can do it in linear time. Easy as that!

Thanks for reading, I hope your rating will skyrocket after applying those in contest! If you have any questions feel free to leave commments or DM me(kostia244) or AryaPawn

  • Проголосовать: нравится
  • +429
  • Проголосовать: не нравится

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

Me: Scrolled down the comments section to see if this was a joke :').

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

Thank you sir

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

Showing yourselves as grandmaster and your friend as specialist will surely get you more DMs than him/her.

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

Thanks! Very helpful techniques!

I would like to point out that the complexity of the segment tree can be improved to $$$log^2\left(log^2\left(log \left( n\right)\right)\right)$$$ if you apply Centroid Decomposition on the segment tree before applying HLD.

It is actually a well-known technique in China, I'll write a detailed blog about it soon.

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

    Now that China is into the picture, I am no longer sure that you are fooling around!!

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

It's also way faster to write sum += a[i] * c[i] than if(c[i]) sum += a[i].

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

whats HLD??

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +33 Проголосовать: не нравится

 Me who haven't use any of them

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

Excuse me... how can the first trick works if I update [1, n] +p each times... the time complexity will be $$$O(nlogn \times Q)$$$...

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится
    Spoiler
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      Damn, you are a real demoralizer!

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

      Sure, I'm quite stupid yesterday. :)

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

I believed the first trick, but after I read the rest of them, I got confused, really really confused.

feels like how did I not know them before, wtf are these?

And I scrolled down to the comment section...

;)

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

If you use bitset they all speed up by factor of log n

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

I wanna point out, kostia244 was orange when he wrote this blog and used some trick to make his name appear red. AND NOW THAT BECAME LEGIT ORZ

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

Do you have more papers on that Linar FFT?

I don't understand really.

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

Is this is how red coders joke arround ?

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

even the red coder's jokes are above my level!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -35 Проголосовать: не нравится

.

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

Another thing that will supercharge your programming prowess is to replace all for-loops with a #define REP ... macro.

Also when you're in the kind of contest where you run your code locally, turning off the heating in your room will cool down your CPU.

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

    Whenever I try to see some submissions and I see #define REP my brain just stops working :( .