11166 - Power Signs

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

Post Reply
jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

11166 - Power Signs

Post by jan_holmes » Sat Feb 17, 2007 8:54 pm

Is this problem related to BigInteger (because the input can be as large as 2^5000) ?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Feb 17, 2007 9:03 pm

There's a dynamic programming solution, which doesn't need bignums. State is the index of current digit and carry from the previous digit.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sat Feb 17, 2007 9:06 pm

Thx for your quick reply. I'll try to think about it.

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Sun Feb 18, 2007 10:25 am

There is a greedy approach also.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Feb 18, 2007 6:25 pm

There is a greedy approach also
Can you explain a bit about greedy method you used to solve the problem ?

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Sun Feb 18, 2007 6:41 pm

replace consecutive 1's with +000..000- pattern from right to left except for the leftmost 11
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Post by pvncad » Mon Feb 19, 2007 8:59 am

I used same logic but got WA.

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Mon Feb 19, 2007 10:14 am

Try creating bruteforce solution for small inputs and test your greedy approach on it. You will find where's your mistake.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Post by pvncad » Tue Feb 20, 2007 7:55 am

I got it. There was a bug in the code which I fixed and got AC

Thanks

sm_hosein
New poster
Posts: 3
Joined: Sat Oct 28, 2006 11:39 am
Contact:

Some Cases

Post by sm_hosein » Sat Mar 10, 2007 1:51 pm

Can anyone tells me this samples answer :

11101110111
1101101100
1010110101
11010101011
11111101111110111111

I got WA and my code's answer is :

+000-000-00-
+00-00-0-00
+0++0-0+0+
+00-0-0-0-0-
+000000-000000-00000-

If it's not true what is the true answer? And if it's true can anyone give me some other testcases?

pvncad
New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm

Post by pvncad » Sat Mar 10, 2007 3:50 pm

correct output is

Code: Select all

+000-000-00-
+00-00-0-00
++0-0-0+0+
+00-0-0-0-0-
+000000-000000-00000-
Eventhough, ++0-0-0+0+ and +0++0-0+0+ has same number of zeros but former is
lexicographically smallest.

-pvncad

eduardojmc
New poster
Posts: 3
Joined: Wed Apr 19, 2006 11:20 pm

WA aaaaaaah...

Post by eduardojmc » Mon Mar 19, 2007 7:40 pm

anyone can post some input/output?
I ve tried creating a program with brute force aproach test my heuristc, but it returns the same results.
I tried a greedy aproach, and it outputs the correct results for the sample input and for the one pvncad posted.
thx in advance

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Re: WA aaaaaaah...

Post by hank » Sat Apr 07, 2007 6:36 am

eduardojmc wrote:anyone can post some input/output?
I ve tried creating a program with brute force aproach test my heuristc, but it returns the same results.
I tried a greedy aproach, and it outputs the correct results for the sample input and for the one pvncad posted.
thx in advance
Hello,

Here are some testdata ,

Input

Code: Select all

1
10
11
100
111
1001
1111111
10101010000111111
1110101110101001111
11111111111110
1101010101010111111111
1100000001100010000000010110
101010101010101010101010101010
100000000000000000000000
1100000000000110000000000
111110111100111111000111111
110000000000110000000000000
0
Output is

Code: Select all

+
+0
++
+00
+00-
+00+
+000000-
+0+0+0+000+00000-
+000-0-00-0+0+0+000-
+000000000000-0
+00-0-0-0-0-0-00000000-
++000000+0-000+0000000+0-0-0
+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0
+00000000000000000000000
++0000000000+0-0000000000
+00000-000-0+00000-00+00000-
++000000000+0-0000000000000

marthapfhui
New poster
Posts: 7
Joined: Sat Mar 10, 2007 7:03 pm

Post by marthapfhui » Fri May 18, 2007 2:00 am

I think I am using the Greedy approach as described above. However, I got WAs.

Any tricky input or traps I am missing? Thanks.

Code: Select all

accepted

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Wed Feb 20, 2008 1:46 am

Excellent problem, isn't it? One of the best DPs on this site.

Post Reply

Return to “Volume 111 (11100-11199)”