-is-this-fft-'s blog

By -is-this-fft-, history, 7 months ago, In English

Trends are silly, but I've been thinking of doing one for a while.

I've been in competitive programming for close to 9 years now, and I've been quite active here. Like adamant is now, I used to be top contributor for a while. I missed the chance to do an AMA when I actually was top contributor, but as they say, better late than never.

Fire away with the questions!

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

»
7 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Has anyone tried proving to you that this is indeed, not fft?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    "-is-this-fft-" means "is this problem solvable using FFT".

    It is generally very hard to prove that a certain technique or algorithm cannot help solve a particular problem. The best you can do is to rely on experience to decide that it is unlikely to be a fruitful route.

    So even if people have tried, they have certainly not been successful.

»
7 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Do you think people would take this AMA seriously?

Спойлер
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    Well now that you've exposed my insecurities, they are less likely to. >:(

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

    Discord server link ? (If it is open to all)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do you think trends are silly and what do you think about this one in particular?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Usually when something is trendy you get people jumping on the bandwagon without much to offer.

    I remember there was a blog called "china orz" with funny jokes. It was followed up by "japan orz", "antarctica orz" and some others. But within a day people started copying those with very low-effort spam without really knowing how to be funny.

    About this one: we'll see. It gave me an excuse to post this blog, but maybe it is also a reason for people to take it less seriously or care less about it. I think we're already seeing a lot of low-effort joke ones too.

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What is your favorite problem ? What is your favorite datastructure/algorithm and what datastructure/algorithm do you hate the most ?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    I am likely to like problems that can be solved by an interesting perspective shift, such as AGC 043 C — Giant Graph.


    Favorite algorithms include:

    • Karger's algorithm. It computes the "global minimum cut" of a graph (i.e. given a graph, partition its vertices in two nonempty sets such that the number of edges passing from one set to the other). The entire algorithm is just "pick a random edge and contract it until you have only two vertices". It turns out that this procedure gives you the actual minimum cut with pretty decent probability. Trying to understand why this is much better than chance is a good exercise.
    • Gomory-Hu tree. Given any undirected graph $$$G$$$ with edge capacities, you can compute a tree $$$T$$$ with edge costs such that for any source $$$s$$$ and sink $$$t$$$, the maximum flow from $$$s$$$ to $$$t$$$ in the original graph is the minimum cost on the path from $$$s$$$ to $$$t$$$ in the tree. It has other nice properties too. This shows that the set of maximum flows (or minimum cuts) in a graph is far more structured than one might think.
    • Goemans-Williamson. Semidefinite programming is a general type of optimization problems where you have $$$n$$$ vector-valued variables from a $$$n$$$-dimensional vector space. The constraints and objective function must be linear functions in the inner products of the variables. It is known that such optimization problems can be solved efficiently. Goemans-Williamson is an approximation algorithm that solves the maximum cut problem by reducing it to such a form. The maximum cut problem itself just asks to again partition the vertices in two sets, this time to maximize the number (or sum of weights) of edges that pass from one part to another. To do that, you make a vector-valued variable $$$v_i$$$ for each vertex, require that all those variables are on the unit sphere by requiring $$$\left< v_i, v_i \right> = 1$$$ for all $$$i$$$ and add a term $$$(1 - \langle v_i, v_j \rangle)$$$ to the objective function if there's an edge $$$ij$$$ (because if there's an edge, you want the edges to point in opposite directions). Once you have solved the semidefinite program, you can pick a random hyperplane and classify the vertices based on that.
    • I am also obligated to name FFT.

    Everything on this list is there because it is beautiful and theoretically interesting, not because it is necessarily the most useful thing.


    I don't have a least favorite algorithm, but I can say that I am frustrated by algorithms with bad names, especially if there are two distinct things with similar names. Exhibit A: "DSU on tree" vs "DSU tree", both of which are distinct from just DSU (which is also a forest). Exhibit B: "convex hull trick" vs "convex hull".

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I think you missed something in the sentence of the First Algo: (i.e. given a graph, partition its vertices in two nonempty sets such that the number of edges passing from one set to the other). Seems like It Is not complete

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Do you actually hate blues ?

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

What are the skills needed to reach Master ?

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How old are you?

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How has 9 years of CP treated you? In particular, how have you seen this sport evolve and what are the things you like/hate about this evolution?

