Brief Editorials ICO Preparatory Mega Contest ICOP1904

editorial
, , ,
1

As @mgch quoted here, who am I to contradict him. So, I am presenting you the brief editorials for ICO Preparatory Mega-Contest. Hoping you all guys had fun in this contest. Here we go!

SHIVIGOD

For every x in range A to B, run sliding window of size x maintaining the sum of elements in ranges of length x, and take the one having the maximum average. Read about Sliding window here. The max(max sum in the range of length x/x) is the answer. Time complexity O(N^2).

SSJG

Build prefix arrays in 2d to compute the sum of subgrid in O(1) time as explained here and for each intersection point, calculate the values of all 4 subgrids if the current intersection is chosen and take the min. The intersection has the maximum value of min is the best intersection. Time complexity O(N^2).

JVPHOBIA

We run a DFS from each node maintaining an included array. The thing is, that once we consider one friend, there’s no benefit to consider him again. So, Running DFS only on non-included nodes at each step leads to a solution in O(N) time.

GRP

This problem is dynamic programming. We precompute cost(i, j, k) being min cost to convert array range [i, j] to bit k, k being 0 or 1.

Now, Let us use dynamic programming with two states, index of array covered and bit at ith node. DP[i][j] = min(DP[i-j][k^1]+cost[i-j+1][k]) for all x \leq j \leq y. Time complexity O(N^2).

TREEDGE

It is tree DP, for each node x, calculate DP(x) = max length path from x to any node in the subtree of x, which has a maximum length. The minimum value of DP(x) is 0 since we can always have a path from x to x itself.

For query u, v, we join two nodes in the subtree of u and v, to get max path length DP(u)+dp(v)+w.

Now, only 2 paths exist between u and v. One with length DP(u)+dp(v)+w and the other from u to LCA(u,v) to v, the length of which can be precomputed computed by DP or binary lifting.

Time complexity is O(N*logN+Q*logN). Dp can be precomputed in O(N) time, overall time complexity dominated by LCA finding.

STRGRA

We use DP[i][j] meaning min cost to reach node i after covering first j characters of the string. Clearly, at each character, we can run multisource Dijkstra to compute min cost to other vertices. Now, Core thing is, for next step, consider only those vertices as the source which have s[j] == a[i]. This way, answer is min(dp[i][|s|]) for i such that a[i] == s[|s|-1]. Impossible cases include disconnected graphs and character not present at all.

Time complexity is O(|S|*(N+M)*log(N)).

Hope you guys had a nice contest.

7 Likes
2

Nice Contest :smiley:

Why this DP solution is not working?

LINK

dp[i][j] = answer when the path starts from Node i and string from position j (0-based for the string) is considered

Base case: dp[i][|S|] = 0;

Rest of the logic is clear from the code

3

I was also doing the same thing for STRGRA in the contest. Even I want to know why it doesn’t work. It would be great if someone could help.

4

#include
using namespace std;

int main() {
int n,k,r,c=1,a=0,b=0;
cin>>n>>k>>r;
while(n>0 && k>0) {
a=k;
b=rc;
k= k-rc;
c++;
n–;
}
//cout<<n<<" "<<b<<endl;
if(a>=b)
cout<<n<<endl;
else
cout<<n+1<<endl;

return 0;

}

5

You can have a look at this https://discuss.codechef.com/questions/146336/strgra-editorial