Hi

I am learning FFT. ChatGPT told me that FFT could assist in solving self-convolution form like Catalan number where the (n+1)-th element is some convolution of the first n elements. For example:

c[n + 1] = sum(c[i][n — i]) for i in 0..n

Unfortunately, no matter where I look (and how hard I press ChatGPT), I couldn't find a single website/book/paper detailing this approach.

My Question: Is it actually possible to compute the first n elements of a self-convolution form like Catalan using FFT in, for example, O(nlogn) or less than O(n^2)?

Thanks a lot

Hi

Euclidean algorithm is popular for finding the modular inverse but I find it a bit hard to implement. Instead, the following algorithm is much simpler. Let's call $$$f(i)$$$ the modular inverse of $$$i$$$ with respect to $$$m$$$

This method is often used in computing modular inverse for a range of numbers and much easier to implement to my taste BUT... what's the time complexity of this algorithm for computing a single modular inverse? I guess it's $$$O(logn)$$$ but my skill is too low to prove it :(.

Any math expert can help :)?

Hi coders,

I have always felt curious about how the IMO/IOI/Nutellas and all academic-successful people are doing in their life. What awesome things they have been contributing to the world? Or about the seemingly-impossible things they have overcome. Such as the story about someone who won the IOI in 2020 with a perfect score despite his own country effort to stop him. Or a certain IOI medalist ended up creating the world's best QA platform called Quora.

I am sure those stories will be very inspiring for the next generations of coders.

Do you happen to know any online tracker for that?

Update 1: I put the raw data here first. If there are many, I'll create a Wiki article for it.

Update 2: Wow, the Vietnamese CPers are great. Come on, everyone. Where are you? Is there no story from your country?

Some Companies created by successful CPers:

• VK (RU) — worth billions $.

• Telegram (RU) — worth billions $.

• Ethereum (CH) — worth billions $.

• Quora — worth billions $.

• Pony.ai — worth billions $.

• Near Protocol — worth billions $.

• Sogou (CN) — worth billion $.

• Axie Infinity (VN) — worth billion $.

• Kyber Network (VN) — worth hundreds of millions $.

• Lunchclub — worth hundreds of millions $.

• Emerald Innovations — worth hundreds of millions $.

• Forethought — worth hundreds of millions $.

• Yugabyte — worth tens of millions $.

• Abivin (VN).

• SubWiz (DK).

Hi,

Recently I came across a problem like this:

Given h[1..n] where h[i] denotes the height of column i, find the largest x such that there exists some i where h[i..i+x-1] >= x.

The best I could think of is O(nlogn): binary search for the value of x and do a linear check. However, this problem reminds me of finding the largest rectangle which could be done in O(n). So I wonder if there also exists a linear solution to this problem?

Thanks

Hi,

[Note: I am a Java developer who loves Python, okay? I just want to learn something like this for Java/Python to use them more in CP]

I have a question buried deep in my head for all these years, but I don't think I can hold back anymore: Why would anyone use Python or Java in Codeforces?

Not everyone knows C++? I doubt so. Most coders would know at least 2 or 3 programming languages and C/C++ is one of the very classic one usually taught in universities.

More features? I doubt so. Except for big arithmetic problems, I doubt if there is any other feature in Java or Python for CP that C++ does not have. On the other hand, C++ does have more features than them such as speed, policy based data structures and direct memory access.

Shorter code? I seriously doubt so. At least compare to Java, C++ is shorter. Compared to Python, unless you want to couple everything into one unreadable line, then C++ should not be very longer.

I did try Python and Java for CP but only because I think Codeforces is a good place for me to learn those languages. What are your reasons?

Thanks

[Results]

1. Debugging. (actually CLion is quite good at debugging but not free and yeah, not excellent)

2. Shortness. (as kabuszki pointed out, I am not a Python natural user yet, so I didn t recognize)

Hi guys,

since I know you great coders are interviewing around the world and cracked lots of system design interviews. I want to ask if you would recommend some System Design interview 'complete' guide (in a '1 book' for example, not necessarily short but complete and in 1 self-contained form) for a competitive programmer to ace his coming interview?

