I was trying to do the following.
Construct suffix automation for each command.
Binary search for length of each key substring.
Binary search works as follows.
For each substring of command of len (lower_bound+upper_bound) /2 check whether it is a substring of another command.

Check my submissions and learn how evil the problem is!

Use unordered map and unordered set.
max_load_factor(0.25)
reserve (1<<x)

Could someone explain this idea?
tbl[0] = 1;
for (int i = 1; i <= N; i++)
{
    for (int j = N; j >= i ; j--)
    {
            tbl[j] += tbl[j-i];
    }
}
cout<<tbl[N]-1<<endl;

I had a MLE 7 test - I split the tree into 3 parts
And choose the best 3 answers
Accepted 0.593 !!!!

-------------------------
Enough for the division into 2 parts

Edited by author 30.07.2011 10:18

#include <iostream>
#include <vector>
#include <queue>
#define INF (1<<29)
using namespace std;

struct Arista
{
    int hasta,costo;
};

Arista armar(int h,int c)
{
    Arista ar;
    ar.hasta=h;
    ar.costo=c;
    return ar;
}

struct Grafo
{
    int suma=0;

    vector <vector <Arista>> adj;
    vector <int> dist;
    vector <bool> visitado;
    bool encontro=false;

    int nodos,aristas;
    int S,F;

    void leer()
    {
        cin >> nodos >> aristas;
        adj.resize(nodos+1);
        dist.resize(nodos+1,INF);
        visitado.resize(nodos+1,false);

        int desde,hasta,costo;
        for(int c=0; c<aristas; c++)
        {
            cin >> desde >> hasta >> costo;
            adj[desde].push_back(armar(hasta,costo));
        }

        cin >> S >> F;
        dist[S]=0;
    }

    void bdfs(int nodo, int padre)
    {

        visitado[nodo]=true;

        for(int c=0; c<adj[nodo].size(); c++)
        {
            int vecino=adj[nodo][c].hasta;
            int costo=adj[nodo][c].costo;
            if(dist[vecino]>dist[nodo]+costo&&visitado[vecino]==false)
            {
                dist[vecino]=dist[nodo]+costo;
                bdfs(vecino,nodo);
            }
        }
    }


    void start()
    {
        if(dist[F]<INF) cout << dist[F];
        else cout << "No solution";
    }

};

int main()
{
    Grafo g;
    g.leer();
    g.bdfs(g.S,-1);
    g.start();
    cout << endl;
    return 0;
}


BFS+DFS
Some test, guys?

j-1 bit must be 1 if prefix of the string could be cut by j palindroms. in notation 9-->1110 , but 9 must be 10000000, isn`t it???

I was using QUEUE.
It was Memory limit exceed #8 or something similar.
Replaced queue by simple an static array of one million elements.
I was using state struct.
There are three members of unsigned char type.
So,  with C limitations, I got AC with 16 MB.

На руби вообще не имеет смысла что-то решать?

add test x = y; x + y < c; x, y < c
example input: 900000000 900000000 1000000000, i had AC with output 900000000 900000000

When I was using STD::SET and STD::MAP,  it was TLE #18.
When I switched to STD::UNORDERED_SET and STD::UNORDERED_MAP,  it was ACCEPTED 0.6 sec 38 MB.
I was using reserve (1<<16) and max load factor of 0.25.

Hello,
Does anybody know what is the 2nd test? I can't get my head round this issue.

If you want to run your own contest system, you can try my open-source server: http://codejudge.azurewebsites.net
Source code: https://github.com/Backs/judge.net
Work in progress, I'll add new features.
If you want to try it, you can write me, I'll help to install and configure it.

Братаны-кодеры в этой задаче нужен особый подход к считыванию
Из условия неясно,какой формат,но пока что он следущий(.=пробел):
ххх.ххх.ххх и т.д.
ууу.ууу.ууу.ууу и т.д.
Не используйте на Паскале eof,eoln.
Часть моего говнокода:
 ...
 s:string[4];
 ...
 len:=1;
 read(s);
 inc(c[90*90*(ord(s[1])-33)+90*(ord(s[2])-33)+(ord(s[3])-33)]);
 f:=length(s)=4;
 while f do begin
  inc(len);
  read(s);
  inc(c[90*90*(ord(s[1])-33)+90*(ord(s[2])-33)+(ord(s[3])-33)]);
  f:=length(s)=4;
 end;
 ...

C++.  I was using recursive DFS. vector <vector<int> >.   I forgot to pass graph vector by reference and got MLE#8. After noticing that I am passing graph vector by value and simply adding an ampersand before vector name AC 1MB memory used.

Edited by author 03.07.2017 15:43

98000 3334 3334
1
25000 3333
3
1 97999 1
2 30000 1
2 25000 1

Answer - You should rent the apartment #1 alone. or You should rent the apartment #2 alone. or You should rent the apartment #3 alone.

21111 1111 7777
5
1111 7777
10000 6556
20000 3131
80000 2
76400 1
4
1 21110 6000
1 21111 6665
2 21111 1220
2 1110 0

Answer - You should rent the apartment #3 alone.

1001 1001 1001
1
1001 1
1
2 1001 1

Answer - You should rent the apartment #1 alone.

I hope it can help. My program, which got WA 6, failed on this tests.

My AC program gives the wrong answer on the test:
2 1A 1A
1
5 1B 1A 1A 1B 1B
=>0.200000000

but rught answer 0.400000000

I was trying C++ for several hours.  Can't defeat test case No.  7. So,  I gave up and got AC using Python Decimal module just after several minutes I stopped trying C++.  It is bad I think that I don't solved with C++.  Literally no idea why WA#7. I tried rounding and truncation.  The result was always the same.

When time is 02:00:00 Good have power=58 and Evil=60 ((x-40)/(130-40)=7200/36000 => x=58).

In your segment tree you have count of zeros on every segment of vector of length N.
Find k-th non-zero element.  Then zero it.  Update tree.  Output.