PALNUM - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Soumyadeep Pal
Tester & Editorialist: Aman Dwivedi

DIFFICULTY:

Easy Medium

PREREQUISITES:

Strings, Palindromes, Graphs, Floyd-Warshal

PROBLEM:

You are given a string S consisting of N digits from 0 to 9. You want to obtain a palindrome from S using some operations.

There are M different types of operations you can make on S. Each operation is described by three integers X, Y and W. In this operation, if there is a digit equal to X in S, you can replace X with Y using W coins.

You can do the operations in any order. One type of operation can be done multiple times. You can use at most K coins total in all operations. Among all the palindromes that can be obtained from S, output the lexicographically maximum palindrome.

EXPLANATION:

Let’s say S is the given string and P is the palindromic string that we are looking for. Assume that the i_{th} digit of both the strings are different. Do we care about the type of operations or number of operations that we took to convert S_i into P_i?

No, we don’t. The only thing that matters for us is the number of coins that were required to convert S_i into P_i. Hence, we now need to find out the minimum number of coins that will be required to convert S_i digit into P_i. How can we do that?

Let us try to build a directed graph from the given operations:

What are the nodes of this graph?

Every digit from 0 to 9 represents a node of the graph.

What are the edges of this graph?

We are given operations as X, Y and W, hence we will have a directed edge from X to Y with a cost of W.

Now, we can use Floyd-Warshal Algorithm in this graph to find out the minimum coins that are needed to covert every digit into every other (i.e. we obtain the cost for every possible conversion {(x \to y)\forall (x \in [0, 9], y \in [0, 9])}, where the x represents the initial digit, and y represents the digit it is converted to).

Now, let’s move towards the other part of the problem and introduce K in our approach. Due to the limit of K we need to find first whether there exists any palindromic string that can be formed by no more than K coins. For that, we can try to find out the minimum cost palindromic string.

Recall that for the string to be a palindrome, it’s (i)_{th} and (n-i-1)_{th} digit should be the same. As we are looking to find out the minimum cost palindromic string, then we will try to find the minimum cost that will be required to make (i)_{th} and (n-i-1)_{th} digit same. To do so we can try to convert (i)_{th} and (n-i-1)_{th} digit to every possible digit and whichever gives us the minimum cost we will add that cost to our running cost.

Finally, we would be able to find the minimum cost palindromic string. If the minimum cost is greater than K then it won’t be possible to get any palindromic string and hence we can simply output -1.

Otherwise, we will try to find the lexicographically largest palindromic string possible with the given cost of K. We can go greedy to find out the same.

Suppose we are at the i_{th} digit, to make the palindromic string lexicographically largest, we will try to make this i_{th} digit as large as possible. Remember (i)_{th} and (n-i-1)_{th} digit should be same, we can covert (i)_{th} and (n-i-1)_{th} digit to digit d if and only if the coins left out after converting are enough to make substring [i+1, n-(i+1)-1] palindromic.

Finally, we get the lexicographically largest palindromic string by using at most K coins. Well, don’t forget to make the middle character as large as possible if the length is odd and you still have some coins left in your pocket.

Here is how we can efficiently find the minimum cost to make substring [i, n-i-1] palindromic:
Recall that we have already calculated the minimum cost to make (i)_{th} and (n-i-1)_{th} digit same. Let us store that in an array and find the suffix sum of this array, then our suff[i] denotes the minimum cost to make substring [i, n-i-1] palindromic.

TIME COMPLEXITY:

O(N.d) per test case where d is the number of digits.

SOLUTIONS:

