If you are unfamiliar, I recommend to google binary search trees.

I just rewritten my AC solution in python (it was originally written in Java) and I got Runtime Error on test #7. Any hint on why this happen ? Any test ? It gives me the same results as my Java solution ..

solution found
1
1

Edited by author 16.12.2019 16:48

Edited by author 16.12.2019 16:51

On my machine all work fine, I'll delete code after I get AC. I think I allow wrong input, stackoverflow, more then 3000 number.


Here code
private static void Main(string[] args)
        {
            StringBuilder builder = new StringBuilder();
            int count; //= int.Parse(Console.ReadLine().Trim(' ', '\t', '\n','\r'));
            //if (count == 0)
            //    return;
            List<int> val = new List<int>();
            string text = "";
#if !Test
            while((text = Console.ReadLine()) != "")
            {
                builder.Append(text.Trim());
                //val.AddRange(text.Split(new[] { ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToList());
            }
#else
            Random rand = new Random();
            builder.AppendLine(3000.ToString());
            for (int i = 0; i < 3000; i++)
                builder.AppendLine(rand.Next(0, 65535).ToString());
#endif
            val = builder.ToString().Split(new[] { ' ', '\n', '\t', '\r' }, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToList();
            if (val.Count <= 0 || val[0] <= 0)
                return;
            count = val[0];
            BinnaryTreeNode tree = new BinnaryTreeNode();
            //if (val.Count == 1)
            //{
            //    tree.value = val[0];
            //    for (int i = 0; i < count - 1; i++)
            //    {
            //        tree = CreateTree(int.Parse(Console.ReadLine()), tree);
            //    }
            //}
            //else
            {
                tree.value = val[0];
                for (int i = 1; i < val.Count && i < 3001; i++)
                    tree = CreateTree(val[i], tree);
            }

            RightToLeft(tree);
        }
       static Stack<BinnaryTreeNode> stackNodes = new Stack<BinnaryTreeNode>();
        static Stack<int> values = new Stack<int>();
        static void RightToLeft(BinnaryTreeNode node)
        {
            // stackNodes.Push(node);
            // while(stackNodes.Count > 0)
            // {
            //     var nn = stackNodes.Pop();
            //     if (nn.Right != null)
            //         stackNodes.Push(nn.Right);
            //     if (nn.Left != null)
            //         stackNodes.Push(nn.Left);

            //     values.Push(nn.value);
            // }

            //for (int i = 0; i < values.Count; i++)
            // {
            //     Console.WriteLine(values.Pop());
            // }
            if (node == null)
                return;
            if (node.Right != null)
                RightToLeft(node.Right);
            if (node.Left != null)
                RightToLeft(node.Left);
            Console.WriteLine(node.value);
        }

       static  BinnaryTreeNode CreateTree(int value, BinnaryTreeNode node)
        {
            if (value > node.value)
            {
                var parentNode = new BinnaryTreeNode() { value = value };
                parentNode.Left = node;
                node.Parent = parentNode;
                return parentNode;
            }
            BinnaryTreeNode tempNOde = node;
            while(tempNOde.Left != null)
            {
                if (tempNOde.Left.value < value)
                {
                    var parentNode = new BinnaryTreeNode() { value = value };
                    parentNode.Right = node;
                    parentNode.Left = tempNOde.Left;
                    tempNOde.Left = null;
                    parentNode.Left.Parent = parentNode;
                    parentNode.Right.Parent = parentNode;
                    return parentNode;
                }
                tempNOde = tempNOde.Left;
            }
            return node;

        }

        class BinnaryTreeNode
        {
            public int value;
            public BinnaryTreeNode Left;
            public BinnaryTreeNode Right;
            public BinnaryTreeNode Parent;

            public override string ToString()
            {
                return value.ToString();
            }
        }

Is there any linear solution to this problem? I have implemented an O(NlogN) one.

Let me tell you the  way I've solved it. We just pick our last vertex (number) as a root and try to divide another part into 2 subtrees. In order to do this we find a border between those 2 parts, so that all numbers in the first part are less than our root and vice-versa for second part. The latter can be easily implemented using binary search. And then we just do all the same from the very beginning with both parts recursively. It's obvious that the only time-consuming part is binary search, which takes O(logN) time in the worst case. Therefore the complexity of this algorithm is O(NlogN).

My code:

[code deleted]

Edited by moderator 20.06.2020 16:24

What is the 11th test about?
Two my solutions (on pascal and c++) got wa11 and I really don't know why.

I can't understand what's wrang? I just build BST and make reverse post order..
Maybe there are some troubles with input?
Please help me. [I'll delete code after receiving some feedback]

[Code deleted]

Edited by author 29.11.2012 21:04

WHY?


type hlist=^list;

list=record
    data: longint;
    l,r: hlist;
    end;


var n,i:longint;
    a:array[1..3000] of longint;
    head: hlist;

procedure add(var v:hlist; x:longint);
    begin
    if v=nil then
        begin
        new(v);
        v^.data:=x;
        end
    else if x>v^.data then add(v^.r, x)
                     else add(v^.l, x);
    end;

procedure draw(var v:hlist);
        begin
        if not (v=nil) then
            begin
            draw(v^.r);
            draw(v^.l);
            write(v^.data,' ');
            dispose(v);
            end;
        end;
begin
readln(n);
for i:=n downto 1 do read(a[i]);
for i:=1 to n do add(head, a[i]);
draw(head);
end.

Why am i getting Crash with this solution in Java? Thank you.

public static Vector<Integer> res=new Vector<Integer>();
    public static class Tree{
        public Tree l;
        public Tree r;
        int val;
        Tree(int v){
            this.val=v;
            this.l=null;
            this.r=null;
        }
        public static void add(Tree t,int v){
            if(v<t.val){
                if(t.l==null){
                    t.l=new Tree(v);
                }
                else{
                    add(t.l,v);
                }
            }
            else if(v>t.val){
                if(t.r==null){
                    t.r=new Tree(v);
                }
                else{
                    add(t.r,v);
                }
            }
        }
        public static void rightSearch(Tree t){
            if(t.r!=null)
                rightSearch(t.r);
            if(t.l!=null)
                rightSearch(t.l);
            res.add(t.val);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        int n=Integer.parseInt(in.readLine());
        String[] input=in.readLine().split(" ");
        Tree t=new Tree(Integer.parseInt(input[n-1]));
        for(int i=n-2; i>=0; i--){
            Tree.add(t,Integer.parseInt(input[i]));
        }
        Tree.rightSearch(t);
        for(int i=0; i<res.size(); i++){
            out.print(res.get(i)+" ");
        }
        out.close();
    }

Don't forget that the way to store tree in simple array when (2i)th and (2i+1)th elements are childrens of (i)th element isn't working here because in worst case it costs about 2^n memory to store this array.


Edited by author 27.08.2012 19:28

It's a Binary Search Tree solution :) Just fill the tree with the elements from behind(from root), then run the reverse postorder(right side, left side, root).

It seems to me, that in a problem a wrong example (Sample output).
It should be 25 27 22 10 20 21 5 7 1
Please correct me if I something has not understood.
  thank.

#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <vector>
#include <string>

using namespace std;
int tree[65536][2];
int a[3000], n;
vector<int> b;
string flag[3000];
void insert_tree(int zveno, int znach)
{
    if(zveno>znach)
    {
    if(tree[zveno][0]!=-1)
    {
        zveno=tree[zveno][0];
        insert_tree(zveno, znach);
    }
    else
        tree[zveno][0]=znach;
    }
    else if(zveno<znach)
    {
    if(tree[zveno][1]!=-1)
    {
        zveno=tree[zveno][1];
        insert_tree(zveno, znach);
    }
    else
        tree[zveno][1]=znach;
    }
}

void topological_sort(int k)
{
    flag[k]="GRAY";
    for(int i=1; i>=0; i--)
    {
    int ind=tree[k][i];
    if(flag[ind]=="WHITE")
        topological_sort(ind);
    }
    flag[k]="BLACK";
    b.push_back(k);
}
int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        tree[a[i]-1][0]=-1;
        tree[a[i]-1][1]=-1;
        flag[a[i]-1]="WHITE";
    }
    int zveno=a[n-1]-1;
    for(int i=n-2; i>=0; i--)
    insert_tree(zveno, a[i]-1);
    topological_sort(zveno);
    for(int i=0; i<n; i++)
    cout<<b[i]+1<<" ";
    return 0;
}

Here's my code. It gets WA11.
Algo: the rightmost number of the current subarray[i..j]
 is a root of a subtree. The left branch includes those and only those numbers which are less than root; right branch -
numbers greater than root. So if we swap these branches in our array and process them recursively we'll get the desired answer.

Example:
 1 7 5 (left br.)  21 22 27 25 20 (right br.) 10 (root)

1 (lb) 7 (rb) 5 (rt)
empty (lb) 21 22 27 25 (rb) 20 (rt)
21 22 (lb) 27 (rb) 25 (rt)
21 (lb) empty (rb) 22 (rt)

result:
 27 21 22 25 20 7 1 5 10

proc "tree" does all the work.
del is the delimiter of the branches.
I've used the most primitive algo to swap
the subarrays to simplify the solution.


program parliament;

{$APPTYPE CONSOLE}

var n,i:integer;
    a,t:array[1..100000] of integer;


procedure tree(i,j:integer);
var q,del:integer;
begin
 if j>=i then begin
  del:=j-1;
  while (del>=i) and (a[del]>a[j]) do dec(del);
   for q:=del+1 to j-1 do
    t[q+i-del-1]:=a[q];
   for q:=i to del do
    t[q+j-1-del]:=a[q];
   for q:=i to j-1 do a[q]:=t[q];
   tree(i,j-del-1); tree(j-del,j-1);
 end;
end;


begin

 fillchar(t,sizeof(t),0);
read(n);
 for i:=1 to n do read(a[i]);
 tree(1,n);
 for i:=1 to n do write(a[i],' ');
end.

Identification numbers do not exceed 60000.

There should be at least a number bigger than 60000 in test 11.

they said that the order numbers can't exceed 60.000. i sent my solution and i got access violation on #11. i didn't know what to do, so i set the limits in my source to 600.000. And it was accepted. Isn't this a little strange?

I've solved this problem in C++. But I can't get AC in Java. Some clever guy from america told me that there's a thread checking my program and because it is not using tree, it uses only recursive calls this checking thread also uses stack. And in result this special thread causes stack overflow. He suggested me to use "java -Xint p1136". p1136 is my class. It worked on my computer. But I think on the server there's no one used this option. Am I right? Does it mean that we must use binary tree to solve this problem and no other way for recursive solution?