I just realized I have zero knowledge of it when I need it. Of course, I do not expect much, though.

Thanks and happy coding

Okay, I know CP is all about ACM and IOI where only self-generated code is permitted, but does Codeforces, Hackerrank and the likes really have to stick to someone else's rules? I mean, does allowing package not promote the correlation between CP and practical programming? Does using package not promote thinking over (but not underrating) implementation? Does it not provide more room for slow languages such as Python? Does it not promote the development of new packages in algorithms and data structures and consequently promoting the popularity of CP among the world of developers (a simple search on Google for algorithm library would throw a bunch of stuff for pytorch and tensorflow)?

Maybe supporting all is no good, but I think there are many advantages to support a few popular options such as numpy, igraph, boost, apache-commons... and the likes. What do you think?

Just a suggestion :) Happy Coding!

After experimenting with Kotlin for a long time, my love for Java grows. Here are a few points I strongly believe that Java is better...

1. Worse parameter type casting. It is even worse compared to Java. At least, Java could detect an int object in a long parameter. Now if I create a method for long, I need to create int wrapper for it.

2. Hardship to create multidimensional array. Even if I agree that linear array is almost 99% of the case in real world scenario, if we somehow need it, like for CP, it is a terrible experience.

3. Immutable function parameters. It should be fine if the outside fields are immutable, but now, even within the scope of the function, we have to declare new variables and if we use the same name, we got the warning "shadowed name". It is even worse than Java.

4. No real interop for functional features in Java and lambda is a bit worse. This is not related to CP, but for software engineering. Another reason to not adopt it.

Well, there are more, but after trying Kotlin for sometime, I am increasing doubtful of its existence. There are hardly strong evidence for it in my opinion. Do you have any idea?

Thanks!

Hallo,

I am stuck on the following graph problem: How many k-colorings (exactly k, k is a constant) of a sparse graph of n vertexes (n <= 50000) with no connected component of size s having more than s + 2 edges (almost tree).

I am completely stuck!!!

Could someone give me a hint? It's a problem from Hong Kong Regional Online Preliminary 2016 (all of their problems are super hard).

Thanks.

Hi Codeforcers,

I often hear people talking about the greatness of VIM and that many red coders use VIM for competitions and VIM is so extensible and powerful of all sorts with numerous plugins available. I also tried some default configurations on the Internet and it looked not that terrible, but since VIM depends so much on plugins to be a great IDE, I am really curious how you installed them during a contest without Internet connection?

Can VIM users share your experience in using VIM for CP :)? I really want to find a good IDE for C++ :V. Even CLion is not too nice :'( .

Thank you so much.

Hi everyone,

for the past few days, I am reading implementations from Per Austrin. I hate to admit but his code is so clean, neat, short, efficient, aesthetic, intellectual, well-organized... and professional that I believe I have never read anything even close to his code.

I can find only some from NWERC solutions. Does anyone know where I can see more of his incredible code? His code gives me more insights into the problem that the official tutorials could not convey.

Thank you very much Thuan

Hi everyone,

I am learning this relatively new data structure with a Kattis problem called Palindromes. In this problem, we are given a string and multiple [l, r] segments and must find the number of palindromic substrings in each segment. The number of queries and length of the string are all 10^5. My question is: Is it possible to achieve this with Palindromic Tree and if yes, how can we do that?

I am not absolutely sure if this DS can handle such problems, but at least, I know that for [1, r] segments, it is possible, Is this variant possible? If it is possible, please give me your guidance.

Thank you very much :). Happy Coding

Hallo Codeforces Hackers,

could you tell me what can possibly go wrong with the following submission? I even changed all ints to long long just in case, but I cannot seem to find out why. It passed all except for test 4_hand_3, what can be in that test? My solution looks the same as that in the tutorial (though I do not know Japanese).

Submission: https://beta.atcoder.jp/contests/abc110/submissions/3261324

Thank you very much.

Hello, do you know Kotlin?

It is a promising language that can be a perfect alternative to Java? Using Kotlin, you can access any Java libraries and benefit greatly from its elegant syntax. It was even acknowledged by Google for Android development. And above all, Kotlin has been officially recognized for ACM ICPC. Why don't you give it a try?

