Document ranking problem, Yandex.Algorithm.2015 — Algorithms?

Question

Yandex

Not so long ago, the Yandex.Algorithm.2015 qualification ended. The format of the round is such that 100 minutes are given and 7 problems to be solved. The tasks are not very difficult, but nevertheless, there were certain difficulties in solving some of them. Basically, these are runtime limits (TL). In general, I would like the participants of the competition to join this topic; I would like to arrange something like a discussion of how to solve this problem, I think it will be very useful for each participant, on the eve of the main part of the competition, however, anyone can participate in solving this problem.
Condition:
Ivan is an ordinary Internet user. One of Ivan's favorite games is "Hat", in which you need to quickly explain the hidden word. In order to make it interesting to play, he searches for unusual words on the Internet, asking various search queries. Ivan has always wondered why one document is higher than another in search results. By asking about this in Yandex search, Ivan found out that documents are sorted automatically in descending order of document relevance. And relevance, in turn, is calculated according to a formula selected by a special algorithm. In this task, we will use a simplified version of the relevancy formula - a linear combination of document parameters. The ranking formula is given by N parameters (a1, a2, …, aN), and each document is described by N numerical parameters (f1, f2, …, fN). Relevance is determined by the formula:

The Internet changes very quickly, and some documents can change several times a minute. Of course, after that it is necessary to change some parameters of this document. Can you find the most relevant documents in the conditions of changing parameters of documents?
Input format:
The first line of the input contains one integer N (1 ≤ N ≤ 100) — the number of parameters in the ranking formula. The second line contains N integers ai (0 ≤ ai ≤ 10^8). The third line of the input contains one integer D (10 ≤ D ≤ 100 000, N * D ≤ 100 000) — the number of documents to rank. Then D lines contain N integers each fi,j (0 ≤ fi,j ≤ 10^8) — the numeric parameters of the i-th document. The next line contains one integer Q (1 ≤ Q ≤ 100 000) — the number of requests to the ranking system. The next Q lines describe queries. The request for issuing the most relevant documents is given by the pair 1 K (1 ≤ K ≤ 10). A request to change a document parameter is given by the four 2 djv (1 ≤ d ≤ D, 1 ≤ j ≤ N, 0 ≤ v ≤ 10^8) and means that the j-th parameter of the d-th document becomes equal to v.
Output Format:
After each query of the first type, print on one line the serial numbers of the K most relevant documents in descending order of relevance (numbers should be separated by single spaces). It is guaranteed that all documents at any given time have different relevance values.
Limits:
Time limit: 2.5 seconds
Memory limit: 64Mb
Input: standard input or input.txt
Output: standard output or output.txt
Example:

Input:
2
1 100
10
1 2
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
4
1 2
1 10
2 4 1 1000
1 10
Output:
1 10
1 10 9 8 7 6 5 4 3 2
4 1 10 9 8 7 6 5 3 2

Below is my java solution:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
 
public class Task3_2
{
    static class CPair
    {
        public int rel;
        public int num;
        public CPair(int r, int n)
        {
            rel = r;
            num = n;
        }
    }
 
    static class CRelComp implements Comparator<CPair> 
    {
        public int compare(CPair p1, CPair p2) 
        {
            return p2.rel - p1.rel;
        }
    }
 
    static int m_N;
    static int m_D;
    static int m_Q;
    static int[] m_listA;
    static int[][] m_listD;
    static int[][] m_listQ;
    static int[] m_listR;
 
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        m_N = Integer.valueOf(br.readLine()); //количество параметров - N.
        String[] line = br.readLine().split(" "); //набор параметров - Ai.
 
        m_listA = new int[m_N];
        for (int n = 0; n < m_N; n++)
            m_listA[n] = Integer.parseInt(line[n]);
 
 
        m_D = Integer.valueOf(br.readLine()); //количство документов - D.
        m_listD = new int[m_D][m_N];
        for (int d = 0; d < m_D; d++)
        {
            line = br.readLine().split(" "); //набор параметров Di-го документа - F.
            for (int n = 0; n < m_N; n++)
                m_listD[d][n] = Integer.parseInt(line[n]);
        }
 
 
        m_Q = Integer.valueOf(br.readLine()); //количество запросов к системе - Q.
        m_listQ = new int[m_Q][4];
        for (int q = 0; q < m_Q; q++)
        {
            line = br.readLine().split(" "); //набор параметров Qi-го запроса.
            for (int i = 0; i < line.length; i++)
                m_listQ[q][i] = Integer.parseInt(line[i]);
        }
 
 
        m_listR = new int[m_D];
        for (int d = 0; d < m_D; d++) //расчет релевантностей.
            for (int n = 0; n < m_N; n++)
                m_listR[d] += m_listA[n] * m_listD[d][n];
 
 
 
