ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1915. Titan Ruins: Reconstruction of Bygones

Maybe an interesting idea to solve this
Posted by DR. Zhihua Lai 28 Oct 2012 03:08
Instead of copying actually data, we might put a marked-number (index to copy) in the array.
For example,

            if (x > 0)
            {
                stack[q ++] = x;
            }
            else
            if (x == -1)
            {
                int y = stack[q - 1];
                if (y > 0)
                {
                    System.out.println(y);
                    q--;
                }
                else
                {
                    y = -y;
                    System.out.println(stack[y]);
                    stack[q - 1] = -(y - 1);
                    if (y == 0)
                    {
                        q--;
                    }
                }
            }
            else
            {
                stack[q] = -(q - 1); // negative numbers mean a copy.
                q ++;
            }

of course, this doesn't work for multiple continuous copy (e.g. 0, 0, 0 ..).
Re: Maybe an interesting idea to solve this
Posted by Bogatyr 29 Oct 2012 17:06
I pursued this idea at first before I noted the easier approach based on the input constraints.   The problem with storing markers representing copies in the stream is that it gets complicated when you have many combinations of partially consumed copies which are then copied, over and over again.  You basically need a tree to represent the state, and the tree must be walked when popping, which takes longer.   There probably is a simplified partial implementation of this, but given the constraints of the problem, it's not necessary.
Re: Maybe an interesting idea to solve this
Posted by DR. Zhihua Lai 14 Nov 2012 15:35
I agree.
It gets complicated when there are copies inside copies.. so, this is not necessary because there are simpler and straightforward solutions.