What have been your most down moments and what are the few best moments you had in these 9 years?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +86 Vote: I do not like it

    The biggest changes that I personally witnessed happened around the time Anton Trygub started to coordinate. Around that time you really did see pretty quick changes on the types of problems that appeared, for better or worse.

    But it wasn't a one-time revolution. Meta shifts have happened before and will happen again. The new kinds of problems aren't "better", they are just different and mostly come from the fact that older topics are thoroughly explored. When I was in high school I thought that data structure problems (which were big at the time) were very obviously purer and belonged to a higher plane of existence than geometry problems (which had fallen out of favor). A supervisor at the IOI camp told me that these are just trends, topics come and go as people explore them. I didn't understand it then, but I understand it now. The "newer" style is not better or more refined, it is just fresher and appeals to people more.

    Another big change is an influx of people who came here mainly to prepare for LeetCode-type job interviews. I have mixed feelings about this because it seems to have created a lot of people who are not truly interested in algorithms and kinda bring about bad attitudes.


    The best and worst moments, emotionally, come from the early days. I remember very well how I felt when I failed to qualify to team selection in 2015, when I failed to deliver good results from BOI 2016 and when I failed to get a silver medal from IOI 2017. Everyone who participated still knows what Nowruz is and not for its significance in Persian culture. Just as well, I remember getting top 5 in Estonian Open 2015 and listening nonstop to Sweet Victory. Now I'd consider that achievement to be unimpressive. Objectively, my most impressive achievement is probably getting to the finals of Hash Code 2020, yet I wasn't nearly as excited about that.

    After a while you become less excited when you succeed and less mortified when you fail. You have seen it all before, you have failed and succeeded countless times. Now if I fail I don't even think about it for more than 10 minutes. (There is also a time pressure thing; you're only in high school for 3 years while any contest I can do now will also accept me when I'm 40.)

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

Do u like burger :))))))

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

    Sure. The best "big chain" burger is Bacon King from Burger King. But big chain burgers aren't generally the best.

    I generally like any type of burger with halloumi. There's also a great burger I once ate with peanut butter and seitan.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What algorithm should I learn next?

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Is this FFT?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    The original problem that prompted me to say "is this FFT?" was this one, because $$$40961 = 2^{13} \cdot 5 + 1$$$. You can figure out the answer by yourself.

»
7 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Is this a real life?

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Is $$$2^{23} × 7 × 11 + 1$$$ equals to $$$998244353$$$?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what are your thoughts on number of rounds per month CF hosts? Do you think there should be weekly schedule to fix timings?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    The current number of rounds is fine.

    I think a weekly schedule is bad. A contest should not be hosted for the sake of hosting a contest. A contest should be hosted if there are enough novel and interesting problems. Furthermore, an irregular schedule allows more people to participate. If you have something on every Thursday afternoon and contests are all on Thursday afternoons then you can never participate.

»
7 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Does contribution in CF count?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you have solved the problem(and you are clear about your approach) and you are not able to understand the tutorial, what is the best way to deal with it?

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

    It would be extremely hard for him to understand our problem. Probably he never ever faced this kind of difficulties, otherwise, he wouldn't have been a GM .

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

    Well, if you have already solved the problem there is not a big issue anyway, right?

    In any case, it's very hard to answer this question because it's not specific enough. "Not able to understand the tutorial" is pretty vague. No one can see inside your mind so if you just say "I can't understand" it's not very helpful. Tons of people have asked me "I can't understand the tutorial" and without further information the only thing I can really do is try to write a better tutorial (which is a big time investment). But two things come to mind:

    • Are you trying to read the tutorial like a storybook? Mathematical text does require a different kind of concentration. You certainly can't expect to casually read the text and understand it, at least most of the time. A proof is a sequence of logical statements. You really do need to understand each step.
    • Maybe you are uncomfortable with mathematical reasoning and text in general. It's hard for me to give advice, but I think it is important that you identify what your precise problem is.
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Skill issue

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Excluding this, Which is the silliest question that someone has ever asked to you??

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am newbie, right now. And I have started solving questions of ratings from 1100 to 1500. Is this the best way to increase rating? Any suggestion will be helpful.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will you aim for LGM?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What advise can you give to someone solving Timus and Project Euler?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you planning to participate in UOJ NOI Round #7, as hos.lyric is?

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

Since I can ask anything, I am new to Linear Algebra and I was wondering why the algebraic form of the dot product is equivalent to the geometric one(i.e. a * b = xaxb + yayb = |a||b|cos α), I did a geometric proof but that doesn't give me any intuition to it can anyone help?

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

    I'm not -is-this-fft-, but this has something to do with $$$\mathbb{R}^2$$$ being an inner product space, and the inner product not depending on the basis. In simpler words, the inner product (aka the dot product in this case) doesn't depend on the choice of the orthonormal basis (aka the coordinate system in this case), but only on the "geometry" of the vectors. I can very well choose a coordinate system which has $$$x$$$-axis along one of the vectors without changing the value of the dot product, and using basic trigonometric facts, it is not hard to see why they are equivalent. Hopefully this helps.

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

      This really helped a lot. Thanks! I'm currently reading Gilbert Strang's book Introduction to Linear Algebra do you recommend any other source?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        For linear algebra, there are two common approaches to introduce it to people — one treating it as a study of vector spaces and linear maps, and the other as the study of matrices.

        I personally think that the first approach is the morally correct one, though to get right to the point for most applications, people prefer the second approach. The book you're referring to follows the second approach too.

        A good book for the first approach is Linear Algebra Done Right by Sheldon Axler, and if you want to have a look at how linear algebra is connected to other math topics (and read about them in brief as well), you might want to look at Evan Chen's Napkin.

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

          I will definitely check it. I appreciate your help. Thanks!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What are your future plans and what particular areas of technology interest you?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How did/do you track your practice ? Do you record and re-visit the problems that you could not solve back then or did you just read the editorial, understand it and then move on forever ?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I have tried many things. There isn't really an exact science to this.

    I started from USACO training, later I did A2OJ ladders. I think there is a lot of value in having to solve every problem, with no editorial to help you. Otherwise it's easy to slip into a pattern where you kinda just ignore the problems that you don't already know how to solve.

    At some point I tried to solve AGC problems systematically-ish. I didn't keep a "backlog" of problems I tried, but I did go back to problems I wasn't previously able to solve.

    I have also tried "gamified" problem recommenders and creating week-long mashup challenges for myself.

    I very rarely read the editorial. I talked about this in my self-deception blog. Editorials aren't useless or evil, but it is very easy to fall into a pattern of "pretend to solve the problem for $$$x$$$ minutes, then read the editorial". You mostly have to improve a certain kind of "thinking skill", not "collect" techniques.

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

      Thanks a lot for you response. Also, really love your self-deception blog.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, I have a traditional (and maybe will regret later) question and wish to get an answer different from "solve more problems", because I do.

