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

Автор ADJA, история, 2 года назад, перевод, По-русски,

550A - Две подстроки

Задачу можно решать разными способами. Авторское решение такое: проверим две возможности — когда подстрока "AB" идет первее "BA" и наоборот. Проверять можно следующим образом: найти самое первое вхождение "AB" в исходной строке и рассмотреть подстроки длины 2 правее. Если среди них встретилась подстрока "BA" — ответ "YES". Аналогично проверяется второй случай. Если оба варианта не выполнены, ответ "NO". Сложность решения — O(n), где n — длина исходной строки.

550B - Подготовка олимпиады

Задачу можно решить полным перебором всех подмножеств задач (всего 2n подмножеств). Для каждого из подмножеств проверим, удовлетворяет ли оно условиям задачи. Найдем сумму сложностей всех задач, входящих в подмножество, и убедимся, что она лежит в отрезке [l, r]. Найдем также разность между сложностями максимально сложной задачи и минимально сложной задача подмножества и убедимся, что она не менее x. Если подмножество задач удовлетворяет условиям — увеличиваем общий ответ на 1. Сложность решения задачи — O(2n·n).

550C - Делимость на восемь

Задачу можно решить как минимум двумя способами.

Первый — через "школьный" признак делимости на 8 (число делится на 8 тогда и только тогда, когда число, образованное его последними тремя цифрами, делится на 8). Таким образом, достаточно проверять на делимость на 8 все однозначные, двухзначные и трехзначные числа, образуемые из исходного вычеркиванием цифр. Это можно сделать за O(n3) вложенными циклами по цифрам числа, где n — количество цифр числа.

Второй способ использует динамическое программирование. Будем считать величину dp[i][j], 1 ≤ i ≤ n, 0 ≤ j < 8 — величину, равную 1, если из префикса числа длиной i цифр можно вычеркнуть несколько цифр так, что остаток от деления полученного числа на 8 равен j, и 0 в противном случае. Формулы для пересчета: пусть i-я цифра числа есть ai, тогда dp[i][aimod8] = 1 (по смыслу — однозначные числа), dp[i][(j * 10 + ai)mod8] = max(dp[i][(j * 10 + ai)mod8], dp[i - 1][j]) (по смыслу — дописывание текущей цифры), dp[i][(j * 10)mod8] = max(dp[i][(j * 10)mod8], dp[i - 1][j]) (по смыслу — вычеркивание текущей цифры), где 0 ≤ j < 8. Ответ "YES" будет в том случае, когда для некоторого i выполнено dp[i][0] = 1. Для восстановления ответа также нужно завести дополнительный массив prev[i][j], который будет хранить индекс k такой, что при подсчете dp[i][j] пересчет был сделан из dp[i - 1][k]. Сложность такого решения — O(8·n).

550D - Регулярный мост

Докажем, что если k — четное, то решения не существует. Пусть наш граф содержит мост(ы), k = 2s — четное число, степени всех вершин графа равны k. Дерево двусвязных (реберно двусвязных, далее слово "реберных" будет опущено для краткости) компонент исходного графа содержало компоненту, связанную с остальной частью графа только одним мостом (не несколькими мостами!) (на самом деле таких компонент как минимум две, но нам достаточно одной).

Рассмотрим эту компоненту. Удалим мост, связывающий ее с остальной частью графа. Тогда в ней будет всего одна вершина степени k - 1 = 2s - 1 и какое-то количество вершин степени k = 2s. Но тогда она будет содержать только одну вершину нечетной степени, что невозможно.

Построим такой граф для нечетных k. Пусть k = 2s - 1 — нечетное число. Рассмотрим отдельно случай k = 1, тогда, очевидно, подойдет дерево из двух вершин.

Для k ≥ 3 сперва найдем минимальное количество вершин искомого графа. Граф будет содержать как минимум один мост и как минимум две двусвязные компоненты, связанные с остальной частью графа одним мостом. Каждая из этих компонент содержит не менее k + 2 вершин (так как одна вершина связана k - 1 ребрами с другими, остальные имеют степень k = 2s - 1 — нечетное число, т.. количество этих вершин должно быть четным, в то же время оно не может быть меньше k = 2s - 1, то есть оно будет не меньше k + 1, что в сумме с одной вершиной степени k - 1 даст k + 2).

Следовательно, во всем графе будет не менее 2k + 4 вершин. Построим граф с таким количеством вершин.

