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

Автор fcspartakm, 9 лет назад, По-русски

525A — Виталий и пирожок

Для решения данной задачи будем использовать массив cnt[]. В нем будем хранить сколько ключей каждого типа мы уже нашли в комнатах, но пока не использовали, а ответ будем считать в переменной ans.

Проитерируемся по строке s. Если текущий элемент строки si строчная буква (ключ), увеличим cnt[si] на единицу. Если текущий элемент строки si прописная буква (дверь) возможны два случая. Если cnt[tolower(si)] > 0, тогда уменьшим cnt[tolower(si)] на единицу, иначе увеличим ans на единицу. Осталось вывести ответ.

Асимптотика решения — O(|s|), где |s| — длина строки s.

525B — Паша и строка

Сначала нужно понять следующий факт — неважно в каком порядке выполнять перевороты, ответ от этого не изменится.

Пусть элементы строки проиндексированы начиная с единицы. Для решения задачи посчитаем сколько переворотов будет начинаться в каждой из позиций строки. Потом насчитаем массив sum[]. В sum[i] будем хранить количество переворотов подстрок, которые начинаются в позициях, не превышающих i.

Теперь проитерируемся по i от 1 до n / 2 и, если sum[i] нечетно, поменяем местами элементы строки si и sn - i + 1. Выведем ответ — получившуюся строку s.

Асимптотика решения — O(n + m), где n — длина строки s, m — количество переворотов.

525C — Илья и палочки

Данная задача решается жадным образом. Насчитаем массив cnt[]. В cnt[i] будем хранить сколько у нас есть палочек длины i.

Теперь проитерируемся по длинам палочек (len) от максимальной длины до минимальной. Если cnt[len] нечетно и есть палочки длины len - 1 (то есть cnt[len - 1] > 0), сделаем cnt[len]-- и cnt[len - 1]++. Если же cnt[len] нечетно и палочек длины len - 1 нет (то есть cnt[len - 1] = 0), просто сделаем cnt[len]--. Таким образом, мы корректно сделали все нужные спиливания и гарантировали, что cnt[len] четные.

После этого вновь нужно пройти по длинам палочек аналогичным циклом и жадным образом объединять пары из 2 палочек одинаковых длин в четверки. Это и будут длины сторон ответных прямоугольников, осталось сложить их площади. В конце могут остаться две палочки без пары, их в ответе учитывать не нужно.

К примеру, если cnt[5] = 6, cnt[4] = 4, cnt[2] = 4, нужно объединить эти палочки в прямоугольники следующим образом — (5, 5, 5, 5), (5, 5, 4, 4), (4, 4, 2, 2). Две оставшиеся палочки длины 2 на ответ не влияют, так как их не с кем объединить.

Асимптотика решения — O(n + maxlen - minlen), где n — количество палочек, maxlen — максимальная длина палочки, minlen — минимальная длина палочки.

525D — Артур и стены

Для решения данной задачи нужно заметить следующий факт. Если в каком-то квадрате размера 2 × 2 в заданной матрице есть ровно одна звездочка, ее точно нужно заменить на точку. То есть если в матрице из точек и звездочек нет квадрата 2 × 2, в котором ровно одна звездочка (остальные точки), то все максимальные по размеру связные по стороне области из точек представляют собой прямоугольники.

Теперь решим задачу с помощью обхода в ширину. Пройдем по всем звездочкам матрицы, и, если есть квадрат 2 × 2, содержащий текущую звездочку, а остальные элементы этого квадрата точки, заменим эту звездочку на точку и положим эту позицию в очередь. Затем напишем стандартный обход в ширину, в котором будем заменять звездочки на точки во всех получающихся квадратах 2 × 2, в которых ровно одна звездочка.

Асимптотика решения — O(n * m), где n и m — размеры заданной матрицы.

525E — Аня и кубики

