### awoo's blog

By awoo, history, 2 years ago, translation, 1555A - PizzaForces

Idea: BledDest

Tutorial
Solution (Neon)

1555B - Two Tables

Tutorial

1555C - Coin Rows

Idea: BledDest

Tutorial
Solution (awoo)

1555D - Say No to Palindromes

Idea: BledDest

Tutorial
Solution (Neon)

1555E - Boring Segments

Tutorial
Solution (awoo)

1555F - Good Graph

Tutorial  Comments (26)
| Write comment?
 » good round
 » nice round
 » Problems A,B,C could have been presented in a different order.
 » thank you for your dedication for this round
 » problem E is so good, but I couldn't solve it during the contest :'(
•  » » How it is good?
 » These are some incredible problems!
 » Quality problems, quality constest. Also i think it perfectly encapsulates what a educational round should be: teaching cool techniques through problem-solving.
 » Can someone pls explain how to implement the segment tree in problem E
•  » »
•  » » 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.
•  » » » You could also $update(L, R)$ by setting $wi$ at every index, do range minimum query, and get rid of the $(+1, -1)$ thing.
 » Can anybody explain how this range based segment tree works, editorial doesn't talks about it
•  » »
•  » » » Thanks helpful very
 » For the problem C, if the map is N*M, how to solve it? Should I use twice DP?
 » 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
 » 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.
•  » » problem A requires O(1) solution
 » "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.
 » Problem B is so interesting! It seems to need Pythagorean theorem, but we can prove that the best strategy only moves vertically or horizontally.
 » 2 years ago, # | ← Rev. 2 →   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 :)
•  » » BIT stands for Binary Indexed Tree also known as Fenwick Tree. You can find more on cp-algorithms
 » 2 years ago, # | ← Rev. 2 →   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[v]; } } 
 » 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.
 » 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 :)