11166 - Power Signs

Moderator: Board moderators

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

11166 - Power Signs

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:
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:

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
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:
There is a greedy approach also
Can you explain a bit about greedy method you used to solve the problem ?

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
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

New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm
I used same logic but got WA.

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
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

New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm
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

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?

New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 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.

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

WA aaaaaaah...

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.

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

Re: WA aaaaaaah...

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.
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
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
Excellent problem, isn't it? One of the best DPs on this site.