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

Set answer as (2+n).
Then n times repeat answer+="+one"in set(input()).
"+" in set(input ())  is also enough.

Create three dictionaries :
    used <boolean>
    connections <set<string>>
    distance <string>

Then import queue.
Then breadth - first search.

If a=1 then what?
For example
2
1 10
1 20

Who got AC, please, send your code to 'my_trashbox@mail.ru'

1.Use a DP with the O(30N) time
2.Use ternary (long long in C++ is needed) to indicate each solution
3.Use a rolling array in case it MLEs

Good luck! ~_~

Edited by author 05.07.2011 19:05

I have WA 7 and I don't understand what the problem is.
My tests:
// check(<input string #1>, <input string #2> as integer, <output string>)

      // tests from acm.timus
      check("10.23", 0, "10")
      check(".04", 1, "0.0")
      check("-0.051e0", 1, "0.0")
      check("1.1e30", 10, "1100000000000000000000000000000.0000000000")
      check("-1.1e-30", 1, "0.0")
      check("2468097632.1358642324268913e-2", 20, "24680976.32135864232426891300")
      check("e23", 3, "Not a floating point number")
      check("1 e3", 1, "Not a floating point number")

      // my tests
      check(" 1 e3", 1, "Not a floating point number")
      check("1e3", 1, "1000.0")
      // http://acm.timus.ru/forum/thread.aspx?id=26503&upd=634425663233423296
      // Posted by Igor Dex 1 Jun 2011 18:28
      // It is clear that we can't have leading spaces in case correct real number. But is it possible to have spaces after correct number till the end of the string?
      // Posted by AterLux 1 Jun 2011 23:05
      // No. Trailing as leading spaces not satisfy the syntactical description.
      check("   ", 1, "Not a floating point number")
      check(" ", 1, "Not a floating point number")
      check("-", 1, "Not a floating point number")
      check(" 1e3", 1, "Not a floating point number")
      check(" .1e3", 1, "Not a floating point number")
      check(".1e-3", 1, "0.0")
      check(" .1e-3 ", 1, "Not a floating point number")
      check(".1e-3 ", 1, "Not a floating point number")
      check(".0e-10000000000000000000", 1, "0.0")
      check(".0e+10000000000000000000", 1, "0.0")

      // int and uint tests
      check("10", 0, "10")
      check("10", 1, "10.0")
      check("-10", 1, "-10.0")
      check("+10", 1, "10.0")
      // simplefloat and usimplefloat tests
      check(".10", 1, "0.1")
      check("10.10", 1, "10.1")
      check("10.01", 1, "10.0")
      check("+.10", 1, "0.1")
      check("+10.10", 1, "10.1")
      check("+10.01", 1, "10.0")
      check("-.10", 1, "-0.1")
      check("-10.10", 1, "-10.1")
      check("-10.01", 1, "-10.0")
      // float tests
      check("10e0", 0, "10")
      check("10e-1", 1, "1.0")
      check("-10e+1", 1, "-100.0")
      check("+10e+3", 1, "10000.0")
      check(".10e-3", 1, "0.0")
      check("10.10e-1", 1, "1.0")
      check("10.01e-2", 1, "0.1")
      check("+.10e-10000", 1, "0.0")
      check("+10.10e-100", 1, "0.0")
      check("+10.01e1", 1, "100.1")
      check("-.10e1", 1, "-1.0")
      check("-10.10e-1", 1, "-1.0")
      check("-10.01e-2", 1, "-0.1")
      // "Not a floating point number" tests

      // But see http://acm.timus.ru/forum/thread.aspx?id=10235&upd=632909844439020000
      // Posted by Kopeliovitch Sergey (1) 30 Jul 2004 21:29
      // Segey say his progamm have AC with other answers, but right answers are