Unfortunately, for Competitive Programmers like us, multidimensional array is a must, while Kotlin still has no good support for it. Please put your votes for this feature on https://youtrack.jetbrains.com/issue/KT-21670 . Your vote will surely help bring forth a new possibility for Competitive Programming.

Maybe if Kotlin has more CP users, Jetbrains may give us more free offers :D ? Everyone will benefit in every way. :)

Thank you.

[Updated] Hello everyone,

do you know if there is any data structure (like std::set) that allows querying on 2 parameters and adding elements? The use case is I have a list of (a[i], b[i]). I want perform a query with parameter MAXB that returns the pair with the maximum value by a[i] but the corresponding b[i] value is less than or equal to MAXB. I also want to perform an update by adding a pair.

Do you know any? Thank you.

[Updated] it seems that LaTex is the way to go, but my sense of design is a bit terrible. Do you know any available configurations for the listings package so that it will looks great like in CLion or VSCode? Thank you. Hello everyone,

I am looking for some software that can (ideally) process the C++ source files and automatically generate me a notebook with syntax highlighting and numbering. Do you know any?

If automation is not possible, doing it by hand is fine, but I cannot seem to find any tool that allows both good syntax highlighting and line numbering. At the moment, I am using Visual Studio Code and Word and the line numbering takes a lot of time. It would be great if some automation tools exist.

Thank you very much.

Updated: Thank to mnaeraxr, my old question has found its answer, but a new one's just arrived. I hope you all can continue helping me in understanding this.

Hello everyone,

I am sure that many of you have known this algorithm. As far as I am concerned, it is one of the most popular techniques in AI. I am learning it and I have a lot of questions regarding the intuition behind it, and hence I am writing today, with hope that some of you can share your experience with me.

To summarize a bit, a MCTS algorithm is consisted of 4 phases — Select, Expand, Simulate and Propagate, and is based on a formula called UCB1 to balance between exploitation and exploration.

[NEW QUESTION] My new question is: does MCTS have memory, by which I mean if it does learn to form its experience, save that experience somewhere and retrieve it for query? I asked this because even after understanding how the tree is formed, I find no information for how to query the tree. The only example with clear code and real serious problem I have found (which confused me and made me doubt MCTS) is after analyzing this (the main body) and this (the tree node). In this case, for every time we want to make an action (in the process()), they "create a completely new tree" and only take action after that by considering actions from "only the root" node ("all" other codes in that website use the same idea). In other words, each action is somewhat "independent" of the previous one. Is this the true nature of MCTS? If not (hopefully), could you please give me some references for how I can efficiently use all MCTS past experience and make a query? Thank you so much.

[ANSWER FOUND] My first concern is about the UCB1 formula, that is UCB1 = (total wins / total visits) + C * sqrt(ln(total visits in parent node) / total visits in current node). My question is what will change if I, instead of using "total number of wins", use something like "total reward" (which may be HP loss, energy increase and so on)? In such case, will the term sqrt(ln(total visits in parent node) / total visits in current node) stay the same?

Thank you for your time and consideration. I am looking forward to hearing from you.

