Whoever made this problem, thanks a lot! Seeing group theory applied in cp felt pretty cool. Alos learnt a lot thanks to this problem

I believe I am having precision errors when calculating the solution.
I changed from doubles to long doubles and got one more test case, so I believe my solution is correct but not precise enough.
Any tips to resolve this?

have no ideas. i've runned my random test generator and my program passed over 1000 tests, but wa.
help, please.

can anybody help me with this problem?

1) Maybe, you are reading long long variable with this command :
  scanf("%d",&arr[i]);
  It is not right. You should do, for example, it with next command
  scanf("%I64d",&arr[i]);
2) Maybe, you were confused by statement. You have to choose such two points so line that passing through this points has maximal absolute value of inclination, not just inclination.
3) Maybe, you are doing something like this :
    for ( int i = 1 ; i <= n ; ++i ) {
      long long d = abs2(arr[i+1] - arr[i]);

       if ( d > x ) {
                 x = d; m1 = i;
       }
   }
There is a mistake in first line. Right way is
   for ( int i = 1 ; i < n ; ++i ) {

It was my biggest mistake, because the problem itself is so simple.

Problem statement says "His friends write numbers from 1 to N on cards", but it doesn't mention that these numbers should be distinct. Yet, it seems like the problem only accepts solutions in which the numbers are distinct (i.e. the numbers on the N cards are a permutation of [1..N]).

If none of your browsers let you run java applets anymore, you can just download the jar:
http://acm.timus.ru/Supplement/CalcEngine/CalcEngineGUI.jar

Then run it as:
java -cp CalcEngineGUI.jar CalcEngineApplet

The cases when all times are less than 6 seconds are neglected. So the cost of each plan should be zero as all calling will be free but adding the basic plan to the cost leads to AC.

puts gets.split(' ').sum { |s| s.to_i }

а вот так ок:
puts gets.split(' ').map { |s| s.to_i }.inject(0) {|sum,x| sum + x }

что не так с с sum?
Edited by author 22.05.2019 11:43

Edited by author 29.05.2019 02:44

?

Any hints for solution? I am completely stuck at TLE.

So, we can decompose like this any connected graph G = (V, E), |E| = 2k, k in Z+? This is lovely, this is nice (I proved it using induction, I'm proud of myself, yay!).

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