Lately I have been seeing many many blogs after the recent Div 3 contest (Codeforces Round 1109 (Div. 3)) regarding cheating and AI usage. While this post is not directly regarding that, one question has been constantly bothering me. That is — are Div 3 and Div 4 contests still relevant?

You can detect if someone copy-pastes an AI generated code. But let's say an user gives the problem statement to an LLM and asks it to break down the problem brick by brick. Or even worse, someone can literally give the AI one of his previous codes (that he wrote himself) and he can then ask to write the solution code in exactly same format (same spaces, same type of variables, human-like variable declaration, no advisory comments etc). This is no big deal if your prompting is not terrible. Nobody can ever detect this type of 'smart AI usage', which is obviously, strictly prohibited!

LLMs like Google Gemini and Anthropic Claude solve problems from Div 3 like it is nothing. There was a time when these LLMs could solve up to C-D, but now that bound is completely broken — it seems that an efficient AI can solve an entire contest today.

And even worse, I would like to share an experience of mine from the last Div 2 contest (Codeforces Round 1108 (Div. 2)). In this contest, I solved A, B and C. After trying a lot, I couldn't solve D, it kept getting wrong answer on pretest 3 (Here are my submissions during the contest: 382292963, 382297206). Finally after the contest, a little frustrated, I opened Gemini and gave the problem and my code. It gave me a 'corrected code' within a minute (382302565) and unexpectedly (or expectedly), it got accepted. Therefore LLMs are solving Problem D-s of Div 2 on first tries, now-a-days. God have mercy on lower divisions.

Edit 1: I seem to have failed to convey what I meant. The fun and excitement of any contest never changed, and it never will (hopefully). But is the rating still relevant? Personally I think the system needs to be adjusted a bit according to the present scenario, involving AI and all.

My friend Anish_Rooj just informed me that his rating, out of nowhere increased to 1120 from 930. So I opened my profile, and found out that my rating went down to 1076 from 1126. What the hell happened? And why?

Motivation

Updating weights in each layer is the core of tuning a Neural Network. Now consider a simple regression model. If I ask you what method we use to update the weights? You'll probably reply — the method of least squares. And that is the most common thing. But it is to be noted that, Least Squares may not always be the most optimal method of updating weights. In this blog, I'd want to tell you about a very powerful method to get the weights. And if you have studied Numerical Analysis, you probably know about this. It's nothing but the very popular Newton-Raphson Method.

Well in general, this is used to solve equations numerically which are not solvable analytically. If we simply have to define the method, it will be something as follows:

Consider the equation, $$$f(x)=0$$$. Then, we can solve for $$$x$$$ starting from any initial guess $$$x^{(0)}$$$; and for the $$$i$$$-th iteration, the update of the solution $$$x$$$ is given by,

$$$x^{(i)} = x^{(i-1)} - \frac{f\left(x^{(i-1)}\right)}{f'\left(x^{(i-1)}\right)}\quad[i \gt 0]$$$

Now let's apply this for weights $$$(\Theta \in \mathbb{R}^n)$$$ in a simple Linear Regression model.

Warning: Heavy Mathematics coming up!

The Idea

Let's consider a simple linear regression model.

Let's consider that we have $$$m$$$ training examples and $$$n$$$ inputs, or more formally, $$$x^{(i)} \in \mathbb{R}^n$$$ for any $$$i \in {1, \ldots, m}$$$. For simplicity, let's take $$$y \in \mathbb{R}$$$ here. We can also have to predict a multidimensional output.

Consider the loss function,

$$$J(\Theta) = \frac{1}{2m} \sum_{i=1}^{m} \Big( h_\Theta(x^{(i)}) - y^{(i)} \Big)^2$$$ where $$$h_\Theta(x^{(i)})=\theta_0+\sum_{j=1}^{n}\theta_jx_j^{(i)}$$$ where $$$i \in {1, \ldots, m}$$$.

First let's take about the Least Squares Method. In this method, to get optimal weights i.e. $$$\Theta$$$, we simply set,

$$$\nabla_{\Theta} J(\Theta) = 0$$$

To be noted that,

You can get this result simply by calculating each partial derivative $$$\frac{\partial J}{\partial \theta_j}$$$.

Now, we needed, $$$\nabla_{\Theta} J(\Theta) = 0$$$

Hence, $$$X^\top (X \Theta - y)=0$$$

Which gives, $$$\Theta = (X^\top X)^{-1} X^\top y$$$

That's the final result that we obtain in this method. Now let's talk about the Newton-Raphson Method.

In the $$$k$$$-th iteration of the Newton-Raphson method, for multidimensional quantities, we have,

Where $$$H$$$ is the Hessian Matrix, in which,

$$$H_{ij} = \frac{\partial^2 J(\Theta)}{\partial \theta_i \, \partial \theta_j}$$$

If you work out the matrix, you'll end up with $$$H(\Theta)=\nabla_{\Theta}^2 J(\Theta)$$$.

Let's begin iterations of Newton-Raphson method with $$$\Theta^{(0)}=O$$$. Then we end up with, $$$\Theta^{(1)}=-(\nabla_{\Theta}^2 J(\Theta^{(0)}))^{-1}\nabla_{\Theta} J(\Theta^{(0)})$$$.

Also, it is to be noted that $$$J(\Theta) = \frac{1}{2} (X \Theta - y)^\top (X \Theta - y) = \frac{1}{2} \text{tr}\big((X \Theta - y)^\top (X \Theta - y)\big)$$$.

So we can do some can do some calculations with $$$J(\Theta^{(0)})$$$ and we'll end up with,

$$$\Theta^{(1)} = (X^\top X)^{-1} X^\top y$$$

Which is the same result as Least Squares!

Conclusion

While solving general scalar equations, we usually do 3-4 iterations of the Newton-Raphson method. Least Squares is already a practised method in Statistics and Machine Learning. And here I showed you how Newton-Raphson method outperforms Least Squares only in one iteration. And now, I'll leave it up to you — to think, how much optimization we'd have in just 1-2 more iterations! Neural Networks generally use Gradient Descent with a given learning rate to update weights. But when we talk about the Mathematics, analytically it becomes quite tough to work with Gradient Descent — we aren't perceptrons after all. So, when you do not have a computer, you can use Newton-Raphson method to determine optimality, and with just two iterations, it will outperform Least Squares by quite a large margin.

And this brings us to the end of the long, mathematical discussion. I really hope you enjoyed reading it, thank you for reading so far!