Page 1 of 1

11166 - Power Signs

Posted: Sat Feb 17, 2007 8:54 pm
by jan_holmes
Is this problem related to BigInteger (because the input can be as large as 2^5000) ?

Posted: Sat Feb 17, 2007 9:03 pm
by mf
There's a dynamic programming solution, which doesn't need bignums. State is the index of current digit and carry from the previous digit.

Posted: Sat Feb 17, 2007 9:06 pm
by jan_holmes
Thx for your quick reply. I'll try to think about it.

Posted: Sun Feb 18, 2007 10:25 am
by fh
There is a greedy approach also.

Posted: Sun Feb 18, 2007 6:25 pm
by jan_holmes
There is a greedy approach also
Can you explain a bit about greedy method you used to solve the problem ?

Posted: Sun Feb 18, 2007 6:41 pm
by fh
replace consecutive 1's with +000..000- pattern from right to left except for the leftmost 11

Posted: Mon Feb 19, 2007 8:59 am
by pvncad
I used same logic but got WA.

Posted: Mon Feb 19, 2007 10:14 am
by fh
Try creating bruteforce solution for small inputs and test your greedy approach on it. You will find where's your mistake.

Posted: Tue Feb 20, 2007 7:55 am
by pvncad
I got it. There was a bug in the code which I fixed and got AC

Thanks

Some Cases

Posted: Sat Mar 10, 2007 1:51 pm
by sm_hosein
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?

Posted: Sat Mar 10, 2007 3:50 pm
by pvncad
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

WA aaaaaaah...

Posted: Mon Mar 19, 2007 7:40 pm
by eduardojmc
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

Re: WA aaaaaaah...

Posted: Sat Apr 07, 2007 6:36 am
by hank
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

Posted: Fri May 18, 2007 2:00 am
by marthapfhui
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

Posted: Wed Feb 20, 2008 1:46 am
by serur
Excellent problem, isn't it? One of the best DPs on this site.