Problem Link : https://www.codechef.com/STRG2020/problems/PADTREE

Problem : Given a tree, where each node is labelled using lowercase latin character. Find the longest palindromic path. (T <= 15 and N <= 5000)

My Idea : Just like finding a longest palindromic substring, we maintain dp[i][j]. And process this dp from length = 1 to length = 2 and so on... We use LCA to find path length and transition states.

My solution : https://www.codechef.com/viewsolution/40866046 Solution summary : I precompute all N^2 paths and sort them by their path length and process as mentioned above. But I got TLE. Complexity — O(T * N^2 Log(N))

Solution by CoderAnshu : https://www.codechef.com/viewsolution/40861653 Solution summary : Uses similar approach but instead of precomputing paths, he expands set from length 1 by keeping queue. Can you please explain the time complexity? And perhaps where I might be going wrong?

Can someone please help with the above problem?

Problem : You are given a NxN matrix and consider if a pair of cells is removed from the square matrix and then if we are able to cover remaining cells of the matrix by a 1x2 tile placing it either horizontally or vertically then the pair of cell removed is called GoodPair. Count number of good pairs.

Problem link : https://www.codechef.com/LOGI2020/problems/CHEFG999

Solution : The given square matrix can be visualised as a NxN chessboard with cells of black and white colour. So we can say that if one pair of cell with opposite colours is removed then only the solution is possible. (As domino tiling matches one black cell with one white cell or vice versa).

I understand that we need to remove cells with different parity of (i+j), but is it ALWAYS possible? Can someone explain the proof of it or provide a constructive approach to lay out the tiles?

Question link : https://www.codechef.com/problems/AVGMED Question summary : Find number of subarrays of length K, such that average >= median and also the median and average must both be prime or non prime.

Solution link using ordered_set : https://www.codechef.com/viewsolution/39036972 Am I doing something wrong with how to use ordered_set? Or my solution is wrong itself? Please help.

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define FI ios_base::sync_with_stdio(false); cin.tie(NULL);
#define PREC cout << setprecision(10) << fixed;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <class T> struct cmp {
	bool operator() (T x, T y) {
		return x.first < y.first;
	}
};
template <class T> using ordered_set = tree<T, null_type, cmp<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long

const int MOD = 1e9 + 7;
const int INF = 1e9 + 9;
const int MX = 1e5 + 5;

bool isPrime[MX];
void sieve() {
	memset(isPrime, true, sizeof isPrime);
	isPrime[0] = isPrime[1] = false;
	for(int i=2;i*i<MX;i++) {
		if(isPrime[i] == false) continue;
		for(int j=i*i;j<MX;j+=i) {
			isPrime[j] = false;		
		}
	} 
}

int n, k;
int inp[MX];

#undef int 
int main() {
	#define int long long
	FI;
	sieve();
	int tt;
	cin >> tt;
	while(tt--) {
		cin >> n >> k;
		for(int i=0;i<n;i++) {
			cin >> inp[i];
		}

		ordered_set<pair<int,int> > st;
		int ans = 0;

		int sum = 0;
		for(int i=0;i<k;i++) {
			st.insert({inp[i],i});
			sum += inp[i];
		}
		int avg = sum/k;
		auto it = st.find_by_order((k-1) /2);
		assert(it != st.end());
		int med = it->first;

		assert(avg >= 0 && med >= 0);
		if(isPrime[avg] == isPrime[med] && avg >= med) ans++;

		for(int i=k;i<n;i++) {
			sum += inp[i] - inp[i-k];
			st.erase({inp[i-k], i-k});
			st.insert({inp[i], i});

			avg = sum/k;
			it = st.find_by_order((k-1) /2);
			assert(it != st.end());
			med = it->first;

			assert(avg >= 0 && med >= 0);
			if(isPrime[avg] == isPrime[med] && avg >= med) ans++;
		}
		cout << ans << endl;
	}
	
	return 0;
}

Another solution : https://www.codechef.com/viewsolution/38989875 Similar solution which got accepted. I am not to able to see what I did wrong (I am blind or what?). Can someone kindly help?

