Predicting Participants’ Performance in Programming Contests using Deep Learning Techniques

Waheed et al. attempted to develop a system that can predict students’ academic success based on clickstream data and assessment results in a virtual learning environment. They used the artificial neural network (ANN) to classify the student performance into different classes and compared the obtained result of ANN with two baseline methods namely support vector machines and logistic regression [14]. It is observed that ANN outperformed the baseline methods. Several works related to student performance prediction have also been accomplished [16], [18],[19],[20].

Sudha et al. [8] worked on the classification and recommendation of competitive programming problems using Convolution Neural Network (CNN). The goal of their proposed system is to determine the required approach for solving the problem. W. Looi analyzed single C++ source code submission on Codeforces and tried to predict a user’s rank and country [9]. Among all the applied models, the neural network attained the highest accuracies of 77.2% in rank prediction (within one rank) and 72.5% in the country’s prediction. A. Alnahhas et al. investigated ML techniques to develop a system that can predict the contestant’s future performance by dissecting their past rating record [10]. Here, they applied five different baseline machine learning approaches. Besides this, they proposed a new deep learning model for result comparison with baseline. To conduct this research, they collected public data from the Codeforces website. They found that most of the applied techniques attain an acceptable result but the deep learning model performed better than the baseline. Chowdhury et al. [11] trained a Kohonen Self organizing feature map (KSOFM) neural network on log data regarding programmers’ performance. Here, programmers are grouped into three distinct clusters ie. ‘at risk’, ‘intermediate’, and ‘expert’. The proportional rules made classification with an accuracy of 94.00%. Besides this, three more models namely multilayer neural networks, decision tree, and support vector machine were trained using the same dataset. Among them, feedforward multi-layer neural networks and decision trees have achieved an accuracy of 97.00% and 96.00% respectively. The precision of the support vector machine was about 88.00%, but it attained the highest recall of 99.00% in terms of distinguishing ‘at risk’ students. By investigating ten years of TopCoder algorithm competitions, J. R. Garciaa et al. reported on the learning curves [12]. They also discussed how these learning curves are employed in university courses. Later, it can aid them to explain the impact of competitive programming in a class.
Ishizue et al. [13] employed machine learning models to try to simplify the process of predicting placement outcomes outside of the conventional, time-consuming placement examination and the level of programming competence outside of a programming contest. The explanatory variables consist of psychological assessments, programming tasks, and student-completed surveys.

Ohashi et al. proposed a unique feature extraction technique and convolutional neural networks to classify the source code. To demonstrate the proposed algorithm, they have used data of an online judge system. It is shown that the model performed well in predicting the right category with high accuracy. Intisar et al. [11] tried to classify the programming problems. For this, they made use of the two topic modeling techniques namely Non-negative Matrix Factorization (NMF) and Latent Dirichlet Allocation (LDA) for extracting the relevant features. Then, by utilizing these topic modeling features and Naive TF-IDF features, six classifiers were trained. It is found a series of beneficial trade-offs between the applied models in terms of dimensionality and accuracy.

Our proposed framework includes two phases. At first, we collected the data of 100 contestants from Codeforces using codeforces public API. The data¹¹1https://cutt.ly/nL120M9 includes contestant’s ratings, competition ranks, problem submissions, and submission verdicts. After collecting the data, we did some pre-processing. We considered each contest as a timestamp. Each timestamp has four types of features.

1. 1.

   Rating: Each contest represents a timestamp. The rating is a metric to evaluate an user/contestant. The more the rating is, the better performer the contestant is. This changes after each contest based on the rank of the user in that contest. We are going to predict this feature.

2. 2.

   Rank: This is the rank/position of the contestant in that contest. The rank is decided by the solve rating of the contestant in that contest. The more the solve rating is, the better rank the contestant gets.

3. 3.

   Solve Rating: Each contest has several problems and each problem has a different point based on its difficulty. The point of each problems decreases with time. The quicker a contestant solves a problem, the better points he gets. A contestant’s solve rating is calculated by adding the points of each problem he solved during that competition.

4. 4.

   Practice Features: This is the information of a contestant about how much practices he did after the previous contest and before the current contest.

   1. (a)

      Accepted(AC): It represents the number of problems that the contestant solved before the current contest and after the previous contest.

   2. (b)

      Wrong Answer(WA): It denotes the number of problems that were attempted by the contestant but failed to solve it correctly before the current competitions and after the previous competitions.

