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.
Posted: Wed Feb 20, 2008 1:46 am
by serur
Excellent problem, isn't it? One of the best DPs on this site.