awoo's blog

Educational Codeforces Round 112 Editorial
By awoo, history, 3 years ago, translation, In English

1555A - PizzaForces

Idea: BledDest

Tutorial
Solution (Neon)

1555B - Two Tables

Idea: adedalic

Tutorial
Solution (adedalic)

1555C - Coin Rows

Idea: BledDest

Tutorial
Solution (awoo)

1555D - Say No to Palindromes

Idea: BledDest

Tutorial
Solution (Neon)

1555E - Boring Segments

Idea: vovuh, adedalic

Tutorial
Solution (awoo)

1555F - Good Graph

Idea: adedalic

Tutorial
Solution (adedalic)
  • Vote: I like it
  • +114
  • Vote: I do not like it

Comments Comments (24)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good round

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

nice round

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you for your dedication for this round

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

These are some incredible problems!

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-10

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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://codeforces.net/blog/entry/93407

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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];
	}
}
→ Reply