### awoo's blog

By awoo, history, 2 months 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 (35)
 » good round
 » nice round
 » Problems A,B,C could have been presented in a different order.
 » thank you for your dedication for this round
 » Finally the editorial is out.
 » 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?
•  » » it can be solved without dp brute force only
 » 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
 » It took me almost 2 hours to come up with an approach for problem A. And my logic is extremely weird. see: 124335979 ;)
•  » » brute force
•  » » » Yes... I'm so dumb
•  » » » » it took me 40 min to solve that prob. ig ,am dumb too. cheers
 » 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
 » They are very good problems， all of div2 ' s contests should like this.
 » "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.
 » 7 weeks 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 :)
 » for problem C, why my i'm getting WA? i've used prefix, suffix sums.firstly i let ALICE to take max point path, then let bob to choose any path which obviously will have less point than alice's path.my submission
•  » » No Alice will not take the maximum point path. She will take the path that minimise the bob's score. See test case 1 Alice can achieve 12 points(max) but then bob will take 8 points which is obviously not minimum and Alice wants to minimise his score, so she will chose the path that forces bob to choose minimum score(7).
•  » » » thanks,i got u!
 » 6 weeks 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]; } } 
 » how to do d using dp?
 » I really appreciate the effort put into the explanations.