So I have been trying to solve Task C https://atcoder.jp/contests/abc286/tasks/abc286_c in Java. Here is what I came up with :-

     static long minCostToConvertToPalindrome(int a, int b, char[] word, int f, int s) {

        if (f >= s) {
            return 0;
        }

        String cacheKey = f + "-" + s;
        if (cache.containsKey(cacheKey))
            return cache.get(cacheKey);

        // Rotate the word
        int amountSpentInRotation = a + (word[f] == word[f + 1] ? 0 : b);

        // Change the word
        int amountSpentInChanging = word[f] == word[s] ? 0 : b;

        long minAmountSpent = Math.min(
                amountSpentInRotation + minCostToConvertToPalindrome(a, b, word, f + 2, s),
                amountSpentInChanging + minCostToConvertToPalindrome(a, b, word, f + 1, s - 1)
        );

        cache.put(cacheKey, minAmountSpent);
        return minAmountSpent;

    }

Note that I call the function like this -> minCostToConvertToPalindrome(a, b, word, 0, word.length - 1) in my main function.

Now, its clear that there are only N^2 possible combinations of parameters f and s. So the time complexity of my solution is also O(N^2) I think. The editorial also suggests a O(N^2) solution so why does mine not make it?

Please help me Thank you for reading

As you can see, in red, it says "unusual UTF-8 characters not supported". Why is that?

I think many of us would love to use emojis in 2022

Please add that feature.

Thank you

Link to problem — https://atcoder.jp/contests/abc175/tasks/abc175_d

Link to my submission: https://atcoder.jp/contests/abc175/submissions/18135753

I am not able to figure out what's wrong in my logic — if the sum of cycle is positive, then I would think of doing as many cycles as possible until reaching k count because it only helps increase cost. Then using mod i can figure out what is the most optimum steps to take further to reach max in the last cycle.

All sample test cases pass but not the submission. Not able to understand why. Any kind of help appreciated

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int mod = 1e9 + 7;

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for(int i = 0; i < v.size(); ++i) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}


ll n, k;
ll p[5005];
ll c[5005];

void solve() {

	cin >> n >> k;

	for(ll i=0; i<n; ++i) {
		cin >> p[i];
		--p[i];
	}

	for(ll j=0; j<n; ++j) {
		cin >> c[j];
	}

	ll best = -1e17;

	for(ll node=0; node<n; ++node) {

		ll curr = node;

		vector<ll> pref;
		vector<ll> mx;

		do {

			curr = p[curr];

			if(pref.empty()) 
				pref.emplace_back(c[curr]);
			else 
				pref.emplace_back(pref.back() + c[curr]);


			if(mx.empty())
				mx.emplace_back(pref.back());
			else
				mx.emplace_back(max(mx.back(), pref.back()));


		} while(curr != node);

		ll score = 0ll;
		ll cnt = k;

		ll cycle_sum = pref.back();
		ll cycle_len = pref.size();

		if(cycle_sum > 0 && cnt >= cycle_len) {
			score += (k / cycle_len) * cycle_sum;
			cnt = k % cycle_len;
		}

		if(cnt > 0) 
			score += mx[cnt-1];

		best = max(best, score);

		//cout << pref << endl << mx << endl << score << endl << endl;

	}

	cout << best << endl;

}

signed main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin >> t;

	while(t--) 
		solve();

	return 0;
}

The problem I am solving is E. Coprime (in At coder's Beginners contest)

https://atcoder.jp/contests/abc177/tasks/abc177_e

My submission that gives TLE

https://atcoder.jp/contests/abc177/submissions/18061844

The problem I am facing comes with identifying if the numbers are pairwise coprime.

I did exactly what the editorial said — There should be no prime number that divides 2 numbers in the input array otherwise their gcd won't be 1. So I found out unique numbers that are prime factors for every number in the array and then when I spot that there exists a prime number which is a factorizing 2 numbers I set the ispwc = false (is_pairwise_coprime). But I get TLE

My code:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll cnt[1000005];

ll gcd(ll a , ll b) {
	
	if(a < b) {
		return gcd(b, a);
	}
   	
   	if(b==0) 
   		return a;

   	return gcd(b, a % b);
}


vector<bool> is_prime;
vector<ll> siever;

vector<ll> upf(ll n) {

	assert(n != 0 && n != 1); 

	// return unique primes that factorize n
	
	// for n = 100, we return [2, 5]

	vector<ll> res(n + 1);
	vector<ll> uniqs;

	ll curr = n;

	do {

		if(res[siever[curr]] == 0){
			uniqs.push_back(siever[curr]);
		}
		res[siever[curr]]++;

		curr = curr/siever[curr];

		if(curr == siever[curr]) {

			if(is_prime[siever[curr]] && res[siever[curr]] == 0) {
				uniqs.push_back(siever[curr]);
				res[siever[curr]]++;
			}

			break;
		}

	} while(true);

	return uniqs;
}

void sieve(ll n) {
	
	is_prime.assign(n + 1, true);
	siever.assign(n + 1, 0);

	for(ll i = 0; i < n + 1; ++i) {
		siever[i] = i;
	}

	is_prime[0] = is_prime[1] = false;

	for(ll i = 2; i <= sqrt(n); ++i) {

		if(is_prime[i]) {

			for(ll j = i * i; j <= n; j += i) {
				siever[j] = i;
				is_prime[j] = false;
			}
			
		}
	}

}

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(0);

	ll n;
	cin >> n;

	// accumulator for setwise gcd
	ll c = 0;

	sieve(1000001);

	// is pairwise coprime
	bool ispwc = true;

	for(ll i=0; i<n; ++i) {
		
		ll x;
		cin >> x;
		
		c = gcd(c, x);

		if(x != 1) {

			// for each unique prime factor of x
			for(ll _p: upf(x)) {

				// cout << _p << " ";

				if(cnt[_p] != 0) {
					ispwc = false;
				}
				
				cnt[_p]++;
			}

			// cout << "\n";

		} 
		
	}

	// is setwise coprime
	bool isswc = c == 1;

	if(ispwc) {
		cout << "pairwise coprime" << endl;
	} 
	else if(isswc) {
		cout << "setwise coprime" << endl;
	}
	else {
		cout << "not coprime" << endl;
	}

	return 0;
}