Problem Link : https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_d

Can someone please help me with the solution of the above problem?

My idea was to inverse the problem, so instead of calculating non overlapping configurations we can calculate total number of overlapping configurations and subtract it from total possible combinations of placing red & blue squares in a given area. Calculating total combinations is trivial. But I couldn't figure out how to calculate the overlapping combinations (I tried fixing square A and then calculate how to place B such that it strictly overlaps). But couldn't handle multiple cases (both squares needs to be inside the square area and how to avoid double counting etc). Thought some inclusion-exclusion could be used. But I am stuck now and not able to figure it out.

Solution from top rank contestant : https://atcoder.jp/contests/hhkb2020/submissions/17295052

Seems like a pretty straight forward solution but not able to understand. Can someone please help?

Hi!

First of all, I would like to thank SecondThread, really appreciate your videos and effort. I think it really helps beginners, like me — to learn, improve, and understand the thought process of high rated coders.

Problem link : https://mirror.codeforces.com/contest/1392/problem/F Solution video link : https://www.youtube.com/watch?v=oHucq2J-3T8&t=12545s

He uses quite an ingenious trick to change the constraint of having adjacent difference >=2 to >=1, by subtracting i from each index initially, and then solving the problem (converts into something much simpler) and again adding the i back to the final array, and thus the solution. Can someone please explain why it works (as in the intuition behind it) (or different way of looking at solution perhaps)? My peanut brain is just not able to grasp it at all.

And if someone has solved it differently and can share the thought process, would really appreciate it.

Question link : https://atcoder.jp/contests/abc175/tasks/abc175_f and My Solution link : https://atcoder.jp/contests/abc175/submissions/15984070

Solution reference of int65536 (rank 1 in contest): https://atcoder.jp/contests/abc175/submissions/15936454

I did some sort of similar approach but instead of applying Dijkstra's algorithm to find the shortest path where state is defined using (prefix & suffix), I tried to use recursive dp approach with memoization (seemed intuitive to me).

I manage to pass almost all the cases but getting RE in 4 test cases. Can someone please help me where I might be going wrong with my solution?

Also can someone share an insight why every high rated coder intuitively thought of applying Dijkstra and not a recursive dp? Is there some property that I am missing? Can someone please help?

For reference : - tribute_to_Ukraine_2022 https://mirror.codeforces.com/blog/entry/81458?#comment-681148 and - galen_colin https://www.youtube.com/watch?v=HmbZiI0rAk4

My Solution :

#include<bits/stdc++.h>
using namespace std;

#define LL long long

const int MOD = 1e9 + 7;
const LL INF = 1e18 + 9;
const int MX = 1e5 + 5;

int n;
vector<string> inp;
vector<LL> cost;

bool isPalindrome(string s) {
	int l = s.size();
	for(int i=0;i<l;i++) {
		if(s[i] != s[l-1-i])
			return false;
	}
	return true;
}

vector<string> getNextState(string s1, string s2) {
	vector<string> ret;

	int l1 = s1.size();
	int l2 = s2.size();
	int l = min(l1,l2);
	for(int i=0;i<l;i++) {
		if(s1[i] != s2[l2-1-i]) {
			return ret;
		}
	}
	if(l1 == l2) {
		ret.push_back("");
		ret.push_back("");
	}	
	else if(l1 > l2) {
		string tmp = s1.substr(l2);
		ret.push_back(tmp);
		ret.push_back("");
	}
	 else {
		string tmp = s2.substr(0, l2-l1);
		ret.push_back("");
		ret.push_back(tmp);
	}
	return ret;
} 

map<pair<string, string>, LL > cache;

LL solve(string pre, string suff) {
	if(isPalindrome(pre + suff)) {
		return 0;
	}

	if(cache.find({pre,suff}) != cache.end()) {
		return cache[{pre,suff}];
	}

	LL ret = INF;

	for(int i=0;i<n;i++) {
		vector<string> cand;
		if(pre.size() > 0) {
			cand = getNextState(pre, inp[i]);
		} else {
			cand = getNextState(inp[i], suff);
		}

		if(cand.size() == 0) {
			continue;
		}

		ret = min(ret, cost[i] + solve(cand[0], cand[1]));
	}

	cache[{pre, suff}] = ret;
	return ret;
}

