Encoder '18 - Solution Outlines

general
,
1

While I get to the organizers for editorials, here are the short solution outlines which you can refer to for solving the problem.

1.$\text{KCHESS-}$Create a hash of positions which are near to king- 3*3 matrix. And after that check whether all the positions are attacking or not.
2.PNTWLL- The last paint will definitely exist on the wall. So we just have to find the increasing sequence from reverse and count it.Moreover to keep the colors distinct, we insert the color id in a set stl and at the end print the set size. Another approach can be using stack as suggested by ____(guess who :p) using stack is possible, where we can just push Ai to stack, until you encounter a element greater than it. Once you find Aj, such that Aj> top of stack, pop top of stack until its empty or Aj< top of stack.
3.SLAEL- Thanks to @Arjun Arul for pointed a noteworthy solution - Find and store all indices of elements >K. Say we stored them in array A. Now find longest length between two such values such that there is exactly 1 element >K in between, which, precisely, is A[i+2]-A[i]. With little modification to above, we cna handle case of multiple maximums in a range- simply dont add the maximum if its equal to top of stack or is equal to most recently inserted maxima.
4. OLDFAR- We are proposing a dynamic programming solution for this problem. For a matrix “mat” with dimensions N*M

a. dp[i][j] represents the maximum sum that can be obtained by traversing a ‘L’ shaped path formed from the coordinates, (i,j), (x,j) and (x,M) where (i<= x<=N) , for the submatrix with top-left corner at i,j and bottom right corner at N,M.
b. revCum[i][j] represents the sum, mat[i][j]+mat[i][j+1]+mat[i][j+2]...............mat[i][M]

c. dp[i][j] can be calculated as- dp[i][j] = mat[i][j] + max(dp[i+1][j],revCum[i][j+1])(Base cases can be handled accordingly)
d. After the dp and revCum have been calculated, the matrix can then be traversed and answer can be calculated using
ans=max(ans, revCum[i][j]+dp[i+1][j])

5.CTOUR- The problem can be solved using LCA and Kadane’s Algorithm on trees.

Preprocessing steps:

Profit from root to all the nodes - profit[n].
For calculating LCA in log(n).

Using kadane’s algorithm (top down), calculate the max profit for each node, if we are at the node and go towards the root and come back - up[n].

Using kadane’s algorithm (bottom-up) calculate the max profit for each node, if we are at the node and go towards downwards and come back - down[n].

Calculation steps:

Every query can be answered in O(log(n)).
There are three cases.

a. If LCA(A,B) != A or B. Then we have only one choice- going from A to LCA(A,B), then towards root to some extent and then to B. The total amount we can gain is profit[A] + profit** - 2*profit[LCA(A,B)] + 2*up[LCA(A,B)].
b. If LCA(A,B) = A. Then we have two choices- going upwards from A and back, or going downwards from B and back. The total amount we can gain is profit** - profit[A] + 2*max(up[A],down**).
c. If LCA(A,B) = B. Then we have two choices- going upwards from B and back, or going downwards from A and back. The total amount we can gain is profit[A] - profit** + 2*max(up**,down[A]).

2 Likes
2

____(guess who :p) = @vijju123 xD

1 Like
3

When will you guys publish the combined ranklist for Div1 and Div2?

4

Please see the announcement on the contest page.

5

An interesting question arising from KCHESS would be to see if the knights can keep a non-checkmated king confined to an area of the board. If the king can get all but one of the knights behind him by a couple of squares, he can certainly never be driven back to the body of knights.

6

can you please review my code,it gives wrong answer

    #include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,t;
	cin>>t;
	for(int i=0;i<t;i++)
	{
		cin>>n>>m;
		int count=0;
		long int h[n],c[n],max;
		for(int j=0;j<n;j++)
			cin>>h[j];
		for(int j=0;j<n;j++)
			cin>>c[j];
		max=h[n-1];
		int pos=n-1;
		count++;
		for(int j=n-1;j>=0;j--)
		{
			if(h[j]>max&&c[pos]!=c[j])
			{
				count++;
				max=h[j];
				pos=j;
			}

		}
		cout<<count<<endl;
	}
	return 0;
}
7

Submission link please