You are not logged in. Please login at www.codechef.com to post your questions!

×

string Question - help

You are given a number (in the form of a string) and an integer k. You have to output the maximum palindromic number that can be formed from the given number and by using at most k changes to the number (replacing digits is the only allowed operations). Output -1 if it is not possible to get a palindrome. any one have solution?

asked 26 Jun '18, 11:29

sna902055's gravatar image

5★sna902055
425
accept rate: 7%

edited 15 Oct '18, 21:48


Ok i see i cant test. Anyways my logic is:
First check out how many positions and which we need to change to make it palindrome. Lets say x positions are needed (consider only one half, we are going to make it equal to the other half.) . Now we have k-x extra changes left. First change those positions where change is needed i.e say at i, s[i]!=s[n-i]. So do s[i]=max(s[i],s[n-i]). Run a greedy algorithm from first position (do everything in first half) . If current position doesnt need a change we see if we can make it larger i.e digit here is not 9. If yes, we will need 2 extra changes if we want to change here. Now suppose pos was a position of change. So we need 1 extra change for this position to make it larger.

link

answered 26 Jun '18, 11:53

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 22%

i understood your logic..thank you.. but one question is how to calculate value of x efficiently?

(26 Jun '18, 11:59) sna9020555★

Its very simple.Just run a loop. while(i<n-i){ if(s[i]!=s[n-i]) x++;}

(26 Jun '18, 12:00) soham12346★

Yes this is what I thought but why is it tagged under DP?

(27 Jun '18, 01:18) sorb19974★

Beats me. Dp would make more sense if adding/deleting characters was allowed.

(27 Jun '18, 01:39) vijju123 ♦♦4★

Can you provide a link? I don't think dp is needed in this problem. But I would like to check if my logic is correct.

link

answered 26 Jun '18, 11:36

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 22%

what is solution , if they ask for swap not for change ??

link

answered 26 Jun '18, 13:36

abba5's gravatar image

5★abba5
1133
accept rate: 0%

can you explain in detail. Minimum swaps to form the string palindrome or minimum swaps to make it largest palindrome?

(26 Jun '18, 13:40) soham12346★

swap to get max palindromic number ex.

s=111221 k=2 ans = 211112

but if k=1

ans = 112211

(26 Jun '18, 13:52) abba55★

I guess same greedyish solution works here too. First lets focus to make it palindromic.Start from max element. Let it's occurence be at i in first half and j in second. See where you want to fix it i.e whether i and n-i or n-j and j. Note that however you fix it number of swaps remains same(think of it as inversion count problem.) Now we have some more swaps left again start from max element and swap it rightwards. A few more bookkeepings will be needed i guess but something similar will work

(26 Jun '18, 14:20) soham12346★

I didn't understand your logic..Can you explain your logic through one example? Thanks in advance...

(26 Jun '18, 16:08) sna9020555★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,167
×349
×4

question asked: 26 Jun '18, 11:29

question was seen: 386 times

last updated: 15 Oct '18, 21:48