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

Автор vovuh, история, 6 лет назад, перевод, По-русски

1144A - Разнообразные строки

Идея: MikeMirzayanov

Разбор
Решение

1144B - Удаления с меняющейся четностью

Идея: MikeMirzayanov

Разбор
Решение

1144C - Две перемешанные последовательности

Идея: MikeMirzayanov

Разбор
Решение

1144D - Приравняй их все

Идея: vovuh

Разбор
Решение

1144E - Медианная строка

Идея: vovuh

Разбор
Решение

1144F - Граф без длинных ориентированных путей

Идея: MikeMirzayanov

Разбор
Решение

1144G - Слияние двух последовательностей

Здесь есть другое решение задачи, оно довольно интересное! Спасибо, Roundgod!

Идея: vovuh

Разбор
Решение
  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

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

G Tutorial is not available?

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

In Problem G, I'm getting WA on test 12. Please help me out. 52149636

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

Why is problem D tagged as dfs and similar?

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

Interesting idea on E, very cool problem!

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

Solving E problem using Python gave TLE, don't know why. I stored the Number as int(base 26). Shouldn't it work?

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

    Nobody can see your submitted solutions. You're probably getting TLE because the operations you are doing on the numbers are too slow.

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

У меня, кажется, третий вариант решения G:

Пусть dp[i] — минимальное значение последнего элемента возрастающей последовательности, если элемент i принадлежит убывающей. Посмотрим, как нужно его обновлять:

  • из предыдщего элемента: всё просто, если $$$a[i - 1] < a[i]$$$, то $$$dp[i] = dp[i - 1]$$$

  • если предыдущий элемент не из убывающей, то нам подойдут все такие $$$j$$$, что между $$$j$$$ и $$$i$$$ массив строго возрастает, $$$dp[j] < a[j + 1]$$$ и $$$a[j] > a[i]$$$. Само $$$dp[i]$$$ теперь станет $$$a[i - 1]$$$. Сооствественно, для релаксации в этом случае, нам достаточно лишь существования подобного перехода. Для его быстрой проверки заведем ДО по значениям, куда будем записывать все такие $$$j$$$, что $$$dp[j] < a[j + 1]$$$ и запрашивать максимум на отрезке $$$[a[i] + 1, maxval]$$$, а после проверять, дейсвительно ли от полученного индекса $$$val$$$ до $$$i$$$ все значения строго возрастают. В реализации я это проверял массивом $$$lst$$$, где $$$lst[i]$$$ — максимальный индекс, в котором нарушается убывание слева от $$$i$$$

Код : 52119835

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

I don't understand E's editorial,can anyone please explain?What are we doing? I thought of seeing the string as base 26,so we can convert it into decimal and take the mean. For example: az = 26^0*25 + 26^1*0 = 25, bf = 26^0*5 + 26^1*1 = 31 now taking the mean we get 28,converting into base 26 we get 12 (26^0*2+26^1*1 = 28),which is bc. But for large string lengths we may have to do 26^100000,so I thought it is not feasible. What are we doing in this editorial?

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

    You misunderstood the meaning.We can represent the string to a number, with base 26. And then we can figure out that if string s is lexicographically smaller than t, the "number" which s represents is smaller than t's "number". So what we need to calculate is a "number" which is the median of [s's number, t's number]. We can Easily calculate it by writing "BigIntegar", to storing big number and doing operations. Here's my Code Link: Here

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

      Thanks a lot for replying,in author's code,I understand the string is stored as int with base 26,but what are the 2 operations done? Is he adding the 2 vectors?

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

        2 vectors represents 2 BigInt(base 26). so, now he add the BigInt and then divide it by 2. (Same as we did addition and division with paper and pencil in childhood :) )

        Then print the vector as characters.

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

This is a real Div.3 :)

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

Another solution to G by considering whether the max.element in the array is in the decreasing or increasing subsequence:52159992

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

anyone please help. In problem F, why my code give me Runtime Error on test 15?.

My Submission: 52160039

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

Runtime error in F: can someone help me debug: https://codeforces.net/contest/1144/submission/52208937

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

    maybe it's the for-loop for finding the largest degree

    you iterate it for i = [0, m), while vector "graph" has the size of n. RTE when m > n.

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

