11166 - Power Signs

[jan_holmes]

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

[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.

[jan_holmes]

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

[fh]

There is a greedy approach also.

[jan_holmes]

There is a greedy approach also

Can you explain a bit about greedy method you used to solve the problem ?

[fh]

replace consecutive 1's with +000..000- pattern from right to left except for the leftmost 11

[pvncad]

I used same logic but got WA.

[fh]

Try creating bruteforce solution for small inputs and test your greedy approach on it. You will find where's your mistake.

[pvncad]

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

Thanks

[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?

[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

[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

[hank]

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]

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]

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