Finally, we built a dataset of sequences where each continuous 16 timestamps of a user are considered as a sequence. Among the 16 timestamps, first 15 timestamps were used as the input and 16th timestamp was used as the target. 80% of the sequences were used to train the models and the rest of the 20% of the sequences were used to test/evaluate the performance of the trained models.

In the second phase of our proposed system, we apply several state-of-the-art neural network models to predict the performance of each contestant in the impending programming contests based on previous contests. First, we describe the concepts of Recurrent Neural Network (RNN), since Long Short Term Memory (LSTM), and Gated Recurrent Unit (GRU) both are categorized into that one. Then we describe Bidirectional LSTM (Bi-LSTM), and a combination of LSTM with an attention layer (LSTM+AL).

In this paper, for all the models described above, we have configured four corresponding model layers with 256 neurons. After each layer, we used a dropout layer of drop rate 0.5. Then, we added a dense layer of 100 neurons with activation function Relu. Finally, a dense layer was used to output the features of the next timestamp of the sequence. In order to train the models, we used ‘mae’ and ‘adam’ as the loss function and optimizer respectfully. We trained all of the models for 1000 epochs with batch size 256. During training, weights of the best accuracy for each of the models were saved using the checkpoint. To check the efficacy of all the models with the test dataset, we used the saved weights of each of the trained models. The test dataset was sent through each of the models and accuracy was calculated to evaluate the models.

Metrics such as Mean Absolute Error (MAE) and Root Mean Squared Error (RMSE), which are often used to determine correctness for continuous data, have been employed to evaluate our proposed framework. These two metrics have been increasingly utilized by researchers to demonstrate the efficacy of their method [1], [2], [3].

Mean Absolute Error (MAE): It is a terminology that provides the measurement of flaws in the assessment compared with original values. It is also referred to Absolute Accuracy Error (AAE). MAE represents the average of all AEs. The MAE is denoted as,

Here, $y_{k}$ and $y^{\prime}_{k}$ denote the actual rating of $k^{t}h$ sample and the predicted rating of them from the models mentioned respectively. $N$ refers the number of samples.

Root Mean Squared Error (RMSE): It is a measurement of standard deviation that indicates how far the predicted value deviates from the actual value. Typically, this approach is suitable for finding the residuals’ standard deviation. Residuals are the prediction errors, or the distance between the regression line and the actual data points. Equation 2 shows how RMSE(t) is calculated. Where the notations are the same as described in Equation 1.

Mean Squared Error (MSE): It is also known as Mean Squared Deviation (MSD), which is another well known evaluation metric userd for prediction tasks.

R-squared ($R^{2}$): R-squared is a statistical metric that represents the proportion of the variance for an observed variable that’s explained by a predicted variable or variables in a predictive model. The correlation describes the strength of the association between the observed and predicted values. It also describes the degree to which the variance of one variable explains the variation of the second variable. R-squared measure is ranged between $0$ to $1$ and usually mentioned as percentages. The more the value of this metric is, we consider the more precise the predictive model to be. Equation 4 shows how R-squared is calculated [21].

Does considering contestants’ practice as an input feature helpful for better accuracy during the contestants’ performance prediction? To answer this question, at first, we ran the models without the contestant’s practice feature. Then, we ran the models without the contestant’s practice features. Result of the different models to predict the performance of the programmer on Codeforces is presented in Table 2 and Table 3.

Table 2 presents the performance of different models for different evaluation metrics without considering the contestant’s practice features. Among all the four models, the LSTM with attention achieved the lowest RMSE value (69.629) outperforming other three models: LSTM (73.133), GRU (85.968), and Bi-LSTM (75.024). The LSTM with attention model also outperformed other three models in terms of other three evaluation metrics: MSE, MAE and $R^{2}$. On the other hand, when the contestant’s practice information is used as a feature, the performance of all models significantly improves (Table 3). The values of RMSE, MSE, and MAE decrease, and $R^{2}$ increase significantly for all models. From the above two tables, we can see that the LSTM with Attention model provides better accuracy than others in both cases. By analyzing the four-evaluation metrics, it is observed that LSTM with the Attention model performed better than the other three applied models, and GRU performed worst among the applied four models. So, the sequence (from best to worst) of the performance of the models is LSTM with the Attention model, LSTM model, Bi-LSTM model, and GRU model.