//Update: Now Segey have WA #1 and WA #12 and didn't have AC.
      check("10.", 1, "Not a floating point number")
      check("10.0e", 1, "Not a floating point number")
      check("10.e", 1, "Not a floating point number")

      //
      check("1E1 1", 1, "Not a floating point number")
      check("-+3", 1, "Not a floating point number")
      check("+", 1, "Not a floating point number")
      check("-", 1, "Not a floating point number")
      check(" ", 1, "Not a floating point number")
      check("-10.01ee", 1, "Not a floating point number")
      check("12.e10", 1, "Not a floating point number")
      check("-.e10", 1, "Not a floating point number")
      check("1e", 1, "Not a floating point number")
      check("e1", 1, "Not a floating point number")
      check("e", 1, "Not a floating point number")
      check("se-1", 1, "Not a floating point number")
      check("+e", 1, "Not a floating point number")
      check("-e1", 1, "Not a floating point number")
      check(".e4", 1, "Not a floating point number")
      check("0.", 1, "Not a floating point number")
      check("1e", 1, "Not a floating point number")
      check("0x123", 1, "Not a floating point number")
      check("1E2.1", 1, "Not a floating point number")
      check("-1E2.1", 1, "Not a floating point number")
      check("1E2.1e2", 1, "Not a floating point number")
      check("1e00-1", 0, "Not a floating point number")
      // # tests
      check("1#", 1, "Not a floating point number")
      check("#1", 1, "Not a floating point number")
      check("# 1", 1, "Not a floating point number")
      check("1 #", 1, "Not a floating point number")
      // big power test
      check("1e10", 1, "10000000000.0")
      check("1e10", 0, "10000000000")
      check("-1e10", 0, "-10000000000")
      check("1e-10", 0, "0")
      check("0e+10", 0, "0")
      check("0e+100", 0, "0")
      check("0e+10000000000000000000", 0, "0")
      check("0e-10000000000000000000", 0, "0")
      check("0e10000000000000000000", 0, "0")
      check("1e000000000000000000000000000000000000000000000000000000000000000000000000000000", 0, "1")
      check("1e000000000000000000000000000000000000000000000000000000000000000000000000000001", 0, "10")
      check("1e-000000000000000000000000000000000000000000000000000000000000000000000000000001", 0, "0")
      check("234565432452433e-10000000000000000000", 0, "0")
      check("-234565432452433e-10000000000000000000", 0, "0")

      // An integral part of a number should be non-empty.
      check(".1e+0", 1, "0.1")
      check("-.1e+0", 1, "-0.1")
      // There shouldn't be leading zeroes in a non-zero integral part of a number.
      // A zero integral part of a number should consist of an only zero.
      check("00000.1e+0", 1, "0.1")
      check("-00000.1e+0", 1, "-0.1")
      check("00001.1e+0", 1, "1.1")
      check("-00001.1e+0", 1, "-1.1")
      check("00001.1", 1, "1.1")
      check("-00001.1", 1, "-1.1")
      check("00001.1", 0, "1")
      check("-00001.1", 0, "-1")
      // A fractional part of a number should contain exactly N symbols.
      check("00001.1", 0, "1")
      check("00001.1", 3, "1.100")
      check("-00001.1", 1, "-1.1")
      // There shouldn't be a sign "+" before a positive number.
      check("+00001.1", 0, "1")
      check("+1.1", 0, "1")
      check("+1.1", 3, "1.100")
      check("+1.1e+1", 1, "11.0")
      // You shouldn't round off a number.
      check("+1.5e+1", 1, "15.0")
      check("+1.06", 1, "1.0")
      check("+1.6e-1", 1, "0.1")

Edited by author 29.03.2017 22:42

Edited by author 29.03.2017 22:47

Edited by author 30.03.2017 00:56

New anti-hash test was added. 141 author lost AC.

-------------------------
10 7
2 3 1 3 4 1 6 1 2 5
3 4 0
1 0
0
3 0
1 4 0
4 5 0
8 0
0
8 0
7 9 0
1
0
2 4 5 10 0

My AC answer:
18
3
4
8
1
2
5
7
9
10
-------------------------
5 7
1 1 1 1 1
2 0
3 0
4 0
5 0
1 0
1
0
1 2 0

My AC answer: No Solution

Good luck!

please give me some hints how to solve the problem fast

use unordered_map instead of map

int main(int argc,char *argv[]){
    //freopen("data.txt","r",stdin);
    int n,i,key = 0,count = 0;
    char p[105],input[105];
    scanf("%d",&n);
    getchar();
    for(i = 0; i < n; i++){
        scanf("%c",&input[i]);
        getchar();
    }
    input[i] = '\0';
    strcpy(p,input);
    while(next_permutation(p,p+n)){
        if(strcmp(p,input) == 0){
            break;
        }
        else {
            count++;
            if(count >= 5){
                printf("Yes\n");
                return 0;
            }
        }
    }
    if(count >= 5){
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
}