        //выполнение запросов.
        for (int q = 0; q < m_Q; q++)
        {
            if (m_listQ[q][0] == 1)
            {
                ArrayList<CPair> pairs = new ArrayList<CPair>();
                for(int r = 0; r < m_D; r++)
                    pairs.add(new CPair(m_listR[r], r + 1));
 
                Collections.sort(pairs, new CRelComp());
 
                for (int i = 0; i < m_listQ[q][1]; i++)
                    System.out.print(pairs.get(i).num + " ");
                System.out.println();       
            }
            else
            {
                int d = m_listQ[q][1] - 1;
                int j = m_listQ[q][2] - 1;
                int v = m_listQ[q][3];
 
                int oldPart = m_listD[d][j] * m_listA[j];
                int newPart = v * m_listA[j];
                int div = oldPart - newPart;
                m_listR[d] -= div;
                m_listD[d][j] = v;
 
            }
        }
 
    }
 
}

The program fails on 22 tests with a time limit of TL.

Answer 1

And if the time limit is removed, how long will it take?
Maybe C++ is needed?

Answer 2

Still, I decided to try testing the algorithm in C++, as Dmitry suggested in his answer. As expected, the program failed on 22 tests with a TL verdict.
Actually, below is the program code in C ++.

#include <iostream>
#include <string>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm> 
using namespace std;

vector<int> readLine();

int m_N;
int m_D;
int m_Q;
int m_listA[100];
int m_listD[100000][100];
int m_listQ[100000][4];
int m_listR[100000];

struct CPair
{
  int rel;
  int num;
};

int main()
{
  vector<int> vars = readLine();
  m_N = vars[0];
  vars = readLine();

  for (int n = 0; n < m_N; n++)
    m_listA[n] = vars[n];

  vars = readLine();
  m_D = vars[0];

  for (int d = 0; d < m_D; d++)
  {
    vars = readLine();
    for (int n = 0; n < m_N; n++)
    {
      m_listD[d][n] = vars[n];
      m_listR[d] += m_listA[n] * vars[n];
    }
  }

  vars = readLine();
  m_Q = vars[0];
  for (int q = 0; q < m_Q; q++)
  {
    vars = readLine();
    for (int i = 0; i < vars.size(); i++)
      m_listQ[q][i] = vars[i];
  }

  vector<CPair> pairs(100000);
  for(int r = 0; r < m_D; r++)
    {
      pairs[r].rel = m_listR[r];
      pairs[r].num = r + 1;
    }
      
  sort(pairs.begin(), pairs.begin() + m_D, 
    [](CPair const &a, CPair const &b){ return a.rel > b.rel;});		


  for (int q = 0; q < m_Q; q++)
  {
    if (m_listQ[q][0] == 1)
    {	
      for (int i = 0; i < m_listQ[q][1]; i++)
        cout << pairs[i].num << " ";
      cout<<endl;
    }
    else
    {
      int d = m_listQ[q][1] - 1;
      int j = m_listQ[q][2] - 1;
      int v = m_listQ[q][3];
        
      int oldPart = m_listD[d][j] * m_listA[j];
      int newPart = v * m_listA[j];
      int div = oldPart - newPart;
      m_listR[d] -= div;
      m_listD[d][j] = v;

      for (int i = 0; i < m_D; i++)
      {
        if (pairs[i].num == (d + 1))
        {
          pairs[i].rel = m_listR[d];
          sort(pairs.begin(), pairs.begin() + m_D, 
            [](CPair const &a, CPair const &b){ return a.rel > b.rel;});
          break;
        }
      }

    }
  }
  //system("pause");
  return 0;
}

vector<int> readLine()
{
  string input = "";
  getline(cin, input);

  istringstream iss(input);
  vector<int> vars;
  copy(istream_iterator<int>(iss),
    istream_iterator<int>(),
    back_inserter(vars));

  return vars;
}