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;
}
, bcz of this I waste my 1 hr .
, will remember this “FLOYD WARSHALL”.Thanks