What an answer for the test:
2
abcde
bcdeh

I think:

2
abcde
bcdeh

Simple algorithm but hard proof?
How to prove that some construction in this problem
is optimal?

When the answer will be 1?

My prog has WA#4

But I do not understend why. Help me!

Give some test

GL ;)

How could i read double without crash?
I use double.Parse(Console.ReadLine());

I thihk that the problem has interesting feature.
Relation in it is tolerance and not an order , therefore
ordered structures:trees,sets,dictionaries unapplicable.

Sorry for poor english...
I think that this code is true (but it's not topsort!):

const
  INF=2000000000;

var
  a : array [1..100] of integer;
  n,i,j,now,k,min : integer;

begin
  read(n);
  for i:=1 to n do
    a[i]:=i;
  for i:=1 to n do begin
    read(k);
    min:=INF;
    while k<>0 do begin
      for j:=1 to n do
        if (a[j]=k) and (min>j) then
          min:=j;
      read(k);
    end;
    if min<>INF then begin
      for j:=1 to n do
        if a[j]=i then
          now:=j;
      if now>min then begin
        for j:=now downto min+1 do
          a[j]:=a[j-1];
        a[min]:=i;
      end;
    end;
  end;
  write(a[1]);
  for i:=2 to n do
    write(' ',a[i]);
end.

May you give me some bad for my algorithm tests? Thanks for your attention.

Edited by author 04.03.2007 00:54

Edited by author 04.03.2007 00:55

I have solved this problem is Java, by now it is the only solution in this not fast language. :-) My solution was rather advanced, real arithmetics only on output, but it used almost all given time 4.75 / 5.00 s.

Then I saw statistics of this problem. There are solutions that work much less than 1s. Is it advantage of fast C++ compiler, is it advantage of hand-written data structures (I used standard PriorityQueue) or is algorithm used much more advanced than mine?

Could anyone explain optimizations of really (<1s) fast solution?

3
aaab
acaa
bcba
What is the answer?

#include <iostream>
using namespace std;
struct node
{
    int item;
    node *l;
    node *r;
    node():item(2),l(0),r(0){};
};
typedef node *link;
int sum;
void buildtree(link a,int k)
{
    int t = a->item;
    if(a->l == NULL)
    {
    a->l = new node;
    a->l->item = t+1;
    if(t+1 == k)sum++;
    if(t+1 > k)return;
    a->l->r = a->l->l = NULL;
    }
    else
        buildtree(a->l,k);
    if(a->r == NULL)
    {
    a->r = new node;
    a->r->item =t*2;
    if(t*2 == k)sum++;
    a->r->l = a->r->r = NULL;
    }
    else
        buildtree(a->r,k);


    buildtree(a->l,k);
    buildtree(a->r,k);
}
int main()
{
    link a = new node;
    int n,p;
    cin >> n >> p;
    buildtree(a,n);
    cout << sum%p;
    return 0;
}

Edited by author 03.03.2007 18:12

it should be 0... am i correct?

9
-100 -100
-100 100
100 -100
100 100
0 -1
1 -1
1 1
-1 1
-1 -1

Answer YES 5 6 7 8 9!

what's the containt of the second test

Edited by author 03.03.2007 17:00

Does all solutions acceptable?

Timelimit for java is 4.0 seconds, like c++. why?

Edited by author 03.03.2007 16:08

I think at least one of them is incorrect.