Analysis of the 2024 test version of the master's program “Software for High-Load Systems” at ITMO

To gain admission to the entrance exam Master's program “Software for High-Load Systems”, which ITMO is doing together with Yandex Education, you first need to pass an online test. Here is the 2024 test, as well as my personal solution to it.

I would like to say right away that the author (that is, me) is publishing this solution as an applicant and I do not claim in any way that the solution is completely correct and strict. And since this online test and no one imposes any restrictions on it, except that I have to solve it and not someone else, then I reserve the full right to use online “helpers” such as graphing services and derivative calculations. I admit that many problems can be solved analytically and without using code. But why, when time is very limited 🙂

I am posting this because I found the problems quite interesting and also especially for the next generations of applicants.

A. New Year's corporate party

Solution:

Let – number of C++ and Python developers in the team

Let – number of C++ and Python developers in the team

Then the answer must indicate

Moreover

Then the probability that the presenter will choose a C++ developer is:

Then we just need to find the maximum value of the function

on

Online search for extrema of a function gives the following result regarding stationary points:

But these points are definitely not suitable for us (and the function is not defined at such values), because they mean that one of the groups will have no developers at all. This also means that there are no extremes in our definition area. There are suspicions that the correct answer is close to these points.

But let's write a program that will go through all the values ​​and find out the maximum probability.

#include <iostream>
#include <vector>

double prob(double x, double y) {
    return (double)1/2 * ((9 - y) / (9 - y + x) + y / (y + 6 - x));
}

void solve(const std::vector<int>& x_values, const std::vector<int>& y_values) {
    double x_max = 0, y_max = 0, max = 0;
    for (auto x: x_values) {
        for (auto y: y_values) {
            double probability = prob(x, y);
            std::cout << "P(" << x << ", " << y << ") = " << probability << std::endl;
            if (probability > max) {
                max = probability;
                x_max = x, y_max = y;
            }
        }
    }

    std::cout << "maximum reaches if x = " << x_max << ", y = " << y_max << " and P = " << max << std::endl;
}

int main() {
    std::vector<int> x = { 0, 1, 2, 3, 4, 5, 6 };
    std::vector<int> y = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    solve(x, y);
}

The program will give the maximum

But the program does not take into account that in the group there should be fewer developers than in So does not fit.

So the answer is: 0.8. Which means that in the first group there is only 1 plus, and in the second group there are 8 plus and 6 pythonists.

Let's check the probability using the original formula that we haven't made any mistakes along the way:

Answer: 08

B. Complex project

Solution:

Since each time 2 bugs of the same type are fixed for one operating system, 1 bug is added for each type of the second, this means that the sum of bugs does not change, therefore it is always equal therefore is bounded from above number of compositions length 4 for the number 7 with possible zeros, which is equal to the number of combinations with repetitions of 8 by 3:

Note: generally speaking, it is not necessary to calculate this number for the task, since the fact that the number is limited from above is enough for us, but it is good to understand the order of this number in order to evaluate whether it makes sense to solve the task using code.

Therefore, we can write a program that traverses the tree of possible solutions in depth with a stop criterion that the number has already been encountered (for this, we will create a set of already encountered possible values).

#include <iostream>
#include <vector>
#include <set>

int to_int(const char state[4]) {
    return state[0] * 1000 + state[1] * 100 + state[2] * 10 + state[3] * 1;
}

void solve(const char state[4], std::set<int>& states) {
    for (int i = 0; i < 4; i++) {
        if (state[i] >= 2) {
            char new_state[4] = { state[0], state[1], state[2], state[3] };
            
            new_state[i] -= 2;
            if (i < 2) {
                new_state[2] += 1;
                new_state[3] += 1;
            } else {
                new_state[0] += 1;
                new_state[1] += 1;
            }

            if (states.count(to_int(new_state)))
                continue;
            
            std::cout << to_int(new_state) << std::endl;

            states.insert(to_int(new_state));
            solve(new_state, states);
        }
    }
}