Занумеруем вершины первой компоненты с 1 до k + 2, вторую компоненту построим аналогично первой. Пусть вершина 1 связана мостом с второй компонентой. Соединим ее k - 1 ребрами с вершинами 2, 3, ..., k. Вершины с номерами 2, 3, ..., k соединим между собой попарно и потом между каждой соседней парой, например 2 - 3, 4 - 5, ... (k - 1) - k, выкинем ребро. После соединим вершины 2, 3, ..., k с вершинами k + 1 и k + 2. Также соединим вершины k + 1 и k + 2 между собой. Тогда все вершины компоненты, кроме первой, будут иметь степень k. Точно так же создаем вторую компоненту и соединяем мостом с первой. Искомый граф построен и содержит O(k) вершин и O(k2) ребер.

Асимптотика решения — O(k2).

550E - Скобки в импликациях

Пусть дано выражение , ai0 или 1 для всех i.

Покажем, что решения нет только в двух случаях.

1) an = 1.

Это следует из того, что , т. е. никакая расстановка скобок не сможет заменить самую правую 1 выражения на 0.

2) Выражение имеет вид или является его суффиксом, содержащим не менее 2 аргументов.

Это несложно доказать индукцией. Для суффикса невозможность расстановки скобок очевидна, для более длинных суффиксов любая свертка импликаций либо приведет к тому, что справа появится 1, либо уменьшит число единиц в выражении на 1.

Покажем, что в остальных случаях решение есть.

1) Для выражения 0 ничего делать не надо — ответ 0.

2) Выражение вида . Можно не расставлять никаких скобок, так как значение такого выражения без скобок равно 0.

3) Выражение вида , где вторая опущенная часть состоит только из единиц. Тогда .

Асимптотика: O(n).

 
 
 
 
  • Проголосовать: нравится  
  • +93
  • Проголосовать: не нравится  

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

please correct the format of problem C editorial,, it seems print the date

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

Problem C is very easy. Don't need Dp

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

Can someone tell me why my A got TLE? : http://codeforces.com/contest/550/submission/11420305

I used Regexp in Ruby.

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

Do you mean bi-connected component by strongly connected component? If not, what is a strongly connected component in an undirected graph, I tried to google it and found nothing :)

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

    Me too, I don't understand why there is a strongly connected component in undirected graph.

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

    no bi connected components are different . Suppose you have a undirected tree then it is strongly connected but not biconnected. Biconnected components means there are always atleast two edge disjoint path between any pair of vertices in the component. It means there is no bridge in that component.

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

      Good to know about biconnected. So what does strongly connected mean?

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

in the bottom of the explanation for C there is a O(8·len). but i think that in the big O notation you shouldn't write constants.

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

    Yes, you are right. It's written in such a way to show that if you have the same problem with some d instead of 8, you can solve it in O(d·len).

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

      Hey!

      For problem C, can you please explain the method to restore the answer using prev[i][j] in its DP solution?

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

        You should calculate it when you are finding DP: for example,

        dp[i][a[i]] = 1;
        prev[i][a[i]] = -1;
        if (dp[i - 1][j] == 1 && dp[i][(j * 10 + a[i]) % 8] == 0){
            dp[i][(j * 10 + a[i]) % 8] = 1;
            prev[i][(j * 10 + a[i]) % 8] = j;
        }
        if (dp[i - 1][j] == 1 && dp[i][j]  == 0){
            dp[i][j] = 1;
            prev[i][j] = j;
        }
        

        When you are printing answer, you may do it recursively, like

        void recursive_print(int i, int j){
            if (prev[i][j] == -1){
                cout << a[i];
                return;
            }
            int k = prev[i][j];
            recursive_print(i - 1, k);
            if ((k * 10 + a[i]) % 8 == j){
                cout << a[i];
            }
        }
        
        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thank you for your reply. I have one more confusion though.

          When we cross out the 'i'th digit (i.e when we do not consider it), why is the DP equation : dp[i][(j * 10) % 8] ?

          I mean, why are we doing (j*10)%8 ? Why not just leave it as it is, because we are crossing out the ith digit?

          Should it not be like below.?

          if (dp[i — 1][j] == 1 && dp[i][j]  == 0){ dp[i][j] = 1; }

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

    Actually O(8*len) = O(len). It's not necessary to write the constant, but you can.

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