Assume that I am $$$0$$$ years old:
It is really difficult for me to solve/prove math problems/solutions.
My math skills are shit in all aspects. My math skills came only from solving problems without any prior knowledge (no good base in math).
How to fix that without getting lost and overwhelmed?
Any course recommendations?
or some path like: learn this then that...etc.
Thanks.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What do you recommend to decrease debug time and avoid edge cases? I solve a lot of problems daily but it almost always takes 2-3 wrong answers before I get it.Also, are there any resources you like to stress test?

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

    My blog on using the command line outlines a procedure for stress testing. I've not really needed anything more, except for occasionally having to be a bit creative with the test generation.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Tere tulemast!

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

    Ma olen siin umbes kaheksa aastat olnud, pisut veider on mind tervitada nii, nagu ma oleksin siin uus.

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

      Kust saite motivatsiooni sellele tasemele jõudmiseks? Minu teada Tallinnas spordiprogrammeerimise eritunde ei toimu

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Ma ei tea ka, et keegi väga teeks. (Teaduskool mingil perioodil korraldab/korraldas kursusi, aga mitte siis, kui mina gümnaasiumis käisin.)

        Reaalkoolis soovitati informaatikaolümpiaadi teha ja nii ma läksin lahtisele võistlusele ilma eriliste teadmisteta (programmeerida selleks hetkeks oskasin). Tulemus oli kesine aga piisavalt hea, et ma hakkasin nende e-kirju saama. Sealt soovitati USACO treeningut (see on nüüdseks üliaegunud, aga see, et see ei lase edasi minna enne kui kõik ülesanded tehtud on, on ülimalt väärtuslik). Sealt see tee alguse sai.

        Aga üldiselt mind motiveerib lihtsalt sügav huvi selliste ülesannete vastu. Ma ei ole eriti kunagi ennast väga sundinud vaid pigem lihtsalt lahendan vabal ajal huvi pärast raskeid ülesandeid. (Samas ilmselt oleks areng kiirem olnud, kui oleks rohkem sundinud ennast.)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you like listening to music? What kind of music do you prefer?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I generally like alternative rock music. Some favorites are Dire Straits, MGMT, Muse, Radiohead, Electric Light Orchestra. That should give you an idea.

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

A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit's starting point, $$$A_0,$$$ and the hunter's starting point, $$$B_0$$$ are the same. After $$$n-1$$$ rounds of the game, the rabbit is at point $$$A_{n-1}$$$ and the hunter is at point $$$B_{n-1}.$$$ In the $$$n^{\text{th}}$$$ round of the game, three things occur in order:

  1. The rabbit moves invisibly to a point $$$A_n$$$ such that the distance between $$$A_{n-1}$$$ and $$$A_n$$$ is exactly $$$1.$$$

  2. A tracking device reports a point $$$P_n$$$ to the hunter. The only guarantee provided by the tracking device to the hunter is that the distance between $$$P_n$$$ and $$$A_n$$$ is at most $$$1.$$$

  3. The hunter moves visibly to a point $$$B_n$$$ such that the distance between $$$B_{n-1}$$$ and $$$B_n$$$ is exactly $$$1.$$$

Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after $$$10^9$$$ rounds, she can ensure that the distance between her and the rabbit is at most $$$100?$$$

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you married ?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are universities in Estonia good(quite vague, I know)?

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

do you like to chew gum

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

first of all, I really like your blog about self-deception any idea how to avoid burnout

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please review my profile and give me some advice , I want to reach Expert by the end of this year or at least Specialist! Am I doing somthing wrong? or I am on the right path !, I am mostly solving 1000 rated problems right now, I would say 50 % of the time I am able solve those problems on my own.currently, I am in the middle of exams in my collge, that is why my graph looks a little bit irregular.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you Fast Fourier Transform?

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

is it really worth it? are you somehow "proud" of everything you've accomplished even at the cost of nights and days being spent learning what pisano periods and pell's equations are?

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Explain the Solution to this?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How much money do you make yearly?