int main() {
    const char begin_state[4] = { 2, 0, 2, 3 };    
    std::set<int> states = { to_int(begin_state)};

    solve(begin_state, states);

    std::cout << states.size() << std::endl;
}

Answer:

C. Traveler Petya

Solution:

Obviously, the travel time depends on the point Petya will cross the stream.

Then you can write a dependency from :

Let's find the minimum point of the function on the interval . To do this, we find a stationary pointat which .

This is the point Plus, the constructed graph shows that this is a minimum point.

Answer:

PS: It is important to add 0 to the answer, as they ask to round to 3 decimal places, the answer 215.43 is accepted as incorrect by the verification system.

D. Bored Analyst

Solution:

There are 9 2×2 squares on the dashboard. We number the squares, going from left to right and top to bottom.

Let – an event that -th square is painted purple. Then:

Then we can calculate the probability of the opposite event to the desired one, that at least 1 square will be painted purple, inclusion-exclusion formula:

Then the desired probability will be equal to

This is too difficult to calculate manually, so we will write a program. The idea of ​​the algorithm is to number all the cells of the dashboard and look for the probabilities of all intersections. When finding the next intersection of events, you need to raise 1/2 to the power of the number of cells that are present in the union of the squares corresponding to the events in the intersection. The algorithm in Python (since there is a package for working with fractions):

from fraction import Fraction

squares = [
    {1, 2, 5, 6},
    {2, 3, 6, 7},
    {3, 4, 7, 8},
    {5, 6, 9, 10},
    {6, 7, 10, 11},
    {7, 8, 11, 12},
    {9, 10, 13, 14},
    {10, 11, 14, 15},
    {11, 12, 15, 16}
]

def calc_union_num(intersect):
    return len(set.union(*intersect))

def calc_prob_intersections(n, cur, interset):
    sum_prob = Fraction(0)
    for i in range(cur, len(squares)):
        interset.append(squares[i])
        if len(interset) == n:
            union_num = calc_union_num(interset)
            prob = Fraction(1, 2 ** union_num)
            sum_prob += prob
        else:
            sum_prob += calc_prob_intersections(n, i + 1, interset)
        
        interset.pop()
    
    return sum_prob

prob = Fraction(9, 2 ** 4)
for i in range(2, 9+1):
    intesect_set = []
    prob += Fraction(-1 if i % 2 == 0 else 1) * calc_prob_intersections(i, 0, intesect_set)

print("P(UAi) = ", prob)
answer = Fraction(1) - prob
print("1 - P(UAi) = ", Fraction(1) - prob)
print("answer = ", answer.numerator + answer.denominator)

The desired probability is:

Then the answer is:

E. Complex surfaces

Solution:

Firstly, since to the right of the equal sign we have the sum of even powers, then

is limited below by the number 0.

Let's get rid of degrees using substitutions Then the equation can be rewritten as follows:

Let's find the partial derivatives:

We'll find it And at which the partial derivatives vanish:

Let's substitute the found ones And into the original equation and we find :

And . But we remember that non-negative, yes

what remains is the meaning And . Let's check the value that it is

maximum… Although, in principle, it is not necessary to check, because since the condition says that the function takes the maximum value, it means that the function has an extremum, which is the maximum, in which the values ​​of the partial derivatives are equal to zero. Obviously, the remaining values ​​(only ), in which the partial derivatives vanish are not suitable for us, since there are more. Well, the maximum cannot be a point at which the necessary condition for the extremum of the function is not satisfied.

So, the maximum is achieved at points we need to find at what x, y such values ​​are accepted:

You can see that there are 4 points where takes on a maximum value, which means that in the sum of the coordinates of all points the values And will be reduced due to the opposite signs and the answer will be the maximum value of the function multiplied by 4, that is

Answer:

F. Delicious donuts

In my opinion, this is the most interesting task from the test from a practical, everyday point of view 🙂

Solution:

Let's turn the donut over so that its center is at the origin, and the non-hollow part in the section is described by a circle. .

