You are not logged in. Please login at www.codechef.com to post your questions!

×

Encoder '18 - Solution Outlines

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[B] - 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[B] - profit[A] + 2*max(up[A],down[B])$.
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[B] + 2*max(up[B],down[A])$.

This question is marked "community wiki".

asked 27 Oct '18, 16:59

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 27 Oct '18, 17:34


____(guess who :p) = @vijju123 xD

link

answered 27 Oct '18, 17:25

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

edited 27 Oct '18, 17:32

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

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

link

answered 27 Oct '18, 19:39

horcrux2301's gravatar image

4★horcrux2301
17117
accept rate: 5%

edited 27 Oct '18, 19:39

Please see the announcement on the contest page.

(28 Oct '18, 02:35) abhineet145★

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.

link

answered 28 Oct '18, 08:04

joffan's gravatar image

5★joffan
9488
accept rate: 13%

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;
}
link

answered 29 Oct '18, 20:13

yash_ag_13's gravatar image

1★yash_ag_13
1
accept rate: 0%

edited 29 Oct '18, 20:31

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

Submission link please

(29 Oct '18, 20:33) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×368
×14

question asked: 27 Oct '18, 16:59

question was seen: 424 times

last updated: 29 Oct '18, 20:33