Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 198 |

2 | Errichto | 196 |

3 | rng_58 | 191 |

4 | awoo | 186 |

5 | SecondThread | 185 |

6 | Um_nik | 182 |

7 | vovuh | 177 |

8 | Ashishgup | 176 |

9 | antontrygubO_o | 174 |

10 | -is-this-fft- | 173 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Educational Codeforces Round 28

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/06/2021 04:47:22 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Is the round rated?

Another nice idea for solving D can be — link .

Can someone tell me why I get wrong answer here in problem D?

http://codeforces.com/contest/846/submission/30118738

Sorry, the size of the array wasn't enough.

Can someone explain

more explicitly?BSuppose you know how many tasks you are solving completely, say

i. This costs youitimes the sum of costs over all subtasks, and gives youi*(k+1)points.For the remaining time, you are not solving complete tasks. How can you do separate subtasks most efficiently? They all give 1 point, so greedily keep solving the lowest time cost one until you have not enough time left.

So try every possible number for

iand take the maximum.Why not solve maximum number of tasks completely and then solve the remaining tasks greedily till we run out of time? I tried doing this, but didn't work.

For example input: 10 2 10 1 9

In this case you can solve 10 times subtask 1 (10 points) which is better than doing maximum number of tasks completely; that would be solving a single task completely (2 + 1 = 3 points).

Thank you!

Maybe O(n2) can solve this problem instead of n2k...

Please elaborate the logic for Problem A.

can someone please explain problem C !

Problem C can be solved in linear time. Solution O(n).

Elaborate it please..

First let's solve subtask: Given an array of length N, for each 0 <= i < n we need to find k such that sum[0, k) — sum[k, i] = max.

Assume we store array A, where A[k] = sum[0, k) — sum[k, i]. Answer for current i is the maximum in A. Now we want to update it for i + 1. To do this reduce all A[0 <= j <= i] by x[i + 1], A[i + 1] = abs(sum[0, i + 1]). So we can use dp, because maximum answer for i + 1 is maximum of (ans[i] — x[i + 1]) and abs(sum[0, i + 1]).

Then iterate with c through array. It divides into two intervals: [0, c), [c, n). You need to find k1 and k2 such that (sum[0, k1) — sum[k1, c)) + (sum[c, k2) — sum[k2, n)) is maximum. We can use previously calculated dp because this two ranges are independent.

why Answer for current i is the maximum in A

I meant A[k] = sum[0, k) — sum[k, i]. Now we want to find answer for current i. Ans[i] = max(sum[0, k) — sum[k, i]) <=> Ans[i] = max(A[k]).

I didn't quite understand your explanation, but my code uses suffix sums and Kadane's algorithm. Let mx[i] denote the maximum possible contiguous subarray sum after index i in the array, and suf[i] denote the suffix sum starting at index i. Then, we just have to maximize the function f[i]=suf[0]-2*suf[i]+2*mx[i], which can be done in linear time. I used Kadane's algorithm from right to left to find mx[i]. Is this the same as your solution? https://codeforces.com/problemset/submission/846/92789040

E's trick in Input constraints! Missed it.

Different approach for F. For each unique value

a_{i}in the array find the probability that a random choice forlandrwill contain at least onea_{i}. To do this assuming we have all the positions ofa_{i}stored we can find the probability of the interval not containinga_{i}by summing each of the probabilities of bothlandrbeing in each of the disjoint intervals not containinga_{i}, which is just the length of the interval squared divided byn^{2}and subtracting this from 1.Finally by the linearity of expectation the answer is the sum of these probabilities over all distinct values in the array.

Can you please explain to me why is the output for

`n = 2`

and`a={2,2}`

is`1.000000`

{2,2} has one unique element in the the array. All segments contain 1 unique element.

That moment when you solve Div 2 A with DP!