Для решения данной задачи воспользуемся методом meet - in - the - middle. Отсортируем заданный массив по возрастанию и разобьем пополам. В первой половине оставим первые n / 2 элементов, во второй все остальные.

Переберем все подмаски всех масок элементов из первой половины. То есть переберем какие кубики из первой половины мы возьмем и на какие из них наклеим восклицательные знаки. Таким образом мы переберем все возможные суммы, которые мы можем набрать с помощью кубиков из первой половины.

Пусть для текущей подмаски мы наберем сумму sumlf, используя tlf восклицательных знаков. Для хранения всех сумм используем ассоциативные массивы map < long long > cnt[k+1], где k — количество восклицательных знаков, которое у нас есть изначально. Тогда для текущей подмаски нужно сделать cnt[tlf][sumlf]++.

После этого, аналогичным образом, переберем все подмаски всех масок элементов из правой части. Пусть для текущей подмаски сумма равна sumrg, а количество использованных восклицательных знаков trg. Тогда в левой части нам нужно набрать сумму (s - sumrg), используя не более (k - trg) восклицательных знаков, где s — сумма, которую необходимо набрать по условию задачи. Тогда переберем сколько восклицательных знаков будем использовать в левой части (пусть это будем переменная cur) и прибавим к ответу cnt[cur][s - sumrg].

Для ускорения работы программы можно сначала проверить есть ли такой элемент в нашем массиве, то есть только если cnt[cur].count(s - sumrg) = true увеличивать ответ. Для перебираемых подмасок можно отсекать перебор по текущей сумме для подмаски и по количеству восклицательных знаков для текущей подмаски. Также понятно, что не имеет смысле наклеивать восклицательные знаки на кубики на которых написаны числа большие 18, так как 19! точно больше чем 1016, что по условию является верхним ограничением для s.

Асимптотика решения — O(3((n + 1) / 2) * log(maxcnt) * k), где n — количество кубиков, maxcnt — максимальный размер ассоциативного массива, k — количество восклицательных знаков.

Разбор задач Codeforces Round 297 (Div. 2)
  • Проголосовать: нравится
  • +110
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

This is fastest Editorial I've ever seen

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

Fastest editorial so far! Thanks!

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

your rounds are awesome :D won't miss any of them :3

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится -8 Проголосовать: не нравится