Seems Codeforces has new feature: autocomment about post changes. Please ignore this comment.

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

    The idea was not to edit such auto-comments so that everybody ignore them =) I guess we'll remove the option of editing auto-comments.

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

In problem C, I think the first approach can be better than O(len^3), O(125*len) can bee achieved, check 11430246

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

hey can someone explain how people solved B without using recursion ?

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

In problem D, how did you come up with the magic figure of 2k+4?? Can you provide any intuition for that?

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

    Actually it is the minimum needed number of nodes (we thought about requiring it, but agreed it would be too hard).

    I or Timur will post the proof later, if you want it and won't come up with it yourself :)

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

      Hi

      Please post explanation if possible.

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

        Hi. Actually I just noticed that this proof is available in the Russian version of editorial :)

        Here is the translation:

        For k ≥ 3 let's find minimum number of nodes needed. The graph will contain at least one bridge and at least two strongly connected components, that are connected with other part of the graph with exactly one bridge. Each of these components will contain at least k + 2 nodes (one node that is connected to the bridge is connected with k - 1 edges with other nodes in the component. Other nodes in the component will have degree k — odd number, so the total number of them should be even, to make component right graph by its own [see handshaking lemma]. So this min number of other nodes is k + 1. Therefore total number of nodes in the component is minimum k + 2 ---- one incident to bridge, k + 1 not incident).

        There are at least two components with at least k + 2 nodes in each, so minimum is 2k + 4.

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

    When we want find a bridge side in th graph . so we can think of two grpah has only one vertex's degree is k-1 ,other's degree is k. And then we connect the graph and another.If we want to get the grpah which has only one vertex's degree is k-1 ,k+2 vertexs can get the graph.... And maybe solving other constructive algorithms can help you.

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

    i didnt, i went for 4*k-2. its pretty easy actually. first consider the bridge and name the vertices u and v. then add k-1 other vertices to the right side and connect all of them to v and them add another k-1 vertices to the right side and connect all of them to the previous k-1 nodes so now those k-1 nodes + v have degree k but the new vertices have all degree k-1 since k is odd then k-1 is even and you can connect every two adjacent pairs of the new k-1 vertices to each other so they now all have the degree k and now do the same thing for u and you are done.

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

    For me its more like 2 * (k + 1) + 2, which is equal to his formula.

    To get weight k in one component we need exactly k + 1 nodes. We have two components, so its 2 * (k + 1). Also we have a bridge, which is 2 more.

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

      Shouldn't the degree of EVERY node be equal to k? The degree of the (k+1) nodes in each component is k, but what is the degree of the 2 nodes which form the bridge? Isn't it just one?

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

        Yes it should. And it would :)

        My algorithm: Generate graph of k + 1 nodes, each connected to each. Remove k-1 edges from there and connect these nodes to the bridge one. After that, you'll have k+1 nodes with k degree, and bridge node with k-1 degree. Duplicate this graph, so you get two of them. Connect bridge nodes. Solved.

        UPD: Forget to tell, that we should pick edges for removing carefully — each of them should have unique nodes connected, so no duplicated allowed (because if any dup k-degreee would be violated)

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

The solution for E is not clear to me Please help if possible

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

    You must be clear fist on the fact that (x->1 = 1)

    This means that the last number in the input must be zero.

    So now our sequence takes the form "xxxxxx...0"

    Now we want to make the second to last number equal to 1 in order to have (1->0 = 0)

    Now we have two cases:

    • Case 1 "xxxxxx..10"

    You can just leave the sequence as it is ... all the numbers to the left of the 1 will just have no effect .. and then the final value will be (1->0 = 0)

    • Case 2 "xxxxxx..00"

    We need to turn this new 0 into a 1 somehow in order to be like case 1.

    In order to get rid of this zero we have to match it with some other number.

    From the rules, we have (1->0 = 0) and (0->0 = 1), so obviously we will try to match this 0 with another 0.

    So we will search for the first 0 to the left of this 0.

    So our sequence now takes the form "xxxx...0111..1100"

    We can get rid of this group of 1s by grouping (1->1->1->1->....->0 = 0)

    So now our sequence takes the form "xxxx...0(111..110)0" = "xxxx...000"

    Now you will just have to group these two 0s together to change them into 1

    "xxxx...(0(111..110))0" = "xxxx...(00)0" = "xxxx...10" = "0"

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