Setter
#include<bits/stdc++.h>
using namespace std;
template <class T> ostream &operator << (ostream &os, const vector<T> &p) { os << "["; for (auto&it : p) os << it << " "; return os << "]";}
template <class S, class T> ostream &operator << (ostream &os, const pair<S, T> &p) { return os << "(" << p.first << "," << p.second << ")";}
#ifndef ONLINE_JUDGE
#define deb(...) dbs(#__VA_ARGS__,__VA_ARGS__)
template <class T> void dbs(string str, T t) { cerr << str << ":" << t << "\n";}
template<class T, class...S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << ":" << t << ","; dbs(str.substr(idx + 1), s...);}
#else
#define deb(...){}
#endif
#define int long long
const int INF = (int)(1e12);
void solve(int tc) {
	int n, m, k;
	cin >> n >> m >> k;
	assert(n >= 1 && n <= 100000 && m >= 0 && m <= 90 && k >= 0 && k <= 1000000000);
	string s;
	cin >> s;
	assert((int)(s.size()) == n);
	for (int i = 0; i < n; i++) {
		int x = s[i] - '0';
		assert(x >= 0 && x < 10);
	}
	vector<vector<int>> dis(10, vector<int>(10, INF));
	for (int i = 0; i < m; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		assert(x != y && x >= 0 && x < 10 && y >= 0 && y < 10 && w >= 1 && w <= 1000000000);
		dis[x][y] = w;
	}
	for (int i = 0; i < 10; i++) dis[i][i] = 0;
	for (int k = 0; k < 10; k++) {
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	vector<int> suf(n / 2 + 1);
	for (int i = n / 2 - 1; i >= 0; i--) {
		int x = s[i] - '0', y = s[n - 1 - i] - '0';
		assert(x >= 0 && x < 10 && y >= 0 && y < 10);
		int mn = 2e9;
		for (int d = 9; d >= 0; d--) {
			int cost = dis[x][d] + dis[y][d];
			mn = min(mn, cost);
		}
		suf[i] = mn + suf[i + 1];
	}
	deb(suf[0]);
	if (suf[0] > k) {
		cout << "-1\n";
		return;
	}
	assert(k >= suf[0]);
	string ans1, ans2;
	int used = 0;
	for (int i = 0; i < n / 2; i++) {
		int x = s[i] - '0', y = s[n - 1 - i] - '0';
		assert(x >= 0 && x < 10 && y >= 0 && y < 10);
		for (int d = 9; d >= 0; d--) {
			int cost = dis[x][d] + dis[y][d];
			if (cost + used + suf[i + 1] <= k) {
				ans1.push_back('0' + d);
				ans2.push_back('0' + d);
				used += cost;
				break;
			}
		}
	}
	assert(used <= k);
	assert((int)(ans1.size()) == (int)(ans2.size()));
	if (n % 2 == 1) {
		int x = s[n / 2] - '0';
		for (int d = 9; d >= 0; d--) {
			if (used + dis[x][d] <= k) {
				assert(used + dis[x][d] <= k);
				ans1.push_back('0' + d);
				break;
			}
		}
		assert(n % 2 == 1);
		assert((int)(ans1.size()) > (int)(ans2.size()));
	}
	reverse(ans2.begin(), ans2.end());
	string ans = ans1 + ans2;
	assert((int)(ans.size()) == n);
	cout << ans << '\n';
	// cout << tc << ' ' << n << ' ' << k << '\n';
}
signed main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;
	cin >> t;
	for (int i = 1; i <= t; i++) solve(i);
	return 0;
}
Tester
#include<bits/stdc++.h>
using namespace std;

#define int long long

long long readInt(long long l, long long r, char endd) {
  long long x = 0;
  int cnt = 0;
  int fi = -1;
  bool is_neg = false;
  while (true) {
    char g = getchar();
    if (g == '-') {
      assert(fi == -1);
      is_neg = true;
      continue;
    }
    if ('0' <= g && g <= '9') {
      x *= 10;
      x += g - '0';
      if (cnt == 0) {
        fi = g - '0';
      }
      cnt++;
      assert(fi != 0 || cnt == 1);
      assert(fi != 0 || is_neg == false);

      assert(!(cnt > 19 || ( cnt == 19 && fi > 1) ));
    } else if (g == endd) {
      if (is_neg) {
        x = -x;
      }
      assert(l <= x && x <= r);
      return x;
    } else {
      assert(false);
    }
  }
}
string readString(int l, int r, char endd) {
  string ret = "";
  int cnt = 0;
  while (true) {
    char g = getchar();
    assert(g != -1);
    if (g == endd) {
      break;
    }
    cnt++;
    ret += g;
  }
  assert(l <= cnt && cnt <= r);
  return ret;
}
long long readIntSp(long long l, long long r) {
  return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
  return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
  return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
  return readString(l, r, ' ');
}

const int mxN=1e14+5;
int sum_n=0;

