awoo's blog

Educational Codeforces Round 112 Editorial
By awoo, history, 2 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 (26)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good round

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

nice round

→ Reply
»
2 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
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you for your dedication for this round

→ Reply
»
2 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
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

These are some incredible problems!

→ Reply
»
2 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
»
2 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
  • »
    »
    2 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
  • »
    »
    2 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
    • »
      »
      »
      2 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
»
2 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
»
2 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
»
2 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.com/blog/entry/93407

→ Reply
»
2 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
»
2 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
»
2 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
»
2 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
  • »
    »
    21 month(s) 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
»
2 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A what would be the answer of test case of n=777 According to tutorial 1945 min is answer but what would be the combination of pizzas to get this answer because 1945 is not multiple of 15,20,25,35,45,40 so how could this answer be feasible.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm new to CP and was utterly demolished by the first problem (PizzaForces). I spent about 4 hours on the problem, with 20 submissions, and 140+ lines of code before I finally caved in and looked at the solution. It's kind of embarrassing how easy the problem really was when you took a mathematical approach first before jumping straight to coding. So much time and energy were spent when all it took was about 10 lines haha. Oh well, I guess that's how you learn :)

→ Reply