I was unable to complete my code of D during the round. I did it differently and it was more intuitive.

Create a bridge. Than create (k — 1), K(k, k) (complete bipartite graphs). Remove 1 edge from each (k — 1) bipartite graphs. Connect nodes of removed edges of (k — 1) / 2 bipartite graphs to the one endpoint of the bridge and of other (k — 1) / 2 bipartite graphs to the other end of the bridge.
So, total nodes = (2 * k * (k — 1) + 2), total edges = (k * k * (k — 1) + k).
My submission : Code
  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Could have done better by creating just 2 such bipartite graphs and removing (k - 1) / 2 edges from each one of them.

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

      I suppose you meant edges not nodes.

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

      Could have done even better by taking a completeGraph(k)[or K(k)]. Refer: http://codeforces.com/contest/550/submission/11437241

      Create K(k + 1) out of vertices 1..K + 1, remove (K - 1) / 2 edges, where all vertices chosen are different. Connect these k - 1 distinct vertices to the bridge vertex 2*k + 3. Connect 2*K + 3 to 2*k + 4. Now construct K(k + 1) out of vertices K + 1 .. 2*K + 2, and proceed similarly.
      

      EDIT: LOL, just realised the editorial does the exact same thing.

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

Problem B can be solved with partial sums?

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

    Well, you can find all permutations of problems and test each segment of each permutation using prefix sum, but the complexity would be O(n!*n^2) and you would get a TLE. I don't know if we can do better than this (using partial sum, of course).

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

In the recurrence of problem C,

I think when we are crossing out current digit,

recurrence should be:

dp[i][j] = max(dp[i][j], dp[i - 1][j])

Correct me If I am getting it wrong?

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

For problem D, if k is even, then Eulerian cycle exists, thus there are no bridges.

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

We can solve problem C in O(1000 * len) without using dp. First find all numbers which are less than 1000 and divisible by 8. Convert them into strings. Now check if any one of them is a subsequence of the given string. This can be done in O(len).

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

E easier than D :)

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

    I also think that E is easier than D but that is subjective. There are [to the date] 363 accepted solutions for E which is lower than half those for D (754 accepted solutions).

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

What is the optimal solution for question B? Thank You

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

Благодаря этому контесту я понял, что регэкспы это круто, но только когда с ними не перебарщивать.

Как же хорошо, что я не осмелился на контесте писать это решение в строку)

И да, я впервые стал синим! Спасибо за отличный раунд!

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

I can't get what the editorial says about the dynamic solution for problem C. Can someone tell me how is it working with a c++ code?

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

can anyone provide dp solution for problem A? As dp was a tag in problem a

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

You don't even need to process the 3 digit numbers in 550C - Divisibility by Eight , It can be done by adding Two Zeros as the Prefix of that number , which would transform a single , two and three digit number to three , four , an five .. which can easily processed by the O(N^3) solution.

UPD : Just don't print the leading zeros

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

In problem C I generated first 125 numbers which are divisible by 8, then convert each of them to string and find if any of them appears in the given string as a substring. This can be done in O(125*len)

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

so many brute questions , not sure is codeforces or bruteforces.

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

I really liked D! Theoretical graph problem is much interesting than a algorithmic graph problem.

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

Somebody should fix the tags for Div 2 Prob A. Seems like someone went crazy and added every possible tag to the problem.

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

in 550C editorial what is meant by "crossing out"

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

11447158 Is it solution for C in O(n)?

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

You could solve C in linear time ( O( (1000/8) * len ), actually ): just check for each multiple of 8 less than 1000 if it is subsequence of the input.

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

In Problem E, when I used the inbuilt 'string' in C++, I got a TLE at case:8. When I replaced the inbuilt 'string' with the character array char[], it got AC.

Here is my code using inbuilt string which got TLE : http://codeforces.com/contest/550/submission/11455328

Here is my code using character array which got AC : http://codeforces.com/contest/550/submission/11455369

Any reasons for that?

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

    Anyway, array of characters is a slightly faster than the string class - but it should not make sense and should not give an advantage to who uses array of characters instead -

    but someone may use the string to produce a much slower running code inadvertently, How is it possible ?

    Every appending operation uses + has a complexity O(n) where n equals to the length of the string,
    - since C++ does a resize operation -
    you may use the built-in push_back function instead or even initialize your string to have such a maximum length and append elements by a direct access using index . look here is your first submission, just swap + by push_back and got AC in 139 ms

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

