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

Автор awoo, история, 3 года назад, По-русски

1555A - PizzaForces

Идея: BledDest

Разбор
Решение (Neon)

1555B - Два стола

Идея: adedalic

Разбор
Решение (adedalic)

1555C - Ряды монет

Идея: BledDest

Разбор
Решение (awoo)

1555D - Скажите палиндромам - нет!

Идея: BledDest

Разбор
Решение (Neon)

1555E - Скучные отрезки

Идея: vovuh, adedalic

Разбор
Решение (awoo)

1555F - Хороший граф

Идея: adedalic

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

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

good round

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

nice round

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

Problems A,B,C could have been presented in a different order.

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

thank you for your dedication for this round

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

problem E is so good, but I couldn't solve it during the contest :'(

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

These are some incredible problems!

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

Quality problems, quality constest. Also i think it perfectly encapsulates what a educational round should be: teaching cool techniques through problem-solving.

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

Can someone pls explain how to implement the segment tree in problem E

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

    First, sort the Segments by $$$w_i$$$

    Then, use two-pointers + Segment tree. For each $$$i$$$, you can add $$$[l_i,r_i]$$$ by 1, and in the segment tree, record the minimal value.

    for the second pointer, if the minimal value of $$$[l_i,r_i]$$$ is bigger than 2, then it means it is no longer useful, so you can add $$$[l_i,r_i]$$$ by $$$-1$$$, and the position of the second pointer ++

    the answer is the minimal value of $$$w_i-w_j$$$ For each $$$i$$$.

    Maybe my English is not good, if you want my code/still don't understand, you can ask me in codeforces.

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

      You could also $$$update(L, R)$$$ by setting $$$wi$$$ at every index, do range minimum query, and get rid of the $$$(+1, -1)$$$ thing.

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

Can anybody explain how this range based segment tree works, editorial doesn't talks about it

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

For the problem C, if the map is N*M, how to solve it? Should I use twice DP?

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

Surprisingly this time Question A stumped me during the contest. It really took some time to understand and solve it, so if anyone would like a more detailed explanation with a slightly different approach feel free to visit my blog on it.

https://mirror.codeforces.com/blog/entry/93407

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

Can't the probelm A be solved using a DP-like approach? I tried but my code was failing on larger values like 99999 and greater.

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

"It induces at least one "all-tree-edge" cycle since u and v are already connected. It can't induce more than one "all-tree-edge" cycle, since it contradicts with tree edge definition, and if it induces a cycle with some other cycle edge, then we can replace that cycle edge with its own tree-edge path: our cycle will become "all-tree-edge" cycle, but it will use already used tree edges. In other words, it's enough to consider only one "all-tree-edge" cycle induced by any cycle edge."

Such Verbosity makes editorials rather convoluted.

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

Problem B is so interesting! It seems to need Pythagorean theorem, but we can prove that the best strategy only moves vertically or horizontally.

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

Could someone tell me how the BIT part of the last problem works in code? It is not something like ‘lowbit’ that I am familiar with. Just providing me a link should be ok :)

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

    BIT stands for Binary Indexed Tree also known as Fenwick Tree. You can find more on cp-algorithms

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

In the solution of F, when add 1 to all the edge on the path, the function addOnPath just add the all the edges one by one. But isn't it O(n)? UPD: My bad, I didn't see that every edge will be at most delete once.

void addOnPath(int v, int l) {
	while (v != l) {
		inc(tin[v], 1);
		inc(tout[v], -1);
		v = up[0][v];
	}
}
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

BledDest Please provide DP solution for Problem C Really Nice Problems