×

# Brief Editorials ICO Preparatory Mega Contest ICOP1904

 7 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. asked 20 Jan, 00:00 3.9k●27●91 accept rate: 22%

 0 Nice Contest :D 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 answered 20 Jan, 08:09 117●8 accept rate: 0% 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. (20 Jan, 15:02)

# include <iostream>

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;


}

1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,631
×649
×177
×31