Can someone explain the DP solution from the editorial ? I dont understand this part-> dp[i][(j * 10 + ai)mod8] = max(dp[i][(j * 10 + ai)mod8], dp[i - 1][j]) , what is this supposed to do ?

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

Is there a reason that you choose to use 2k+4 nodes in 550D?

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

For problem B I see many solutions have this statement if(i&(l<<j)){...} in the 2^n loop, what's this mean?

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

    (i&(1<<j)) is basically used to check whether the j-th bit in bit representation of i is set or not.

    As an example, consider i=5(101). (i&(1<<j)) will be true for j=0 and j=2.

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

550C- Which data type should I choose for the integer n <= 10^100 in C++? I am using long long, but with it test# 23 gives incorrect answer probably because of limit of long long.

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

Can somebody please explain why we do we have always this general notation of for(int j=0; j < x ; j++ ) dp[( 10*j + added digit ) %x ] +=dp[j] . I mugged it up . but now i want to know reason behind this

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

I didn't get the idea behind the DP solution for the problem, "Divisibility by Eight." Could someone kindly explain the solution in greater detail?

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

    Let's first define DP state as dp( index , mod) = {0,1}, which means using the digits between the leftmost digit and digit at index, is it possible to make a number x such that x%8 == mod

    We loop through all digit (i.e. loop through all index) for each digit, we have two choices naturally:

    1. Ignore this digit (i.e. delete it)
    2. Append this digit

    For the first choice, dp( index , mod) |= dp( index -1, mod) for all mod

    For the second choice, it becomes tricker.

    Consider dp( index -1, mod ) for all mod

    If it is true, then if we append current digit,

    the modular at index will become ( mod *10 + digit( index ))%8

    So we just update this way: dp( index , ( mod *10 + digit( index ))%8) |= dp( index -1, mod)

    Here's my code using this idea: 12143232

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

      Hey kirakira amazing explanation! But i would like to point out that even though your solution got accepted, the way you handled the dp table for filling the store table .. distorted the dp table filling base logic and even confused me in the beginning.

      You just cannot assume dp[0][0]++

      even though you have added store[0][0]=" " and further in the final ans checked

      for(int i=0, l=strlen(s); i<l;i++) 
      if(dp[i][0] && store[i][0].length())
      { cout << "YES" << endl << store[i][0] << endl;  return 0;}
          cout << "NO" << endl;
      

      This way it distorts the dp table filling logic and even confused me in handling the base case. This can be managed just by adding

      for(i=1;i<n;i++)
      	{
      		for(j=0;j<8;j++)
      		{
      			dp[i][d(i)%8]=1;
      			store[i][d(i)%8]=s[i];
                              //Added the above two lines instead
      			if(dp[i-1][j])
      			{
      				store[i][j]=store[i-1][j];
      				store[i][(j*10+d(i))%8]=store[i-1][j]+s[i];
      			}
      			dp[i][j]|=dp[i-1][j];
      			dp[i][(j*10+d(i))%8]|=dp[i-1][j];
      		}
      	}
      

      The rest is same .. this is my accepted solution 16596112 . Still better explanation than the editorial :) It helped me. Thank you!

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

What on Earth has happened for the test on question A? My code is returning "NO" for the input "ABA", but when I submit it, is says that "YES" is being returned for the string "ABA".. What?!

#include <iostream>
#include <string>

using namespace std;

int main() {
  int n, i;
  bool ab, ba = false;
  cin >> str;
  n = str.size();
  i = n-1;

  while (i >= 0) {
    if (!ab) {
      if (str[i] == 'B') {
        i--;
        if (i >= 0) {
          if (str[i] == 'A') ab = true;
        }
      }
    }
    if (!ba) {
      if (str[i] == 'A') {
        i--;
        if (i >= 0) {
          if (str[i] == 'B') ba = true;
        }
      }
    }
    i--;
  }

  cout << (ab && ba ? "YES" : "NO") << endl;

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

Need O(n*8) solution for problem 550C

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

Could not understand dp solution for C. Can you explain it more clearly with code? ADJA

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

Hi... .

Could you please help me with my code for problem 550A - Two Substrings?

submission: 21399858

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

Please explain me the dp solution of problem C . thanks in advance :)

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

awesome solution to div2 C !

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

if same ques with 9..then can we use 2nd approch?