My algo is as follows:
1.for any contestant i:
2.     if(there is a contestant j whose three speeds all equal to i )
3.     then   i and j are both sure losers;
4.     else if(the three speeds of j are no less than i)
5.     then   i is a sure loser;
6.     else if(the three speeds of j are no more than i)
7.     then   j is a sure loser;
8.for any contestant i:
9.     if(i is a sure loser) writeln(No);
10.    else writeln(Yes);

3
10 10 10
6 100 17
100 6 17

2
1 2 3
1 2 3

Edited by author 23.01.2010 12:58

Can someone who has had problems on this test put a tes the used to figure the problem? Thank you very much

Later Edit:
This tests helped me:
4
1 1 1
3 1 2
4 1 2
5 2 1

and

3
1 1 1
2 2 2
3 2 2

Edited by author 15.04.2011 02:21

My solution (as well as solutions of some other authors) got AC, but gives incorrect answer for such test case:

3
9999 9999 1
10000 9998 10000
9998 10000 10000

The correct answer is:

Yes
Yes
Yes

Please add it to system tests.

Edited by author 04.05.2009 00:44

I was getting WA 25 and was failing this test (from the forum):

Input:
3
9999 9999 1
10000 9998 10000
9998 10000 10000

Output:
Yes
Yes
Yes

I was using Epsion 1e-6 and got WA #25. After changing Epsilon to 1e-9 I got AC.

3 4
0 2000 1000 3000 0 3000
0 0 3000 0 3000 3000 0 3000
ans: 647.1067811865

5 6
0 2000 500 2500 1000 3000 1500 3000 0 3000
0 0 1500 0 3000 0 1500 0 3000 3000 0 3000
ans: 647.1067811865

3 4
0 0 4000 0 2000 4000
0 0 4000 0 4000 4000 0 4000
ans: 3517.7087639997

4 4
0 0 3000 0 3000 3000 0 3000
2000 2000 5000 2000 5000 5000 2000 5000
ans: 940

4 4
0 0 3000 0 3000 3000 0 3000
1000 1000 -2000 1000 -2000 -2000 1000 -2000
ans: 940

4 3
0 0 30000 0 30000 30000 0 30000
10000 40000 40000 10000 40000 40000
ans: 7011.0678118655

4 4
0 0 3000 0 3000 3000 0 3000
-1000 1000 5000 1000 5000 2000 -1000 2000
ans: 1940

4 4
0 0 3000 0 3000 3000 0 3000
-1000 2000 1000 -1000 2000 -1000 -1000 2000
ans: 647.1067811865

3 3
0 0 4000 2000 0 4000
3000 2000 7000 0 7000 4000
ans: 387.2135955000

Also, WA6 = integer overflow

input : ABCDLKOIKJTFIDCBA

ouput is a single letter such as A K and I
NOT “ABCD” or what have you .

I passed WA #10 by printing 90 decimals and using custom decimal computations accurate up to 45 digits.

What is the test 4?

This test was failing on my solution. Other similar (symetric) tests could fail other similar (symetric) solutions.

Input:
2 1
-999999999 0
-999999999 1

What's wrong with this test?

Before you look at the solution I have to clear up some confusion.

If we are talking about the lowest bound it takes for the program to complete, then it is O(N^2), because you have to evaluate each table cell no matter what and print the value. This is also considering that by N we denote the side of the table.

On the other hand, the function that takes in i and j and spits out the correct number in O(1) **is possible** without any lookup, which can be also be parallelized and be ported as fragment shader. You can see it below, it's the `eval` function and all calls are independent of their neighbors.

The core challenge is to figure out how to calculate which diagonal are you on -- I call it level -- and what is your local index on that diagonal line. For example, for N=3, we have:
4 2 1
7 5 3
9 8 6

where, "1" is on the first level, "2,3" are on the second level, "4,5,6" are on the third level and so on. Furthermore, 6 is the third number on that line.


```cpp
#include <stdio.h>

int abs( int x )
{
    return x >= 0 ? x : -x;
}

int sum( int n )
{
    return ( n + 1 ) * n / 2;
}

static int n;
static int totalLevels;
static int topRight[2];

int eval(int i, int j)
{
    const int level = abs( topRight[ 0 ] - i ) + abs( topRight[ 1 ] - j );
    if( level < n )
    {
        const int origin = n - 1 - level;
        const int index = i - origin;
        return 1 + sum( level ) + index;
    }
    else
    {
        const int index = i;
        return 1 + n * n - sum( totalLevels - level ) + index;
    }
}

int main()
{
    scanf("%d", &n);
    totalLevels = n * 2 - 1;

    topRight[0] = n - 1;
    topRight[1] = 0;

    for( int j = 0; j < n; ++j )
    {
        for( int i = 0; i < n; ++i )
            printf("%d ", eval( i,j ));

        printf("\n");
    }

    return 0;
}
```

try this test:
1 1 3 100 3000

ans: 1000

take sample output and
map it affinly to data triangle and you will have AC

Edited by author 24.03.2026 20:05

Please tell me this test and tell me if the three-time repetition of the position by the king is taken into account (in chess, in this situation there is a draw)

I use 'set' in python. Very simple. But I have WA3. Don't know why. Please help.

Tricky test case (even can't find its analogue). It contains such placement of draughts that you should precisely touch one or several other draughts by your move, and almost identical angles (+/- 1e-8 radians) will not give correct answer. When allow precisely touch got AC.

P.S.
Seems like one enemy draught you touch on the left side and other one - on the right side simultaneously.

Edited by author 23.04.2023 18:44

Is this a rounding issue in the output?