Да, я неправ :(

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

What was test case 4 for problem C??

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

    Now we can see it's 8 5 3 3 3 3 4 4 4. I got 3 WAs on test 4 because of misunderstanding the problem statement

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

      i too misunderstood the problem statement :(

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

        What's that? I don't see it... Where does the "25" come from?

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

          It was the sum of all possible rectangles that could be made. Not the max of those.

          I also got to know now ! :(

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

          We can choose {5-1, 4, 4, 4} to make a rectangle and choose {3, 3, 3, 3} to make another one, and we get the maximum total area which is 16 + 9

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

        me too!but I understand it finally

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

    we convert 5 to 4 so we have 4, 4, 4, 4 -> 4 * 4 = 16 and we have 3, 3 , 3 ,3 — > 3 * 3 = 9 so total maximum area is 9 + 16 = 25 not 16 !

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

    In problem C use long long Because the input and Output is large it can't covered by long

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

Thank you for nice problems:) BTW, for 530E, I think associative array cnt should be map < long long, int >

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Подскажите, что нужно было делать в задаче D? Валится на 12 тесте, и потому даже нет возможности узнать, что конкретно работает не так... Делал следующее, шел по массиву, от каждой свободной клетки поиском в глубину находил компоненту связности, где данная клетка лежит. У данной компоненты находит левую, правую, верхнюю и нижнюю границы и всё пространство между границами заполнял точками. Удивился, что падает на WA, а не на TL, в чём может быть проблема?

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

    Да, я делал так же, и у меня тоже WA на 12. Вот тест, на котором не пройдёт:

    3 4
    .***
    ..*.
    **..
    

    Видимо, просто эта идея не работает.

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

      Спасибо за тест, действительно упало решение.

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

Im getting wrong answer on test 4 problem C....why? where 25 comes from?

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

Есть в математике такая вещь ТРАНСНЕРАВЕНСТВО: Пусть {i1,…,in} — некоторая перестановка набора {1,…,n}. Если x1≥⋯≥xn,y1≥⋯≥yn, то x1y1+⋯+xnyn≥x1yi1+⋯+xnyin≥x1yn+⋯+xny1.

отсортировал все палки по длине и разбил на пары с максимально возможнымми длинами, по транснеравенству произведения пар с наибольшими последовательными длинами должны давать максимальное произведение. Не зашел 37 тест(( Такое решение неверно?

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

    Тоже пытался воспользоваться транснеравенством во время контеста, однако забыл про типы данных и зафейлил еще при проверке третьего теста из условия на собственном компьютере. А так — решение рабочее. codeforces.ru/contest/525/submission/10478118

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

    Во втором if'е не хватает фигурных скобок. Под него попадает не весь кусок кода.

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

Can someone please explain why in Problem C the output for test 4

8
5 3 3 3 3 4 4 4

is 25 instead of 16? Thanks.

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

    You can use 5 (-1), 4, 4, 4 for one rectangle and 3, 3, 3, 3 for another.

    4*4+3*3=16+9=25

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

    5 becomes 4, and then the rectangles are: { 4, 4, 4, 4 }, { 3, 3, 3, 3 }. First's size is 16, second's is 9.

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

    man i did the same mistake....i thought they need the maximum possible area....but they needed the sum of all maximum possible area... I think this problem should be reviewed...

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

      I totally agree with you. A lot of people including myself misunderstood the problem statement. It should have been something like:

      "..maximum total area of ALL THE POSSIBLE rectangles that Ilya can make .."

      Aside from this the round was great. Many thanks to the problems setter =).

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

I liked E a lot, and I had the idea in contest, but made some stupid mistakes...Anyway, now, after the contest ended, I tried to find the bugs, and, apparently, I found them, but I have TLE because of map(I checked, not at the point when we insert in map, is because of the point where we are "querying" the map).Here is my source: http://codeforces.com/contest/525/submission/10476721

I really don't know what's so wrong.It inserts me in map in 0.5 seconds and queries in 18 seconds...

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

    On lines 40,41 and 78,79 you make about 2^n iterations, wich is way larger than 3^(n/2), wich is the optimal complexity for finding all the submasks of a mask.

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

      It's not because that.I reimplemented it and it was the same thing.The idea is that I have 2^n and it enters in for just for 3^(n/2) :-P .Here is the new source: http://codeforces.com/contest/525/submission/10477139 I thought it was easier for someone to look at th first source ant that's why I posted that one.

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

        First, don't try this _j < (1<<n_bit);, it is slow. Second, you could implement 3^(n/2) in a faster way by just iterating the masks from 1 to 3^(n/2) and considering : 0->not taken 1->taken without factorial 2->taken with factorial

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

    Try unordered_map.

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

      I'll try it but I still can't believe that it take it so much to query, knowing that it inserts in 0.5 seconds with the same complexity

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

    As editorial said, "To accelerate our programm we may increase answer only if cnt[cur].count(s  -  sumrg)  =  true."

    The operator[] creates a new object if it wasn't there before, which will slow down subsequent queries by a bit.

    Accepted: 10478038

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

      WOW, it's a really big difference of times just because that...I'll never make the same mistake :))Thanks

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

Hey, there is a O(n) solution, we can just use BIT and mark the intervals being chosen each day. Then segments having even count sustain their original order and the ones with odd cf, are transformed.

»
9 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Pasha and string can be solved in O(n) time using BIT. :)

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

Probably a silly mistake on my part, but This code outputs the right answer (8) for the first test case (4, 2 4 4 2) when i debug it on my machine but outputs 4 and fails on pretest 1 when tested on the website. I know the algorithm is greedy and might not be right but why does it have a different output? Thanks in advance!

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

