It is easy to solve this problem by using such recursive formula
(k+1)P_k(N)=(N+1)^(k+1)-1-sum_(l=0)^(k-1) C_(k+1)^l P_l(N),
where
P_k(N) is a sum of powers k from 1 up to N,
C_k^l is a binomial coefficient.
I assume that P_0(N)=N.
You can check this formula by summing up from 1 to N following identities
(n+1)^k-n^k=sum_(l=0)^(k-1) C_k^l n^l.

However, P_k(x) has non-integer coefficients, so it is better to introduce polynomials Q_k(x) by formula Q_k(x)=(k+1)!P_k(x). It can be proven by induction based on recursive formula above that Q(x) has integer coefficients!!! So, use BigIntegers in Java, otherwise you would have overflow. Good luck!

Edited by author 08.05.2017 19:44

Edited by author 08.05.2017 19:44

n^3 is suitable for which n<=200
but pay attention to the collinear problem

Edited by author 17.05.2019 14:43

Remove this comment it contains solution to the problem via z-function.
http://acm.timus.ru/forum/thread.aspx?id=41561&upd=636936488140008501

#include <stdio.h>
int main(){
    int n;
    scanf("%d", &n);
    if (n == 2) {
        printf("10");
        return 0;
    }
    if (n == 4) {
        printf("670");
        return 0;
    }
    if (n == 6) {
        printf("55252");
        return 0;
    }
    printf("4816030");
    return 0;
}

I thought my solution is quite "brute", are there any other solutions?
And I have to say it is a really good problem for sufficient samples and a clear statement.

I cant ivent any tests that my solution will fail, but I have WA1!
Can any body help...
Give me some test!
Plz...

8
AA
BB
CC
DD
EE
FF
GG
HH
6
AA HIT BB IN HEAD
AA HIT CC IN HEAD
AA HIT DD IN HEAD
AA REVIVE BB
AA REVIVE CC
EE REVIVE DD

CORRECT
AA BB CC FF
DD EE GG HH

100000000
10
1 5 even
6 10 even
11 18 even
19 25 even
1 8 even
16 25 even
16 40 even
9 40 odd
1000 5000 odd
1000 6000 odd
-1

answer: 7

I had runtime error 25, but when i surrounded sorting with try catch it accepted
Any ideas why?

#solution 1068
x=int(input("enter your number:  "))
def factorial(x):
    if x>0:
        return x + factorial(x - 1)
    elif x<0:
        return x + factorial(x+1)
    if x==0:
        return 0
y=factorial(x)
if x<0:
    print(y+1)
else:
    print(y)

n = int(input())
if n > 0:
    print(int(n*(n+1)/2))
elif n == 0:
    print('1')
else:
    print(int(n*(n-1)/-2 + 1))

delete

Edited by author 04.10.2020 16:38

What's wrong with test #38? I got AC with sorting but failed on majority search?

input :
15 4
1 2 30 994 50 600 700 999 900 990 991 992 993 40 800
output :
   1  50 900 993
   2 600 990  40
  30 700 991 800
 994 999 992

If you have WA4, try a 100x100 matrix with all 1 or with all 0.

Edited by author 12.05.2019 20:53

wa18 ...please

import java.util.Scanner;


public class task9 {


    public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int n = sc.nextInt();
          int m = sc.nextInt();
          int x = sc.nextInt();
          int y = sc.nextInt();
          int cl = 0;
          int stroka =1;
          int[][] mas = new int[n][m];
         for(int i=0;i<n;i++){
             if(stroka%2==1){
                 for(int j=0;j<m;j++){
                 mas[i][j]=cl;
                 cl++;

                 }
                 stroka++;
             }
             else{
                 for(int j=m-1;j>=0;j--){
                 mas[i][j]=cl;
                 cl++;
                 }
                 stroka++;
             }
         }
        System.out.println(mas[x-1][y-1]);

            }


}

The problem is to find how many l*1 or 1*l while rectangles that do not *included* by each others.

My solution is O(NlogN),but I thought there may be some solutions use only O(N) time, thank you for your sharing!