I solved it using pretty straigtforward DP O(n * m^2), obviously it's just a complexity without any additional factors but it doesn't seem to be fitting time limit. Somehow it did. But I wonder, is there any more intricate idea for a faster solution?

In my solution, it was a bug with precision. So I fixed it, by using int instead of double, as much as it was possible

sys.setrecursionlimit(10**9) + python instead of PyPy

Test:

1 4
m
m a
a b
b c
c a

Output:
-1

How I can check the tests?

Use BFS, use bitset, use binsearch, use random shuffle and get easy AC!

The description of the problem says: "Your program must take into account the command \", which is used to write two dots above a vowel. For example, \"e means the symbol ë." But you don't really have to distinguish between vowels and consonants for this command.

Edited by author 26.08.2024 17:37

My program use iostream for reading data. Always when i use iostream i add this lines to turn off flushing after each line:

signed main(void) {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    // solution
    return 0;
}

But in this problem program with this lines getting WA#1, without - AC. Why?

Use Manaker's algorithm

I've got WA 5 cause I checked that distance less than d only in case where Gnusmas is not on the border of the arc.

So, if you have WA#5 be careful with case where Gnusmas is on the border of the arc of fire.

Один и тот же алгоритм и практически один и тот же код,  с учётом схожести синтаксиса языков,  даёт :

AC 15 ms C++14 Clang

TLE #9 Python  2.7/3.4

But O(N^2 * logN) is death for python

Edited by author 23.08.2024 14:56

Statement is unclear. If you want to solve it you must try all possible interpretations of this statement 'till find the one that the author intended.

These tests helped me to fix WA8

10
4811511
2282103
4376795
8402551
3861207
8577438
2810768
5559695
8993319
5240873

infinity

10
9706784
5106148
5528237
9514430
1047500
6715041
9514430
7524350
4524591
2186600

infinity

But then I had WA27, which I fixed by ignoring number 1 somewhere in my code, and got AC.

But my AC solution is still wrong, here is the test breaking it (upd: my second AC code passes it):
10
8246707
8246707
6566521
3418657
9048372
2505801
428602
9261803
4761595
6564437

Correct answer:
2
My AC code output:
infinity

Edited by author 20.08.2024 19:31

#include <cstdio>
#include <vector>
#include <math.h>
#include <cstdlib>
#include <algorithm>
using namespace std;
double line_k(double x1, double y1, double x2, double y2)
{
    double k = (y2 - y1)/(x2 - x1);
    return k;
}
double line_b(double x1, double y1, double x2, double y2)
{
    double b = y2 - (y2 - y1) * x2 / (x2 - x1);
    return b;
}
bool is_on_line(double k, double b, double x, double y)
{
    if (y <= x * k + b + 0.01 && y >= x * k + b - 0.01) return true;
    return false;
}
struct point{
    double x,y;
};
int main()
{
    int n, counter = 2, max_zerosx = 0, max_zerosy = 0;
    double x, y, k, b;
    vector <point> koord;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lf %lf", &x, &y);
        if (x == 0) max_zerosx++;
        if (y == 0) max_zerosy++;
        {
            koord.push_back(point());
            koord[i].x = x;
            koord[i].y = y;
        }
    }
    int maximal = max(max_zerosx, max_zerosy);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            k = line_k(koord[i].x, koord[i].y, koord[j].x, koord[j].y);
            b = line_b(koord[i].x, koord[i].y, koord[j].x, koord[j].y);
            for (int l = j + 1; l < n; l++)
                 if (is_on_line(k, b, koord[l].x, koord[l].y))
                     counter++;
            if (counter > maximal) maximal = counter;
            counter = 2;
        }
    }
    printf("%d", maximal);
    return 0;
}

Я написал рекурсию которая каждый раз делила отрезок на два и брала максимальный среди ответа всех таких отрезков которых поделила.(типо Merge Sort). У меня был memory limit на 3 тесте. Это значить рекурсия берет память?