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

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3655 |

4 | ksun48 | 3547 |

5 | jiangly | 3492 |

6 | Miracle03 | 3480 |

7 | ecnerwala | 3400 |

8 | maroonrk | 3385 |

9 | peehs_moorhsum | 3384 |

10 | sunset | 3338 |

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

1 | 1-gon | 214 |

2 | Um_nik | 190 |

3 | sus | 183 |

4 | Errichto | 179 |

4 | awoo | 179 |

6 | tourist | 178 |

7 | -is-this-fft- | 172 |

8 | Radewoosh | 170 |

9 | maroonrk | 169 |

10 | Ashishgup | 168 |

Comments

+1
We're working on it. It'll be posted soon. |

0
wow ._. |

+14
I have time, but unfortunately, I lack patience. |

0
Can you give me some hint / any tutorial about that algorithm? |

+10
How to solve E? |

+1
Let us first calculate the expected gain of NSU for a given fixed entrance day Suppose, Where,
If you can calculate How to calculate Suppose,
Then: |

0
For problem 4(Universities), Is |

+25
I can solve this problem if both the arrays are some permutation of the first n numbers. But what if one number appearance more than once? How to create a graph in such case? |

+68
We applied 2nd time for the visa today and we got accepted. May be you can think about applying for the second time if it is possible. |

+1
I've gone through the "Advanced Topics" part and my reaction while reading this book can be described as: wow wow wow wow wow wow..... Thank you for sharing it. |

+15
Why does it work? |

+3
"For the arrangement to be liked by Jon each of the f + 1 partitions created by f food boxes must contain either 0 or greater than h wine barrels"- I don't get the "must contain either 0 or..." part. Is it possible for a stack to be empty? |

+5
Yes I also think that it's similar to rectilinear Steiner tree problem. So yes, may be it's NP-hard. |

+3
I first misunderstood problem D and thought that I'm allowed to change " * " sign to ".". I found this problem interesting but couldn't come up with any solution. |

+30
But this guy managed to pass :) |

0
Oh thanks! Didn't see that the editorial was there. |

0
That's a cool trick :) I tried to solve the problem "Make n00b land great again" but couldn't figure out how to efficiently update the queries. Can you please explain how to do it efficiently? |

+5
Me too. I don't know why :/ |

+19
Break the problem into two cases: when k > sqrt(n) and when k <= sqrt(n). Deal with them in different ways. Case 1: For any k > sqrt(N) there will be less than sqrt(N) alternating segment. If you have an array, having cumulative sum, you can get the sum of a contiguous segment in O(1). So you can just loop over the alternating parts and get the sum in O(sqrt(N)) for a single query. Case 2: Now when k <= sqrt(n), you need to do some preprocessing. let arr[k][i] be the "k alternating sum" of a subarray which starts at position i and keeps alternating untill it reaches a position x such that if you add another segment of size k then it will go out of the array. [ This array can be computed in O(N) , and as you're doing it for every k < sqrt(n), the total complexity is O(N * sqrt(N))] With the help of this array, you can answer every query having k < sqrt(N) in O(1). Hope that helps. |

+5
wow :D Awesome experience :D I enjoyed the contest very much :) |

+8
Does it work correctly in case f(mid) == f(mid + 1) ? For example: f = {0, 1, 0, 0, 0} |

0
For every edge (x<->y), we need to calculate how many edges (p<->q) intersect it. In order to make sure that we are not overcounting, we'll only consider such edges (p<->q) where x < p < y < q [They surely intersect each other] We can do that in O(log n). Maintain a segment tree where a node in the segment tree having range [i..j], holds the end points of the such edges (u <-> v) such that i <= min(u,v) <= j, in sorted order. Now suppose we want to know how many edges (p <-> q) intersects with (x<->y) where x < p < y < q. To get this, we'll query on the range [x+1..y-1]. As we have the end points in sorted order in the segment tree, we'll binary search on y to get the answer. |

0
Can you please elaborate? |

0
We can use dp for checking half-palindromes. Suppose our good[][] array works correctly for substrings of length 1,2,3...i-1 Now we have to consider the substrings of length i and update the good[][] array. It's obvious that good[i][j] = 1 if and only if, |

+49
1699 to 1699 ._. |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/19/2021 01:30:40 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|