I originally read the problem statement as stating that the radius could only be up to 1000 in length. Hence, I was really confused when everyone was saying the problem was really easy. But that nightmare is behind me now.

I never figured out how to do it with that kind of restriction of the radius in under 1 second. What would be the optimal algorithm to use for that case?

Мне кажется, что моя формула верна.
Пусть f(n)=кол-во последовательностей длины 2*n,содержащие числа 1,1,2,2,...,n,n, причём любые два соседние числа различны; g(n)=кол-во последовательностей длины 2*n,содержащие числа 1,1,2,2,...,n,n, причём существует только одна пара соседних равных чисел.
Тогда f(n)=n*(2*n-2)*f(n-1)+n*g(n-1), g(n)=n*(2*n-1)*f(n-1)+n*g(n-1) => f(n)=g(n)-n*f(n-1) => g(n-1)=f(n-1)+(n-1)*f(n-2) => f(n)=n*((2*n-1)*f(n-1)+n*(n-1)*f(n-2)).
f(1)=0, f(2)=2 (mod p).
Ответ на задачу f(n-1) mod p.

Хотелось бы увидеть ответы на следующие тесты:
5 10000000
6 10000000
7 10000000

Edited by author 29.05.2017 13:01

И все же...
Что там за набор такой?

Edited by author 12.06.2017 20:33

solved. thanks

Edited by author 26.12.2013 09:01

I used scanline to solve this problem. This method is shown
here: http://e-maxx.ru/algo/length_of_segments_union. All the given points are put in array with 2n+m elements, each point having one of 3 types: start of a segment(0), end of a segment(2), a point for which the answer is needed (1). Then the array is sorted, and we go througth its elements: if the element has type 0, then we insert according segment into the set, if the element has type 2, then we delete according segment from the set, if the element has type 1 then we take the segment of minimum length from set in O(1), and output its id. The complexity is O((2n+m)log(2n+m)) (quicksort).

Edited by author 09.02.2016 14:53

Hi! I use greedy algorithms and can't get past first test. Could someone please provide me with some tests? I tried these tests with following results:
1
-1 0
-5 -3
2 5
0 0
-----------
No solution

1
-1 0
0 1
0 0
-----------
0 1

10
-5 1
1 14
-5 2
2 3
3 19
0 0
---------
-5 2
1 14

5
-5 0
0 1
1 2
2 3
4 5
3 4
10 49000
0 0
---------
0 1
1 2
2 3
3 4
4 5

4
0 4
-5 0
3 4
-4 4
0 0
-------
-4 4

6
0 5
7 8
0 0
-------
No solution

10
0 9
0 0
-------
No solution

import java.io.*;
import java.util.*;


public class Main {

    private static final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private static final PrintWriter out = new PrintWriter(System.out);
    private static final StreamTokenizer tok = new StreamTokenizer(in);

    public static void main(String[] args) throws IOException
    {
        int windowSize = nextInt();
        Queue<Integer> q = new LinkedList<Integer>();
        Deque<Integer> maxQ = new LinkedList<Integer>();
        while(true)
        {
            Integer n = nextInt();
            if(n == -1)
                break;
            q.add(n);
            while((maxQ.isEmpty() == false) && (maxQ.peekLast() < n))
                maxQ.removeLast();
            maxQ.add(n);
            if(q.size() == windowSize)
            {
                Integer elemToRemove = q.remove();
                Integer maxElement = maxQ.peek();
                out.println(maxElement);
                if(maxElement == elemToRemove)
                    maxQ.remove();
            }
        }
        out.flush();
    }

    private static int nextInt() throws IOException
    {
        if(tok.nextToken() != StreamTokenizer.TT_NUMBER)
            throw new IOException();
        return (int)tok.nval;
    }

}

//note, though there's while loop to remove elements from maxQ,
//amortized comlexity is still O(n)

So at first I got AC in 68 ms using scanf("%c", *char)  and then I replaced scanf with_getchar_nolock()  and got AC in 46 ms...

If you got Median on the Plane AC you can get Akhbardin roads AC with the same code (with minimal changes).

Maybe you are using expressions like (n-j) for j=0...n-i-1 and 0-indexing when checking diagonals.  So,  (n-j)  results in WA #8. Correct expression is (n-1-j)

Since n^m can be very large (n,m <= 50), does one need BigInteger? I would not want to do it, since I've already started coding the whole thing in C++...

Use Manacher's algo for comprehensive list of palindroms and try to calc 2 arrays:
beg[i] - number of palindroms begins at position i,
end[i] - number of palindroms ends at position i.
after that ans = beg[i + 1] * end[i] for every i.

To calc arrays you can use either O(n) offline (+=cnt at beg -= cnt after end; then sum) or efficient data structures.

Edited by author 22.05.2017 20:40

Пролистал кучу форумов, нахожу везде очень сложные формулы, может я слишком загоняюсь и есть какой то простой алгоритм решения? Кто нибудь может помочь?

Hi,  I tried all the tests can be found in that discussion.
My program gives always the right answers.
I am using Python,  so,  there can't be any integer overflow.
I am using gcd function from Fractions.

So the task is to determine whether the sum C[n][1]+C[n][2]+...+C[n][k] is greater than X and do it FAST.
I can't do it fast.


#include <stdio.h>
typedef unsigned long long huge;
huge calc(int n, int k){
     huge Up=k, Dn=0;
     while(Up-Dn>1){
           huge Md=(Up+Dn)/2;
           huge cnt=0;
           long double aux=1;
           for(int i=1; cnt<k && i<=n; ++i){
                  aux*=(long double)Md+1-i;
                  aux/=i;
                  cnt+=aux;
           }
           if(cnt<k)
                Dn=Md;
           else
                Up=Md;
     }
     return Dn+1;
}
int main(){
    huge n,k, ans[1000];
    int tot=0;
    scanf("%llu %llu",&n,&k);
    while(n>0 && k>0){
         ans[tot++]=calc(n,k);
         scanf("%llu %llu",&n,&k);
    }
    for(int i=0; i<tot; ++i)
          printf("%llu\n",ans[i]);
    return 0;
}

Named         avg =5
High          avg>=4.5 not contain 3   nooooote  that
Common             not  3 and less than 4.5
None            not all of the above

I have implemented a greedy algorithm to solve this problem and it got accepted and after reading the discussion I have noticed that many people used Prims algorithm to solve.
I have no idea of what Prims algorithm is. Could anyone please tell me what exactly is my code doing and how is it different from Prims algorithm?

[code deleted]

Edited by moderator 21.01.2020 16:06

Obviously USED array is MLE.  Probably using unordered_set is OK. Are there better things than unordered_set?  Maybe there are some mathematical properties?..

(n+2)*((n+1)*n)/2