Hints for problems : A. Check for every 4 length substring of original string. Time complexity is O(N*4).

B. Do a binary search within given accuracy to get such a minimum answer such that (H-ans)/D > max((hi-ans)/di) over all i's. Time complexity is O(N*log2(accuracy)).

C. We can basically binary search on the answer. Inside a binary search, let's check if it's possible for the answer to be more than equal to the middle element of the binary search. For each person find mask of powers which are more than considered middle element of binary search. Now we need to take any 3 masks from given array of masks such that total overlap is (2^5 — 1) or the complete power set mask. Repeating a mask is also a possibility. Time complexity is O(log(A)*(32*4*N))

D. We first need to get the string after 'R''s are removed. We can notice that if number of blocks of strings between 'R's are S1 R S2 R ..... SK R SK+1, 2 possible cases arise : - if K is even, final string is SK' SK-2' .... S2 S1 S3 .... SK-1 SK+1 - if K is odd, final string is SK' SK-2' .... S1 S2 S4 .... SK-1 SK+1 where S' is the reverse of a string S. After obtaining this string, we can build the answer string using a stack based solution where we push a character only if stack is empty or it's top is not equal to my current character to get the minimized answer string. Note that there won't be any possible operation possible after 1 reversal sequence and 1 reduction sequence. Time complexity is O(N).

E. For each cell create a dummy node, and add adge (i,j) -> (i,j,dummy) with weight 1 and also (i,j,dummy) -> (i,j) with weight 0. Also add edges corresponding to "i" in "1+i" transition from (i,j,dummy) -> (i-1,j,dummy) with weight 1. Now between all the normal nodes(cells), add rest of the edges from the first 3 transitions given. Answer will be shortest path between (1,1) to (R,C) in this graph. Time complexity is (O(R*C*log(R*C)).

F. Since we cannot make a transition from a node with value from given value set, let's find the remaining value set, ie, complement value set from {0,1,....n-1}. Now from each node, it is easy to see we can make a transition to other node if and only if their xor is some subset xor of this complemented set. To find how many subset xors are possible, let's build the basis of this set, also keeping the minimal elements added(this will help us build the tree) to the basis. If basis has k elements, then total possible elements in connected component of any node is 2^k including itself. If n is not equal to 2^k, we cannot build an answer. Otherwise we can. Add an edge from each node i to it's xor with each of the original element that was inserted into basis. There are log(n) such elements for each i. Hence graph has nlog(n) edges. Now we can find any spanning tree of this graph and print it. Time Complexity is O(nlog(n)).

Can someone please clarify why this is giving tle for the task D

                FastScanner fs = new FastScanner();
		// int t = fs.nextInt();
		int t = 1;
		StringBuffer res = new StringBuffer();
		for (int tt = 1; tt <= t; tt++) {
			String s = fs.next();
			int count = 0;
			String ans = "";
			boolean flag = false;
			for (int i = 0; i < s.length(); i++) {
				if (s.charAt(i) == 'R') {
					if (ans.length() == 0)
						continue;
					count++;
					flag = !flag;
				} else {
					if (flag) {
						ans = s.charAt(i) + ans;
					} else {
						ans = ans + s.charAt(i);
					}
				}
			}
			if (count % 2 != 0) {
				ans = (new StringBuilder(ans)).reverse().toString();
			}
			Stack<Character> st = new Stack<>();
			for (int i = 0; i < ans.length(); i++) {
				if (st.size() > 0 && (ans.charAt(i) == st.peek())) {
					st.pop();
				} else {
					st.push(ans.charAt(i));
				}

			}
			StringBuffer y = new StringBuffer();
			while (!st.isEmpty()) {
				y.append(st.pop());
			}
			y.reverse();
			res.append(y);
		}
		System.out.println(res);

Can someone explain to me the 3D DP solution of Problem C , which is mentioned in the editorial .

F: Random solution passed the tests, just take vertices randomly vertices and take all edges incident to them and find any possible spanning tree. This way by taking around 40*n edges passed the time limit. Code

F, "from each node, it is easy to see we can make a transition to other node if and only if their xor is some subset xor of this complemented set."

Actually, I still do not see why this is. Can somebody explain with simple example?

Let $$$B=(1,2)$$$, and $$$v_1\oplus v_2 = 1$$$ and $$$v_3\oplus v_4 = 2$$$

Then how can we see that $$$v_1$$$ is somehow connected to $$$v_3$$$ ?

chokudai, tatyam, why not just switch C & D instead of having the point values out of order and adding a note? Just curious.

can someone explain why the following editorial code for F works ,taking y as min of its xor with elements of elim,I tried randomly permutating elim when considering a new x and it fails the sol surprisingly so order matters

int y = x;
for(int b : elim) chmin(y, y ^ b);
if(y){
      base.push_back(x);
      elim.push_back(y);
 }