Note that we have a torus in front of us and its volume is calculated using a definite integral as the volume of a figure of rotation around an axis . But we can also use a definite integral to calculate the volume of Sasha's part (shaded in green). This is the same figure of rotation, which is limited from above on the plane by the function and below .

Then the volume of the figure:

The torus has volume

Then the answer to the problem is:

Answer:

An interesting observation: the answer does not depend on .

G. Meeting of friends

There are 3 ideas how to solve the problem:

1. 

   We save all friends in an array together with a mark whether the person has left or not. At each exit, search on the left for people who have not left and search on the right for people who have not left. Each such search for total searches for operations. But, as a rule, in such problems, solutions for a square will not be accepted, since they will not be completed within the established limit.

2. 

   Let's get a tree (std::map in C++) friends, with the key friend number. Then at each exit of a friend it is enough to search on the left and on the right, each search for but the search for the most out of . After the search, we remove the current one, who is leaving, from the tree for . There are the same number of searches as in the previous example. . The main thing is not to forget to take into account the border guys in the tree, otherwise you can get a segfault.

#include <iostream>
#include <iterator>
#include <string>
#include <map>

using map_t = std::map<int, std::string>;

int main() {
    int n;
    std::cin >> n;

    map_t friends;
    for (int i = 1; i <= n; i++) {
        friends[i] = {};
        std::cin >> friends[i];
    }
    
    for (int i = 0; i < n - 3; i++) {
        int id;
        std::cin >> id;

        auto it = friends.find(id);
        if (it == friends.begin())
            std::cout << std::prev(friends.end())->second;
        else
            std::cout << std::prev(it)->second;
        std::cout << " ";

        auto it_right = std::next(it);
        if (it_right == friends.end())
            std::cout << friends.begin()->second;
        else
            std::cout << std::next(it)->second;

        std::cout << std::endl;

        friends.erase(it);   
    }
}

3. 

   The problem can be solved in linear time if you store friends in a doubly linked list, plus store pointers to the friend in the list in an array. Finding the most outlier (since we store the index → ​​list element mapping in an array), search left and right total searches .

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <iterator>
#include <utility>
#include <unordered_map>


struct node_t {
    std::string name;
    node_t *next = nullptr;
    node_t *prev = nullptr;
};

void add(node_t *head, node_t *new_node) {
    
    new_node->prev = head->prev;
    head->prev->next = new_node;

    head->prev = new_node;
    new_node->next = head;
}

void remove(node_t *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;

    delete node;
}

int main() {
    int n;
    std::cin >> n;

    std::unordered_map<int, node_t*> ptrs(n);
    node_t *head = nullptr;
    for (int i = 0; i < n; i++) {
        node_t* new_node = new node_t;
        std::cin >> new_node->name;

        if (!head) {
            head = new_node;
            head->next = head;
            head->prev = head;
        }
        else
            add(head, new_node);
        
        ptrs[i] = new_node;
    }

    for (int i = 0; i < n - 3; i++) {
        int idx;
        std::cin >> idx;

        idx--;
        auto node = ptrs[idx];
        std::cout << node->prev->name << " " << node->next->name << std::endl;
        remove(node);
        ptrs.erase(idx);
    }

    for (auto [_, node]: ptrs)
        delete node;


    return 0;
}

H. Points and plane

Solution:

This problem can be solved by a naive algorithm or by using the fact that the initial points lie on the same line.

The idea of ​​the naive algorithm is simple – for each of the q queries, run through the array of n elements of the source points and calculate the length from the point from the query to each point in the array and find out which of them is the least distant. Obviously, such a solution and it is not suitable for us, since the number of points n can reach and the number of requests can reach which when changed gives order operations multiplied by a constant, which is unacceptably many. So I won't even attach the solution, his system is not an example.

