Привет, Codeforces!
Мы рады сообщить, что собираемся провести новый раунд на csacademy.com. Раунд #20 состоится в вторник, 07.03.2017 19:00 (Мск). Этот раунд рассчитан на Div2, это означает что изменение рейтинга коснётся только пользователей с рейтингом ниже 1600, а также пользователей без рейтинга. Пользователи с более высоким рейтингом могут принять участие неофициально.
Если Вы хотите принять участие в этом раунде, Вам необходимо зарегестрироваться перед началом. Так как раунд ориентирован на Div. 2, он будет состоять из 5 заданий более доступной сложности.
Формат контеста:
- Вам предлагается решить 5 задач за 2 часа.
- Мы обеспечиваем обратную связь на протяжении всего конкурса.
- Задачи не будут засчитываться частично: то есть либо вы выполнили задание, либо нет (ACM-style);
- Оценки будут присваиваться в динамике: в зависимости от количества пользователей, которые справились с проблемой, оценка будет варьироваться от 100 до 1000;
- Помимо баллов, у каждого участника будет "пенальти", который будет учитываться при определении победителя.
О системе пенальти:
- Пенальти вычисляется по следующей формуле: время, потраченное на выполнение последнего выполненного задания + "пенальти" за каждую решённую задачу. "Пенальти" для каждой решенной задачи равен log2 (no_of_submissions) * 5.
- Решения, которые не компилируются или не подходят для примеров тестовых случаев игнорируются.
- После того, как вы решили задачу и отослали результат, вы можете поэкспериментировать с решением, все последующие ответы уже не будут учитываться.
Что нового:
Мы поменяли дизайн сайта. Теперь панель навигации находится в верхнем левом углу страницы, в то время как чат и форум легко найти в правом верхнем углу.Так же мы изменили главную страницу и блог. Надеемся, вам понравятся изменения на сайте.
Мы по-прежнему рекомендуем использовать обновленную версию Google Chrome. Если вы обнаружите какие-либо ошибки, пожалуйста напишите нам по адресу [email protected] или в комментариях ниже.
Nice New Design!
Really nice design, but get back the logo! :)
Just a reminder, the contest starts in 2 hours.
How to solve second problem?
Maintain BIT/seg tree as you iterate the array from left to right . When you are at index j , you want to find minimum i such that arr[i] < arr[j] and just update the maximum answer .
How to solve with binary search?
No need for any data structure even though it's very easy if you use one but kind of too much for B.
It can be solved by preprocessing using a simple DP in O(N).
Let DP[x] represent maximum index i such that v[i] >= x.
Initially DP[v[i] = i, and transitions are looping from n — 1 to 1, and updating DP[i] with max(DP[i],DP[i+1]). You can see why transitions are valid if you trace it on small sample.
Now for iterate over all v[i]'s, and take maximum of DP[v[i]] — i.
Here's my code : http://ideone.com/7dgRoE
Binary search method —
maintain a stack, initially with just first element. iterate from index 1 to n-1
if the new element is lesser than top of stack element -> push to stack. note that the stack contains elements in strictly decreasing order.
else if the new element a[i] is greater than top of stack element -> apply binary search on the stack to find lowest index element smaller than a[i]. Maintain this maximum value.
You can solve it by using sets.
Initially maintain a vector<pair<int,int>> which holds the value and its index. Insert all the indexes into a set.
Sort the vector according to the value in increasing order.
Now,we iterate through the vector.
In each step, we erase the index corresponding to that element in the set.
Then find maximum index in set and subtract it with current index. Let this value be z.
Then ans=max(ans,z).
Code
Store the permutation in a array of pairs {value , index}
Sort the pair
Now starting from val = 1 to n you just need to find the maximum index greater than index of current value in range from (val + 1 ) to n which can be done using max suffix array.
See the code for implementation details : Code
Thank you all. I like csacademy problems. Problem are short and hard problems
How to solve C?
You can binary search on the answer. For validating the "mid", you can upgrade cities greedily. Iterate in increasing order of coordinates of cities. When you encounter a city whose max distance to an already upgraded city to its left exceeds the "mid", you need to upgrade another city to the current one's right. This can be chosen greedily, i.e. the farthest city to the right of the current one whose distance from it is <= "mid".
Code
Thanks for the Solution! Binary search is so versatile. I feel stupid for not being able to solve it during the contest.
Here's how I solved it after the contest. We can see that the if our best distance is let's say D then obviously we can also upgrade the cities in such a way that the maximum distance between regular and upgraded city will be ≥ D which means it will be monotonic and we can apply binary search on D. We sort the xi's first. Now to check if a particular D is valid, we can greedly start from first city and upgrade the city at distance D (We choose the last city with distance atmost D because it minimizes the number of upgraded cities). Now we start from this upgraded city and keep ignoring the cities to right which have distance ≤ D. Now we can easily count the number of upgraded cities and compare it with K, and change our binary search limits accordingly.
Thanks for your help :)