Please help me with the logic used in the problem 525B especially the 'sum' part ? :

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

    So, let's start with an example word "abcdef".

    Our possible operations include:

    1 (reversing letters from [1,6]),

    2 (reversing letters from [2,5]),

    3 (reversing letters from [3,4]),

    4 (reversing letters from [3,4]),

    5 (reversing letters from [2,5]),

    6 (reversing letters from [1,6]),

    I will call operations rather by their intervals now, I think it's easier to understand that way.

    Now focus on the first letter "a" for a while. It can only change it's place after reverse operation [1,6]. Where it can go? Only at the end, swapping with "f". And after the second one of that type? "a" will go back to the first position again, swapping with "f". No other operation can change position of "a", all other operations will only change something inside the word, between "a" and "f". So how can we now where is "a" after all operations? Well, that's simple, let's count all of the type [1,6], if it's even then "a" stays on the position 1, if it's odd then "a" is swapped with "f". If you can't see it just do few operations [1,6] in your head or on piece of paper and look what happens. Let's store information about number of operations [1,6] in sum[1], you will see why in few seconds.

    Ok, moving onto "b". "b" can be swapped with "e" after operations [2,5], but also [1,6]. "Even-odd rule" works there two, as it's really the same thing — only changes "b"-"e" are possible and they come after [1,6] or [2,5]. Ok, so if we store number of operations [2,5] in sum[2] only thing we need to know is number of operations [1,6]. Now sum[1] comes into play :) Only thing we have to do for "b"-"e" is check if sum[1] + sum[2] is odd and, if it's the case, swap "b" with "e".

    One thing you may not see now, but it's also the small problem — for position 3 it's easy, just sum up sum[1] + sum[2] + sum[3]. But you would have to do that addition for every position from the first half of the string and for long ones it can be little bit painful. Don;t worry though, there is one Jedi trick :) Just iterate over all i's from 1 and do:

    for (int i = start_position; i < s.length() / 2; ++i) {

    if (i != 0) sum[i] += sum[i — 1];

    //computations here

    } In first iteration we have sum[1] in sum[1], in the second one sum[2] + sum[1] in sum[2], in the third one sum[3] + sum[2] + sum[1] in sum[3] and so on. Just what we needed :)

    EDIT: My code: http://codeforces.com/contest/525/submission/10479343

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

For E can't we just loop over all k-sets in a maximum of (25 choose 12)=5*10^6 ways and update the sum from one k-set to the next in O(1) by simply changing one factorial to a different factorial? (Of course we ignore factorials which are too big)

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

В задаче D непонятно почему если в квадрате 2 х 2 есть ровно одна стена, то ее нужно удалить. Кто-нибудь может доказать правильность этого факта?

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

    Три пустые клетки должны лежать в одной комнате, а комната прямоугольная.

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

Can someone explain to me the solution for #4? I used BFS on a space, then got the width and height of the total room, and within the width and height set everything to a '.'. It gives me a wrong answer on case 20, but the case is too large.

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

    I don't understand solution well enough to explain it, but those are smaller counterexamples to your solution:

    the one showing something is wrong with your bfs

    3 3

    **.

    **.

    ...

    and the one showing "one-time" bfs is not enough

    3 3

    **.

    .**

    ...

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

In the editorial's solution for Pasha and String

Then we need to count array sum[]. In sum[i] we need to store count of reverses of substrings, which begin in positions which not exceeding i.

I don't get this statement. Could someone explain it in greater detail?

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

In problem E you don't need to sort the given array.

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

Пытаясь сдать задачу D, столкнулся с непонятным мне багом: локально (Dev-C++ 4.9.9.2) этот код 10479962 исполняет первый тест правильно, а на Codeforces и Ideone — нет. В чем может быть проблема?

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

I tried to solve problem D in the following,

