Я долго бился с этой проблемой несмотря на то,что сложность <200. Я пытался решить с помощью ДП,но там очень много случаев и сложная реализация. Задачу можно решить логически: во-первых,первые символы "<" и последние символы ">" ни на что не влияют,поэтому удалим их; во-вторых,если слева есть хоть один ">",то он в ЛЮБОМ случае будет меняться с КАЖДЫМ "<" РОВНО один раз(если "<" существует). Т.е. нас не интересует конструкция строки. Нас интересуют числа Z[1],E[1],Z[2],E[2],...Z[p],E[p],где Z[i] -количество ">" в последовательности 00000000...00000,а E[i]- количество "<" в последовательности 11111....11111111. Т.е. нашу строку делаем в виде 00...0011..1100..0011..11........00..0011..11,где P чередований (я ">" заменил на "0",а "<" на "1")
. Тогда ответ есть Z[1]*(E[1]+...E[p])+Z[2]*(E[2]+..+E[p])+...+Z[p]*E[p]. Сумму можно посчитать через частичные с помощью ДП. Асимптотика O(N).

The problem is quite evil.  The problem is actually very easy.  It is hard to understand that the problem is that easy.
Possible solution.
First ,  eliminate all such segments I=[l;r],  that l>M or r<0, because of such I's can't appear in the answer.
Second,  build your dp[].
Your dp[x]  contains rightmost right end of all such segments [l;r],  that l<=x.
Finally,  just start from segment whose right end is dp[0],  jump to a  segment whose right end is dp[dp[0]] and so on.

How to build dp[x]?
I have used an additional array right_end[y].  Where right_end[y] is the right end of a segment with maximal length from all segments whose left end is y.
dp[x] =max(dp[x-1], right_end[x]).

What does it mean? Runtime error (access violation)
This is my code on c++
#include <iostream>
using namespace std;
int n,ans;
string s;
int main()
{
    cin>>n;
    ans=n+2;
    for(int i=0; i<n; i++)
    {
        cin>>s;
        for(int j=0; j<s.size()-3; j++)
        {
            if(s[j]=='+' && s[j+1]=='o' && s[j+2]=='n' && s[j+3]=='e')
            {
                ans++;
                break;
            }
        }
    }
    if(ans==13) ans++;
    cout<<100*ans;
    return 0;
}

Edited by author 31.05.2017 21:40

I used the same code

The answer is either one or zero.
The answer is one when all the children tastes are lying on the same straight line. And the best friends are two children with maximal possible distance between their tastes.

You can just brute force all possible points on the grid.  For every point check whether that point is under attack. So,  your grid is just a SZ*SZ square matrix.  SZ=200 is accurate enough,  and even somewhat smaller values are OK.

You can solve it using :
(1) canonical straight line formula for perpendicular length ;
(2) cosine theorem to know whether your perpendicular length is the answer to the first question or not;
(3) Just formula for Euclidian distance and maximum function to answer the second question.

For those who couldn't do straightforward O(n^2) with tricks.
Think of < as 0 and > as 1.
Every time you see >< (10) you replace (swap) it with <> (01).
Which means, you stop as soon as you get sorted stuff, 0*1*.
Doesn't it look like count of swaps in bubblesort? :)

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++...