for E:someone plzz explain how division by 2 is done in 26 base

for (int i = 0; i <= k; ++i)

{

    int rem = a[i] % 2;

    a[i] /= 2;

    if (i + 1 <= k) {

       a[i + 1] += rem * 26;

    } else {

       assert(rem == 0);

}

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

    If the digit in the pos[i] is not divisible by 2, you can just pass a one to the next digit, a 1 from $$$1*26^i$$$ is equivalent to 26 in $$$26^\left( i-1 \right)$$$, if it is divisible by 2 then you just need to divide it by 2

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

problem ID:1144F

problem F is also done by BFS

problem F code(happy coding)

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

Can I solve E using big integer?

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

for problem g is this correct approach? let say i have two array X(increasing),Y(decreasing) and A is Merge(X,Y). Find the longest increasing sequence of A this sequence will contain X and atmost one element of Y and after removing that element from Y Y will still remain decreasing.

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

Why is this solution for E giving TLE? https://codeforces.net/contest/1144/submission/52223063

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

    You are doing ans = ans + (char)(median[i] + 'a'); This takes more time as compared to ans+=(char)(median[i] + 'a'); I am not sure of its reason. But i too have faced similar issues before.

    Can someone explain why this removes TLE?

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

there is a another way to solve problem G
first we found the LIS of the array and then there is a fact : if we can split the given sequence a into one increasing sequence and one decreasing sequence then at most one of the elements of the LIS could not appear in x ( x is the increasing sequence ) otherwise in the y ( the decreasing sequence ) we have two numbers A , B which a[A] < a[B] and A < B and its impossible so if we fix which index i is not gonna appear in x we can solve the problem

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

In problem E, why is it only allowed to do a[i] %= 26 when i > 0?

For this test case, for example:

6

nijfvj

tvqhwp

The sum in the base 26 is: 33 3 25 13 17 24

Why is it allowed to have this "33" in the first position?

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

    In my program,its allow a[i] % 26 in i = 0

    but if u do that, you need to deal with leading zeros,it's a little bit more trouble, but it doesn't really matter.

    For example

    33 3 25 13 17 24 -> 1 7 3 25 13 17 24

    then u div 2

    0 16 14 25 19 21 25

    now,u need cheak the zero,if u dont do that ,the answer will be an extra a

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

Help me! I dont understand print problem F in tutorial: cout << (color[e[i].first] < color[e[i].second]); ???????????? please

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

    when you split vertices in to two part . you want obtain direct of edges such that every edge in part one direct to the second pare or you can direct all edges from second part to the first part . and we know that every edges has two end point such that one of them from first and one of them from second (because its bipartite) so if color[first endpoint] < color[second endpoint] that means color[first endpoint] = 0 so that condition return 1 and otherwise return 0

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

In editorial 'G',what is the meaning of 'maximum possible minimal'?

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

    minimal element from the sequence is a const value , this const value be maximum as possible means .

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

Somebody please tell me why this submission 52323233 works but this submission 52321524 does not ??

The only difference in both the codes is that in accepted one, I've accepted the input as strings while in wrong answer I've accepted them in character arrays

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

Первый раз увидел на контестах длинную арифметику. Когда залил на питоне Медианную строку и увидел TL, подумал, что решение состоит в другой идее)

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

I can not understand the tutorial of problem G.

Please anyone Explain the tutorial.

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

In problem F,the solution does not include the visited array.So,won't it end in a infinite loop and give tle as it will keep on checking two vertices again and again?

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

    color acts as a visited array. If any node has color other than -1 means it is already visited.

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

But I my opinion , the statue may be dp[0][i] represent that "The i-th element is in increasing sequence and the max possible element in the decreasing sequence",and dp[1][i] represent that "The i-th element is in decreasing sequence and the min possible element in the increasing sequence" May be I am Wrong ,But I hope you can correct my mistake , Thank you

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

What is the difference among test 7-10 in G?They are too similar.I WA on # 10 and I don't know why

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

Can someone explain why it's (color[left vertex] < color[right vertex]) in F's solution of author in the cout section