void solve()
{
  int n,m,k;
  n = readIntSp(1,100000);
  m = readIntSp(0,90);
  k = readIntLn(0,1000'000'000);

  int cost[10][10];

  for(int i=0;i<10;i++)
  {
    for(int j=0;j<10;j++)
    {
      if(i==j)
        cost[i][j] = 0;
      else
        cost[i][j] = mxN;
    }
  }

  sum_n+=n;

  string s;
  s = readStringLn(n,n);

  for(int i=0;i<n;i++)
    assert(s[i]>='0' && s[i]<='9');

  while(m--)
  {
    int x,y,w;
    x = readIntSp(0,9);
    y = readIntSp(0,9);
    w = readIntLn(0,1000'000'000);

    assert(x!=y);

    cost[x][y] = w;
  }

  for(int x=0;x<10;x++)
  {
    for(int i=0;i<10;i++)
    {
      for(int j=0;j<10;j++)
        cost[i][j] = min(cost[i][j], cost[i][x]+cost[x][j]);
    }
  }

  // when length is 1
  int pref[n/2+1];
  memset(pref,0,sizeof(pref));

  int tot_cost = 0;

  for(int i=0;i<n/2;i++)
  {
    int x = s[i] - '0';
    int y = s[n-i-1] - '0';
    int val = mxN;

    for(int d=0;d<10;d++)
      val = min(val,cost[x][d]+cost[y][d]);

    tot_cost += val;

    if(i==0)
      pref[i] = val;
    else
      pref[i] = val + pref[i-1];
  }

  if(tot_cost>k)
  {
    cout<<-1<<"\n";
    return;
  }

  int runn_cost = 0;

  string ans = "";

  for(int i=0;i<n/2;i++)
  {
    int x = s[i]-'0';
    int y = s[n-1-i] - '0';

    for(int d=9;d>=0;d--)
    {
      int temp_cost = cost[x][d] + cost[y][d];

      if(runn_cost + temp_cost + (tot_cost-pref[i]) <= k)
      {
        ans+=char(d+'0');
        runn_cost += temp_cost;
        break;
      }
    }
  }

  string rev_ans = ans;
  reverse(rev_ans.begin(),rev_ans.end());

  string mid = "";

  if(n%2!=0)
  {
    int x = s[n/2] - '0';
    for(int d=9;d>=0;d--)
    {
      if(runn_cost + cost[x][d] <=k)
      {
        mid+= char(d+'0');
        break;
      }
    }
  }

  cout<<ans+mid+rev_ans<<endl;
} 

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);

  int t;
  t=readIntLn(1,1000);

  while(t--)
    solve();

  assert(sum_n<=1000000);
  assert(getchar() == EOF);

return 0;
}
2 Likes

Great !! This was what I was doing for whole contest.

code

If you can tell where it is wrong. Trust me, code is pretty neat.

Thanks. @soumyadeep_21

1 Like

On the 48 th line - dp[k][j] != INT_MAX
I think dp[j][k] != INT_MAX should be perfect
Also there are some more problems such as you need to store the cost to make the S[(i+1)…(n-i-1)] palindrome in an array . After that start traversing from index i= 0 to n/2, at each step check what maximum digit you can place.

Go through the editorial . It is written pretty well. Also you can refer the video editorial on Codechef channel.

1 Like

I have also done the same thing here

1 Like

Using Dijkstra: Solution: 48972173 | CodeChef

here – Accepted.

Thanks for guiding, the issue was that I was constructing the minimal cost palindrome, and then going for lexicographically maximum, the point being if final result is s[i] → s2[i], then getting it from s[i] → s1[i] (minimal cost) → s2[i] lexicographically maximum wont yield proper result.

Decent problem for Div3, but I think we should be moving away from Floyd’s algorithm. I see it being overused in beginner oriented contests. It’s okay to repeat algorithm with new ideas, but this is about as creative as Floyd’s algorithm gets, the hardest part of the problem is implementing algorithm. I’d rather have a construction problem or some kind of observation-based problem than a shortest path one with small constraints.

Problems using Floyd’s are usually designed to allow the use of Floyd’s algorithm, when it should be the other way around. It feels like those segment tree problems. How do you make an easy problem tougher for beginners? Throw a segment tree in. It’s not fun and it does not teach most participants to think, it just tells you to straight up write an algorithm/data structure.

