Блог пользователя Polichka

Автор Polichka, 13 лет назад, По-русски
Задача A

Так как на первом месте должен стоять солдат с максимальным ростом, то логично поставить на первое место самого левого солдата с максимальным ростом, чтобы минимизировать время (число обменов). Исходя из таких же соображений на последнее место поставим самого правого солдата с минимальным ростом. Таким образом количество обменов это номер самого левого солдата с максимальным ростом  - 1 + n -  номер самого правого солдата с минимальным ростом. И если самый левый солдат с максимальным ростом стоит правее самого правого с минимальным ростом, то из этой суммы нужно вычесть один.

Задача B

Переберем все точки, в которых сидят генералы, и посчитаем количество не покрываемых никакой окружностью. Пусть xa < xb и ya < yb, если это не так, то просто поменяем xa и xb, ya и yb местами. Тогда генералы сидят в точках: (xa, y), (xb, y), (x, ya), (x, yb), где xa ≤ x ≤ xb и ya ≤ y ≤ yb. При подсчете ответа нужно аккуратно посчитать генералов, которые сидят в точках (xa, ya), (xa, yb), (xb, ya), (xb, yb), чтобы не учесть их дважды.

Задача C

Посчитаем количество каждой из букв во второй строке и сохраним это, например, в массив a[1..26]. Для первой строки для префикса длины, равной длине второй строке, (это первая подстрока) посчитаем в массив b[1..26] количество каждой из букв. Знаки вопроса в массиве b не будем учитывать. Если для всех i выполняется b[i] ≤ a[i], то значит это хорошая подстрока. Далее перейдем ко второй подстроке: вычтем из массива b первый символ: b[s[1] - 'a' + 1] –  и прибавим n + 1 символ, если n --- длина строки p: b[s[n + 1] - 'a' + 1] +  + . Если какой-либо из этих символов вопрос, то для него прибавление или вычитание делать не нужно. Далее повторяем выше рассмотренную проверку и переходим к следующей подстроке. Повторяем эти действия, пока не переберем все подстроки строки s длины n.

Задача D

d[i] --- минимальные расстояния от вершины s до вершины i, посчитанные с помощью алгоритма Дейкстры. 
Далее переберем все ребра графа, и для каждого из них посчитаем количество точек, не совпадающих с вершинами, лежащих на них, находящихся на расстоянии l от вершины s (причем l - минимальное расстояние от этих точек). 

Рассмотрим ребро (u, v):

если d[u] < l и l - d[u] < w(u, v) и w(u, v) - (l - d[u]) + d[v] > l, то прибавим к ответу точку, лежащую на этом ребре на расстоянии l - d[u] от вершины u;

если d[v] < l и l - d[v] < w(u, v) и w(u, v) - (l - d[v]) + d[u] > l, то прибавим к ответу точку, лежащую на этом ребре на расстоянии l - d[v] от вершины v;

если d[v] < l и d[u] < l и d[u] + d[v] + w(u, v) = 2 * l, то прибавим к ответу точку, лежащую на этом ребере на расстоянии l - d[u] от вершины u и l - d[v] от вершины v.

Также если d[i] = l, то прибавим к ответу вершины.

Задача E

Рассмотрим каждого спортсмена в отдельности. Очевидно, что мы можем по координатам спортсмена понять: какие клетки на побочной диагонали являются ближайшими к нему, они образуют "отрезок" на побочной диагонали. Выпишем для каждого спортсмена эти отрезки.

Выберем спортсменов так, чтобы каждому из них мы могли сопоставить ровно одну клетку на побочной диагонали из его "отрезка", и каждой клетке на побочной диагонали соответствовал не более, чем один спортсмен. Понятно, что спортсмены смогут дойти до "своих" клеток, не побывав с кем-либо на одной клетке. Осталось максимизировать количество выбранных спортсменов. Таким образом переформулированная задача решиется жадно.
Разбор задач Codeforces Round 103 (Div. 2)
  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится

»
13 лет назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

Чтобы в D не рассматривать случаи, можно было на каждом ребре (u,v) добавить вершину между u и v на расстоянии l - d[u]  и l - d[v] (пара проверок, чтобы новые вершины не совпали и существовали) и запустить Дейкстру ещё раз.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится
    Легче пару проверок сделать и не запускать Дейкстру =)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

>> ... посчитанные с помощью алгоритма Дийкстры.

Поправьте, пожалуйста.

»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Thank you for the contest and fast published tutorial :-)
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Actually I'm confused by how to greedy in Pro E... I have worked out the convertion, but didn't know how to solve the "segment" problem. THX
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    After sorting the left endpoints of the segments, you loop through them, and use a priority queue (heap data structure) to repeatedly select the next non-intersecting segment with the leftmost possible right endpoint.

    By the way, the editorial's question marks are not displaying properly.

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

