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

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

1095A - Повторное шифрование

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

1095B - Стабилизация массива

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

1095C - Степени двойки

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

1095D - Хоровод

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

1095E - Почти правильная скобочная последовательность

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

1095F - Сделай связным

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

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

In problem C, what if the constraints for n and k are 1018 ? Is there any other better solution possible since the given one will run out of space and time !

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

    since in worstcase you need to print k numbers... there is no way... if we change the output format to print tuples (2^x, count) it is possible

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

I would like to know if my AC algorithm for problem D could actually be hacked somehow

https://mirror.codeforces.com/contest/1095/submission/47607217

What the program does is:

  1. If the I kid remembers kids A and B in front of him, that means I is before A and B, so we draw two directed edges I->A, I->B.

  2. There is an order to be decided between A and B that we don't know of yet, so we also draw a pointed line A---B between them.

  3. When all the lines have been drawn, we iterate over each directed edge U->V, and if there was a pointed line U---V, then i assume the order U->V is indeed correct, so we add this directed edge U->V to an answer graph G. Note that there might be multiple solutions, so U->V and V->U might end up existing at the same time.

  4. When we finished generating this answer graph G, visit all the nodes, starting from 0 and going to a any non-visited neighbor that we can go to through an edge

I think the go to any part might actually be hackable

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

In problem C, the for loop is from i=0 to i=30. As we know that 'int' is of 32 bytes,so I am unable to understand as to why the loop is not from i=0 to 31. Also I saw the codes of many programmers for the problem C and nearly everybody has done it from 0 to 30. So please explain the reason for this.

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

    230 = 1073741824. You don't even need 30 in this cycle, 29 is pretty enough, because for numbers up to 109 the maximum power of two in their representation is 229 = 536870912.

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

Where is editorial for problem 1095C - Powers Of Two?

P.S: "Unable to parse markup [type=CF_MATHJAX]" in spoiler.

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

So my solution for D was completely different... I created a matrix in which placed the 2 neighbors for each kid. But how? Well, for example, if the next 2 kids after the first one are 3 and 5, 3 will be a neighbor for 5 and vice versa. Now i could just pick a number, go through this matrix and find the next one. But one more problem.. Sometimes the result was counter-clockwise, so i just added an extra condition : so for the first kid, i would go through that matrix and see which one of those is a 3 or a 5 (one of them), then pick it and do the same thing for it and so on. It was such a rushed solution, yet it worked and i am really please with it ;)

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

anyone please explain Problem E..I am unable to understand "if conditions in loop" especially.

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

Problem E can also be solved easily using a segment tree+lazy updates

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

    actually just segment tree works, without the lazy updates.

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

    Then i wonder how it is implemented

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

      we convert the string to +1 and -1 (+1 when opening parens, -1 when closing parens) then we compute the cumulative sum array, and then we put the cumulative sum array in a segment tree.

      To check if changing the i-th parens "fixes" the sequence we do the following: if the i-th element in the string is opening parens we subtract 2 from me segment [i,n] and if its a closing parens we add 2. (this simbolizes changing the parens to the oposite one) then we do rmq(0,n) and rmq(n,n) if rmq(0,n)<0 or rmq(n,n)!=0 then its an invalid sequence

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

        the way i did it was in each node of the segment tree, I stored

        • i>The number of valid pairs in the range
        • ii>The number of unpaired opening brackets
        • iii>The number of unpaired closing brackets

        While merging the nodes, observe that the unpaired opening brackets in the left can be paired with unpaired closing brackets in the right child.

        In the end, just check whether the root has any unpaired opening or closing brackets.

        The problem is similar to https://www.spoj.com/problems/BRCKTS/

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

    Please give me the segment tree idea for problem E

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

Is there any easy explanation of problem E.

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

In E, can you explain your choice of indices for this part:

for (int i = 0; i < n; ++i) {
    pref[i + 1] = pref[i] + (s[i] == '(' ? +1 : -1);
    okp[i + 1] = okp[i] & (pref[i + 1] >= 0);
    suf[n - i - 1] = suf[n - i] + (rs[i] == '(' ? +1 : -1);
    oks[n - i - 1] = oks[n - i] & (suf[n - i - 1] >= 0);
}

It seems arbitrary to me whether you'd do that or do something like pref[i] = pref[i-1] + (s[i] == '(') : 1 : -1). The code is actually different, but I don't understand the difference.

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

For Problem E with test case 8 )))((((( why is the answer 0? Can't I change it to ()()()() with modifications at positions 1, 3, 4, 6 and 8?

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

    Because you can and only can change exactly one bracket according to the problem description

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

    Hi aakash have you understood this testcase Please clarify this problem if you got it .

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

In problem C what is the function of map<int,int> ? and what it is doing in program i don't understand

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

In problem E, in the first example, why the answer can't be ()(())? this is a regular bracket sequence

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

    It can. You can flip positions $$$2$$$, $$$3$$$, and $$$4$$$ (1-indexed) while being valid in that test case, and your answer is a result of flipping the position $$$2$$$.

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

In Problem D, why is the counter clockwise not acceptable?