Find the connected components from the given maze. And also find the boundary of the connected component.( top,bottom, left,right). And make all the cells in the maze which lies in the boundary to ".".

Also kind of handled case like this with double run of algo.

.... .... ..*.. ...*. ....*

Is there anything wrong with this approach ? This approach was failing for test case 12.

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

    Consider this initial connected components:

    *********
    *1*******
    *1*******
    *1***3***
    *111*****
    *1*******
    *1*22222*
    *********
    

    When you only draw dots on the boundary you get:

    *********
    *1112222*
    *1*1***2*
    *1*1*3*2*
    *111***2*
    *1*1***2*
    *1122222*
    *********
    

    You don't discover that 3 is also part of the 1-2 room.

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

      After you find a boundary ( top, bottom, left, right), my idea is to convert every cell inside the boundary to "." .

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

        hello , your idea is correct, you have a lot of rectangles , but you have to merge rectangles that intersect, and then fill the rectangles with '.'

        the most difficult is solve the last part, how do you merge rectangles optimaly???

        my idea was make a sweep line on x , and then merge rectangles on y , keep a structure, the code is very difficult , therefore is better analize the problem and make it more easy!!

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

        I used the same method as yours, but I got TLE on test 12. I don't know why I got TLE, because I don't think it would cost such long time.

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

Could somebody help me come up with a case where my solution fails?

I chose to forgo the option of keeping track of how sticks of length L I had. Instead, I sorted the sticks in descending order according to their lengths. Then, I tried greedily choosing the four largest sides, assuming that the difference between the opposing was always less than or equal to 1 (otherwise, I would be unable to cut accordingly). Thanks for your help in advance.

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

For problem E, I din't pass the system test if I used map(10491477) but passed with unordered_map(10491490). But, interestingly, 10480213 (from which I got the idea because it was easy to understand) passed system test. What is going on?

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

Что не так с этим решением (кроме того, что массив должен быть в 2 раза больше): 10460355?

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

Какую роль играет сортировка в задаче E? По идее ведь что с ней, что без неё, должно быть одинаково, однако без сортировки не заходят тесты, может кто объяснить почему?

Upd.: Извиняюсь, была другая ошибка. Интересно вышло, что при сортировке, ошибочное решение проходило 89 тестов, а без — 26. Всё-таки сортировка не нужна, не понятно зачем авторы указали, что её необходимо сделать.

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

I get wrong answer for problem c for test case 37. Can somebody provide a counter example for my approach. 10502423

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

Hello, I tried to solve problem D about 20 times but verdict is always "runtime error on test 92". Could you help me, please? Regards 10507530

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can anyone discuss solution of D and proves of solution?

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

How to prove that the algorithm for Problem D removes the minimum number of walls??

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

could someone explain where my solution goes wrong for 525C . I am having wrong answer in test case 37 . http://codeforces.com/contest/525/submission/10501081 . My output : 11234878867001938 jury's answer : 11234878866984153 . Thank you for help

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

    Try the following test case:

    6
    7 7 6 6 6 4
    

    Should output 42. But yours outputs 43. Third time through the loop i=1,area=1,count=2. So you add area to totalarea which you shouldn't.

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

How can one prove the solution to D? (I mean the property of 2x2 matrix)

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

Can someone explain the solution for D better? I honestly can't understand the editorial's solution, as the writer's English is not the best.

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

In problem D, my dfs solution is accepted but when the same logic is applied using bfs i am getting tle. Can anyone guide me why is it hapenning ??

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

Почему валится 10574466, но не валится 10571455 ? Никак не пойму. Код почти одинаковый. В чём тут разница?

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

can anyone explain why am i getting wa !!

TIA

here is maah code

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
  1. In problem B : How I should approach if given problem is like given index l and r . You have to reverse the string the string from a[l] to a[r].
  2. What would be its approach ?
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem A ,I used unordered multiset to store the keys, but why its getting TLE in test 8?