Updated: Thank everyone for your helps, but it seems that I missed a certain condition of the problem, and my version maybe really just impossible to solve :v, the original problem with that condition is a thousand time easier than this and is straight-forward to CP coders like us (The original problem description was a bit confusing to me :'( )

Hi everyone,

today, I am stuck with a problem. I hope you can help me with it. I think this is a very interesting problem and I am not even sure there exists a deterministic solution to it. The problem is as follows:

" Given n (n <= 1000, but O(n^3) is also fine) distinct integers, group them into sets of at least 4 elements, and each set is an Arithmetic Sequences. "

Example:

Input: 1250, 3748, 6246, 8744, 2493, 4993, 7493, 9993, 2497, 4996, 7495, 9994, 2498, 4997, 7496, 9995, 2499, 4998, 7497, 9996

Output: (1250, 3748, 6246, 8744), (2493, 4993, 7493, 9993), (2497, 4996, 7495, 9994), (2498, 4997, 7496, 9995), (2499, 4998, 7497, 9996)

In this test, if you find the longest sequence first, then the rest will not form any valid sequence anymore.

(Assumption: For the given input, there always exists at least one solution that satisfies the constraints and no number is left)

I have spent hours working on this problem but unfortunately I cannot think of any ideas that will work well in general. What do you think?

Thank you.

Dear coders,

Last weekend, there was a Machine Learning contest on Hackerrank, namely GS CodeSprint 2018. It was my first time participating on a Machine Learning contest, so the result was horrible, but the important thing is: it is fun. During the contest, I only attempted to solve the easy problem, Car Popularity Prediction, but failed to solve it perfectly. It is simply a multi-classification problem: Given m features, map it to one of the 4 classes.

I saw many people perfectly completed it. Therefore, I wonder if it is possible to share your approach? In my solution, what I did was to use a simple sklearn SVM and a grid search on C from 0.001 to 100. Only these few line of codes could get me 0.92. Run it a few more times and I get 0.94, but it was not possible to get 1.

I would be thankful if you can share with me what you have done to solve such problem perfectly. Thank you. Besides, is there anyone knowing how to resubmit the problem? I tried to resubmit but their server did not accept?

Thank you for your time and consideration. I am looking forward to hearing from you.

Hallo, everyone.

Can you please help me with the following problem?

If a[n] = b[k] * a[n-k] for k = 1..n, then the generating function A(x) = a[0] / (1 — B(x)) We can compute all a[n] with Divide and Conquer algorithm in O(nlog^2(n)). What is that Divide and Conquer algorithm?

I have the feeling that it is strongly related to FFT but that's just my feeling. Can someone give me the exact algorithm?

Thank you

Hallo everyone,

Do you know any simple formulas that are often unknown to many? For me, some can be mentioned are

• Graph: Euler characteristic, Handshaking theorem, Caley Formula, Kirchhoff's theorem, Kőnig's theorem

• Polygon: 2-Ear Theorem, incenter formula of a triangle, pick theorem, Shoelace Formula

• Logic: Pigeonhole

• Prime: Fermat, Wilson's theorem

• Number: McNugget theorem

• Fibonacci: Zeckendorf's theorem

• Counting: Burnside Lemma, stars and bars

• Combinatorics Identity: Vandermonde's Identity, Hockey-stick identity

• Math: Linearity of Expectation

• Other: harmonic series sum

... And what about you? Can you share some?

Thank you.

Dear friends,

"Driving in Optimistan"

I have read this problem from last year to this year, but I am still unable to understand the example. The English is perfect. The way they express the problem is super nice, but it seems a little overwhelming for me. Therefore, can someone please help me clarify the sample input/output???

Thank you.

Hello,

I have been looking for an implementation of 2D Fenwick Tree for n, m<= 100000 without using std::map but with no luck. I want to ask if it is possible to implement 2D Fenwick Tree using O(nlogn) memory and O(logn^2) per update?

Tutorials, ideas or papers, all are very welcome.

Thank you.

Hello, everyone!!!

I would like to post some old problems from old ICPC Regionals/WF... on Kattis and create some contests for me and my friends, but I cannot find anyway to do that. Does any one have an idea how we can do something like that?

I already tried ICPC Archieve and feel very unacceptable. My output presentation was correct on udebug and get WA while while my output not matching with udebug, my solution get ACcepted.

Thank you.

Hallo,

I have been using e-maxx.ru for quite some time. It has also been my great dictionary when it comes to learning algorithms, but it seems clear to me that e-maxx has been outdated. I recently hear a lot more algorithms that are not covered by e-maxx. A few to mention are palindrome tree, Lichao Segment tree, Dominator Tree (not sure if this is a correct name)... and a dozen more.

I wonder if there exists a new page that has the same functionality as the great e-maxx page where we can see new algorithm updates? If there is implementation, it is nice, otherwise, the name and definition should do. English page is wonderful, but even if it is in Russian, it would be still marvelous with Google Translate. I also tried wcipeg.com but it is not even comparable to e-maxx.

Thank you for your time and consideration.