UPD. Большой вопрос под спойлером. Уже решён.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Так точка не обязательно на середину должна попадать, если она одна. Пример: до одного конца ребра расстояние 1, до другого 3, длина ребра 4.
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Ой.... блиииин! Вот из-за тупого косяка задача провалена :(

      Спасибо!


      UPD. Удалил лишь условие в третьем if`е (d[t1[i]]==d[t2[i]]) и AC... Эх :(

»
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
" Понятно, что спортсмены смогут дойти до "своих" клеток, не побывав с кем-либо на одной клетке. " - достаточно неформальное доказательство, не так ли?:)
И как именно "жадно" решалась Е?
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    Ну на самом деле это практически очевидно. 

    А Е решалась так: сортируем полученные интервалы, затем пробегаем по точкам от 1 до n и для каждой точки берём по одному отрезку, если таковые есть под данной точкой - стандартная задача, похожа на вот эту http://e-maxx.ru/algo/covering_segments . А я вообще делал эту задачу иначе :) Закинул n точек в set, отсортировал точки по рядам затем по столбцам и для каждого интервала (l,r) находил максимальную точку из оставшихся, которая лежит в этом интервале (методом lower_bound), и удалял её.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      но допустим жадность придумать несложно, но вот как доказать (более четко), что пути спортсменов не пересекуться
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        UPD. Под спойлером доказательство на пальцах. Лучше читайте ниже..

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится
        1. Спортсмены стартующие с разных диагоналей не пересекаются - очевидно.
        2. Рассмотрим всех спортсменов на какой-то фиксированой диагонали в порядке возрастания y ( x убывают в этом случае), отсортируем конечные точки на побочной диагонали в том же порядке возрастания y и сопоставим спортсменам - очевидно при таком разбиении пути не пересекутся, если спортсмены сначала будут ходить только по вертикали, а потом только по горизонтали  
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится

        во-первых заметим, что спортсмены, которые стоят на разных диагоналях (параллельных побочной) никогда не окажутся в одной клетке, т.к. если  идти по кратчайшему пути, то каждый раз спортсмен должен переходить на более близкую к последней диагональ.

        Теперь рассмотрим спортсменов и их пункты назначения на некоторой диагонали. Понятно, что и спортсмены и их пункты назначения будут идти в одинаковом порядке на диагоналях, иначе они обязательно пересекутся. Теперь каждый спортсмен идет до  нужного столбца влево, потом вверх. Очевидно, что если они будут двигаться таким образом, то пути не пересекутся

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Никак не могу найти ошибку в своем решении на задачу D 1083266 (
Может кто-нить заметит в чем проблема?

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I still don't know about the solution to the Pro-E "segment" problem.Could you explain it more clearly?
Thanks a lot.
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Very sad that its impossible to get Accepted on problem B with Ruby.

Here is my code, may be some optimizations?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Seems like you are iterating the whole grid... of course it'll get TLE.
    Try to iterate only cells of the frame of the rectangle.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to prove the correctness of problem A.
I simulate 2 times.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    The solution is a greedy approach which is proved by contradiction. Consider the best case and assume it's not the one that your algorithm produces and then come up with a contradiction to prove its correctness.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У одного человека из моей комнаты увидел алгоритм Дийкстры с queue вместо priority_queue http://codeforces.me/contest/144/submission/1079923
Дийкстру так можно писать?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если я не ошибаюсь, то это уже ширина:)
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Ширина для графа, где ребра имеют вес?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Поиск в ширину с апдейтами
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Ну да. Каждый раз, когда обновляешь значение в вершине снова кладешь её в очередь. На большинстве графах этот алгоритм летает.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          это и есть, примерно, алгоритм Левита?
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да.
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Нет! Ширину намного легче заламать чем алгоритм Левита. 
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            Алгоритм Левита - это чит над вышеописанным методом, который кладет вершину не в конец очереди, а в начало, если ее до этого обрабатывали.
            http://codeforces.me/contest/144/submission/1078267
            Интересно, он все-таки валится или нет?
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              это намного его ускоряет?
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Я не знаю. Я ему не доверяю и пишу Дейкстру
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Вообще-то, да. Но всё равно есть тесты которые ламают это.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Можно, только работать будет за O(VE).
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Хм, в этой задаче V до 10^5, а Е до V^2 . И 60-й тест там с V = 10^5, E = 10^5.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Значит, в тестах очень мало случаев, когда одна и та же вершина обновляется много раз.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Есть соблазн попробовать написать генератор, чтобы заваливать такие решения :)
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Если сделаешь это, обязательно выложи. Есть у этого алгоритма пара хаков ))
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              В принципе конкретную реализацию завалить в общем-то можно, и я даже слышал про то что это где-то когда-то кто-то делал. А вот завалить сразу все хаки типа того чтобы вершины которые добавляются не первый раз добавлять в начало, которые еще и в голову не все придут....
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

В разборе задачи D прибавляем к ответу точку по 3 условиям
d[u] < l и l - d[u] < w(u, v) и w(u, v) - (l - d[u]) + d[v] > l. Но зачет 3 -е условие, что оно дает?

Предположим d[i]=7, d[j]=3 a[i,j]=9 l=10. Почему я не могу из i отложить 3 и добавить его в ответ???

  • »
    »
    13 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    Третьим условием мы проверяем корректность точки отстающей от u на расстояние l - d[u].
    l - d[u] - расстояние от точки до u;
    w(u, v) - (l - d[u]) - расстояние от этой точки до v;
    w(u, v) - (l - d[u]) + d[v] - расстояние, если идти в искомую точку из s в v и по ребру (u,v);
    w(u, v) - (l - d[u]) + d[v] <= L - это значит, что проходя через v мы можем прийти в точку по более короткому пути и она нам не подходит!

»
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody help me with this (code) problem (C) ?

Something strange starts from test #13 (look at input params).

From problem statement:
The first line is non-empty string s, consisting of no more than 105 lowercase Latin letters and characters "?". The second line is non-empty string p, consisting of no more than 105 lowercase Latin letters.

PS.
Got Accepted, but the question remains.
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Are you talking about the cases that only have one line?

    I think maybe because the string in the first line is so long that the system can only show a small prefix of it. then the whole input file remained is ignored.

    eg.

    xxxxxxxxxxxxxxxxxx
    yyyyyyyyyyyyyyyyyy
    zzzzzzzzzzzzzzzzzz
    aaaaaaaaaaaaaaaaaa
    bbbbbbbbbbbbbbbbbb

    will looks like

    xxxxxxx...

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In Codeforces, large test case displays first 256 characters only, after which they show ellipsis (...)

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hello! I want to know why the Pro-D could use Dijkstra to solve? That the  complexity of Dijkstra is O(v^2), isn't it ? And this time , |V| <= 10^5. 
thanks, Happy new year ~!~
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    We can improve complexity to O(V × logE) using data structures to extract minimum in O(logn), for example, prority queue based on either binary heap or sorted set.
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

PROBLEM A I don't understand, what my mistake is, i'm getting wrong Answer on test case 4, everytime! I implemented everything according to the Tutorial only.

Can Any1 help me?


import java.util.*; import java.lang.*; import java.io.*; public class CodeForces { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] heights = new int[n]; for (int i=0; i<n; i++) { heights[i] = sc.nextInt(); } int maxE = Integer.MIN_VALUE, minE = Integer.MAX_VALUE; int minP = -1, maxP = -1; for (int i=0; i<n; i++) { if (maxE<=heights[i]) { maxE = heights[i]; maxP = i; } if (heights[i]<=minE) { minE = heights[i]; minP = i; } } // int result = 0; // if (maxP > minP) { // result = maxP + (n - 1 - minP) - 1; // } else { // result = maxP + (n - 1 - minP); // } int result=maxP-1+(n-minP)-(maxP>minP?1:0); System.out.println(result); // Close the scanner sc.close(); } }
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well, good job! you almost got it. Now, what did you miss? as we iterate through the array we need to get the first occurance of the max height and the last occurance of the min height. This is to decrease the time required to place the soldiers in their respective positions. Here's the accepted code:


    import java.util.*; import java.lang.*; import java.io.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] heights = new int[n]; for (int i=0; i<n; i++) { heights[i] = sc.nextInt(); } int maxE = Integer.MIN_VALUE, minE = Integer.MAX_VALUE; int minP = -1, maxP = -1; for (int i=0; i<n; i++) { if (maxE<heights[i]) { maxE = heights[i]; maxP = i; } if (heights[i]<=minE) { minE = heights[i]; minP = i; } } // int result = 0; // if (maxP > minP) { // result = maxP + (n - 1 - minP) - 1; // } else { // result = maxP + (n - 1 - minP); // } int result=maxP-1+(n-minP)-(maxP>minP?1:0); System.out.println(result); // Close the scanner sc.close(); } }
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi, I just started j hope this isn’t a stupid question but any idea my code doesn’t work?

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    int a[n];
    int maxIndex = 0;
    int minIndex = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] > a[maxIndex]) maxIndex = i;
        if (a[i] <= a[minIndex]) minIndex = i;
    }
    cout << maxIndex - 1 + (n - minIndex) - (maxIndex > minIndex ? 1 : 0);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}