int main() {
	cin >> n;
	inp.resize(n);
	cost.resize(n);
	for(int i=0;i<n;i++) {
		cin >> inp[i] >> cost[i];
	}

	LL ans = INF;
	for(int i=0;i<n;i++) {
		ans = min(ans, cost[i] + solve(inp[i], ""));
	}
	if(ans == INF) {
		cout << -1 << endl;
		return 0;
	}
	cout << ans << endl;

	return 0;
}

Hi,

Can someone please explain the approach for the following problem :

Problem Link : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff08/0000000000386d5c

There's an editorial blog as well, but am not quite able to understand the solution. Editorial Link : https://mirror.codeforces.com/blog/entry/80040

Problem link : https://atcoder.jp/contests/abc154/tasks/abc154_e

Can someone please explain what does the dp state denote in this solution? Solution Link : https://atcoder.jp/contests/abc154/submissions/9982527

I was able to solve the question using recursive (+ memoization) approach. My solution : https://atcoder.jp/contests/abc154/submissions/15031609

My approach : solve(i, res, k) — At position i, if there's a restriction on digit at this position, and number of non-zero digits remaining to be taken.

But am not able to understand the iterative dp approach. Sorry my peanut brain is not able to understand. If someone could please explain what does the state denote & why it works? (need explanations in terms of intuition and not in code or mathematics sense). Because it seems like coding iterative is much faster and simpler.

Hi,

Can someone please help me with the following problem? https://atcoder.jp/contests/abc155/tasks/abc155_e

I found this dp solution, am unable to understand what does dp state denote and how transitions are made? https://atcoder.jp/contests/abc155/submissions/10154214

Or any other solution?

The follow up question to the previous blog https://mirror.codeforces.com/blog/entry/78752

I still don't really understand the permutation formula for numbers with duplicates. (I googled but didn't get the intuition besides it saying to account for repetitions we divide). Sorry for the silly question.

Calculate the number of ways a rooted tree can be reconstructed (by adding one node at a time) such that it remains connected.

Problem E. Can someone please help me find issue with my solution? Was able to pass sample test cases but it failed on submission.

Problem Link : https://mirror.codeforces.com/contest/1366/problem/E Solution Link : https://mirror.codeforces.com/contest/1366/submission/83481690

Here is my greedy approach. For each element (at index i) in B, I keep three variables

0-indexed
start[i] and end[i] : denoting the range in Array A in which B[i] is minimum.
start[i] denotes index in array A from where B[i] can start being minimum (first occurrence of B[i] from where it can start being minimum). 

mov[i] : the index of the last occurrence of B[i] in range (start[i], end[i]), such that B[i] is minimum in range (mov[i], end[i]) in Array A (I calculate this for B[1, m-1])

Note : That means for B[i-1], I can choose subarray ending at index from end[i-1] to mov[i] - 1
I calculate answer for each i from 0 to m-2
ans = 1
ans = ans * ((mov[i+1] - 1) - end[i] + 1) for all i in range 0,m-2

Example : 
A     : 12 10 15 20 20 25 30
B     : 10 20 30
start : 0  3  7
end   : 2  6  7
mov   :    4  7
ans   : 2  1 

ans = 2 * 1 = 2

Need help in solving the following Codechef problem :

https://discussed.codechef.com/questions/95355/task-scheduling-problem-or-graph-problem-need-help?sort=oldest

P0, P1, ...., Pn players in tournament. In first level, P0 plays with P1, P2 plays with P3 and so on. In level 2, Winner of P0,P1 plays with winner of P2,P3. For i,j output level in which they will face each other assuming they win all games.

Given string S, and let K be the minimum number of rotations required to get the same string.

For Example: (1) For S = "aaaa", K = 1 (2) For S = "abcabc", K = 3 (3) For S = "abcdef", K = 6

Now my question is, can there be any string for which K > len(S)/2 and K < len(S) ? If not, can someone please help me prove it?