One way this could be escaped is by using Dijkstra’s algorithm instead of Floyd’s as it is much more flexible and allows for thinking outside the box. Here’s an example of such a problem: E - Sneaking

This could have easily been another Floyd’s algorithm problem, where you just bruteforce all the possible midpoints, but instead the given constraints force us to come up with a smarter approach - in this case create a temporary node which we can enter when moving upwards, so that we reduce number of edges from N^3 to N^2 and thus pass the tests easily. Is this a trivial problem? Most definitely not, yet it uses a popular minimum path algorithm.

This is just my feedback to the problem authors to help improve the future problems, take it as a critic. This was by no means a bad problem, for this type of contest and I personally enjoyed it. :slight_smile:

5 Likes

after making the minimum cost palindromic string , we are updating i and n-i-1 if possible with the remaining number of coins ,
but why the sub-string needs to be taken care of as written in the editorial ?
@cherry0697

It’s just one way to do it, you can start by doing it on a prefix as well (that’s even the provided solution and how most people including me solved it). So no it’s not mandatory, but it doesn’t really make a difference whether you take a prefix or a suffix, it will still be of the same complexity.

I feel like this “central substring” idea is much easier to convey to the beginners though. You’d have to invent a name for the object that contains first k and last k characters, and thus turn those parts into palindrome. You’d agree it sounds a bit confusing?

Because after updating i and n-i-1, if the coins left are less than the minimum coins required to make substring palindrome then how would make that substring palindrome.

1 Like

actually while making the minimal cost palindrome ,I modified by actual string which I wasn’t supposed to , it was just to keep the track of costs in a suffix array , I got ur point
, just watched the video editorial and thanks for ur reply

Thanks for your constructive feedback.

1 Like

“Solution: 49076465 | CodeChef”

Help me where I did wrong ? @cubefreak777 @soumyadeep_21 , like I did almost same but WA

Order of for loops in Floyd’s is wrong. Variable z should be part of the outermost loop, it’s a fairly common mistake. I have no formal proof, but I like to think of it this way:

By running z as the outermost loop, we limit the nodes that can be used to determine the shortest path (remember in order for DP to work we must have solutions to the smaller subproblems), so this way we ensure that all the paths that use some combination of values less than z have already been computed. It is similar to other DP problems such as knapsack in which you choose whether to use a certain value or not for every value that is smaller than z. I hope you get what I mean.

A fun fact is that Floyd’s algorithm returns correct answer when run 3 times with incorrect order of loops - https://arxiv.org/pdf/1904.01210.pdf

1 Like

:rofl:

This is new thing which I learn today , thanks

1 Like

oh my bad , actually in my floyd warshall template “z” or “k” is in outermost loop , but in code I did mistake :zipper_mouth_face: , bcz of this I waste my 1 hr .

“in my template”

loop(i,e){
        lli x,y,cost;
        cin>>x>>y>>cost;
        //undirected weighted graph
        dp[x][y]=min(dp[x][y] , cost);
        dp[y][x]=min(dp[y][x] , cost);
    }
    for(lli k=1;k<=v;k++){
        for(lli i=1;i<=v;i++){
            for(lli j=1;j<=v;j++)
            {
                dp[i][j] = min(dp[i][j] , dp[i][k]+dp[k][j]);
            }
        }
    }   

In code

loop(i,10)
    {
        loop(j,10)
        {
            loop(k,10)
            {
                dp[i][j] = min(dp[i][j] , dp[i][k]+dp[k][j]);
            }
        }
    }

It’s a mistake worth acknowledging early though, I’ve struggled with this issue in a contest so I had to learn it the hard way :stuck_out_tongue:

1 Like

Lessons will be repeated until learned :slight_smile: , will remember this “FLOYD WARSHALL”.Thanks

Can anyone tell me what is wrong?
My code

You’re not calculating the minimum path from every digit i to digit j. Changing i directly into j may not always be optimal. Suppose 3 -1 weighs 2, 1 - 2 weighs 3 and 3-2 weighs 6. If you want to change 3 into 2 it’s optimal to first change 3 into 1 and then 1 into 2 as it will cost a total of 2 + 3 = 5, whereas changing 3 into 2 directly has a cost of 6.

So you need to do Floyd’s/Dijkstra’s/Bellman Fords’s algorithm first and then compute the other parts you are doing in your code. Hope this helps you understand the problem.