Let's use the fact that the points lie on one line. Then for each point from the query we can find the intersection point of the perpendicular dropped from this point to the same line on which the original points lie, and since the distance from the point from the query to any point on the line is the length of the hypotenuse of a right triangle formed by the perpendicular, the line itself and the segment connecting the point from the query with the point on the line, it is enough to find the closest point on the line to the intersection point of the perpendicular and the line (let's denote it by ), because the second leg (the perpendicular itself) does not change length, that is, the length of the hypotenuse depends only on the distance between and a point on a line. On a line you can find the closest point to sorting the array of points on the line lexicographically by pair using binary search for a point lexicographically not less than point P (in C++ this can be done using std::lower_bound). Then don't forget to take the previous point and compare its length to with the length from the found one, well, and don't forget the borderline situations, when has the least number of points on the line or the most.

We still need to figure out how to find that very point. for some point from the query, first you need to take two different points And from the original array, which define the line itself, and then angem will help us (or this one link):

Note: all points in the formula are vectors, that is, all operations should be considered as operations on vectors.

Let's analyze the complexity: first, we sort the array of points on a line by then for each request we find a point for we find the closest lexicographically not smaller point on the line to the point P using binary search total of such operations that is, we get the final complexity .

The code is in C++, but it would probably be easier to implement it in Python if the author had more skills with libraries like numpy for working with vectors.

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <iterator>
#include <utility>
#include <cmath>
#include <optional>

double operator*(const std::vector<double>& lhs, const std::vector<double>& rhs) {
    double res = 0;
    for (double i = 0; i < std::min(lhs.size(), rhs.size()); i++)
        res += lhs[i] * rhs[i];
    return res;
}

std::pair<double, double> find_perpendicular_point(const std::pair<double, double>& line_point_1, const std::pair<double, double>& line_point_2, const std::pair<double, double>& point) {
    std::vector<double> line_vector = { line_point_2.first - line_point_1.first, line_point_2.second - line_point_1.second };
    std::vector<double> vector = { point.first - line_point_1.first, point.second - line_point_1.second };

    double P = line_vector * vector;

    std::pair<double, double> result;
    result.first = line_point_1.first + line_vector[0] * P / (line_vector[0] * line_vector[0] + line_vector[1] * line_vector[1]);
    result.second = line_point_1.second + line_vector[1] * P / (line_vector[0] * line_vector[0] + line_vector[1] * line_vector[1]);

    return result;
}

double distance(const std::pair<double, double>& lhs, const std::pair<double, double>& rhs) {
    return std::sqrt((lhs.first - rhs.first) * (lhs.first - rhs.first) + (lhs.second - rhs.second) * (lhs.second - rhs.second)) ;
}

int main() {
    int n;
    std::vector<std::pair<int, int>> points;

    std::cin >> n;

    std::optional<std::pair<int, int>> first_point, second_point;

    while (n--) {
        std::pair<int, int> pair;
        std::cin >> pair.first >> pair.second;
        points.emplace_back(pair);
    }
    std::sort(points.begin(), points.end());

    first_point = points[0];
    if (points.size() > 1 && points.back() != *first_point)
        second_point = points.back();

    int m;
    std::cin >> m;
    while (m--) {
        std::pair<int, int> point;
        std::cin >> point.first >> point.second;

        if (!second_point) {
            std::cout << first_point->first << " " << first_point->second << std::endl;
            continue;
        }
    
        auto intersect_point = find_perpendicular_point(*first_point, *second_point, point);
        auto lower_point = std::lower_bound(points.begin(), points.end(), intersect_point);

        if (lower_point == points.begin()) {
            std::cout << lower_point->first << " " << lower_point->second << std::endl;
        } else if (lower_point == points.end()) {
            std::cout << points.back().first << " " << points.back().second << std::endl;
        } else {
            auto left_lower_point = std::prev(lower_point);

            if (distance(*left_lower_point, point) <= distance(*lower_point, point))
                std::cout << left_lower_point->first << " " << left_lower_point->second << std::endl;
            else 
                std::cout << lower_point->first << " " << lower_point->second << std::endl;

        }
    }

    return 0;
}

Good luck to everyone with their admissions!