11111 - Generalized Matrioshkas

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

fcsc
New poster
Posts: 3
Joined: Wed Mar 01, 2006 4:33 pm

11111 - Generalized Matrioshkas

Post by fcsc » Sun Oct 08, 2006 7:33 pm

Everytime that i read the problem i get more confused, can somebody explain it to me?

Thanks
____________________________
"Free software for a free society"

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun Oct 08, 2006 7:50 pm

as the problem statement is too long,i haven't read the problem statement Completely during the Contest,
consider you have some boxes that some of them are nested in some other boxes , each box should begin with negative number and end with the absolute value of that negative number , the absolute value shows the size of box , and the sum of size of inside boxes should be less than the outside boxes , you are given sequence of the numbers , you should check whether it violates the above rules or not, that's all
Hope it helps
In being unlucky I have the record.

User avatar
Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

Post by Tariq Shahriar » Mon Oct 09, 2006 12:24 pm

To clear more , consider the following input:

Code: Select all

 -10 -8 8 -5 5 10
this is a invalid input; -8 8 -5 5 is surrounded by -10 10 and 8+5=13 sized box cannot be allocated in a 10 sized box. but above input can be validated in this way-

Code: Select all

 -10 -8 -5 5 8 10 
Now it is possible. because, if the 5 sized box is placed in 8 sized box then it allocated in the 10 sized box easily. now see the picture below. fig 1 is for input 1 and fig 2 for input 2.
Image

But i got wa in this problem(?). i used stack of stl and a lot of checks.
i also checked on with this input:

Code: Select all

-9 -7 -2 2 -3 -2 -1 1 2 3 7 9  
-9 -7 -2 2 -3 -1 -2 2 1 3 7  9
-9 -7 -2 2 -3 -1 -2 3 2 1 7  9
-100 -50 -6 6 50	 100
-100 -50 -6 6 45 100  
-10 -5 -2 2 5 -4 -3 3 4 10
-9 -5 -2 2 5 -4 -3 3 4 9
-10 -5 -3 3 -1 1 5 -4 4 10

10
-10 10

-10
my output is:

Code: Select all

:-) Matrioshka!
:-( Try again.
:-( Try again.
:-) Matrioshka!
:-( Try again.
:-) Matrioshka!
:-( Try again.
:-) Matrioshka!
:-( Try again.
:-) Matrioshka!
:-( Try again.
I inputed char wise and escaped the blank lines of the input.

Kindly any body helps me by giving more input.
[ Common thing of every man is that, everyone thinks that he is uncommon ]

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Mon Oct 09, 2006 6:59 pm

I also got WA many times on this problem

It needed many details to solve the problem, and my code fell on these

Code: Select all

-10 -5 3
-10 -5 -3 3 5 10 11
The correct answers are easy to know

Hope it helps

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Mon Oct 09, 2006 10:16 pm

I dont solve this problem, yet. But i think for your input, output should be:

Code: Select all

:-( Try again.
:-( Try again.

User avatar
Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

Post by Tariq Shahriar » Tue Oct 10, 2006 3:53 am

Wei-Ming Chen wrote: and my code fell on these

Code: Select all

-10 -5 3
-10 -5 -3 3 5 10 11
Wei-Ming Chen, i can understand the problem of your code.
you think the line of input as stack. when a positive number(let x) is inputed, then check that-
if(stack_size!=0 && top_of_stack == x ) pop the top num;
else print "try again".

My program generated correct output for your input.
please any one post more input.
[ Common thing of every man is that, everyone thinks that he is uncommon ]

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Tue Oct 10, 2006 8:09 am

input:

Code: Select all

-9 -7 7 -2 2 9
-9 -2 2 -1 1 -6 6 9
-9 -2 2 -1 -5 5 1 9
-9 -2 2 -1 1 -2 5 9
-9 -2 2 -1 1 -1 1 9
Output:

Code: Select all

:-( Try again.
:-( Try again.
:-( Try again.
:-( Try again.
:-) Matrioshka!

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Tue Oct 10, 2006 5:32 pm

Code: Select all

-200 -180 -50 50 -60 60 -69 -50 -40 40 50 -11 11 69 180 200
-3 -1 1 -1 1 3
-3 -1 -1 1 1 3
-50 -20 20 -15 15
-8 7 -7 8
-60 -55 -53 -6 6 -12 12 -40 40 53 55 60 

Code: Select all

:-) Matrioshka!
:-) Matrioshka!
:-( Try again.
:-( Try again.
:-( Try again.
:-( Try again.
Hope it helps.

StanleY Yelnats
New poster
Posts: 12
Joined: Tue Sep 12, 2006 6:54 pm

Post by StanleY Yelnats » Tue Oct 10, 2006 9:41 pm

my o(n) solution using stacks exceeds the time limit,
is there any faster aproach or there is something wrong about my code?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Oct 11, 2006 1:49 am

StanleY Yelnats wrote:my o(n) solution using stacks exceeds the time limit,
is there any faster aproach or there is something wrong about my code?
Something is wrong about your code. My O(n) solution using recursion runs in time, and using stack is always faster than recursion. Probably your code has infinite loop.

User avatar
Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

Post by Tariq Shahriar » Wed Oct 11, 2006 8:31 am

Thanks Wei-Ming Chen.
my code would fail in your this test case -3 -1 -1 1 1 3 for improper checking.

Now ac in 244 millisec.
[ Common thing of every man is that, everyone thinks that he is uncommon ]

StanleY Yelnats
New poster
Posts: 12
Joined: Tue Sep 12, 2006 6:54 pm

Post by StanleY Yelnats » Wed Oct 11, 2006 8:58 am

what's the correct output for this :

Code: Select all

-9 -1 1 9 -9 9

User avatar
Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

Post by Tariq Shahriar » Wed Oct 11, 2006 9:07 am

Obviously

Code: Select all

:-) Matrioshka!
(from my ac code)
[ Common thing of every man is that, everyone thinks that he is uncommon ]

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sun Nov 12, 2006 8:45 am

Hello..~

I don't clearly understand this problem..
Please tell me what the correct output is for this input..

Code: Select all

-10 -8 -5 5 8 10
Thanks.. :D

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Nov 12, 2006 9:30 am

My ac code outputs

Code: Select all

:-) Matrioshka!

Post Reply

Return to “Volume 111 (11100-11199)”